スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Beta Round #66

2011/04/10 17:00~19:30 (JST)
Codeforces Beta Round #66 の参加記録

寝過ごした上に選挙に行ってたので、開始 75 分後から参加。

Tags : プログラミング Codeforces 未解決

結果

A. WA, AC (264)
B. -
C. AC (556)
D. -
E. -
Hacks : -100 (0/2)
Standing : 226/1035
Rating : 17391719


問題

問題セットの原文はここを参照。

A. The Elder Trolls IV: Oblivon
1 つの頂点が原点にあり、軸に平行に置かれた、大きさ x × y × z の直方体を考える。
「平面 x=C, y=C, z=C ( C は整数) のどれかで直方体を分割する」という操作を k 回行うとき、分割される領域の最大数を求めよ。

1 ≦ x, y, z ≦ 106
0 ≦ k ≦ 109

B.

C. LionAge II
文字列 s, 非負整数 k, n 組のボーナス (xi, yi, ci) が与えられる。
(xi, yi, ci) は文字列中に xiyi という並びがあるとき、ci 点を加算するという意味。

s から高々 k 文字を置換することで、得られる点数を最大化せよ。

s は長さ 100 以下でアルファベット小文字からなる。
0 ≦ k ≦ 100

D.

E.

解答

言語は C++。テンプレはここを参照。

A.
int main(){
ll x,y,z,k; cin>>x>>y>>z>>k;
ll cnt;
if((x-1)+(y-1)+(z-1)<=k) cnt=x*y*z;
else{
cnt=1;
ll cx=0,cy=0,cz=0;
rep(i,k){
int rx=(cx<x-1)?cx:INF,ry=(cy<y-1)?cy:INF,rz=(cz<z-1)?cz:INF;
if(rx<=ry && rx<=rz){
cnt+=(cy+1)*(cz+1);
cx++;
}
else if(ry<=rz && ry<=rx){
cnt+=(cz+1)*(cx+1);
cy++;
}
else{
cnt+=(cx+1)*(cy+1);
cz++;
}
}
}
cout<<cnt<<endl;

return 0;
}

切ることのできる方向は 3 種類あるが、直感的にも、これまでに切った回数が少ない方向を優先的に切っていけばいい。
ただし、辺の長さを L とすると、その方向には L-1 回しか切れないことに注意。 (整数座標で切るという制限のため)
1 回のカットで増える領域の数は、これまでに別の方向に切った回数によって決まる。
x 方向に切ったとき、それまでに y 方向に cy 回、z 方向に cz 回切ってあったとすると、領域の数は (cy + 1)(cz + 1) 個増える。

ここで、「x 方向に切る」は「x 軸に垂直な平面で切る」の意味。 y, z についても同様。

B.



C.
int main(){
string s;
int k,n; cin>>s>>k>>n;
int len=s.length();
k=min(k,len);
int bonus[128][128]={};
rep(i,n){
char x,y;
int c; cin>>x>>y>>c;
bonus[x][y]=c;
}

static int dp[100][101][128];
rep(i,len)rep(j,k+1)for(int c='a';c<='z';c++) dp[i][j][c]=-INF;
dp[0][0][s[0]]=0;
for(int c='a';c<='z';c++) dp[0][1][c]=0;
for(int i=1;i<len;i++){
rep(j,k+1){
for(int c='a';c<='z';c++){
dp[i][j][s[i]]=max(dp[i][j][s[i]],dp[i-1][j][c]+bonus[c][s[i]]);
}
if(j==k) continue;
for(int c='a';c<='z';c++){
for(int c2='a';c2<='z';c2++){
dp[i][j+1][c]=max(dp[i][j+1][c],dp[i-1][j][c2]+bonus[c2][c]);
}
}
}
}

int ans=-INF;
rep(j,k+1)for(int c='a';c<='z';c++) ans=max(ans,dp[len-1][j][c]);
cout<<ans<<endl;

return 0;
}

典型的な DP。
dp[i][j][c] := ( s1 を始端, si を終端とする部分文字列について、ちょうど j 文字を置換していて、si = c であるときの最大点数 )
とする。
状態の遷移は、最後の文字を置換する場合としない場合に分けて考えればいい。

O(L K C2)。
L は文字列長、K は置換回数、C はアルファベットの種類数。

D.



E.



感想

時間もなかったので、A. と C. を解いたあとは Hacking に専念した。
結局 1 つも落とせなかったが。

落とせたはずなのに見逃したコードは、どこが悪かったのかあとで復習しておく。
この練習は自分のコードのバグを減らす効果もある気がする。

A.
A 問題としては難しい印象。B か Div2 Only の C くらいの難易度。
空間幾何的なイメージがうまい人なら一瞬で解けたのだろうけど。

C.
この手の問題もだんだん解けるようになってきたが、まだ安定しない。
この前の SRM 501 Div1 Medium は結局解けなかったし。

[ 追記 ]
A. は k=0 で落ちているコードが多かった。
C. は TLE になるコードとボーナスがすべて負のときに 0 を返すコードが多く落とされていた。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。