ICPC 2017 模擬国内予選

去年と同じくチームnocowとして今年も参加します．(5回目のICPC)
osrehun.hatenadiary.jp

チームメンバー
@osrehun
@icchyr
@xthexworldx

結果は5完10位(guestを除くと8位)でした．去年より順位が5つ上がった．
今年の模擬国内予選は少しひやっとした．(理由は後述)

以下詳細なタイムスケジュールと感想

使用した競技環境は次のとおりです　
Ubuntu 14.04
GCC 4.8.4

(-1:00)
コンテストサイトにアクセスするも何も起こらない。(コンテストサイトにアクセスできなくなるフェーズが無かったので、案の定という感じが...)
チームメイトが、「これはトラコンだ」と言い出す。

0:00
コンテスト開始　(借りた部屋にプリンターがないので、問題は各自のPCで見ることにした)
icchyrが環境構築を行いながら，自分がA問題を読む．xthexworldxにはB問題を任せる．

0:03
icchyrがスクリプトを書き終えたところで，A問題のコードが頭に浮かんだのでicchyrにコードを伝える．

0:10
特にバグもないので，そのまま提出する． A AC
この段階でB問題の方針が浮かんだと聞いたので，コーダーをxthexworldxにバトンタッチ

2人で残り6問の問題文を読み進めていく．

自分がC問題を読む．
面倒だなと思うけど、最小の得点と最大の得点の計算は簡単
あとは、最大の得点にする人top-2と最小の得点にする人worst-2を求めて、組み合わせて終わりだなという方針が立つ

icchyがD問題の概要を伝えてくれる．
二分探索+尺取り法で解けそうな雰囲気があると伝えておく。

E問題
幾何で解けそうな見た目しているけど、後回しにすべきだよねということで後回し

F問題
マトリョーシカの入れ子関係から早速フローの気配を感じ取る。

G問題
適当に読んだけど、はてなが浮かんだので飛ばす

H問題
TDPCのS問題と似ているし、実装は割と重そうなので、後回し

0:25?
B問題をバグらせて辛いとヘルプが飛んでくる。
題意を読み取るのが本当に辛そうだし、累積和やるだけだったのでバトンタッチする。
問題の読み間違えもあったけど、罠を意識してちゃんと考える。
サンプルが通る。

0:36
B AC
そのまま、C問題のコーディングに移る。チームメイトにD問題を任せる。
ただ、紙で印刷された問題文がないのは厳しいなぁと思いながらコーディングする。
特にバグらせることなく実装を終える。

0:55
C AC
ただ、この時点で後輩チームにタイムペナルティで1800差があったのでちょっと遅いなぁと思う。

D問題のコーディングを始める間に、自分はF問題に取り掛かる。
ちゃんと、考えると最大流じゃなくて、最小費用流を流せば良さそう。
サンプルを手計算する合っていそう。

1:30
チームメイトがD問題をコーディングを終えて、提出 WA
ここで、チームメイトにデバッグ作業をしてもらう。(slackにソースコードを送る)
F問題のコーディングを始める。
ライブラリを写経していくうちに、流量が無限の場合はどうするんだっけと考える。
冷静に考えて、流せなくなったら終わりだし、最大でN-1回しか流れないから良いかとする。
サンプルは通る

1:50
F AC

この時点で4ACして11位くらいだった気がする?
D問題について話し合っていく．

二分探索の答えが合わないから、つじつま合わせしているような部分をみて、怪しいのでは？と話す
それを元に色々修正する。この間に2 WA

unclear M回以上 | M回未満
という判定関数で、やっていて少し怪しいかなと思った。
問題文を真面目に読むと、lb = s_1 に設定すれば必ずクリアできるじゃん!

そして、D1.inに対するプログラムの出力をみる。
「-1が多いし、やっぱり間違えているんじゃない？」
「でも、その出力ファイルをちゃんとジャッジに投げた？」
「ないね...」

提出してみる。

2:53
D AC
「任意のテストケースを作れるし、仕方ないよね...」
ここから、G問題の考察をする。

i -> a[i] に辺を貼ったグラフを考える。
グラフの連結成分ごとに考える。
各連結成分は長さ2のループを持たないといけない．

実装するけど、時間が足りない．
ここで，タイムアップ

3:30

感想
去年より順位が良かったので、嬉しい．
ただし、環境に対する慣れがないので、本番までに環境になれます...
ライブラリをちゃんと印刷します．

次の日
G問題の誤読をしていたことに気づいて、冷静に数式を立てたら通った．
実装は少し重いし通せるか怪しいなという気分になった。