SRM 526 500pt : PrimeCompositeGame

TopCoder

問題概要

二人でゲームをする。石がN(<5*10^5)個ある。先手は石を1..K個取り除いて残りが素数になるようにしなければならない。後手は石を1..K個取り除いて残りが合成数になるようにしなければならない。石を取り除くことができなくなったら負けになる。両者が最善を尽くしたとき何手で勝負が付くか求める問題。

考えたこと

  • タイトルの割に数論っぽくない問題のようなので安心した。
  • 最短手数を求めるゲーム木探索は、勝ちのとき(INF - 手数)、負けのとき-(INF - 手数)を評価値にすればnegamaxで行けるんだっけか。
  • ナイーブな実装ではO(N*K)でTLEっぽい。とはいえ単に最小値を取り出すだけだからスライド最小値かRMQで計算量落ちる。
  • スライド最小値の方が計算量はよいけど端の処理が面倒なのでRMQで書こう。多分間に合うだろう。
    • 今見返すと結構厳しい。
  • よし分かったので書こう。ってこれ先手と後手でルール違うんだからnegamaxじゃダメじゃん。
  • しかし修正はそんなに難しくはない。DP配列を2本用意すれば良いだけだ。
  • RMQも二ついるのでglobalな配列や関数をstructに押し込む。
  • 実行したらRE起こす。なぜ？
  • しばらく悪戦苦闘した結果stack overflowしていることに気づく。構造体の中にでかい生配列が入ってるから局所変数にするとそりゃおちる。
  • 配列をvectorで書き直して何とか実行可能になった。
    • あるいは、global変数にするか。
  • 実行すると負けのとき何故か-INF周辺の値が帰ってきて、勝ちのときは値が2だけずれてる。
  • 正直時間ないし理由とかどうでもいいのでサンプルが通るように適当に符号や値を修正する。
  • 残り2分というところで何とかサンプル通った。最大ケースらしきものだけテストしてから送信。
  • まったく自信はなかったけど通っていた。コーナーケースとかにハマらなかったのは運が良かった。
  • なんかmultiset使ったり二分探索使ったりしている解答もあるけどよく分かっていない。
    • 追記：multisetの方は自明だった。というかPOJのSliding WindowsでそれやってTLEもらいつづけていたのを忘れていた。

本番中提出したコード

計算量O(N*log N)。

#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int INF = 1<<28;
const int MAX_N = 474747;

int dp[MAX_N+1][2];
bool checked[MAX_N+1][2];

struct PrimeCompositeGame {

	int theOutcome(int N, int K) {

		if(N == 1){
			return 0;
		}
		seive();
		RMQ a, b;

		a.init_rmq(N+1);
		b.init_rmq(N+1);

		checked[0][0] = checked[1][0] = checked[0][1] = checked[1][1] = true;
		dp[0][0] = dp[1][0] = (INF - 1);
		dp[0][1] = dp[1][1] = (INF - 1);

		a.update(0, dp[0][0]);
		a.update(1, dp[0][1]);
		b.update(0, dp[1][0]);
		b.update(1, dp[1][1]);

		for(int i=2; i<N; i++){
			if(isPrime[i]){
				checked[i][0] = true;
				dp[i][0] = (INF - 1);
				a.update(i, dp[i][0]);
			}
			else{
				checked[i][1] = true;
				dp[i][1] = (INF - 1);
				b.update(i, dp[i][1]);
			}
		}

		for(int i=2; i<=N; i++){
			//先手
			if(!checked[i][0]){
				int score = b.query(max(0, i-K), i);
				if(score > 0){
					int turn = INF - score + 1;
					dp[i][0] = -(INF - turn);
				}
				else{
					int turn = score + INF + 1;
					dp[i][0] = (INF - turn);
				}
				a.update(i, dp[i][0]);
			}

			//後手
			if(!checked[i][1]){
				int score = a.query(max(0, i-K), i);
				if(score > 0){
					int turn = INF - score + 1;
					dp[i][1] = -(INF - turn);
				}
				else{
					int turn = score + INF + 1;
					dp[i][1] = (INF - turn);
				}
				b.update(i, dp[i][1]);
			}
		}

		int ans = dp[N][0];
		if(ans > 0){
			return INF - ans - 2;
		}
		else{
			return -(INF + ans) + 2;
		}
	}

};