TopCoder SRM 493 (Div 1) 参加記録

Challenge Succeeded / System Test Failed / Unopened
220位
1789 -> 1710

skyさんeomoleさんと一緒の部屋。

N個の石が一列に並んでいて、M個目だけが白で他は黒。
二人のプレイヤーが、手番に白石が入っている連続するK個の石を逆順にするゲームをする。
最初にL番目に白石を置いたプレイヤーが勝ちである。
お互いが最善の戦略を取ったときどちらが勝つか求めよ。

石の数は100万以下。

石の白黒をひっくりかえすという致命的な誤読をする。

ゲームが3手以上続いて、どっちかのプレイヤーが必勝になるなら、最初の1手か2手で相手と同じ選び方をして、状態を無限ループさせることができるので引き分け。

ゲームが最初の1手で終わるなら先手勝ち。
これはM個目とL個目が同時にK個の選ぶ範囲に入ればおｋ.

そうでないなら先手はなるべく石をMから遠ざける。
で、そっから同じように後手が勝てるなら後手勝ち。さもなければ引き分け。

お、簡単！？書いた。サンプル合った。
間違ってないか慎重に確認してサブミット。

0〜Kの数字からなる文字列が与えられる。
文字列のそれぞれの0を、好きな1〜Kの数字に置き換えて、
「任意の同じ数字のペア間の距離の最小値」を最大にしたい。

そのような最大値を求めよ。文字列の文字数は50以下、Kは7以下。

Easyを見直して、論理におかしいところはないし、もしかしたら久々にレート下落に歯止めがかけられるかな、とか思う。

まず、答えの上限はK.なぜなら数字はK種類しかないので、K回以内に必ず同じ文字が出現するから。
よって答えに影響を与える数字は、最高でも過去6文字分。

てことはdp[i][j]で、i文字分、過去のK個の情報jでDPすればいい。
jは2^7通り？
違う、位置も覚えなければならないから7^6通り。
50*7^6*7=4000万　で余裕で間に合いそう。
じゃあjを8^6にすればビット演算使えてちょっと書きやすい。

コーディング。
ビット演算逆向きにしてたりで少しハマる。
落ち着いてよく考えろ自分。
合った。ミスしてないよね？時間大丈夫だよね？大丈夫。
送信。

開いてない。

皆の300の解法が全然ちがう！速攻で自分の300が落とされた。
えー解法おかしいとこないと思うんだけどなあ。

450、skyさんのこんなにvectorとかmapとか使っても間に合うんだろうか。
まあよくテストしてたし間に合うんだろうなー。

落とせるものがないので終了。

450まで落ちた。しょっく。。。
計算量に、数字をK-1個見るコストを考えてなかった。
自分のコードだと計算量50*8^6*7*6になってるよ。これじゃあ間に合わない。