JAG Practice Domestic Contest 2010

Contest

国内予選へ向けての課題が見えてきたといえなくもないのかな。

今年のチーム

  • 今年のチームは .Watch になりました。Watch.c, Watch.d ときて、今年は予想を裏切る設定ファイルです。
  • メンバーは @romanchu, @iakasT, そして私 (@matyaa)。
    • @romanchuと組んでかれこれ4年目になりますが、@iakasTと組むのは今年が初めて。
    • ICPCは5年目になりますが、実は毎年違うチーム編成だったりします。
      • そもそもうちの大学において、2年続けて同じチームが組まれた例は意外にもまだ無いようです。
    • ずっと同じ面子で出続けている d3sxp さんとか _ さんとか 40010 さんとかがちょっと羨ましくもあったりします。

開始前

  • 使用予定のプリンタがトナー切れを起こしていることが発覚。
    • コーチと @shioshiotaネ申 が研究室のプリンタからトナーを持ってきて差し替えてくれました。ありがとうございます。
  • @romanchuが A を、@iakasTが B をやっている間に私が C, D を検討し、それぞれ@romanchuと@iakasTに振って私は E, F, G に移る、という方針で行きましょうかと。

A: 連続する整数の和

  • を解いてもらっている間に C を読む。
    • 差の2乗を最小化 -> 最小二乗法 -> 微分 -> 絶望
      • いやいやまてまておちつけおちつけ
    • DPですよねそうですよね。うん。よし。
  • とりあえず D にも目を通そう。
    • 何もかもすっ飛ばして最後の文だけ読む。
      • 「集配業務が完了するまでの時間」
    • はいダイクストラ！決定！
  • @romanchu 「A 通りました」
    • え。ちょっと早すぎるんだけど。

B: ムーンライト牧場

  • を@iakasTにやってもらう。
  • C を@romanchuに投げようかと思ったけど、基本的にDPは私の担当なので、私がやることに。
    • @romanchuにはDをやってもらおう。
  • 紙の上に C のコードをがりがり書く。
  • 一方@iakasTがハマる。2WA.
    • 通った頃には C もただのタイピングゲームになってました。

C: 差分パルス符号変調

  • ひたすら打ち込み打ち込み。
    • サンプルの値、入力が短い割に出力大きいな。しかも N <= 20,000って。
      • オーバーフローしそうで怖い。long longにしよう。
    • inf を int で宣言しててちょっと悩んだけどすぐできた。
  • Accepted!
  • 結構早かったよねと思ってStandingsを見たら2位になってた。やった。

D: Mr. リトー郵便局

  • の裏で E をがんばる。

E: 不死の宝石

  • え、難しくないこれ？
    • 境界を全部調べる系なのはなんとなくわかるけど...。
      • 磁力円どうしの共通接線を全て試せばいいのかな？
        • それだと磁力円が重なる場合にうまくいかない。
        • そもそも2円の共通接線ってどうやって求めるの？
  • 別の方向から考えてみよう。
    • 直線の傾きを決めれば、そのときの最適解は比較的簡単に求まる。
      • どうすれば考えるべき傾きを全列挙できる？
      • ...
      • 共通接線の傾きだけ調べれば。
        • それが分かったら苦労しないよ...。
      • えぇい、少しずつ動かしながら -pi から pi まで試してみるか？
      • 座標値は +-1,000. 1,000,000通り試すとして...
        • 2,000 * sin(pi/1,000,000) = 0.006 ぐらい。
          • なんかいろいろ間違ってるけど桁数はこんなもんでしょう。
      • いける...かな？
        • 確信は持てないけど、他に出来ることが無い。書くだけ書くか？
      • って、あれ。傾き決めたときの最適解求めるのって O(N2) だよね。
        • 1,000 通りぐらいしか試せないぞ。やっぱ無理だ。
  • そういえば、Dはどうなった？

D: Mr. リトー郵便局

  • cost[現在地][船の位置][どこまで届けたか] を求めるダイクストラがなかなか終わらないらしい。
    • 状態数 4,000,000 ぐらいか。もうちょっと減らせないかな。
    • ...
    • 現在地っていらなくね？
      • 届けた直後の状態だけを考えても特に問題なさそう。
      • あとは (現在地, 船の位置) の全状態間の最短距離を求めておけばよい。
        • 移動はつまり
        • a -- (徒歩) -- b -- (船) -- c -- (徒歩) -- d
        • のような経路だけを考えればよくて、徒歩だけの全点間最短距離と船だけの全点間最短距離を求めれば簡単に計算できる。
    • という話を@romanchuがしてくれたのだけどすぐに理解できなくて、あとで同じことを自分で考えた。
      • そして (現在地, 船の位置) の2乗がでかすぎるんですよ、と@romanchuに突っ込まれた。
      • ぐぬぬ。
      • ...あれ？
      • 嘘だよ！
      • 徒歩だけの全点間最短距離と船だけの全点間最短距離があれば (現在地, 船の位置) の2状態間の距離は定数時間で計算できるんだから、陽に持っておく必要がない！
    • ペアプロ開始。しばらく頑張ったらsample出てきた。
    • ジャッジデータもしばらく待ったら出てきた。送信！
    • WA...

