SRM diary(Sigmar)

SRM511 Div1 250 Zoo

SRM511, Div1 | 17:46 |

Problem Statement

コーディングフェーズ

明らかに片方が0～n、もう片方が0～mみたいになるはずだ

考え方は簡単だが、サンプルがすごく弱いので、コーナーケースに細心の注意が必要そう

まずは各数字の数をカウントしておく

数字の0を最初とすると、最初はカウント2が0個以上の任意数続いて、次にカウント1が0個以上の任意数続いて、最後は全てカウント0となるはずだ

全パターンを網羅すると、、カウント数の遷移としては以下のように分類される

（有効は解が存在可能、無効は解がないことを示す）

• 2→1 ... 有効
• 2→0 ... 有効
• 1→2 ... 無効
• 1→0 ... 有効
• 0→2 ... 無効
• 0→1 ... 無効
• 任意の数→3以上の任意の数 ... 無効
• 3以上の任意の数→任意の数 ... 無効

少しまとめると、前の数字より増える場合は無効、3以上の数が含まれる場合は無効、それ以外は有効となる

あとは2の数(=twoとする)と、1が登場するかどうかを判定する

答えは2^twoで、1が登場する場合のみ、さらに2倍する

（例えば、0,0,1,1,2,3,4とかだとすると、0の選び方が2通り、1の選び方が2通り、2の選び方が2通り、3,4は2の選び方に応じて一意に定まる）

ということでコーディング

いろんなパターンを試す

有効パターン：2→1→0、2→0、1→0等

無効パターン：上記で挙げたもの

全部問題なさそう

提出

かなり入念に確認したので結構遅くなった・・・でもコーナーケースが怪しそうな回はそれで良いと思う。

（本当は怪しげなコーナーケースが出てこない書き方をするのが最も良いと思いますが・・・）

チャレンジフェーズ

上に挙げたテストケースで、サンプルに含まれない2→0のパターンが最も怪しそうだと睨んだ

この場合に1が登場する場合と同様に最後に2を掛けている人がいそうだ

実際いた

確認中に誰かに落とされる

気づいたらそんな人はみんな落とされていた。みんな早い・・・

システムテスト

Passed

ソースコード

class Zoo {
public:
	long long theCount(vector <int> answers) {
		long long res=1;

		int cnt[50];
		memset(cnt, 0, sizeof(cnt));
		for(int i=0; i<(int)answers.size(); i++) {
			cnt[answers[i]]++;
		}
		if(cnt[0]==0) return 0;
		bool one=false;
		int two=0;
		for(int i=0; i<=40; i++) {//あまり場合分けがうまく書けていない・・・
			if(cnt[i]>2) return 0;
			if(cnt[i]==1) one=true;
			if(cnt[i]==2) two++;
			if(one && cnt[i]==2) return 0;
			if(i>0 && cnt[i]>0 && cnt[i-1]==0) return 0;
		}

		for(int i=0; i<two; i++) {
			res*=2;
		}
		if(one) res*=2;
		return res;
	}
};

SRM511 Div1 500 FiveHundredEleven

SRM511, Div1 | 17:46 |

Problem Statement

コーディングフェーズ

相変わらず500は難しい

まず511=(2^9)-1=111111111(2進数)

ということで、最終的に9つのビットが全て立てば負けということか

or演算なので一度立ったビットが戻ることはない。。。

普通に使用したカードでビットDPすると・・・2^50なのでできるはずがない

まともにやると2^50の呪縛から抜けられないので使用したカードが厳密に分からなくても勝敗が分かる方法があるはずだ

Nimだとxorした結果で勝敗が分かるがそのようなルールはないのか・・

・・・

・・・

20分くらい時間を使ってしまった。すぐには見つかりそうにない。Wrong Attemptのような気がする。

よく考えると、ある状態のときに、使っても状態が変化しないカードは区別する必要がないな

（例えば2進数11のとき、01や10や11を使っても状態は変わらないので、全て同じカードと見做せる）

逆にある状態のときに、使うと状態が変わるカード集合は一意に定まるのでは

うむ。間違いない。ということは、状態が2^9で、さらに使っても状態が変わらないカード数が最大50枚のはずなので、512*50=250000くらいの状態数に落とせる。いける。

ある状態のときに、使うと状態の変化するカードを管理するため、9つの各ビット毎にそれを含むカードをまとめておこう（←誤ったアプローチ）

あとは、全カードのorが511にならない場合は特別扱いしておけば良いかな

