IOPC2014

今週末はeha君,natsugiri君と一緒にIOPCというコンテストに参加した.

このコンテストの特殊なところは,ICPC形式にもかかわらず時間が24時間もあるところ. さすがに徹夜で参加するのは無理だったけど,始まってからは睡眠と食事を除けばだいたいコンテストの問題を解いていた. 途中何回か1位になったりもしたけれど,UTPCと時間帯がかぶっていて最後の2時間に参加できなかったこともあったりして, 結果としては15問正解して3位という順位だった. 問題はここ, 順位表はここから見ることができる.

せっかくなのでコンテスト中にやったことを箇条書きにしてみる.

14:00

  • 大学の談話室に集まる.
  • 早く来すぎて誰もいない

15:30

  • 他の二人がやって来る
  • アメリカで買ったおみやげの謎エナジードリンクとかをわたす.
  • そうしているうちにコンテストが始まった.
  • 適当に真ん中辺りの問題を読み始める
  • 問題文長くて難しい
  • そのうちにnatsugiri君がAを書き始める

16:00

  • 他のチームがAでWA出まくりでやばそう
  • うちもWA出しながらもAがACされた
  • 一方自分は読んでる問題が全部わからない

17:00

  • eha君とO問題についていろいろ話す
  • 問題文読み違えとかありながらもなんとかAC
  • そのあとnatsugiri君がフィボナッチ数の問題を正解.First ACだった(たぶん).
  • R問題を書き始める.提出するもWAでよくわからないから放置する.

18:00

  • eha君が自分が放り投げてたR問題をACしてくれた.
  • かわりに探索っぽい問題を書き始める
  • 書けたけどWAでるし,原因がわからん.
  • なんか色々直したら原因わからないまま正解した.

19:00

  • ドミノピザ食べる
  • 美味しい

20:00

  • Cの幾何っぽい問題をeha君が解こうとしてる
  • 凸包してそのうえの頂点の個数を数えたらいいらしい.
  • 自分の凸包ライブラリを貼り付けてもらって堤出するもなぜかWA.
  • 他の人のライブラリを貼り付けるとACが出たようだ.
  • 自分のライブラリ間違っていたのか…….

21:00

  • 部分文字列の問題がわからんのでnatsugiri君に投げたらすぐに解法を見つけてくれた
  • 書いて堤出するもWA.原因がわからないまま色々直したらACした
  • 原因わからないままなのですっきりしない.

22:00

  • ボンバーマン問題の説明を聞く
  • 少し考えてみると最小辺被覆問題に帰着できるっぽい
  • 蟻本を読むと最小辺被覆は最大マッチングを求めることで解けるらしい.
  • 一般グラフの最大マッチングとか知らない.
  • スパソにあるらしいので貼り付けて出して見る
  • TLE…
  • V = 100でO(V^3)なのにTLEとかつらすぎ.
  • いろいろ直してみるけどだめっぽい
  • 解散して続きは家で.

23:00

  • natsugiri君がeuler tour + LCA + segment treeとかいうやばそうな問題を通した
  • このあたりで1位になったり抜かれたりしてた.

24:00

  • ボンバーマン問題,Edmond’s Blossam C++で検索して出てきたコードを貼り付けたら爆速で通った
  • O(V^4)なのに通るとは謎だ.
  • また1位にもどる.
  • グラフの期待値問題を読んで概要を説明する.
  • 連立方程式で解けそうとのコメントをもらって,たしかにそうだと思って書き始める.
  • ACした.

25:00

  • なんか二人がグラフのクエリ問題について話している.
  • トポロジカル順序がうんぬんかんぬんとか言ってる.
  • chefの息抜きにeulerやって,eulerの息抜きにchefをやるとか言ってる人がいる.
  • そろそろ眠いのでねる.
  • 今は1位だけど起きたら何位になってるやら.

7:00

  • 目が覚める
  • 順位表確認したら4位くらいまで落ちてた.

8:00

  • 昨日の夜話してた問題を読むと,確かにトポロジカル順序を求めたら解けそうなのでonline topological sortとかで検索して出てくる論文を読む.
  • 英語はわからないけど,シンプルな擬似コードが乗っていたので理解できた.
  • 計算量微妙っぽかったけど,実装したらAC.

9:00

  • セグメントツリーの遅延評価使えば解ける問題があるとか言ってるので書いてもらう
  • 大学に行く

10:00

  • バグってるっぽいので,解ける問題もないし一緒にデバッグする
  • 遅延評価がすこし失敗していたっぽい
  • AC

11:00

  • あんまり解ける問題がない
  • powertowerが望みありそう
  • そもそもx^(y^z)のmodの計算がわからないので教えてもらう
  • オイラーの定理使うらしい.へえ.

12:00

  • 色々話しているうちにnatsugiri君が解法分かったっぽくて書き始めている
  • おなか空いたのでご飯買いに行く
  • 帰ってきてご飯食べてるうちにACした
  • ついに1位にもどる
  • そろそろUTPCが始まるのでここでおしまい.

15:30

  • コンテスト終わり
More Reading
Newer// Sublime Text
Older// SRM 609