天下一プログラマーコンテスト2015 本戦

2015-09-06 | [Competitive programming]

F

• 問題をざっと眺める
• A, B を見てやばさを感じたが，ペナルティがないので一旦完全に無視
• 少し考えると F が一番とっつきやすそうなのでまじめに考える
• データ構造ゲー
• 最初「木の各状態ごとに爆速」で答えないといけないと勘違いしていたが，「クエリごとに，クエリ長さだけかけてよい」ことを思い出したら解法はわりとすぐに見えた
• 書いて AC (ほとんどバグが出なかった)
• 木の DFS 順序を使う問題では，「入力で与えられる頂点番号」と「DFS 順序番号」を混同することによるバグが多発するので，これを明確にすべくコメントなども入れて警戒した
• LCA をその場で実装したのはあまりよくなかったかなあ (ライブラリ化するべきな気がする)
  • segment tree の実装はなにも頭使わないしすぐ書けるので別によさそう

E

• C を少し考えて，なんとなく解けそうな方針が見える
  • 部分点解法で，各区画 (横棒と横棒の間) で DP やら Dijkstra するのを適切にさぼる
  • 各位置において，「その下で 1 ステップで入れ替え可能なペア」たちの集合を考え，この集合が切り替わる地点のみまじめに調べ，他の場所はさぼる
  • すると，集合は高々 21 回くらいしか切り替わらないので，間に合う
  • ただし，この解法は嘘である
• ただ，面倒というか混乱する系の問題に見えたので躊躇する
• 順位表を見ると E が解かれていたので考える
• 最初 O(N^2) を考えていたがよく考えるとすぐ O(N) にできたので，場合の数の式を立てて実装
• 送る．WA (15 点)
• こういう問題で本質的に何か間違えるということはあり得ないしどうせ mod の取り忘れだろうと思ったら案の定そうだった
• 直して送る．AC

C

• その後，さっきの方針で C を実装
• 送る．WA (0 点)
• 仕方がないので部分点を取りに行く (少しコード書き換えるだけ)
• 考えても何が違うのかわからない (今もわかってない) ので，とりあえず最初のコードの反例を見つけるコードを書いて走らせる
• その間に D の部分点を実装し，通す

B, A

• 相変わらず C はわからないので，気分転換に B を書く
• ヒューリスティックを書くことも考えたが，よい方法が分からないので有名な (最大次数の頂点に注目する) 探索を書く
  • この探索は 4 年前の夏季セミで実装したことがあった
• 書いて自明なバグを取ったら，簡単なテストケースはすべて通るようになった
• バグが怖いがどうせペナルティないので送って AC
• A はよい戦略が思いつかないので，適当に大きく非自明なグラフを作って送る
• 自分の B のコードに投げるとどうやっても 30ms とかで終了するので弱いのは明らかだったがパラメータをどうやっても強くならないのであきらめる

再び C

• 反例生成器は結局 1 個も反例を作らなかった
• 途中で G の部分点を考えるも問題文を読み間違えていて解ける問題に見えないので中止 (正しく読んでいたとしても，メモリが足りないと思い込んで解けなかった気がする)
• 「小さいケースに変なケースがあるのでは」と思って部分点の場合だけまじめにやるようにしたら WA が 2 個だけであることが判明
• しかしまじめに考えても何が違うのかさっぱりわからない
• そうしているうちに sky さんが C を通していて焦る
• やけくそで「最初，最後 100 個もまじめに調べる」コードを送ったが，時間がかかりすぎることが判明
• ただちに 50 個に変更したコードを送る→AC

• (後で検証したところ，本当に最初最後 50 個だけ調べるコードでも通るらしい)

• 残り時間の戦略を考えるも，D はついに誰も満点をとらないので無理であると判断し，A の強いケースを考える
• 自分の B のコードで時間がかかるようなケースを作ろうと試みたが，何やっても 30ms とかなので送り直すのはやめる

結果

• 終了直後の地点で，1 位か 2 位であることは確定 (A, B の未確定部分では高々 76 点しかとれないので)

• 途中で B 問題の結果が判明し，A 問題の点数はわからないものの 1 位っぽくなる

• 結果発表，A, B の点数公開で盛り上がる．よすぽ強い
• 結局 A 問題もそれなりに点が来ていて 1 位だった！

問題の感想

• A, B のような形式の問題はかなり意外で面白かった．(あえて有名問題にしたのは，時間がきついからかなあ)
• G は「解法に至るステップ数が多い」問題という感じがあって，大量に時間があってこれだけしか考えるものがない，とかだったら解けたかもしれない
• 逆に D はいくら時間があっても解けなかったと思う (そもそも，解が全部列挙可能なので列挙するという発想に至らなかった)
• C の想定解はかなりきれいだと思った (これ思いつきたかったなあ)