昨年組んでいただいたゆきのんさんが引退されたので、kenchoくんに入ってもらってsuisen, otera, kenchoの 3 人でチーム「Bu-Bu-Du-Ke」として ICPC 2022 Yokohama Regional に参加しました。昨年はアジア予選に進出することは叶わず、今年に関しても国内予選や模擬国内/地区予選ではずっと2桁順位だったのですが、アジア予選で 7 位という一番良い結果を残せました。特にsuisen, oteraは今年でICPC引退で、最後のチャンスで力を十分に発揮できてよかったです。株式会社オプトさんから7位の企業賞まで頂けて嬉しかったです。
チームの役割分担は
みたいな感じです。得意分野がばらけていてバランスはいいと思ってます
本番前々日
ライブラリが完成したので印刷をした。Y.Y.さん対策のDM分解が入っていたり、絶対に使わないであろう特性多項式のライブラリが入っていたりする。ライブラリ無制限の文言を見てライブラリを全部持ってくるくらいしようかと思ってたけど、写経用に短く書き直すのと書き直しで壊れてないかのテストを書くのが大変すぎて泣く泣く断念...
3時間だけ本番に近い状態でチーム練をしようという話になっていた。VS Codium に拡張機能が何も入っていないという噂を聞いて急遽 CLion をインストールして練習したが、よくわからないお節介機能 (慣れると便利なんだろうけど) でめちゃくちゃになっていた。
18時開始予定だったけどなんだかんだ開始が遅れたり感想戦をしたりしていたら終電になっていて危なかった。
生活習慣の調整が下手だったので眠気が来なくて、27時くらいにやっと寝れた気がする。
本番前日
チームメイトと中華街で合流して、昼食を摂って会場に向かった。朝が得意ではないので12時くらいに到着するように新幹線を取っていたけど、2人は早起きして横浜を満喫しててちょっと後悔。
会場に早く着いたので、チーム紹介ドキュメントを眺めていた。うちのドキュメントは実行可能なBrainf*ckのプログラムになっていてコピペして実行してもらおうという魂胆だったけど、よく考えると印刷物はコピペできないので...
↓にコピペ用のドキュメントを貼っておくので、良かったら https://copy.sh/brainfuck/ などで実行してみてください。
>>>>>>>>>++++++[-<+++++<+++++++++++++<+++++<+++++++++++++<+++++<++++++<++++ +++++++++<+++++<+++++wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww++++++++>>>>>>>>>]<+ +<-<++<-<++<+<<++<->-* Bu-Bu-Du-Ke (Kyoto University) *------------------.> >>.........<+++++++++* > kencho *<...>............... .....................* > otera *<.....<...<<.>>>..<< +++++++++++++++++++++* > suisen *<+.<<..........>>+++ ++++++.>--.>.........* > suibaka (Coach) *<................... ...<++.>>+.-.........wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww+.<<--.<<.>>>..>-... .........+.<...............................<----.<<<............>>+++++++++ ++++++.<.>>>.<++++++.<<<...-------.>>>>....>++++++++++++++++++++++.>>...<++ +.<<..<...>....<....>....wwwwwwwwwwwwwwwwwwwwwwwwwww..............>.>>..+.> ....<<<<<.>>>>-....<+wwwwMw!+=.=<<~..~::~~<..>.. ??MMwww...<....<<.>>>.<.>> >>...<.<<..<..>>>>.MM**~ ...:~``7H=<<====<=<``~~:::<==<?MM<.>>>>..>>>---.++ +..<--.<<...>>>--Mv*-.+++.~ .;d\<.XXXXAzzwHm < ~:*;*==?M<.............. ....>>>...<.<<..M*.<=:~``` .WWmgkJZXzkwXXXI_*dY^ `~**>>M.>>...<.<<..<. >>>>...<++.<<..M*<=*;* .=>!>>(=sjXkZXkzXUr?TTXQaJ(> .?*=.M.>+.<<<<<<<.> >>.<--.>>>>...+M*(;*~. ` dHH-.77TUWWWX.(~(Hmmg ~ .*;=M...<--.<----- -.<...>>>...<<<Myz<<~<~ < ?H _7YH= .gHY"Wa>_J9\ ` _>~(zM>>...>>>...<< <<<<<.>>>>.....Mblli=.~.. .!` TH=.d"% .dm==(Y` ` ..(JllM.....>>>...+. .-......<-.<<...Mslllz(=<+.>_ ?= ~*` _ _>>(JllllM>...<<++.<..<+ .>>>>...<<<<<<.>M5zzOz>>.1>>>---.___ _ _ __+++((zzztlltlM..........+.<< <<--.>..<++.>>>>-.Mzl..zIzz<?<?--1-=(((((((=-zzzzOOOllllOzOM.<..<.>>>>...<< +.<...<--.>>>>.....MzOzl.?.=zzIzzzzz.==.==<+?=++=lllzOZOllM.<<...<++.>>>>.. .........<<+++++++++MelvOwzz?++==???=?++=+=++.zzzZZOltlllM<<.>..>---------. >>..<<<<<<<.>>>>...>++Mz+=.zOVrwyzzz>>zzzzvOz..llllltlllM<--.<<....>>>..... ....<<<<<<<------.>.>>>.Mx>?--?=-.>>z=z1z=...==lzzzttOM<<----.<...<--.>>>>. ...<<<<<<<-----.>>>>.<++.>Mae>zz>>OOOOtOOOOOOOOzllOgMM..+.<<.<..<.>>>>-...< <----.<.................<.>>>Mzwzzzzz>...-zzzzudM------.>-....<+++++++....< <++++++.<..>>>...<<-----.<...>MwwwwwwwwwwwwwwwwM>>...<<<<<<<+++++.>.>>>.>>> ....>...<<<<<.>>+++++++.>>....<<--------.<.>>>---.+++..<.<<...>>>---.+++... <<<<<-.>>.................<-.>>>>...<<+.<...<+.>>>>....<.<<.<.>>>>...<+++++ +.<<..<.>>>>...-------.<<<<<<.>>>.>>>+++++++....+..-......<<<<<<<.>>>>..>>> ---.+++...+.<<++++++++++.>>-.....<<<<<+++.>>.................>>>---.+++...+ ..-.......<<---------.<.<.>>>>...+.<<+++++++++.>>-.....-------.<<<<<<.>>.>> >>+++++++..........>+++.-.--...<<<<<.>>>>.....<<<<<<<++.>>>>>>>....<<------ -.<.................>++++.>>..........<<<<+++++++++++.>>----.<...>>>+++++++ .-------.....<<<<-----.>>>>...-------.<<<<<<..>>>.<------.>>>-.<+++++++.>>+ ++++++......+.<<++++++.<<.>................................>---------.>>-.. .>+.-....<<<<<.>>>>.+.<++++.<<<<<.>>>.<.>>>>-...........<<---------.<...... .........................>>>...+.<<+++++.<..<.>>++++.>>-....<+++++++.<<<<<. >>>.<--.>>>>...<+++++++.<<...<.>>>>....<<<<++.>............................ ..>>>...>+++.---.<<<<<.---.>>>>....<<<<<<<++.>>>>.........<+++..>.<<<.>>>.< ------.>>>>...<<----.<....>>>---.+++...<<---.<.<++++++.>>>>...<<-.<..<.>>>> ...<<<<<.>>................<.>>>>...+.>++++++++.<-....<<<+++.++++.-------.. ....<.---.>>>>.....+.<<<<+.<<.>>>.>>>----.+++..+.<<<.....<+.>>>>-...<<.<.<. >>>>...<<++++.<..<.>>>>..+.<<<.................<+.>>>>-........<<<<<------- ---.>>.......<.>>>>..<<<+++.>--.<---.<<++.>>>>>..+.<<<<.<<.>>>.>++++++.>>-. .<<<+++.---.....>.>>...<<<+.-.>.>>..-------.<<<...>.>>+++++++..<<<+++.---.. ..<--.>>>>.........>---.<<<<..<++.>>>>........<<<<<------.>>......<.>>>>... <<<+.-..<.>>>>...<<<<<+++++++++++++.<.>>>.>>>...<++++++.<<....<.>>>>...<+++ +++.<<..>>>...<<-------.<...>>>...<.<<.................<.>>>>...<<.<<--.>>> >....+.<<<<++.>....>>>-...........<<+++.<<<<.>>>.>>>...<.<<..<.>>>++++.>... <<<<<<<----.>>>>..<.>>>>...<<<<<--.>>..<.>>>>...<----.<<.................<- .>>>>...<<---.<..>---------.>>...+.<<<<-.>...>>>-...<.<<<<<<-.>>>>+.<<+++.> >>++++++++++++...<<<<.>>>-.>>>...+..-.....<.<<...<++.>>>>...<<+++++++++++++ .<<.>>>++++.>....<----.<<.................<------.>>>>...++++++++++++++++.< <<...<.>>>+++++++....>+++++.<<<..>>...>.<<<<++++++.>..<.>>>.+.<<<--.<<.>>++ .>>>-........<<<<<<+.>>>>+.-.....>>-----.+++++.........>-----.<<<.......... .......<------.>>>...>.<<<....<++++++.>>>..<<<<<<.>>>-------.>..<+++++.>>>. ......-----.>+.<<<<<<..
リハーサルでは、ジャッジシステムは模擬地区予選と変わらなさそうだったので最低限の確認だけやったあとはタイピング練習をした。
ノートPCしかまともに使ったことが無かったのでストロークの深いキーボードを打つのは本当に辛くて、数十行のテンプレートを写経するのに10-15分くらい掛かっていて不安が残った。4年半JIS配列でずっとやってきたのを突然US配列に変更したというのもあって、本当にボロボロだった。
US配列の練習としては、本番まで時間が無かったので練習初日にABCのA,B,C問題でまだ解いていないものを全部実装して無理やり矯正するなどしていた。
以降もJIS配列を一切封印して練習して今までの7-8割くらいの速度が出るようになって安心していたんだけど、いざリハーサルでキーボードを触ってみると物理的に形と大きさが違うキー
(Enter とか \ とか) とかストロークの深さとかの諸々に全く対応できなかった。
コンテスト
コンテスト開始 ~ AB 2 完 (49:00)
コンテスト開始時の役割は予め話し合っていて、
- suisen: 環境のセットアップ・テンプレート写経
- otera: 前から順番に読んで、テンプレ写経が終わり次第A,Bを書けそうなら書く
- kencho: 後ろから順番に読んで考察
という分担で開始。CLionのプロジェクトをC++14で作ってしまったり案の定テンプレート写経がとんでもなく遅れてしまったりで結局oteraにPCを渡したのが多分15分時点ぐらいだった。その後Aが通って、Bの考察も終わっていて書けそうとのことだったのでそのままBを実装してもらった。1ペナしつつも49分で2完。
この間suisenはCDEを読んで
- Cはフローの見た目をしてるけど何もわからない
- Dは「右端または左端を揃える」&「上端または下端を揃える」で探索すれば筋力で解けそう？みたいなことを言っていた。動かす駒が右端から左端 (または上端から下端) に動いている場合に壊れることを指摘してもらって、よく分からなくなったので放置
- Eはシンプルに何もわからない
という感じだった。kenchoは後ろから問題を読んで概要をまとめつつ考察も軽くやっている感じだったと思う。
~ ABG 3 完 (80:00)
その後suisenがGを読んだ (Fはsuisenがテンプレート写経でもたついている間にoteraが読んでいた)。簡単な木クエリの問題ですんなり解けた (つもりになった) ので、PC をもらって実装を始めた。辺uvを張った時にできるサイクルに含まれる頂点であって入り口から一番近い頂点を求めるパートを lca の多数決を取るやつでできると勘違いしていてサンプルが合わなかった。よく考えると入口を根とした木の lca(u, v) が欲しい頂点と分かって、修正してGをAC (80分時点)。lcaと距離計算のためにHLDを写経していて、これが無駄になるとそこそこの痛手になるところだったのでヒヤッとした。書き始めた時点では0ACだったのでFAを取りたかったが、迷走している間に3チームくらい通っていて結局FAから9分遅れだった。
~ ABDFG 5 完 (167:00)
その後はACが出ているDEFを考えていた。oteraにDの概要を話すと辞書順で高々2個ずつ取ってそれぞれ対応させる解法を生やしてくれた。実装が大変めなのでsuisenが書くことに。元の配置を回転する方針を選んでしまったせいで最後の移動の復元で頭を壊してしまい、炎上。4通りの回転それぞれに対して丁寧に場合分けを手打ちしていたのがどう考えても悪手だった。後にhenoさんから目標を回転すると簡単ということを聞いて、大反省...
自分がDをバグらせている間、oteraはEを、kenchoはFの考察をしていた。Dのデバッグを終えて提出しようとすると、submitボタンが反応しなくなるトラブルが起きた。スタッフの方を呼んで対処してもらい、submitに成功してDが通った (155分)。スタッフの方が見守る中の提出で、通ったときに拍手をもらえたのはかなりレアな経験そう？このトラブルの影響でBu-Bu-Du-Keのコンテスト時間が1分伸びた。
Dが通った後にFの進捗を聞くと微妙な反応で、考察を共有してもらってみると何と解けていたので実装してAC (167分時点)。本人曰く正当性に自信が無かったらしい？3完から一気に5完になって順位が跳ねた。
~ ABDEFG 6 完 (237:00)
Fが通ったあとは順位表の雰囲気的にEは通すべき問題っぽかったのでsuisenはEを考えていた。(Iの個数)=(Cの個数)<(Pの個数)の場合を考えてみると、
- (Iの個数)=(Cの個数) の条件は、Iを+1に、Cを-1に、Pを0に置き換えた数列の累積和
について
が成り立つことと言い換えられる
- (Cの個数)<(Pの個数) の条件は、Iを0に、Cを+1に、Pを-1に置き換えた数列の累積和
について
が成り立つことと言い換えられる
で、区間和クエリに帰着されて Fenwick Tree で log 1 つで数えられそうとなった。(Cの個数)=(Pの個数)<(Iの個数)の場合と(Pの個数)=(Iの個数)<(Cの個数)の場合も同様で、結局置き換えのパターン 3 種類に対して累積和を作って、累積和の値ごとに座圧した Fenwick Tree を持てば元の問題も log 1 つで数えられることが分かった。
大量の座圧をガチャガチャやっていたら当然バグらせて、悩んでいる間にJの考察が終わったらしくoteraに実装を渡してEの紙デバッグを始めた。結局バグの原因は座圧ガチャガチャパートではなくFenwick Treeにあった。Fenwick Treeくらいなら写経するよりそらで書いた方が速いので練習でも毎回そらで書いていて、今までそれでバグらせたことは無かったので気づくのが遅れてしまった。
修正したコードをまだバグってるだろうな～と思いつつ提出すると一発で合ってくれて、6完 (237分時点)。
~ コンテスト終了
Jの実装をoteraに任せてsuisen, kenchoでKの考察をした。想定解に近いところまでは考察できていたが、計算量を落としきれなかった。その後Jの実装をsuisenが引き継ぐも、線分の交差判定のやり方がまずかったのかサンプル2が合わないままコンテスト終了。
おわりに
オンサイト開催になって本当に良かった。準備していただいた方や交流していただいた方、チームを組んでくれたoteraくんとkenchoくん、ありがとうございました。
