JAG Practice Domestic Contest

ICPC

OB/OG会の模擬国内予選。
5問解いて6位でした。

  • A, Cをyukが、B, Dを私が解くという方針で行くことにしました。
  • 後輩Kにはペアプロに回ってもらうことに。
Problem A: 幸運の操作者
  • 問題文印刷している間にyukが頑張って通した。
Problem B: Matsuzaki 数
  • 緊張して頭が回らなかったけど、辛うじてyukがAを解く前に最悪100個ぐらいの素数しか必要ないよねと気づいた。
  • バグった。問題文中に N = 0のときの例があるので、それと比較しながらデバッグ。
    • 怪しいところは直したはずなのに、素数和リストが一致しない・・・。
    • 合うわけないよな、と思いながらSample読み込ませてみたら何故か正しく出てきた。
  • 問題文が間違っていると信じて送ったら通った。
    • 問題文の N = 0 のケースには 15 (= 2+13) が欠けている。
    • Clar送ろうかと思ったけれども、もうAC貰ったので放置しました。
  • ここでCとDの内容を聞いてみた。
  • Cを私がじっくり読んでいる間に、yukがDを書く方針で。
Problem C: 勇敢なお姫様またも現る
  • 読めたのでyukと交代。
  • Dijkstra書くのが面倒くさいので、Bellman-Fordでどうにかしようとしてみる。
    • しばらく格闘してあきらめた。
  • 実装にものすごく手間取った上に、コピペミスによってWAまで食らってしまった・・・。
  • どうにかAccepted。
Problem D: 制限されたファイルシステム
  • yukがごりごり実装して通した。
Problem E: 鏡の洞窟
  • BFSだと思うんですが、と後輩Kから渡される。どうみてもBFSですよね。
  • Dの裏で後輩Kとペアプロ。
    • Dが通ったらトリプロに。
    • ひたすらコピペして 'M-% rin len' しました。
  • RinとLenが左右反対の動きをすることを忘れてたりしたけど、チームメイトのおかげで比較的スムーズに通りました。
Problem F: 海岸線の浸食
  • 無理ゲー。
  • 5問通した時点で4位だったのに、時間差でHABRushとLittleBugに抜かれていきました。残念。
  • 一応書くだけ書いてみたけど、アルゴリズムが詰め切れてなくて完成しませんでした。
反省タイム
  • Cに時間を掛け過ぎました。
    • 天敵であるところのBを無難にやり過ごしたと思ったら、今度はこっちで・・・。
    • 他のアルゴリズムでどうにかなりそうでも、Dijkstraで決め打ちすることにしよう。
  • Eを先に解いておくべきだったかも。ただのBFSだったし。
講評を見てみた
  • Fは全然無理ゲーじゃない。なぜこの方法を思いつかなかったんだ・・・。
  • BでついにnextProbablePrimeが日の目を見るという奇跡。
    • 「誰がこんなの使うんだよ・・・」とずっと思ってましたごめんなさい
  • 私の感覚では E < C < D だったのですが、AC数は C < D < Eだったようです。
  • 審判団の皆さん、お疲れ様でした。ありがとうございました。