cafelier@SRM

Google Code Jam 2009 Round 2

GCJ | 12:29 |

GCJ09-R2 の成績・ソース : AC-AC/_-_/AC-_/AC-_ : パニクりすぎ

A開く

• お、問題文短い！
• 『N×Nの、各要素は0か1の行列があります。隣接する行と行のswapを最小の回数やって、下三角にだけ1があるようにしてね』
  • Small: N≦8
  • Large: N≦40

• とりあえず、各行毎に一番右の1の位置を計算しておけば
• 『N要素の、各要素は0～Nのint配列vがあります。隣接要素のswapを最小回数にして、v[i]<=i になるように並び替えてね』
• という問題になる

• これ解がない場合もあるよなあ
  • あ、そういう入力はないと仮定して良い、と書いてある

• うーん。なんだ。ということはソートすれば確実に正しい状態になってる。
  • バブルソートを書いて回数数えればいいとかかな。
  • いや、でもソートしきらなくても正しい状態になることはあるし…
  • …？？？

• さっぱりわからん！次！

B開く

• うわ面倒くさそう。後回し
• digとか書いてあるし絵の感じからして、ミスタードリラーみたいなゲームかな…

C開く

• 『折れ線グラフをN本描きたいんだけど、接したり交差したりするグラフは紛らわしいので別の図にしたい。そうでないのは1枚の図に詰め込む。最小で何枚の図が必要？』
  • Small: N≦16
  • Large: N≦100

• とりあえず折れ線グラフの交差判定をしてから、
• 「交差しないグループ」何個で全体をカバーできるか…という最小カバー問題にはなるなあ。
  • SmallのN≦16は愚直に全部のカバー方法を試して間に合うか
  • Largeは、折れ線の交差で作られる関係に限ることを利用するとなんかグラフのマッチングとかフローとかになるのかな。D-Largeよりは解けそうかも
  • (折れ線グラフ的な意味の)グラフをネタに(組み合わせ論的な意味の)グラフの問題を作ったというわけか！

• それはそうとコード量多そう。めんどくさい。後回し。

D開く

• 要は
• 『半径rの円がN個、二次元平面上にばらまかれています。全部を、半径Rの円2個で覆おうと思ったとき、Rを最小にしてね』
  • Small: N≦3
  • Large: N≦40

• て、読んでる間にもうA解いてる人がいる。すげー
• それはともかく、N=3 なら、1個をカバーする円と2個をカバーする円に分ける分け方は3通りしかないから、全部試して最小を選べばよい

• N=1 の場合…はR=r
• N=2 の場合…R=max(r)
• N-3 の場合…は、3通りの分け方の最小値を…
  • よし、だいたいかけた。
  • 2個(x0,y0,r0)と(x1,y1,r1)を1個でカバーするには半径Rをいくつにすればいいかな？
    • 絵を描いてみる
    • 2つの円の中心を結ぶ線の上に中心を置いて、両方に接するようにすればよさそう
      • distance( (x0,y0), (x1,y1) ) + r0 + r1 が直径

• できた。サンプル通った
• Small提出。通った

• Largeは…2円か3円かに接する様な円を全列挙してそこから2つとって全カバーできるペアを全探索、かなあ。
• 3円に接する円の中心を求めるとか書きたくない。放置。

Aに戻る

• 点数も低いし、大量に解いてる人いるし、そんなに難しいはずは…

• は…
• あ、そうか、Smallの場合8行しかないから、並べかえ方は 8! = 40320 通りしかない
• てことは、1回のswapでできる状態、2回のswapでできる状態、…を幅優先探索で全部探していっても余裕で時間内に終わる

• 書いた
• サンプル、Small通った。よし

• そしてLargeは相変わらずさっぱりわからない…。
• …なんでこんなにたくさん解いてるんだ。点数も低いし
• 謎だけどわからないし他をやる

Cに戻る

• とりあえずSmall書く
• あ、折れ線の折れるポイントは全部共通だから、交差判定はすごい簡単だ

• さて最小カバー。
  • 「まだ図に描いてないグラフの集合」を与えると、メモ化再帰で必要な最小の図の枚数を求める関数を書く
  • 引数の状態数は 2^N。
  • 各ステップは、重ならないグラフ集合は O(2^N) 個あるから
  • O(4^N) かー。4分ならなんとか終わるんじゃないかなー。ペナルティ低いしやってしまえ

• 書いた。
• サンプル通った
• Small…うわー全然おわらない。4分の時点で1/3くらいしか終わらなかった。
  • なんかよくみたら O(N 4^N) か O(N^2 4^N) くらいのソースを書いてる気がする。これはダメだなあ。

• たしか、むかしSRM過去問解いたときに、最小カバー使ったことがある…
  • （過去コード探索中…）
  • あった！
• よくわからんが、これ使えば通るんじゃ。
• コピペ。Go!

• ゼロ除算で落ちた
  • は？
  • next_combination でなんか落ちてる
  • うーん。このコード書いたときに暗黙に仮定してた前提条件がなにかあるんだろうな…
  • わからんなー。

• その昔のコードを読んでみると、
  • カバーに使う集合を極大集合に限定する等々の最適化 → 地道に探索
• の２ステップになってる。前半はちゃんと動いてるっぽいので後半だけ今書こう。
  • 書いた。
  • Smallのデータ改めていれてみる
  • なんだか、前半が時間かかりすぎるデータがまだあるっぽい

