Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-06-06

SRM472 Div1 Easy(250): PotatoGame

| 17:20 | SRM472 Div1 Easy(250): PotatoGame - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM472 Div1 Easy(250): PotatoGame - naoya_t@topcoder SRM472 Div1 Easy(250): PotatoGame - naoya_t@topcoder のブックマークコメント

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

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

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

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

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: 先手は1をとるか4をとるか選べる。

  • 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, ... }

といった感じで、周期5でパターンが繰り返されている。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 | SRM472 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM472 - naoya_t@topcoder SRM472 - naoya_t@topcoder のブックマークコメント

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

TaroとかHanakoとか><

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

Easy(250): PotatoGame

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

Medium(500): TwoSidedCards

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

Hard(1000): 開いてない

Challenge Phase

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

結果

0point

Room: 15/20

Div1: 457/753

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

http://gyazo.com/5a7bc9f7e6095652d0642724a16fc154.png

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100606