Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-06-11

SRM472

| 14:23 | はてなブックマーク -  SRM472 - cafelier@SRM

SRM472 の成績・ソース (要ログイン) : WA/AC/- : ちゃんと考えよう

250開く

  • 250-600-900という配点だし、不穏な空気も流れていたので、Mediumは難しいだろうと回避。250から。
  • 『Taro and Hanako ...』
    • 日本人出題者キター!!!これは確実に難しいセット
    • Mediumほとんど解かれないだろうから250を全速力で解いてそこでスコアを取る…
  • 『最大10^9の自然数nを使って二人ゲームをします。自分のターンでは、nから4のベキ乗の数1,4,16,64,..を一つ引きます。0にした方が勝ちです。最善手を打ったとき勝つのはどっち?』
  • 10^9 なので全状態を探索すると終わらない…
  • 簡単な規則があるかな?
  • 4のベキ乗が問題なので4進数で考えると、
    • 4のi乗を引く == i桁目を1減らす  (※間違い)
  • なので、結局、4進数の各桁の数字の和のターンで終わる!
  • ので、その値を計算して mod 2 とるだけか!!!
  • 書いた
  • サンプル通った
  • よっしゃだしちゃえ。247点台!

600開く

  • 『n≦50枚のカードがあって、表に1~nまでの別々の番号が書いてあります。裏にも1~nまでの別々の番号を書きました。このn枚を(それぞれ表を使うか裏を使うかは自由に)並べて作れる数字列のパターンは何通り? mod 1000000007 で』

  • テストケース増強
    • 最小例は1枚の場合
    • 2枚、3枚の場合も適当に増やしておく
    • 最悪ケースは…とりあえず50枚裏と表が全部同じ数字の場合
    • 50枚1個ずらしの場合(1の裏に2、2の裏に3、…50の裏に1)も足しておこう。
    • もっとランダムな例の方が難しかったりするかな?
    • まあいいか後で考えよう

  • えーと、裏返す枚数で場合分けとかはどうだ。
    • 0枚裏返す場合、n! 通り
    • 1枚だけ裏返す場合は、
      • 表-裏に同じ数字が書いてあるカードならn!通り…なんだけど、これは0枚裏返しで出てくるパターンと変わらないから0通りみたいなもの
      • こういう重複するのか…めんどいな…
      • 表a-裏bのように違うのを裏返す場合は、bが2枚、残りn-1枚違う番号、になるので
        • 並べ方は nC2 * (n-1)! 通り。これはこれまでの例とかぶらない
        • どのa-bを裏返すパターン同士もかぶらない


    • 2枚裏返す場合…
    • 表a-裏a のを裏返すケースは1枚か0枚裏返しと変わらないから数えないでいい。
      • 表a-裏b 表c-裏d のようにバラバラにひっくり返すケースと
      • 表a-裏b 表b-裏c のように連鎖してひっくり返すケース
    • えーと、裏や表には別々の数が書いてあるので
      • 表a-裏b 表c-裏b のようなのはない。
      • 表a-裏b 表c-裏d は b と d がだぶるので、nC2 (n-2)C2 (n-4)!
      • 表a-裏b 表b-裏c は結局cがダブルだけなので1枚裏返しと同じ nC2 (n-2)!
  • あ、表a-裏b 裏b-表a があるな。これは…結局全部の数字が出るので0枚裏返しと同じパターン


  • むむむ。この調子でn枚裏返しまでパターン列挙していったら指数爆発しそう。

  • しかしあれですよ、a-b b-c c-d ... みたいに連鎖して裏返してるかぎりは、"2枚かぶりで残りは全部違う"になって
  • それを伸ばしすぎて a-b b-c ... z-a とループすると全部違う元々のパターンと同じことになる。
  • ので、この連鎖して伸ばしていくパターンをうまく数えればいい。

  • どの表番号から初めても裏が1個ずつあるので、番号をグラフのノード、表→裏をエッジと思うと、このグラフではサイクルが何個かできて、
  • そのサイクルそれぞれで別々に考えられる。
    • 連鎖伸ばしていくやつはサイクルから外には出られないので。

  • ということで、とりあえずサイクルに分解するコードを書こう。
  • 書いた。
  • 長さ L1, L2, .., Lk のサイクルに分解されたとしよう。
  • 長さLのサイクルから作れるパターン数をp(L)とすると、
  • それぞれ独立なので単純な掛け算で良くて、
  • n_C_L1 * p(L1) * (n-L1)_C_L2 * p(L2) * ...
  • という掛け算。よって p(L) さえ計算できれば解ける。

  • さて…?
    • 裏返し連鎖が0個なら、L! 通り
    • 1個なら、えーと、L! 通りとみせかけてダブってるのが一組あるので L!/2通り
    • c個なら、L!/(2^c)通り

  • 裏返し連鎖の個数がc個になるような物は何通り有るか数える…
  • 全探索すると 2^L だし L は最悪50だし死ぬよね。
    • あ、やっぱり最初に作った最悪例は最悪っぽい。サイクルが長い奴。
  • ぬぬぬ
  • ぬぬぬ
  • これDP
    • それぞれ裏返さない(0)か裏返す(1)かの2^Lパターンのそれぞれのうちで、1→0 に落ちてる箇所の個数がcだから、
    • i個目まで0/1を全部試してみて、1→0に落ちてる箇所の数がc個で、最後がe=0 or 1で、あとループなので先頭がs = 0 or 1だった場合の数、
      • を覚えておけば i+1 の場合もなんか求まる
    • 50*50*2*2 くらいの状態空間。計算量もせいぜいこれに50かかるくらいだろう。
    • 外のループも高々50だから、50^4。行ける。

  • 書いた
  • 通った
  • よし