• よく考えたら N≦8 くらい向けに書いたコードだった気もしてきた。16だときびしい…

• うおおどうすれバインダー

• あらためて今やっていることを整理
  1. 「一つの図に描いてよい折れ線グラフ部分集合」を全列挙
  2. 無駄な物（他の一つの図に描いてよい集合の真部分集合になってるもの、など）を除く
  3. この集合族の中から最小個数の要素を取り出して、元の折れ線グラフ集合を全カバーする。ここは全探索。

• うーむ
• 無駄な物を除くフェーズは、昔のコードはなんかすごい頑張ってるけど、
• 極大じゃない判定は、1要素増やしてみて大丈夫か判定、をN回くりかえすだけでわかる。これは全体で O(N*2^N) なので十分動く
  • それで十分な枝刈りになってそう
• 全カバーを全探索のところは、next_combinationとかで探すより、普通に幅優先探索でいいんじゃなかろうか。

• 書き直し…
• できた。幅優先探索はAのソースからコピペ。
• よし、さっき間に合わなかったSmallも終わる！
• 再ダウンロード。通った！
• ふぅ…

• 終わってみれば当たり前のことを当たり前に書くだけだった…
• なんで1時間もかかってるんだ俺…orz

A-Largeに戻る

• これだけたくさんの人が解いてる問題が難しいはずはないんだ…ｎ！
• なんかシンプルな戦略で最適解がでるはず。

• 上の方の列ほど制約がきついから
• 上の方に入れるやつは下の方にも入れる
• ということは、制約のきつい上から順にgreedyに埋められるもので埋めていく感じで最適解がでたり…

• 自信全くないけどとりあえず書いてみる
  • 上の方の列から見ていって、下三角条件をみたしてなければ、
  • 一番近い、条件を満たす列をとってきてswapで持ってくる
  • 以下繰り返し

• これで良いという証明がまったく思い浮かばないけど、
• …このアルゴリズムでSmallの全探索君と答えが一致した
• これは行ける！
• Largeサブミット。

さて

• 残り45分。
  • スコアボードを見ると
  • 500位の合格ラインは、あとどれでも1問解けば確実そう
  • 解けないとダメそう

• B-Small、C-Large、D-Large、のどれなら解けるか…
  • D-Largeはたぶん僕には45分で書けない
  • C-Largeは…アルゴリズム思いつけるかどうか自信ないなあ
  • B-Smallは…実装重そうだけど、穴掘るゲームなら、やるべきことはどうせビットDPだろうし、45分全力で実装すれば…

というわけで、Bに戻る

• 堀り方はミスタードリラーじゃなくてロードランナーだった。
• 『C×Rマスのマップがあって、1,1からゲーム開始です。左右に動けます。右斜め下と左斜め下が掘れます。下まで降りるには最小で何マス掘ればいいですか』
  • ただし、下に落ちるときにFマスより多く一気に落ちると死亡
  • Small: 横6縦10
  • Large: 横50縦50

• 今いる座標(6*10) * 今いる行の掘られ状態(2^6)
  • からの最小掘り進み回数をDP or メモ化再帰で求めればよい。
  • 今いるより上の行の掘られ状態は関係ないし、今いるより下の行は、今の行に到達した時点では掘れてない初期状態なのでやっぱり関係ない。一行分の状態だけ覚えとけばよい

• 問題は、
  • 今いる座標(6*10) * 今いる行の掘られ状態(2^6)
• から次にいける状態を列挙する処理で…
• その処理だけ中身空の関数で実装してまわり全部は書けた。

• えーと、どうする。
• まず、キャラクタが動ける範囲は、
  • 現在位置から左右に、
    • 今の行にブロックがない
    • 下の行にブロックがある
  • 範囲

• この範囲は＆この範囲のみ自由にうろうろ歩ける
• 掘ってから落ちるわけだけど、どういう落ち方があるかというと、
  • 落ちる前の足場はないといけない
  • 足場の右に落ちる場合、下の行で左にはいけないので、足場より左の堀り方は関係ないので掘らなくていい。
    • 逆も同様。
  • 行ける範囲の端っこまでいって、足場まで戻りながら隣を掘っていけば、
  • 足場から落ちる側は自由に掘れる。これを全パターン列挙する。

• つまり
  • 動ける範囲を求める
  • foreach 動ける範囲(6)
    • foreach {左に落ちる, 右に落ちる}(2)
      • foreach {落ちる側の堀り方全通り}(2^6)
• だ

• 頑張って書く
• 結構時間かかった。のこり7分
• サンプルあわない！
• 細々としたバグをフィックスしまくり
• わあ残り4分だ。もうSmallダウンロードしとけ！
• 残り3分。サンプル通った！
• Small動かした。よしサブミット！incorrect！！！！！！！！！！
  • どこが悪いんだ2分でバグとか見つかるわけが…

おしまい

• 543位。通過ならず。

• とりあえず、Bは上にブロックがあるマスは掘れないという条件を見落としてました。他にもまだあるかも…
  • ロードランナーはそういうマスも掘れたような記憶が…と思ったけど、そっちも掘れないっぽい。もうだめだ

• とにかく C-smallがひどかったなあ、と。ここが30分早く解ければB-smallも余裕をもって直せたと思う。

• まあ、「調子よければ通過できたはず」程度の実力で通過できても喜ぶところじゃない気がするので、来年がもしあれば「絶不調でもRound 2くらい余裕だぜ」と言えるくらいになっていたいものです。がんばろう。