pepsin-amylaseの日記

2014年 修士2年 diff out out のたたかい

01:03

去年の練習不足により、atetubouから三行半をつきつけられたぼくとy3。

そこにちょうどチームメイトが2人とも引退してフリーになっていた not さんを引き込み、国内予選突破を目指すことにしました。

成功した2012年の方針を踏襲し、会津練習会に毎週参加してチームとしての動きを確認しながら練習を重ねました。

模擬予選では5位（学内4位）に食い込み、「いけるか……？」という雰囲気で本番を迎えます。

動きとしては A, B, C を個人がそれぞれとき、Dをy3が解いている間にEまで方針を詰めてぼく & not で最後の方に出てそうな幾何の問題を詰めに行くというのを予定していました。

A

競技開始と共にy3が問題を読みさくっと実装。サンプルが合わないトラブルがありBのnotさんと交代するも問題の誤読とわかり修正して提出、AC。

B

ぼくがCを詰めている間にAC。

D

ぼくがCに取り組んでいる間に not さんが「これは一瞬なので」ということを見ぬいたので、PCを交代。

ちょっと実行に時間がかかったものの予定通りさくっと提出。

→WA

すぐにコードを印刷してCに交代。

これまたすぐにバグを発見して修正し、Dを走らせ直しながらCに復帰。

→AC

C

見た瞬間に二分探索を検討しましたが、そのあとの入ってるかどうか判定する部分で自信がなくなり not さんに相談すると「外側の端の点だけ見ればよくてそれで時間が一意になるからにぶたんいらないです」という旨のコメントをいただく。

にぶたんのまま書いてたら結構実装などが面倒だったと思われるのでちゃんと相談してよかった。

→AC

E

D を書いている間（Cを書く前）にy3と相談。

葉につながる辺は通らなくてよいことに気づき残った木の上でいかに通る回数をケチるか考えていくと、どうも直径部分だけは1回であとは2回とおればいいのではないかという結論に至りました。証明はしていないのですが、sampleも会うし結構あってそうなのでこれで行くことに。

→WA

コードを見ると木の直径を見るときに辺のコストを考慮しないようになっていたのでそれを指摘し再提出。

→WA

実はさっきの嘘解法なのでは……とかと不安になっていたがバグを発見し再提出。

→AC

F, G

この段階で3WAを背負ってしまい6問通さないことには苦しい展開。

Fは辞書順最小の定石で可能性判定をかければいいということになっていて、Gはやらないだけの幾何の匂い。

ここでさいころの各面を頂点とし、隣接する面同士に辺を貼ったグラフを考えれば、それぞれの頂点を訪れる回数がt_iになるパスがあればよいことに not さんが気がつく。

これは練習会の時に似た問題を見たことがあって、たしかフローで解けるはずとぼくが思い出し、この方針で行くことに。

F を書くも最後のサンプルが合わず。

y3がフローが流れている場合でも連結なパスが再現できるとは限らないことに気が付き修正。

終了10分前にサンプルが合い祈りながら走らせるも終了したのは競技終了10分後……。

終了

というわけで5完の16位でした。　http://icpc.iisf.or.jp/2014-waseda/domestic/results/

あとでGについて他のチームと話していて「3 つ以上の円が共通領域もしくは共通点をもつことはない．」と問題に書いてあるらしいことがわかり、not, y3ではじめに検討していたらしい方針でちゃんと解けるっぽいことが判明し絶望。基本的には円の内側で分断されないので中心を結んだ線分でグラフ双対やる感じだったらしいとのこと。