cafelier@SRM

SRM457

SRM | 00:56 |

SRM457 の成績・ソース (要ログイン) : AC/AC/- : こんにちは2500

500開く

• 『6角形のマス7つが合わさって6角形の形に並んでます。1～2n までの数から異なるもの7個選んで各マスに書き込みます。ただし隣接マスの値がmod nで等しくなってはいけません。書き込み方は何通り？』
  • 1≦n≦150
  • 回転して重なるのは同一視します

• 7マスで固定なら、組み合わせの数が式で求まるよなあ
  • えーと、とりあえず7マス全部に違う数字を入れるには n≧4 でないと。
  • n≦3なら無条件で0返す。
  • チャレンジポイントになるかな。メモメモ。

• それ以外の普通の場合は…
  • えーと、とりあえず中央のマスにはどの数字を入れても、他に埋められるパターン数は変わらない。
  • なので中央には仮に 2n を入れたとしちゃって、残りのマスの場合の数を求めて 2n 倍すれば答えは求まる。
  • 2n を入れたら、mod n で 0 になるのは残り n の１つだけ、他は 2 つずつある。
  • てことは、周囲6マスにnを入れる場合と入れない場合で場合分けかな…
    • えーとnを入れる場合…
    • 場合…
    • 入らないよ！ 2n と n が隣り合っちゃダメじゃん！
  • 入らないので、残り2(n-1)個の数字を周囲6マスに振り分けます。

• 回転は同一視するらしいので、
  • えーと、使う最小の数字を固定して、それが常に一番左上に来ると考えて埋めていけばいいかな
  • いや、回転同一視は気にしないで、あとで6で割る方が多分簡単。

• 気にしないで数える。残り6マスの埋め方は…
  • ええと、mod n が同じ数字は2個までしか使えない
  • 隣どうしには、mod n が同じ数字は並べられない
  • 中央の2nのマスとは衝突しないので気にしなくていい
• なので
  • 全部mod nで違う数字{1,2,3,4,5,6}の場合
  • 最初5マス違って最後だけ他と一緒になる
    • {1,2,3,4,5,4}, {1,2,3,4,5,3}, {1,2,3,4,5,2}, {1,2,3,4,5,1}…これはダメだな…
    • …
    • あー、n＜6 だと最初のパターンは作れないからそこでも場合分けが必要で…

• って、こんなパターン分け手で列挙しているようではいけない！
  • なんか 6 マスしかないから手で列挙もできそうだけど、そんなことではいかん。
  • ここは断固としてプログラムで書く。
  • まあ「mod n が同じ数字は2個までしか使えない。 隣どうしには、mod n が同じ数字は並べられない」ような{1..min(6,n)}の並べ方をDFSで全列挙するだけです。
  • もっとずっと綺麗に書けそうな気がするけどまあいいや…
  • これはサンプルさえ通せば通る問題のような気がするし

• 全列挙できた。
  • で、例えば {1,2,3,4,5,2} だったら、
  • 5個の違うmod nの同値類を取ってくるわけだから、nP5通り
  • 2については2とn+2のどっちをどっちに入れるかで2通り
  • 1,3,4,5 についても、2つあるどっちを入れるかで各2通り
  • を全部掛け算すればこのパターンについての解はでる

• これを総和をとればいい。
  • なんか凄いコードが汚くなってしまったけど…
  • サンプル通った！

• n=150でも時間的に問題なし
  • 答えはあってるかわからんけど、サンプルは全部あってるしまあ大丈夫でしょう。
  • あ、n=150だと答えだいぶ大きいな。64bit越えてないか？
  • 150^6でも2^63よりだいぶ小さいっぽい。じゃあ大丈夫だ。
  • submit

250開く

• 問題文ながいぞ…
• 『"hh:mm GMTof" という時計の表示が入力です。hhは00～23、mmは00～59、ofは-9～+9。ただし、ところどころ ? になってるかも。GMT+0 では今何時か推測してね。』
  • ?があると一意に定まらないので、その場合は、可能な一番早い時刻を返すこと。

• 可能な表示パターンは 24*60*19 通り。
  • 全部ためして、与えられた表示になりうるかチェック
  • →なりそうなら記憶。最終的に最小値を返す
• これで十分間に合う。

• ガリガリガリ
• 実装実装実装
• 書けた
• 僕は頑なにiostreamを使ってないでおとなしくsprintfの軍門に下るべきかもしれない
• だが断る

• できた。
• sample通った。手元だと数百msかかるなあ。
• 念のためサーバでもテスト。うわ一瞬。
• なんだろう。VC++のstringstream遅いんだろうか。まいっか。
• submit！

1000開く

• たしか残り37分くらい
• 『n×nのマス目に駒がたくさん置いてあります。i行目にR[i]個置いてあったとしましょう。この状態から駒を上下左右に一マスずつ動かして、最短手数でi"列"目にR[i]個ある状態にもっていくにはどうすればいいですか。』
  • 最短手数解が複数ある場合は終了盤面が辞書順最小のものを
  • 返す物は終了盤面
  • n≦18

