2014-04-13
GCJ 2014 Qual
Other | | 
Template を Java 8 にバージョンアップして出てみた。というより template 更新ばかりに時間をかけて危うく時間切れになるところだった。。とはいえ並列ストリーム以外は全然使ってないけど。
A: やるだけ。もうちょっと詳しく説明すると、 4 行 4 列の行列が 2 つあるのでそれぞれから指定された行を抜き出して一致する数字はいくつありますか？1つならその数字も教えてねという問題。まあ、登場人物は盤面を90度回転させればよかっただけのになぜそうしなかったのか、謎である。
B: クッキクリッカーで所定の枚数を最速で集めるには？ただし、施設は農場だけで(ばーさんもいない)、さらに連続時間モデル。建てる施設数をパラメータに最適化すれば良くて多分凸性もありそう。なんか制約から線形探索で良さそうな気がしたのでそれ投げてしまったけど通った。でも、あとでよく考えてみると C=1, F=1, X=100,000 とか渡されるとヤバイことに気付いた。これだからランダム入力は…
C: 盤面のサイズと地雷の数が与えられるので、1 クリックで終了できるような盤面を生成する問題。Small は全配置を生成してそれぞれ 1 クリックで終了できる位置がないか調べた。Large はそれでは無理なので、左と上に幅 3 の領域を残して角にクリックポイントを置き、残りの部分に規則的に埋め、次に幅 3 の領域に規則的に並べて、最後に残った 3x3 は全探索した。3x3 の領域に離接する外側のタイルでアドホックな場合分けを入れたので、そこで撃墜できそうな予感だったけど、落ちなかった。ランダム入力さまさま…
D: 問題文に警告が出ているように理解するまで時間のかかる問題。詐欺プレイをするときは釣りができるので、Ken の各おもりりに最大までそれに勝てる自分のおもりを割り当てることができる。一方、しないときは自分の持っているおもりの重さしか伝えられないので、避けられないとき以外は Ken によってそれより小さい重さのおもりが 1 個ずつ消費されてしまうので、残りが答えとなる。
結局全部通って満点 90 点でした。
