Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-26SRM522 Div1

SRM522 Div1 250 RowAndCoins

| 01:47 | SRM522 Div1 250 RowAndCoins - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM522 Div1 250 RowAndCoins - SRM diary(Sigmar) SRM522 Div1 250 RowAndCoins - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何も考えずbitメモ化再帰した。

10分弱で書けた

答えが全然合わない。なんで・・・

見なおしても分からない。やばい。あせる

ステップ実行してチェック。

メモ化の代入が逆になってる。memo[mask][d]=resとするところがres=memo[mask][d]となっている。合うわけない。

修正。提出。

10分も無駄にして随分低い点数を取ってしまった。。。痛すぎる。。。

こういう凡ミスがいつまで経ってもなくならない。どうしたもんだろう。


ソースコード

他の人を見ると左端か右端がAならAlice、それ以外ならBobでいいらしい。

それを思いついたとしても自分なら安全を見積もって結局メモ化で書いただろうな。。

int memo[1<<14][2];

class RowAndCoins {
public:
	string cells;
	int n;

	int rec(int mask, int d) {
		int res=0;
		if(memo[mask][d]>=0) return memo[mask][d];
		if(__builtin_popcountll(mask)==n-1) {
			for(int i=0; i<n; i++) {
				if(!(mask&(1<<i))) {
					res=((cells[i]=='A')^d);
					memo[mask][d]=res;
					return res;
				}
			}
		}
		for(int i=0; i<n; i++) {
			for(int j=i+1; j<=n; j++) {
				int cmask=(((1<<(j-i))-1)<<i);
				if(mask&cmask) continue;
				if((mask|cmask)==(1<<n)-1) continue;
				if(rec(mask|cmask, 1-d)==0) res=1;
			}
		}
		memo[mask][d]=res;
		return res;
	}

	string getWinner(string _cells) {
		string res;
		cells=_cells;
		n=cells.size();

		memset(memo, -1, sizeof(memo));
		int r=rec(0, 0);
		if(r) res="Alice";
		else res="Bob";
		return res;
	}
};

SRM522 Div1 450 CorrectMultiplication

| 01:47 | SRM522 Div1 450 CorrectMultiplication - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM522 Div1 450 CorrectMultiplication - SRM diary(Sigmar) SRM522 Div1 450 CorrectMultiplication - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

あるA,B,Cについて元の値a,b,cからの合計距離を少なくすることを考えると、

A*B<cかつ(A+1)*B<=cのとき、Bが1以上であることを考慮するとC=A*BにするよりC=(A+1)*B、A=A+1にするほうがいい

(Aはaから1離れる可能性があるが、Cは確実にcに1以上近づくため)

同様にA*B>cかつ(A-1)*B>=cのとき、C=A*BよりC=(A-1)*B、A=A-1とするほうがいい

Bについても同様のことが言える


ということを前提に考えると、単に尺取法の変形版をせよと言われている気がしてきた

A=1、B=cと置くと、この時点でC=A*B=cとなる

Aを1増やすと、A*B>cとなるので、Aを固定したままA*B>cの条件を崩さないような最小のBを求める

(先ほどの前提により、途中のBは考慮する必要がない)

Bを1減らすと、A*B<=cとなるので、Bを固定したままA*B<=cの条件を崩さないような最大のAを求める

(先ほどの前提により、途中のAは考慮する必要がない)

またAを1増やして・・・と、Bが0になるまで繰り返す

計算量の見積もりは難しいがまあAやBが小さいと一気に移動できるから多分問題ないだろう


書いた

サンプル通った。

最大ケースも一瞬で終わる。問題なさそう。

提出。


・・・

何か不安になってきたので色々合っているか考える。

450と言いつつ結構コーナーケース満載っぽい問題だし・・・

やっぱり合ってるように思う。大丈夫かな・・・


チャレンジフェーズ

他の人が軒並み√nでイテレーションしているのを見てよく考えたらそりゃそうだよなと思いつつ、心細さが急上昇

終わり際に勘違いして1チャレンジミス。Easy点低いしMedium落ちたら終わる・・・


システムテスト

通ったのでものすごくほっとした


ソースコード

class CorrectMultiplication {
public:
	int a, b, c;
	ll calc(int aa, int bb) {
		return (ll)abs(aa-a)+abs(bb-b)+abs((ll)aa*bb-c);
	}

	long long getMinimum(int _a, int _b, int _c) {
		long long res;
		a=_a; b=_b; c=_c;

		int aa=1, bb=c;
		res=calc(aa, bb);
		while(1) {
			aa++;
			bb=c/aa;
			res=min(res, calc(aa, bb+1));
			if(bb==0) break;
			res=min(res, calc(aa, bb));
			aa=c/bb;
			res=min(res, calc(aa+1, bb));
			if(aa==0) break;
			res=min(res, calc(aa, bb));
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111026