ほんとは昨日の夜書くつもりだったのだけど、なんか眠かったのでズレました。
基本的に推敲せず書きっぱなしです。ほとんど自分用メモ。
今年の参加記に興味がある人はそこまでジャンプしてください。
クラスの友人に誘われて実践的プログラミングの講義を取ったのが ICPC との出会いでした。
誘ってきた友人は5月頃にあっさり授業を切ってしまい、当然ほかに知り合いもいないぼく1人で寂しくプログラムを書いていました。
この講義では最終的に履修者でチームを作って ICPC に出るのですが、このような状態ですので金子先生の「はい3人組つくってー」攻撃で困っていたところに atetubou が救いの手を差し伸べてもらったのが彼との出会いでした。
ぼくと atetubou ともう1人の女の子（彼女は予選当日に用事があって結局2人で戦うことになった）のチームで初めての ICPC に挑むことになったわけです。
とはいっても全員がこの講義で競技に入門した初心者。当時のぼくはソートが必要なときにバブルソートを再発明して頑張っていたようなレベルで、当然勝てるわけはありませんでした。
コンテスト自体は、当時の実力を考慮すれば奇跡的なのですがぼくがCのDPを思いついて3完し39位でした。
結果はこちら: http://icpc2010.honiden.nii.ac.jp/domestic-contest/result
atetubou にさそわれこの年も ICPC に出ることにしたのですが、もう1人をどうするかという問題がありました。どうしようかと困っていたところにちょうど ICPC に興味を示した当時知り合ったばかりの学科の同期 y3eadgbe がチームに参加したいということでめでたく atetubou, y3eadgbe, amylase というチームでICPCに出ることと相成りました。
このチームでは結局3回ICPCに出て、そのうち1回は幸運にも国内予選を突破できたのでICPCのことを考えるときはまず真っ先にこのチームのことが思い起こされます。
この年は特にICPCに向けて何かをした覚えはありませんが、ちょうどこの時期に本郷へ進学して地下生活を始めると同時に simezi_tan に布教されてTopCoder SRMに継続的に参加するようになりました。
その甲斐あってか、この年は4完だったように思います。公式サイトが死んでいて standings が確認できないですが。
この年に atetubou も理学部情報科学科に進学し、完全地下チームとなりました。
この年は ~shiokawa, wakaba の面々と毎週3回地下に集合し、AOJ Virtual Arena で開かれている会津大の練習会に参加しました。今思えばこの時に競技力が高まった気がします。
ぼくは基本的に演習量が足りていなかったので、練習会でいろんな問題に触れるうちに問題のパターンを覚え、解ける問題がどんどん増えていく時期でした。競技に限らず物事を学ぶ上で一番楽しい段階ですね。
その中でも一番重点的に力を注いだ分野が幾何です。練習会で毎回幾何が出るたびにぼろぼろと取りこぼし、これはちょっとまずいのではないかと思い、ライブラリづくりを兼ねて幾何の勉強をしました。
いろんな人が言っていると思いますが、幾何の勉強法はライブラリ整備を兼ねて簡単な問題から順に解いていくのが一番効果的だと思います。こんどそのための幾何問題集とか作れたらいいなあ。
練習会で atetubou が実装力で頭ひとつ抜けていることもわかったので、ぼくとy3が一生懸命アルゴリズムを考えてatetubouに実装してもらうのを基本戦略に据えました（幾何がでたらぼくが書きます）。並列せず前列と後列にわかれるスタイルですね。
この年の国内予選はこれらの対策がバッチリあたり、なんと全体3位という予想外の好成績で国内予選を突破します。 http://www.cs.titech.ac.jp/icpc2012/domestic-contest-result.html
C, D のややこしい実装は実装担当として鍛錬を積んだatetubouの敵ではなく、Eに解ける幾何が来たことで5完を達成しました。
この年も国内予選突破を目指し日夜練習……にはあまり励みませんでした。ぼくが国立情報学研究所にある研究室に配属されたのもあって、本郷の地下から疎遠になってしまったからです。
結果、この年は7位（学内5位）で国内予選落ちです。 http://sparth.u-aizu.ac.jp/icpc2013/d_result.php
今見返せば、この年が東大1強の最たる年だったような気がしてきますね。
去年の練習不足により、atetubouから三行半をつきつけられたぼくとy3。
そこにちょうどチームメイトが2人とも引退してフリーになっていた not さんを引き込み、国内予選突破を目指すことにしました。
成功した2012年の方針を踏襲し、会津練習会に毎週参加してチームとしての動きを確認しながら練習を重ねました。
模擬予選では5位（学内4位）に食い込み、「いけるか……？」という雰囲気で本番を迎えます。
動きとしては A, B, C を個人がそれぞれとき、Dをy3が解いている間にEまで方針を詰めてぼく & not で最後の方に出てそうな幾何の問題を詰めに行くというのを予定していました。
競技開始と共にy3が問題を読みさくっと実装。サンプルが合わないトラブルがありBのnotさんと交代するも問題の誤読とわかり修正して提出、AC。
ぼくがCを詰めている間にAC。
ぼくがCに取り組んでいる間に not さんが「これは一瞬なので」ということを見ぬいたので、PCを交代。
ちょっと実行に時間がかかったものの予定通りさくっと提出。
→WA
すぐにコードを印刷してCに交代。
これまたすぐにバグを発見して修正し、Dを走らせ直しながらCに復帰。
→AC
見た瞬間に二分探索を検討しましたが、そのあとの入ってるかどうか判定する部分で自信がなくなり not さんに相談すると「外側の端の点だけ見ればよくてそれで時間が一意になるからにぶたんいらないです」という旨のコメントをいただく。
にぶたんのまま書いてたら結構実装などが面倒だったと思われるのでちゃんと相談してよかった。
→AC
D を書いている間（Cを書く前）にy3と相談。
葉につながる辺は通らなくてよいことに気づき残った木の上でいかに通る回数をケチるか考えていくと、どうも直径部分だけは1回であとは2回とおればいいのではないかという結論に至りました。証明はしていないのですが、sampleも会うし結構あってそうなのでこれで行くことに。
→WA
コードを見ると木の直径を見るときに辺のコストを考慮しないようになっていたのでそれを指摘し再提出。
→WA
実はさっきの嘘解法なのでは……とかと不安になっていたがバグを発見し再提出。
→AC
この段階で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ではじめに検討していたらしい方針でちゃんと解けるっぽいことが判明し絶望。基本的には円の内側で分断されないので中心を結んだ線分でグラフ双対やる感じだったらしいとのこと。
おそらく文章に主題がないからだと思いますが、なんかあとで読み返すと本当にまとまりがない文章でした。まあ2011年あたりの力をつけていく部分などは少しは参考になるのではないかなあと思います。
海外の地区大会に出るかどうかは未定です。もし行くことになったら一緒に行く方はよろしくお願いします、行かないことになったらJAGの皆さんよろしくお願いします。
結果についていろいろ思うところはありますがひとまずお疲れ様でした。チーム戦楽しかったです。
どちらにせよ、あのセットだとやっぱり6問通したかったですね……。
今まで4回チームを組んでくれてありがとう、ぼくも多くのものを得られて楽しかったです。