900開く

  • 『二次元のH*Wのマス目を4色で塗り分けたい。ただし、どのマスも、隣接8マスと違う色にしないといけません。今既に適当に塗られている塗り方から、Kマス塗り替えて条件を満たす見たし方は何通りあるか。mod 1000000007で求めよ。』
    • H,W≦50

  • あれ?4色で8方向全部と違う色って可能?
  • 平面グラフにもなってない気がするし…
  • あ、できるか。市松模様の偶数行目を色反転させるようなパターンとか

  • ただ、かなり制約きついな。
  • 4^(50*50) オーダの塗り方があると思いきや
  • 上辺の塗り方は 4*3^49 通り
  • 最上段を塗ってしまうと、二段目の左のマスの色を決めたら、その右隣、その右隣…と可能な色は1通りしかないので、全部色が決まってしまう。
  • というわけで、後は左辺を2^49通り決めれば全部塗り方が定まる
  • e^2500 オーダかと思ったら e^100 オーダの塗り方しかない

  • でも100乗って十分大きいよ…

  • うーむうーむ
  • わからず

撃墜準備タイム

  • 案の定600はほとんど出てない
  • 250考えるか…
  • ええとまず自分の解を忘れているので読み直す…

> - 4のベキ乗が問題なので4進数で考えると、

> -- 4のi乗を引く == i桁目を1減らす  (※間違い)

  • ええと…ええ?
  • 8 から 1 を引いたら、四進数でいうと 20 が 13 になります。
  • おいこれ二桁以上同時に変わってるぞ!
  • 間違えたー!
  • 実際 8 の場合に手で解析してみると、間違えてる。
  • おわた

撃墜タイム

  • 4で割りながら和を取ってるコードを見た瞬間に 8 を叩き込む。100点ゲット
  • そして自分のは落とされてる。

感想

  • ちょっと 250 焦りすぎた。酷い
  • しかし Medium が解けたのでわりと満足です
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100611
 | 

presented by cafelier/k.inaba under CC0