JAG Regional Warmup

ICPC

ネタバレ注意。

  • 自分の研究室にて参戦。印刷とかちょっと手間取った。

Problem A: Era Name

  • よく分からないけど@romanchuが瞬殺してた。
  • 「CtrlとCapsLock入れ替えてください」と頼まれたけど、個人的には今のままが好き。
  • じゃあ両方Ctrlにしますか。
    • 適当にxmodmapを書いたら何やらエラーを起こしてしまった。諦めて再起動。
      • ごめんなさい...。

Problem B: Step Step Evolution

  • よく分からないけど@iakasTが頑張って通した。

Problem C: Dungeon Quest II

  • 問題読んだ。
  • 位置とポーションでDPするだけの簡単なお仕事っぽい。
    • @romanchuに放り投げる。
  • 紆余曲折の末通った。

Problem D: Dice Room

  • 読んだ。うん、簡単そう。
    • ...あれ？その割に全然解かれてない？
    • 怖いので後回しにしよう。
  • ...
  • Clarが来て、何チームかが一気に通したので、Jを解いたあたりで戻ってきた。
    • うん。まぁ、書くだけだよね。
  • @romanchuがごりごり書いて通した。
    • 「作業」だそうです。

Problem E: Alice and Bomb

  • グラフに落としてダイクストラだろうか。頑張れば解けそう？
    • どこかの頂点まで逃げればいいはず。
      • すべての頂点の付近で爆死するかどうか調べて、可視グラフ作って最短経路。
  • ...いや、頂点じゃなくて放射線の上に逃げるパターンもあるのでダメだなぁ。
    • 爆風の多角形を作って、建物と接していない任意の辺までの最短距離でいいかな？
      • 爆風の多角形は、建物の頂点を偏角でソートしてうまく繋いで行く形で。
        • 複数の点が同じ偏角であるときなども適切にどうにかする。
  • ...ムズくね？
  • 実はグロ問のような気がする。とりあえず次行こう。

Problem F: Two-Wheel Buggy

  • 捨てたくなった。
    • けどちょっとだけ考えてみる。
  • LspeedとRspeedの符号が等しいケースは、両輪が同心円上を同じ角速度で動くことからどうにか計算できそう。
  • 異なる場合は・・・
  • 次読もう。

Problem G: Camera Control

  • うーむ。よく分からないぞ。とりあえず次。

Problem H: Road Construction

  • _ が解いている。
  • しかしこれは相当難しいのではないだろうか。
    • 10,000回ダイクストラして全点間最短経路を求めて。
    • 使う辺の候補をうまくごにょごにょして...。
  • 無理じゃね？
  • ...
  • 問題読み間違えてた。全点間でなく、首都からの最短距離さえ保存されればいいのね。なら出来そうだ。
    • UAPC2010のWinter Bellsの要領で、使っても良い辺 (その辺を通れば最短経路になるような辺) を列挙する。
    • 各ノードごとに、そこにたどり着くための辺の中で、先ほど列挙したもののうち建設コスト最小のものを選べばよい。
  • 他の問題を通した後で実装開始。
    • 使っても良い辺を全列挙した後でごにょごにょしようと思ってたけど、特に全部覚えておく必要がないことに実装中に気づいた。
      • 使わない情報を持って回りながらダイクストラしてるけど、まぁいいか。オーダ変わんないし。
  • 一発で答え出てきた。submit.
    • Runtime Error.
  • 配列の長さがどう見ても足りない。直してsubmit.
    • Time Limit Exceeded.
      • ...え？
  • 実装を面倒臭がってるのがいけないのだろうか。定数倍の高速化をしてみる。
    • TLE. TLE. TLE.
  • いくらなんでもおかしい。ちょっと遅いとはいえ、たった10,000ノード20,000エッジで通らないはずがないだろ...。
  • ...
  • ...あー！
  • priority queueから取り出すときに、最小でなく最大を取り出してた！ばか！
  • Yes.
    • そうか、最悪優先探索でも (すごく時間掛かるとはいえ) 答えは正しく出てくるんだよなぁ...。

Problem I: Operator

  • バイナリサーチ + シミュレーションだろうか。
    • 単調性がちょっと怪しい気もするけど...。
      • シミュレーションの計算量と相談しつつ、線形探索するなり、二分探索の解から -100 ぐらいまで調べるなりしてしまおう。
  • ...
  • D とか H を通した後で@romanchuが挑戦してみた。
  • sampleが出てくる前に試合終了。

Problem J: Merry Christmas

  • 何も考えずに、プレゼント a を届けた後でプレゼント b を届けられるなら a - b の有向辺を張る、というグラフを書いてみる。
    • 重ならない最小数のパスでDAGの全頂点をカバーできれば言い訳だ。
      • あ！この問題蟻本で見たことあるぞ！
        • Dilworth's Theoremですね。
          • 極めてどうでもいいですが、Dilworth's Theoremと聞くとなぜかバルキスの定理を思い出します。
  • とはいえこの定理を使った問題を解いたことがないので、使ったことがあるという@iakasTに相談してみた。
    • 「良さそうですね」とのことなので、そのまま二部マッチングのライブラリと一緒に押し付けた。
  • WA. Yes.

Result

  • 6完5位。
    • 関西勢がお休みのせいで、順位が高く見えてしまう。
  • H で頭悪いことしなければもう1問通ってたかもなぁ。
  • F はかなり難しい気がするのに、通したチームが多くて驚き。
  • ジャッジの皆様、お疲れさまでした。ありがとうございました。