SRM612に参加。
Easyをかなりの速度で解けたものの、Mediumを題意を読み間違えて解けず。
チャレンジも1ミスしてしまった。Easyを解いたのが早かったためなんとかレート維持。
http://community.topcoder.com/stat?c=problem_statement&pm=10543
問題
初期状態でテキストボックスに1文字配置されている。
ここに以下の手順を繰り返してS文字を配置したい。以下の各手順がコスト1かかるとき、S文字配置するのにかかる最小コストを答えよ。
解法
状態として(テキストボックスの文字数,クリップボードの文字数)としてBFSなりDijkstraなり行えばよい。
Div2 Mediumも「1文字削除」がないことを除けば同じように解ける。
O(S^2)程度で解ける。
const int ma=3001; int st[ma][ma]; class EmoticonsDiv1 { public: int printSmiles(int smiles) { int x,y; FOR(x,ma) FOR(y,ma) st[x][y]=9999999; st[1][0]=0; queue<pair<int,int> > Q; Q.push(make_pair(1,0)); int loop=0; while(!Q.empty()) { loop++; int cn=Q.front().first; int cl=Q.front().second; Q.pop(); if(st[cn][cn]>st[cn][cl]+1) { st[cn][cn]=st[cn][cl]+1; Q.push(make_pair(cn,cn)); } if(cn+cl<ma && st[cn+cl][cl]>st[cn][cl]+1) { st[cn+cl][cl]=st[cn][cl]+1; if(cn+cl==smiles) return st[cn+cl][cl]; Q.push(make_pair(cn+cl,cl)); } if(cn>0 && st[cn-1][cl]>st[cn][cl]+1) { st[cn-1][cl]=st[cn][cl]+1; if(cn-1==smiles) return st[cn-1][cl]; Q.push(make_pair(cn-1,cl)); } } return 99999; } };
まとめ
これは本番すんなり回答が思いついて239ptとかなり高速に解けた。