チーム構成とか
去年はサークルに入った時には時すでに遅しでICPCには出られず今年はどうしようかなと思っていたところ, たまたま1枠空いていたチームに誘っていただき加入.
チーム名はsuzukaze_Aobayama いかにもぞいぞいできる名前でお気に入り.
メンバー
- mugenさん : データ構造・ライブラリめっちゃ持ってる. 幾何強い. 過去問を大量に解いていて引き出しが多い.
- sotanishy君 : データ構造・ライブラリめっちゃ持ってる. 実装強い. 解ける問題の幅が広い.
- 自分 :数学とか一発発想系担当?
最近自分がatcoder黄色になれたのでatcoder換算で黄色*3という構成になった.
過去の戦績とか
なけなしの記憶力を頼りに書いたので嘘や虚言が含まれてそう.
ACPC(day1&day2)
day1 6完/9問 20位
day2 8完/11問 25位
感想: day2のG問題で自分が考察担当して実装大変だなとなった時にmugenさんがライブラリを投げてくれてすぐに通った. チーム戦ってスゲーとなった.
PGbattle
せんべい担当. チーム内での相談等が一切禁じられているこのコンテスト, チーム戦と呼ぶかは不明.
模擬国内
まずmugenさんがA, 自分がB, sota君がC にそれぞれアタックして解けた人から順にD以降を見ていくという戦術をとった.
Bを通したときには既にmugenさんがDの解法を生やしていた. 聞いたところ証明はすぐに出来なかったが反例も特になく直感的に正しそうでそのままmugenさんが実装, 自分はEをみる.
ここまでは良かった.
その後Eでこれ貪欲的な感じでできるのでは?との声が自分の中で湧きあがりここから嘘解法製造マシーンになる. 嘘解法を思いつく→コードを書いてみる/書いてもらう→落ちるケース発見→嘘でしたを繰り返す. 結局mugenさんが正しい解法に気づきAC.
発想, 発見寄りの問題だったので自分が解くべき問題だったし何より嘘解法をチームメイトに投げまくるのはよろしくないなと反省.
その間にF問題に取り組んでいたsota君も苦戦していたようで結果は学内4位の全体43位(オープン参加含めると47位).
例年だと学内2位まではまあ通過できるだろうといった感じなので厳しい結果. 精進を誓う.
KUPC
いつもの通り前の方を分担して解けた人から後ろに進んでいく形式. B問題の構築が割とすぐ解けて気分が良くなる.
Eを見るとしたいことは見えるが実装法がまるで分からない. Cを解き終わったmugenさんやsota君に救援要請を出したところ色々やったら解ける旨を教えてもらえる. 正直そこで聞いて理解した内容を実装できる自信がなかったので実装をsota君に委ねて自分はFを読む. 何かそれっぽいDPを思いつくものの細部が未証明. 模擬国内の嘘解法製造マシーンが頭をよぎる. 結局お気持ち程度の正当化の後えいやっと提出してAC.
どうやらEは謎のWAが出続けているようでsota君のコードを読むもののおかしな点が見つからなかったのでゴリッゴリに数学のHをみる.
トリボナッチ数列の一般項のような見た目をしているのでindexを3つずらしたものを考えれば良さそうと思うものの既にかなり使った頭でこれを考えるのはしんどかった. 糖分補給したかったが家に何もなかったので砂糖をタッパーから直食いした.
自分がHの指数と格闘している間にE問題をmugenさんがsota君のとほぼ同じ実装をしたらACしたらしくはてな？をしていたりsota君がIを〇〇〇(アルファベット三文字だった気がするけど知らない単語だったので覚えていない)やるだけって言って通したりしていた.
最後はみんなでMを考えていたところで時間切れ. 8完2200点の24位.
(余談)その日のAGCはKUPCで疲れてるし冷えてもしかたないもんねーの精神で出たら案の定の冷え. おまけにチームメイトはしっかり温まっていて言い訳をしてごめんなさいになった.
国内予選2007バチャ(全6問)
いつもの戦法. 自分がBを解き終わった頃にはDがほぼ終わっていたので後半2問をみる. どっちもヤバい見た目しかしていない. 本番中後半にこんなの出てきたら泣くだろ. Eの幾何をmugenさん, Fの構文解析を自分とsota君で考える. sota君の方が方針をたったようなので自分はEに移る. これすれば解けるやろってのは思いついたのでmugenさんから幾何ライブラリをもらって実装を試みるもsampleすら合わず. mugenさんとやっぱ辛ぇわっと言いあっているとsota君からF問題ACとの報告が入る.
結局E問題は解けず5完. 2007のボーダーとかは知らないがかなり良いのではとなる.
ちなみにE問題, 最初に思いついた方針で大まかにはあっていたようで1000000007個の誤差評価と998244353個のヤバい時の処理を追加したら通った. テストケース覗いてグラフソフトに描いてみてコードの変数を逐一全て出力して確かめてキレて書き直してというのを3時間半繰り返した. 1000点問題AC!!
国内予選本番とか
前日
学祭の手伝いとかバンドリとかをするなどした. 以上.
朝~昼
起きる. フルグラ食う. 大学行く. 学祭やってるのを尻目に一人青葉山登山. 時間があったので350点くらいの問題を適当に開いたら数学問だったので気持ちよく解いた.
本番開始少し前
mugenさんがラムネを, sota君がRedBullを, 自分がミニドーナツを持ち寄っていたため机上が賑わう. とりあえずRedBullをみんなでキメる.
自分が緊張していたのかどうかはよく分からなかったが落ち着かなかったのでウォーミングアップとしてAOJ-ICPCの150点数学問を解こうとして解けなかった. え?
本番
いつもの戦法. Bは何か良いのが思いつかなかったので脳死でUnion-Findした. 入力の情報の一部を全く使わないことに不安を思いつつも合ってると確信して提出, AC.
D問題をmugenさんが見ていてCのsota君も解けそうらしいのでEをみる.
Dが貪欲だとサンプルで落ちるらしいので2人で考察開始. 何か突然風船を3つのグループに分けたら上手くいく気がして実際に上手くいったのでそのことを伝えてそのまま自分が実装に取り掛かる. 制約的に適当でええやろと言って適当な実装をしたら思ったより実行に時間がかかったので流石に少しコードを改善. AC.
Eはmugenさんが解けてそうだったのでFを読む. 手元でガチャガチャしてみるものの分からず.
そうこうしているうちにsota君からCを通した報告が入ったのでFを一緒に考える. しばらくしてmugenさんからEも通った報告が入る. この時点で5位かつF以降を1チームも通していない状態. これはかなり良い状況なのではという空気が漂う.
F問題は残余グラフ考えて強連結成分分解してという大まかな方針をsota君が思いついたので皆でそれを軸に考察. 自分はグラフの知識がそこまでないうえに既に脳が緩み切っていたため, Fの話を聞きながらヤバそうなケースを探ったりG問題を考えて2900の計算が間に合えばGを通せるとかいう適当な事を言ったりしていた.
終了数分前にFで詰めていた考察がそのままだと厳しいことが発覚したためここで早めの感想戦に移行し予選終了.
結果
全体6位 学内1位!!!!!!
30位~40位に滑り込んでで学内2位で予選突破位が予選開始前の目論見だったのでチーム一同喜びを通り越して放心気味.
感想
楽しかったに尽きる. マジで楽しかった.
戦いを分析するとするとsuzukaze_Aobayama用に問題が作られているのかと思うレベルで問題セットとチームとの相性が良かった. 良い感じに3人が分業できたしそれぞれが高いパフォーマンスを発揮できたと思う.
sota君はあの厳ついC問題を一人でいけると宣言して実際きっちり通したしmugenさんもEを既出っぽいわと言いながら重めの実装をこなしていたし自分もBとDみたいな気づけば割と簡単だよね枠の早解きに成功したしで全てがかみ合っていた.
ラーメン
予選後チームメイトと食べに行った. めちゃくちゃ美味かった.
順位表配信視聴
友人から競プロ系Vの蟹江もなみさんの配信でsuzukaze_Aobayamaが言及されていることを聞いた. 帰宅後アーカイブで視聴をした. 自分のチームが言及されていてしかも黄色3人のチームの躍進により舌を巻かせることができていたようでとても嬉しかった. 正直ニヤけが止まらんかった.
今後
自分の強みを伸ばすのと弱点の改善のどっちもしないとな......とりあえず重実装から逃げないようにします. アジアまではそれなりに時間があるのでデータ構造辺りも最低限何ができるのか程度は学んでいきたいなと思っております. AOJ-ICPCも全然埋めきってないしね.
最後に
チームメイトのお二方には感謝の気持ちでいっぱいです. このチームでまた戦うことができるというのが本当に嬉しいです。アジア大会もがんばるぞい！！
