kmjp's blog

競技プログラミング参加記です

TopCoder SRM 612 Div1 Easy EmoticonsDiv1

SRM612に参加。
Easyをかなりの速度で解けたものの、Mediumを題意を読み間違えて解けず。
チャレンジも1ミスしてしまった。Easyを解いたのが早かったためなんとかレート維持。
http://community.topcoder.com/stat?c=problem_statement&pm=10543

問題

初期状態でテキストボックスに1文字配置されている。
ここに以下の手順を繰り返してS文字を配置したい。以下の各手順がコスト1かかるとき、S文字配置するのにかかる最小コストを答えよ。

  • テキストボックスの内容をクリップボードにコピーする。
  • クリップボードの内容をテキストボックスに追加する。
  • テキストボックスの内容を1文字削除する。

解法

状態として(テキストボックスの文字数,クリップボードの文字数)として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とかなり高速に解けた。