よし書けた

何か色々変な書き間違いを発見

直した

間違いないよね・・・（←コードだけ確認して、コーナーケーステストを怠っていた）

提出

システムテスト

チャレンジされなかったのでいけると思いきやあっさり落ちた

後で

• 0のカードは最初から常に状態を変化させないカードとして計上しないといけないのに、無視していた。コーナーケース何も考えてなかった。猛省すべき点だ・・・
• ある状態から別の状態に遷移するとき、各ビットごとに、まだ立っていないビットに対して、そのビットを立てることのできるカード集合を管理していた。遷移するとき、各ビットのカード集合の中で状態を変化させられなくなるものだけ数えておけば良いと思ったが間違いで、別のビットを立てるカードも数えないといけなかった。

例えば01と10と11の3つがあり、現状態が0とすると、1ビット目集合が{01,11}、2ビット目集合が{10,11}としており、1ビット目に着目して11を使用したときに、状態を変化させなくなるカードは01だけかと思った。実際には10も状態を変化させなくなるため計上漏れが発生していた。

これははっきり言って気付けそうにもない。どうすればいいんだろう。無駄にビットごとに管理などという結果的に意味のないことをしたのが誤りなんだろうが・・・

なるべくシンプルに書くように注意することくらいしかできないのかな。。。

ソースコード

修正済み版

int memo[1<<9][52];

class FiveHundredEleven {
public:
	vector <int> cards;

	//free: 使っても状態が変化しないカード数
	int rec(int mask, int free) {
		if(mask==(1<<9)-1) return 1;
		if(memo[mask][free]>=0) return memo[mask][free];

		int res=0;
		if(free>0) {
			if(!rec(mask, free-1)) res=1;
		}

		for(int i=0; i<(int)cards.size(); i++) {
			if((mask|cards[i])==mask) continue;
			int nmask=mask|cards[i];
			int fcnt=0;
			for(int j=0; j<(int)cards.size(); j++) {
				if(i==j) continue;
				if((mask|cards[j])!=mask && (nmask|cards[j])==nmask) fcnt++;
			}
			if(!rec(nmask, free+fcnt)) res=1;
		}

		memo[mask][free]=res;
		return res;
	}

	string theWinner(vector <int> cards) {
		memset(memo, -1, sizeof(memo));
		this->cards=cards;

		int cmask=0;
		int fcnt=0;
		for(int i=0; i<(int)cards.size(); i++) {
			cmask|=cards[i];
			if(cards[i]==0) fcnt++;
		}
		if(cmask!=(1<<9)-1) {
			if(cards.size()%2==0) return "Toastman";
			else return "Fox Ciel";
		}

		int r=rec(0, fcnt);
		if(r) return "Fox Ciel";
		else return "Toastman";
	}
};

間違ってたやつ

int memo[1<<9][52];

class FiveHundredEleven {
public:
	vector <int> m[9];

	int rec(int mask, int free) {
		if(mask==(1<<9)-1) return 1;
		if(memo[mask][free]>=0) return memo[mask][free];

		int res=0;
		if(free>0) {
			if(!rec(mask, free-1)) res=1;
		}
		for(int i=0; i<9; i++) {
			if(mask&(1<<i)) continue;
			for(int j=0; j<(int)m[i].size(); j++) {
				int nmask=mask|m[i][j];
				int fcnt=0;
				for(int k=0; k<(int)m[i].size(); k++) {
					if(k==j) continue;
					//m[i]の外にもfreeとなるカードがあるので誤り
					if((nmask|m[i][k])==nmask) fcnt++;
				}
				if(!rec(nmask, free+fcnt)) res=1;
			}
		}

		memo[mask][free]=res;
		return res;
	}

	string theWinner(vector <int> cards) {
		memset(memo, -1, sizeof(memo));
		for(int i=0; i<9; i++) m[i].clear();

		int cmask=0;
		for(int i=0; i<(int)cards.size(); i++) {
			cmask|=cards[i];
			for(int j=0; j<9; j++) {
				//ビット毎にカード集合を管理している
				if(cards[i]&(1<<j)) m[j].push_back(cards[i]);
			}
		}
		if(cmask!=(1<<9)-1) {
			if(cards.size()%2==0) return "Toastman";
			else return "Fox Ciel";
		}

		int r=rec(0, 0);//無条件に第二引数を0にしているので誤り
		if(r) return "Fox Ciel";
		else return "Toastman";
	}
};