cafelier@SRM

SRM472

SRM | 14:23 |

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桁目を１減らす　　（※間違い）
• なので、結局、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 とループすると全部違う元々のパターンと同じことになる。
• ので、この連鎖して伸ばしていくパターンをうまく数えればいい。

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

• ということで、とりあえずサイクルに分解するコードを書こう。
• 書いた。
• 長さ 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

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

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

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

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

撃墜準備タイム

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

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

> -- 4のi乗を引く == i桁目を１減らす　　（※間違い）

• ええと…ええ？
• 8 から 1 を引いたら、四進数でいうと 20 が 13 になります。
• おいこれ二桁以上同時に変わってるぞ！

• 間違えたー！
• 実際 8 の場合に手で解析してみると、間違えてる。
• おわた

撃墜タイム

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

感想

• ちょっと 250 焦りすぎた。酷い
• しかし Medium が解けたのでわりと満足です