立命合宿2013 1日目

オンサイト参加記

立命館大学競技プログラミング合宿に参加しています。

現地集合Phase

何もかもが上手くいけば11:30ごろには到着するような予定を組んでいきましたが、残念ながら乗り換えで間違えたり（湖西線と琵琶湖線）、電車が遅れたりして、結局30分ほど遅れて到着しました。（とはいえ、集合時間には余裕で間に合いました）

昼食Phase

立命大の方に案内してもらい、大工大の方々と一緒に食堂に連れて行ってもらいました。

チーム決めPhase

ミーティングPhase

  • エディタはCotEditor
  • 言語はC++
  • REPやFOR_EACHといったけしからんマクロは使わない（もし使うのであれば、人によってマクロの割り当てがかなり異なるので、紙デバッグのことも考えてなるべく統一するように努力したほうがいいと思います。）
  • 「問題を読み終わった」「解き方が分かった」「解けた」の表を作る
  • 最初は@mizo0203さんがA、@refiuteがB、@shora_kujira16（私）がCを読む ということだけ決めました。

また、@refiuteが@kyuridenamidaのライブラリを拝借してきたようです。

コンテストPhase

問題はこちら

  • C問題を読む。確率DPか…まともに解けたこと無いんですよね
  • っていうかこれ状態数多すぎませんか
  • 10分経過したところで途中経過を報告することに。A問題がうまくいかないということだったので、私がドヤ顔で交代しましたが、全く解ける気配がありません
  • 複数回適用？任意の本数のビデオ？？？
  • りひゅーとがBを解けるということだったので、交代。3Dのライフゲームらしい。
  • その間、他の問題を読んでみる。D問題の用紙には「パズドラ」と書かれたメモが残されていた。パズドラはチュートリアルだけやって「ふーん」という感じでそれ以来触っていなかったのですが、そのときに「これは探索大変そうだな〜ｗ」と当時は感じていたので、とりあえず後回しにすることにしました
  • 続いて、E問題の用紙には「k番目の最短路/巡回セールスマン？」という文字が残されていました。SuperCon2011の予選の問題がk-shortest-passだったので経験はあったし当時のソースがGithubに上がっているのですが、とりあえず保留
  • F問題を見る。りひゅーとにボロノイ図というものを教えてもらう。ボロノイ図を作って、落下地点の誤差範囲の四角形との共通部分の面積を取り出したらあとは書けますねということでアルゴリズムは分かりましたが、coding-hardだということで後回し
  • G問題を見る。明らかにデータ構造の問題であることは分かりましたが、segtree的なものを考えて結局そこからあまり進展しませんでした。
  • りひゅーとのB問題がバグるということだったので見てみると、新たに生物が誕生したセルが、誕生したターンと同じターンに死ぬという、ライフゲームでよくあるバグがあったので、ifをelse ifに変更してから提出すると、Presentation Errorで痛い1WAを食らってしまいました。
  • この後はA問題を全力で解こうとしていましたが、なかなかうまく行かなかったので、私が幾何ライブラリを写すことに
  • @mizo0203と@refiuteがAで奮闘するも、残念ながら解くことができませんでした

解説Phase

  • Aは貪欲で、種明かしをされてしまえば「なんだそれだけか」と思ってしまうような解法だったのですが、解けなかったのはたぶん「制約条件に惑わされていたから」なのかなと思います
  • Dは解いた人曰く「ゴリゴリ実装するだけ」だそうなので、あとで復習しないといけませんね
  • Eは最短路をk番目まで持つように拡張したダイクストラ法を適用するだけで良かったらしく、まさしく私が過去に解いたものだったので、経験が生かせず残念でした
  • Gのジャッジ解はRMQを使ったものとのことですが、BITを使って解いた人や ext/rope の __gnu_cxx::rope を使って解いたという人もいました

感想

  • 過去に似た問題を解いたことがあるものもあったので、「これはたぶん解けないなぁ」と思ってもとりあえず手を動かしてみるべきでした
  • Aは解法自体は難しくないようだったので、条件を整理してみると良かったかもしれません（超基本的なことですが）