JAG Practice Contest for Asia Regional

ICPC

早くも忘れかけてるけど、参加記録をざっくりと書いてみます。以下ネタバレ。

Problem B

  • DPかと思ったけどどう見ても間に合わない。
  • 一番大きいのを消していくGreedyかな？
    • ちょっと考えたら反例が見つかった。
  • 消せるのがある限りひたすら消していけばいいんじゃね？
  • 書いた。念のため消していく過程を吐かせてたりもしてみた。半信半疑で送ったら通った。
  • First Acceptだ。やったー。

Problem A

  • @romanchuが嵌ってたので手伝ってみた。
  • 問題が全然読めない。わけわからん。AなのにBよりむずい。
  • ここはこういう意味だよね、と問題の解釈を喧々囂々議論しているうちにSample出たので送ったら通った。

Problem C

  • 去年はこういう問題はnobに丸投げしてたけど、今年はがんばって書かないといけない。
  • と思ってたら後輩Kがいろいろ式を立ててくれた。
  • 二人で協力してAccepted。
  • lower_boundを何度も使うことになりそうだったのでSTLに慣れている私が書いたのだけど、実際には1回しか使いませんでした。

Problem H

  • 11の倍数って、3の倍数みたいに簡単な判定法なかったっけ？と考えててしばらく嵌った。
  • もしかしてDP？と思って考えてみた。あっという間に思い浮かんだ。
  • 一瞬で書けた。バグったけどすぐ直った。一発Yes。

Problem F

  • @romanchuによると二分探索 + シミュレーションだそうなので、そのまま書いてもらった。通った。

Problem D

  • これも@romanchuがさっくり通した。解法説明してくれたけどあんまり頭に入ってない。

Problem E

  • 自機は整数座標じゃないとダメだと勘違いして一回WA食らった。
    • 斜め読みしたせいでnoの掛かる単語をまちがえたんですごめんなさい
  • 最終的に、「領域をレーザーの右端左端の直線でざくざく分割して、得られた小領域のうちレーザーから十分遠いものがあればOK」というアルゴリズムになりました。
    • 国内模擬予選F: 海岸線の侵食を思い出した結果です。
  • WAを食らってはバグを見つけ、を数回繰り返しましたが解けずにタイムアップ。6問でした。
  • どんなケースで落ちてたんだろう・・・。

Problem G

  • E解いたらやるつもりだったので、結局手をつけられなかった問題。終了直後に問題の意図を理解しました。
    • 脳内ではなぜか円はねこもねずみも囲わないことになっていたので、「どうやったって0やないですか・・・？」と思ってました。
  • コンテスト後はすぐに成田へ発つことになっていたので、電車内でちょっと考えてみました。
  • まず、両方囲む円も両方囲まない円も要らない。
  • 同時に置けないような円ペアを全列挙してグラフに落としてみるか。
    • えーと・・・最大安定集合とか言うんだったっけ？
    • ライブラリ持ってない。つかNP完全じゃなかったっけ?　(*追記: どう見てもNP困難です)
    • N = 1000。無理ゲー。問題の性質をうまく使わないと。
  • つまり、このツリーのようなものが作れれば幸せになれるわけだ。
  • 円Aが円Bを包含するならばAからBに有向辺を張ったグラフを作って最長経路長を出せばよさそう。
    • O(N^2)のDPで解けるはずなので計算量的にも丁度良い。
    • 1000ぐらいだったら手抜きしてWarshall-Floydにしても間に合うかもしれない。
    • 素直にこっちを先に解くべきだった。これで正しいか分からないけど。
  • 早く講評見たいなぁ・・・。

スタッフの皆さん、お疲れ様でした。ありがとうございました。