読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ICPC2016 国内予選参加記

ICPC

3度目のICPC国内予選に参加してきました.
問題文はこちらhttp://icpcsec.storage.googleapis.com/icpc2016-domestic/problems/all_ja.htmlです.

チームの詳細は
http://icpc.logic.cs.tsukuba.ac.jp/team/279567に色々書いてあります.
チーム名は「lovablepleiad」なんですが,正しい読み方は誰も知りません.身内のTwitterIDを(勝手に)チーム名にしました.

結果から報告しますと,5完16位(大学内1位)でした.
名大のチームに勝つことを目標にしていたので,目標が達成できてよかったです.

以下参加記っぽいなにか

リハーサル(12:00)

リハーサルをする.特に何もなし

コンテスト前

4時間くらい暇でそわそわする.
先輩に手伝ってもらってピザ屋に電話を掛けたりして打ち上げの準備をする.
余った時間はスプラトゥーンをして士気を高めていた.

コンテスト開始前後

チームメイトがそろったのが5分前とかだったのでめっちゃ焦ってた.
演習室の1台しかないプリンタを最初にとれなくて少し出遅れた.
印刷時間中テンプレートを爆速で書いてもらった(本当に速い

A問題 AC(btk

ソートしてNlogNでやるか愚直にN^2でやるかで何故か凄く悩んだ.
チームメイトにはWAしなければOKと言われていたのでいつも通り8分ぐらいかけてACした(激遅

B問題 AC (takamoto)

完全に任せてほかの問題を読んでいたのでこの問題についての情報は一切知りません.
個々が問題なく一人でACしているという状態なので全問題この状態になるのがベストだと思います.

この間にC,Dを二人で読んでいたのですが,C問題はmathの香りがしたのでtakamotoさんに投げることにしました.
D問題を読むとそこには親の顔より見た光景(区間DP)が広がっていた.
...のはずだったんですが,B問題AC後Dを実装するもバグらせサンプルが合わない.
四苦八苦してるうちにtakamotoプロがCの解法を思いついたので交代する.

C問題 AC (takamoto)

本当にこの人プロ

D問題 WA (btk)

完全に戦犯

D問題 AC (btk)

本当にすみませんでした

この時点で23位ぐらい(残り1.5h)だったので,とりあえず国内は抜けれそうなので安心する.
E問題が厳しすぎる制約のせいで立方体を頂点,接触関係を辺とするグラフと考えたとき
単純経路or単純閉路にしかならないことに気づいたので,重そうだけどtakamotoさんにお願いする.

Eを実装している間,残りの3問の考察を2人で進める

  • F : yukicoderのカゴメカゴメにめっちゃ似てる.根付き木の同形判定ができればいいことに気づいたけどそんなライブラリは持ってないので死
  • G : 不可能
  • H : プレゼントの渡し方は無向辺のフローに帰着できることに気づき,最小流量制約付きの最大流が解ければいいことに気づく.しかし蟻本に載っていることを知らなかったので最小費用流に帰着して解こうとする.無向辺の場合が分からず死
E問題 WA (takamoto)

この時点で残り30分だったのでEを3人でデバッグするかHに行くかの分岐点に立たされる.

E問題 AC (takamoto)

takamotoさんはプロ

この時点でtebamoto(名大のチーム)に完数で勝ってたのでめっちゃ喜ぶ
takamotoとtebamotoがめっちゃ似てて凄く紛らわしい

コンテスト終了直前

残り時間でよんさまに蟻本の最小費用流を写経してもらったんですが3分ぐらいでコードができててマジでびびった.

コンテスト終了

感想

takamotoさんがラストICPCなので国内予選が突破できて本当によかったです.
欲を言えば順位がもう一つ上ならレコチョクの景品が貰えたので少し残念でした.