naoya_t@topcoder

SRM472 Div1 Easy(250): PotatoGame

過去問, 初心者記事 | 17:20 |

Nimとかこういう石取り・芋喰い系ゲームが苦手…

• 普通だったらDPで解くような問題なのだが
  • 今回は1e9までなので、DPしてたら間に合わない(ローカルマシンで60秒超)。パターンを見つけて数式を書くだけ
• 大抵、両者が最適手を打つ、というのをすごく難しく考えてしまって破滅する
• 落ち着いて順序を追って考えたらある重要かつ初歩的な事実に気がついた

芋数がNのとき、それは先手必勝か後手必勝かのどちらかしかない

次回、眠くても目を瞑ってても解けるようにメモしておく。恥ずかしい記事なのでDiv1の人は見ないようにｗ

N=0: もう取るものがない。先手必敗・後手必勝。// dp[0] = G;

N=1: 先手は1をとるしかない。残りが0(後手必勝)なので先手必勝。// dp[1] = S;

N=2: 先手は1をとるしかない。残りが1(先手必勝)なので後手必勝。// dp[2] = G;

N=3: 先手は1をとるしかない。残りが2(後手必勝)なので先手必勝。// dp[3] = S;

N=4: 先手は1をとるか4をとるか選べる。

• 4をとれば残りが0(後手必勝)なので勝てる
• 1をとれば残りが3(先手必勝)なので負ける
• 先手必勝手（＝取った先が後手必勝）がある場合はそれを取る（のが最適手というものだ）。どれを取っても先手必勝なら仕方がない（後手必勝）
• というわけでこの場合、4を取って先手必勝。// dp[4] = S;

N=5: 先手は1をとるか4をとるか選べる。

• 4をとれば残りが1(先手必勝)なので負ける
• 1をとれば残りが4(先手必勝)なので負ける
• というわけで、勝てる手がないので先手必敗。// dp[5] = G;

N=6: 先手は１をとるか４をとるか選べる。

• 4をとれば残りが2(後手必勝)なので勝てる。
• 1をとれば残りが5(後手必勝)なので勝てる。
• というわけで、どちらを取っても勝てる。先手必勝。// dp[6] = S;

こんな感じのことをDPで調べていけばよい。

  if(i>=1 && dp[i-1]==G) dp[i]=S;
  else if(i>=4 && dp[i-4]==G) dp[i]=S;
  else if(i>=16 && dp[i-16]==G) dp[i]=S;
  ...
  else dp[i]=G; // 1手先は後手必勝でないなら先手必勝。

適当なNまで見てみると

{ G, S, G, S, S, G, S, G, S, S, G, S, G, S, S, G, S, G, S, S, G, S, G, S, S, ... }

といった感じで、周期５でパターンが繰り返されている。N mod 5が0か2ならG, 1,3,4ならTが来る。（この問題ではGが後手の"Hanako"、Sが先手の"Taro"に対応）

答えが

    return (N%5==0||N%5==2)?"Hanako":"Taro";

でいいのかどうか、プログラムを書いてDP結果と照合してみたら、1<=N<=1e9の範囲で完全に一致した。（が、このチェックには1分46秒かかった。DPで解いていたら到底間に合わない）

SRM472

10:35 |

二時間半のGCJ Round 2の後で疲れてて眠いのに参戦。

TaroとかHanakoとか＞＜

DIV	level	問題名	競技中	後で	System Test	通過率	備考	levenshtein
1	250	PotatoGame	撃沈	-	-	-	_	0
1	500	TwoSidedCards	間に合わず	-	-	-	_	0
1	1000	開いてない	-	-	-	-	_	-

Easy(250): PotatoGame

• ４進法に置き換えて、人力でパターンを見つけようとしていた。
• 眠いのに無理
• 最適戦略とか直感的に理解できてない
• あー解けないやとか思ってgdgdコードを出してまあ当然のごとく沈む

Medium(500): TwoSidedCards

• パターン数え上げ
• 長さいくつのループがいくつできるか、に分割してみた
• で、そこからどうしたら良いか。長さ１，２なら分かりやすいが３以上（長いやつは割と長い）の時どうするか色々考えてて時間切れ

Hard(1000): 開いてない

Challenge Phase

• あー。みんなmod5で簡単なコードになってる
• mod5の判定と自分のコードを照合するコードを書いてn=1から見て言ったら出るわ出るわ撃墜ポイント
• うとうとしながら誰かが落としてくれるのを待ってたがなかなか落ちなくて
• 最後は轟沈

結果

0point

Room: 15/20

Div1: 457/753

1528→1461 また青か。もう嫌じゃ