• 駒動かす時って重なってもいいんだろか。
• 問題文には特に書いてないな
• うーんと、関係ないか
  • 「駒重ねる→重なってるの動かす」と「先に動かす→どいたとこに動かす」は同じ手数だし

• 最大18×18=324マスだから…2^324オーダの状態があるわけで…
• いやまあ、1000点問題なんだからそんな全探索で済むわけがないですよね。
• むむむ…

• 辞書順最小だから、一番左上角に駒が行く最短解がもしあればそれが速い。
  • 「１個を左上角に動かしてみる」→それで残りの部分に解があるか再帰的に求める
  • のループでじわじわ決めていけばいいんじゃね？
  • その「１個を左上角に動かしてみる」の「１個」ってどれ？
  • 全通り試してたら 342! 通りかかりまーす

• 駒ではなく駒でないマスに注目するという裏技的発想はどうだ？
• 駒を動かすのはすなわち同時に駒でないマスを動かしているので
• 駒でないマスを動かしてn-R[i]をn-R[i]にするゲームと考えてもいい。まったく双対
• つまり、駒のあるマスとないマスで少ない方のゲームと考えれば…
• せいぜい 2^162 とか 162! になるだけですね。ダメですね。

• ううむ。
• 左上角へのマンハッタン距離が近いやつから順に動かしてみるとか…
• 少なくとも追い越しをする必要はないはずなので、他のやつの進路上にある奴は優先して使って間違いないはずで…
• でもマンハッタン距離だけではその条件にいまいちあってないな…

• ううむ。
• 待て待て。
• 左上角への移動だけじゃなくて全マスto全マスの全移動を考える。
  • 初期状態から
    • （n×n個の・をノートの左側に書く）
  • 全部の駒を動かして別の状態へ持って行く
    • （n×n個の・をノートの右側にに書く）
    • （んでもって左から右に完全２部グラフ的に線を引く）
    • （各枝の重みは表してるマス間のマンハッタン距離）

• この動かし方のうち、重みが最小になるような完全マッチングだ！

• 違う！
• 右の状態では、「i列目の駒の数 = R[i]」でないといけない。

• いやでもこれはedgeを増やしてどうにか…

Src  初盤面　　　　　終盤面　　i列目代表点     Dest
・──・　　完　　　　・────・───────・
　＼　・　　全　　　　・────　　　　　　　／
　　＼・　　２　　　　・　　　　　　　　　　／
　　　・　　部　　　　・────・─────
　　　・　　グ　　　　・────　　　　　↑
　　　・　　ラフ　　　・
　↑　　　　↑　　　　　　　↑
　｜　マンハッタンコスト　全部容量１　　　容量R[i]
　｜　容量は全部１　　　　コスト０　　　　コスト０
　｜
　｜
　最初に駒があったマスにだけ
　容量１コスト０の辺

• これだ！
• これの最小費用最大流
  • 最大流は元の駒の個数
  • 元の駒の個数にすると、終盤面は自然とi列目にR[i]個になる
  • コストはマンハッタン完全２部グラフのところだけかかってるので
  • そこが最小になるのは移動手数最小のとき

• えーと頂点数は…
  • 18*18*2+2+18…360くらい？
  • 最小費用流ってO(n^3)だよね。大丈夫かこれ
  • しかも辞書順最小ってなんかさらに18*18回この最小費用流回さないとダメでは

• えーいダメもとで書いてみてから考える！
• 書き書き
• 書き書き

• できた！
• 回数は求まった！でも辞書順最小じゃない解が出てる！
• そしてあと１分しかない！
• だめだなあ時間かかりすぎだ…
• しかもこれ324回まわずどころか、1回回すだけでも最大ケースでタイム怪しいぞ…
• 残念無念。力及ばず。

撃墜タイム

• 撃墜タイムに入る前に、部屋のスコアボードチェック
  • 1000は誰も出してない
  • 500は何人か出してるけど…
    • 物凄い超絶場合分けのソースとか絶対読む気しないし
    • 逆に綺麗な数式出されても検証できる気がしない
    • これは無理だ
  • 250に集中。
    • 落とし穴はなんだろう？
    • コーナーケースは… "GMT-0 はない GMT+0 だ" かな
    • "00:00 GMT-?" にうっかり "00:00 GMT-0" と答えてしまうと間違い。正解は "00:00 GMT-1" の1時。
    • こんな間違えする可能性は…あるか？
    • あるか？
    • あるなあ
    • 「全パターン生成→マッチング→あってるのだけ残す」方式では、パターン生成のところでGMT-0は作らないだろうからなさそうだけど、
    • 「?をDFSで全通り埋めてみて最早のを返す」のは、?に機械的に0-9を埋めてると絶対ある
    • これだ
• 200点ゲット

感想

• 1000はコストうまく調整して最小費用流一発で辞書順最適解が出せたりするのかなあ。わからぬ…

• 順位は4位でした。自己ベスト順位更新！
  • ただ、最近完全にチャレンジ頼りになっちゃってるのがどうしたものか。
  • 自分自身としては、チャレンジ能力は問題解く能力並に重要だと思うのでわりとこれは満足なんですけど、これってそういうゲームではないような気もする。
  • まあ頑張りましょう。