E: 不死の宝石

  • @iakasT「傾き決めたときの最適解って、直線からの距離でソートしてスキャンすれば O(N) でできますよね」
    • 素晴らしい。ちょっくら実装してみますか。
    • sample出てきた。けどWA...
  • この辺の時系列順は記憶があやふやですがご容赦ください。

D: Mr. リトー郵便局

  • @romanchuがうまくいきそうにないケースを発見した。
    • 確かにうまくいかない。どういうふうに直せばいいんだろ？
    • ...
    • なるほど、常に船に乗る (少なくとも、船のところまでいく) ことになってるからマズいんだ。
      • 船スルーするルートを追加した。
    • WAった提出データと違う値になってることを確認。
    • さらに遅くて途中までしか終わらなかった3次元の状態のものと同じ値になってることも確認。
  • submit. Accepted!

E: 不死の宝石

  • @romanchuは F を頑張るということで。
  • とりあえず 100,000 分割を 300,000 分割に増やして答えが変わるかどうかをチェック。
    • 変わらないなぁ。
  • やっぱり共通接線で真面目に計算するしかないのかな。
  • ...!
  • 磁力円だけじゃなくて宝石円も考えるようにすれば、磁力円が重なってても大丈夫だ！
    • で、共通接線はどう求めるの...？
  • ...
  • えーと。
  • 一般的に嘘に嘘を重ねるのは泥沼コースなのですが、嘘解法に嘘解法を重ねるとどうなるのでしょう。
    • 傾き決めてイベント列挙する。傾きを少し変えたとき、その前後でイベントの列が異なっているようだとアヤシイ。
      • つまり、一度に大きく傾きを変えすぎてしまったかもしれない。
    • 傾きの区間 [a, b] における最適解を求めるには、a のイベント列と b のイベント列を求める。
      • それらが同じであれば、それ以上細かくする必要がないので、適当にひとつ傾きを決めてそのときの最適解を返す。
      • 違うのであれば、[a, (a+b)/2] の最適解と [(a+b)/2, b] の最適解を求めて大きい方を返す。
  • いけるんじゃね？どう思いますか@iakasT君？
    • @iakasT「それをあと1分で実装するんですか？」
    • あれ？17:30で終了？マジで？
      • あぁそうか。国内予選だから3時間か...。

Result

  • 4AC, 9th.
    • 是非とも夏合宿には行きたいので、1桁順位をキープできたのは一安心だけど。
  • 序盤が計画どおりにいかなかったのがちょっと怖い。
    • C を誰かに押し付けて、Dをもっと深く考えるべきだったのかな。
    • @romanchuは基本的に爆速で A を通すので、心の準備が出来ないまま B とか C にバトンが回ることが多い。
      • そしてハマる。
    • キーボードが空いたとしても、すぐに打ち始めない勇気が大切なのだろう。
      • 実際、B でハマってたおかげで C は十分に準備する時間が出来て、書き始めが遅れたにも関わらずかなり早く通ったわけだし。

ところで

  • Dをやってて思ったのだけど。
  • 物事を考えるとき、@romanchuは実例ベースで考える一方、私は抽象的に考える傾向にあるようです。
    • WAった！
      • @romanchu「撃墜されるようなケースを作ってみよう！」
      • @matyaa「アルゴリズムの正当性の証明のギャップを探そう！」
    • みたいな感じで。
  • もちろんこれはどちらが優れているといった類のものでなく、互いに補い合うものです。
    • @romanchu「こんなケースも出てきます？」@matyaa「それは徒歩 - 船 - 徒歩のルートでカバーされるので大丈夫です」
    • @matyaa「この解法で大丈夫だと思うんだけど証明できない」@romanchu「この入力で撃墜できますよ」
  • そう考えると、手前味噌ながらいいコンビだなぁと思ったり。
  • OB/OG会の皆様、楽しいコンテストをありがとうございました。お疲れさまでした。