ICPC 2022 参加記

2021年以前はこちらからどうぞ

これまでのあらすじ

ICPC2021が終わり、突如としてvalorantにハマったツバサ君。
早生まれのためICPC2022の参加権利を持っていたが、競プロのモチベーションも低迷しており、コーチとして出るつもりでいた。
しかし、3月ももうすぐ終わりというタイミングで、かつてのチームメイトに声を掛けられる。
少し悩んだ結果、せっかく出場権があるので参加することにした結果、過去最大級の上振れを引き、国内予選を通過。
3年ぶりのアジアオンサイト予選、かつて大失敗したその会場で待ち受けているものとは…？

登場人物(チームMSB関連のみ)

m_tsubasa(僕)

チーム「MSB」のM担当。
修士2年生だが、早生まれのため、ICPC2022に参加。
valorantにハマっているが、ゲームがそこまで上手くなく、シルバーとゴールドを反復横跳び。
ICPCは泣いても笑っても最後。

suzuken君

チーム「MSB」のS & さわやかイケメン担当。
かつてはM担当の人に顔を忘れられていたことも。

ばやしこ君

チーム「MSB」のB担当。
彼のツイートは独特な雰囲気が漂っており、隠れファンが多い。

はてぃー

チーム「MSB」のコーチであり、M担当と同期。
原神にハマっており、discordではほぼ常にプレイ中と表示されている。

1日目

会場に着いてまず待ち受けていたのは、日本語と英語のミルフィーユだった。
受付の進行がどのようになるのか決まっていなかったのか、あるところは日本語で、またあるところは英語で会話が行われていた。
自分は英語がからっきしダメなので、英語が必要なパートはばやしこ君に押し付け、日本語パートだけしゃしゃりでるという先輩風の吹かせ方をしていた。

受付が終わり、荷物を置き、あたりを見渡すと、茶色のTシャツを着たスタッフがせっせと仕事をしていた。
よくよく見ると、Tシャツを着ていたのはりあんさん、てぃーいけさん、beetさん、つたじぇーさんのような、かつてICPCに参加していたレジェンドの方々だった。
その後おろおろしていると、てぃーいけさんに「ツバサさんですか？」と声を掛けられ、自分が覚えられていることに感動した。

リハーサルを終え、早稲田から出場している2チームのメンバーで夜ご飯(ｵｽｼｰ!)を食べることになった。
移動中、はてぃーに「今何時？」と聞かれ、つい脊髄反射で「おやじ」と答えてしまった。
1分ほど口を聞いてくれなかった。

寿司です pic.twitter.com/rkelVUW7Z6

— ツバサ (@emtsu_ba) 2022年12月27日

ご飯を食べ、ホテルの部屋に戻ってしばらくしていると、チームメイトから銭湯にいきませんかと誘われた。
自分は行きたいところがあるといい、一人で行動することにした。
銭湯に行く二人を見送った後、自分も外を出て、ひたすら散歩した。
赤レンガ倉庫や山下公園に行き、3年前に来た場所を思い出しながら地面を踏みしめた。
海岸は非常に寒く、眼鏡をかけないと暗くて見えないが、眼鏡をかけると息のせいであたり一面が白くなってしまった。
しかし、まわりがカップルだらけであることははっきりと見てとれた。

3年前に写真を撮った、公園にある謎の噴水近くのベンチで10分ほど座り込んでいた。3年前のことをはじめとして、いろいろなことを思い返していた。
さらにしばらくすると、チームメイトから今どこですかと声をかけられ、慌てて帰ることにした。どうやら1時間半くらい徘徊していたらしい。
ホテルに帰った後は、シャワーを浴び、ポケモンsvのテラピースを集め、就寝した。

2日目

7時20分に起床した。ほかの二人を起こし、準備をして、会場へ向かう。
二人とも様子がおかしい。
昨日コーラを飲み過ぎただかなんだかで、ずっとトイレに行っていた。
やれやれといいながら、競技中のモチベーション向上のため、エミリアたんが載っている眼鏡拭きをテーブルにセットし、かつて国内予選で部屋に置き忘れたことがあるエミリアたんボールペンを取り出した。EMT。

3年前とは異なり、今年は時間通りに競技が始まった。
チームの方針として、ばやしこ君がA、suzuken君がBを担当することになっていたので、英語を読みたくない自分はさぼっていた後ろの方の問題がどのような問題かをざっと眺めていた。
A, B問題ともに解法ができ、コードを投げるが、どちらもWAが出てしまった。とくにばやしこ君は緊張していたのか、キーボードをうつ手が震えていた。
3年前に2完52位を取り、コーチに煽られたあの悪夢が脳裏にちらついた。
しかし、さすがにICPC5年目ということもあり、とくに焦ることはなかった。 それぞれの問題の現状を聞き、間違っている箇所や困っている箇所の修正案を提示すると、二人とも無事にACをもぎ取ってきてくれた。

その後は順位表を見つつ、解けそうな問題をピックアップして考察・実装した。
自分はDとGを実装、suzuken君がEを実装し、コンテスト中に解くことができた。
順位表ではこれでもかというほど通されていたFは、部分和問題というところから進まず、通すことができなかった。

最終的な順位は15位だった。昨年が13位だったことを考えると、競技から遠のいていた割には健闘した形ではあった。
しかし、昨年から国内予選・模擬・アジア予選とあらゆるところで自分の少し上に立ち、注目を浴びていた早稲田のもう片方のチームに勝つという夢は、相手のエースがコロナで不在の今回でさえ、果たすことができなかった。

5完で15位でした。DとGをやりました。 pic.twitter.com/T4E5nxESHN

— ツバサ (@emtsu_ba) 2022年12月28日

コンテスト終了後は、企業ブースに行ったり、懇親会(非公式)が行われていた。
こたつがめさんや熨斗袋さんのような、昔に会ったことある方々にいくらか声をかけたが、名乗りもせず話しかけたせいで相手を困らせたりした。
その後、(早稲田とすごく縁がある、)いい生活でとてもお世話になっている多賀さんに声をかけると、すでに持っている名刺を新たにくれた。ロゴが変わったから是非、とのことだった。たしかに変わっていた。
じゅぴろさんにも初めて会った。思いがけないタイミングでびっくりして声が出なかった。
また、かつて会津合宿でチームを組んだこともあるホスフィンさんにわざわざ声をかけていただいた。声をかけられることはこれまであまりなかったので、感動して涙が出そうになった。
最後には、自分の競プロのモチベーションの原点とも言える、WAsedACのコーチを務めていたtossyさんともお話した。JAGの勧誘もされた。

懇親会後は、はてぃー、suzuken君と3人でお土産を買い、帰宅した。
帰り道、最後二人と別れた後、1時間電車に揺られながらポケモンsvのテラピース集めをした。テラピース緩和待ってます。

現役時代を振り返って

競プロを始めてICPCに初参加してから、今日で引退するまで、あっという間の日々でした。

• 2018年に、競プロと出会い、ICPC世界大会に出場したWAsedACに憧れを抱きました。

• 何をやっても上手くいっていた、人生の極大点とも言える2019年、ICPCでも国内予選を突破することができましたが、アジア予選という大きな壁を知りました。

• 手にしていたものがほとんど零れ落ち始めていた2020年、レート順で高い方から集めたチームで組んで出場したICPC国内予選で予選落ちという結果に終わりました。

• 心機一転やり直しをしていた2021年、ICPC国内予選でリベンジを果たし、アジア予選でも13位という結果を取ることができました。

• 集大成の2022年、久々に開催されたオンサイトアジア予選で、これまでに会った様々な方に再会しました。最後まで公式に学内1位を取ることはできませんでした。

これまで何の取り柄もなく、自分に自信が無かった僕にとって、競プロに出会い、様々な経験をしたことは、間違いなく人生の大きなターニングポイントの一つでした。
これがなければ、競プロはもちろん、人間関係や就活も含め、様々な観点から見ても、今の自分は存在していないと思います。
これは、自分ひとりに限らず、これまで参加してきた多くの競技者に当てはまるのではないかと(勝手に)思っています。
今後、まだどうなるかはわかりませんが、ICPCのような大会が続いていき、様々な人にいい影響があるといいなと願っています。

本当はもっといろいろなことを書こうと思っていたのですが、自分の中での考えがあまりうまくまとまらないため、いったんここまでに留めておこうと思います。
最後になりますが、ここまで読んでくださった読者の皆様、これまで一緒にチームを組んでくれたチームメイト、一緒に競いあったライバル、ICPCを運営してくださっている皆様、自分のICPC出場を応援してくれていた友達の皆、仕事まで休んでアジア予選を応援してくれていた母親、いい結果を取るたびに褒めてくれた父親、競プロがきっかけで関わってきたすべての皆様に、この場を借りてお礼申し上げます。

本当に、これまでありがとうございました！！！

おまけ

今後についてはまだ何も決めていませんが、せっかくなので何か恩返しができればいいなと思っています。
身の回りが落ち着いたら、JAGの招待リンクを探すところから始めようと思います。

ABC271

もう少しうまくできたはずです。
コンテスト
提出

C - Manga

二分探索。
捨てられる本を先にカウントします。

D - Flip and Adjust

DPです。枚目まで選び、総和がになるとき、最後に選んだ表裏の種類、としてDPしていきます。

E - Subsequence Path

諸悪の根源。数列が頂点の列だと思って30分以上費やしました。これがなければFが通っていたと思うと…
項目まで見たときの頂点の最小距離、としてこれを一次元に圧縮します。

F - XOR on Grid Path

一行足りなくてコンテスト中ACまで3分足りませんでした。 半分全列挙します。
回移動した段階でどのマスでどの値になっているか、を列挙します。これをスタートからとゴールから行います。今いるマスについて、スタートから今までの値と、そこからの値は同じになっていれば最終的に0になるので、あとはうまく組み合わせを探して数えればおしまいです。

G - Access Counter

今時で、次に誰かがアクセスした時刻がになるような確率、とすると、これを行列とみなして乗し、が23、が青木君のアクセス時刻になるようなもののマス目の値を足して答えになります。
行列の中身ですが、これは無限等比級数になります。1日誰もアクセスしない確率が公比、初項は直近のでアクセスする確率です。
あとはこの級数の和を求めればOKです。

ABC 245

2か月以上競プロをしてなかったらしいです。リハビリバチャ。

提出

A - Good morning

問題
A, B, C, Dの順番を間違えて1ペナ。

B - Mex

問題
setとwhileでやるいつもの。

C - Choose Elements

問題
番目がを選ぶような方法で、までを完成できるか
でDPします。

D - Polynomial division

問題
最初とっつきにくい問題でした。
から決めていけばいいです。
二重ループを回し、が確定したらその寄与をの係数から減らすだけ。

E - Wrapping Chocolate

問題
ほぼこの問題 の強化版です。
やることは同じで、片側でソートしてから二分探索。

* F - Endless Walk

問題
SCCしてチェック。

G - Foreign Friends

問題
人が国の人気者と友達になる最小コスト

とします。人に対し、実は小さい順で2つの国に対する最小コストさえわかっていれば解けるので、計算量が落ちます。あとはダイクストラ。

ICPC2021アジア予選 参加記

suzuken君、bayashiko君と「MSB」で出ました。

コンテスト前

模擬は13位でした。可もなく不可もなし。
前日は友人とvalorantをしていましたが、明日があるから早く寝ろと怒られました。彼は優しいのでモテると思います。

コンテスト

まずばやしこくんがA、すずけんくんがBを読み、自分はざっと後ろの問題の雰囲気を確認しました。
自分は英語を読まない担当だったので、すずけんくんが読んだBを共有してもらい、そのままAC。この時点で3位になり、順調にいけば弊学ライバルチームのgive usに勝てるとニコニコしていました。

その後は、へのさんのチームがGを通していたので、数え上げが好きな自分はGに特攻。ばやしこくん、すずけんくんはそれぞれ問題の翻訳を進めつつ、ACが出ている問題に手を出す、という形になりました。
G問題は明らかにDPであるとにらんでいましたが、ループができるパターンをうまく排除する方法が全く思い浮かびませんでした。ARCの問題の解説も見たりしましたが、めどが立たなかったため、一度離れてJを見ることに。
Jの嘘解法を思いつき、せっせと実装をしていました。
その間、ばやしこくんやすずけんくんはC,Dあたりとにらめっこしますが、完全な解法まではたどり着けず。刻一刻と時間だけが過ぎていきました。
コンテスト開始から2時間が経過し、自分が嘘解法を修正してJの解法を思いついたとき、Wavelet Matrixが必要になったので、「これはばやしこくんに"譲ってあげよう"」と思い、ばやしこくんを呼び寄せて解法を押し付け伝えてバトンタッチしました。
すずけんくんはその間にもDの考察を進め、開始から3時間後に無事ACすることができました。


G, Jは完全に炎上しました。G問題は全く考察が進まず、J問題は手元で生成したランダムケースですべてACしているにも関わらず、提出するとWAになってしまいます。
順位表が凍結するとき、give usチームは5完で10位にいたのにも関わらず、自分のチームはまだ3完でした。
さすがに全員疲れと焦りが出ており、微妙な空気が漂っていました。

残り30分くらいになり、急にGで困っていた部分を解決する方法が天から降ってきました。 必死で実装を進めていると、残り10分くらいでJ問題では悲劇が起きました。
なんと、Home画面に問題文の解釈に関するClarが届いていたのです。
今回のシステムでは、(少なくとも自分は)通知が来なかったため、全然気づいていませんでした。
ばやしこくんが「これ直すの無理だ…」と落ち込んでいましたが、修正を始めていました。
すずけんくんがCを進めながら、三並列で進めていると、残り4分で自分のGが通りました。
どうにか3完を阻止できたと、すずけんくんと二人で喜んでいると、なんと残り2分でJも通りました。
達成感と疲労感に包まれながら、コンテストはそのまま5完で終了しました。

結果として、5完・13位でアジア予選を終えました。

コンテスト後

gather townにて、いろいろな人と話しました。
noimiさんや熨斗袋さんにおめでとうを伝えたり、tossyさんと再会したり、人が多いところでミュートして静かに聞くモブを演じたりしていました。
最後には、むげんさんが募集していたGartic Phoneに参加しました。
競プロerが集まっていたため、AntsやAnd Grid、Earsといった競プロ有名問がお題に出ていても、綺麗に伝わっていきました。感動。

おきもち

2019年のアジア予選では、パフォーマンスが全く発揮できず、自分の中で満足いく結果が出せませんでした。同大会に出ていたもう一つのチームは、オンラインで世界大会に出場できる結果を残したのもあり、自分のチームのコーチから煽られもしました。
2020年、早稲田の中で現状一番ともいえるチームに入りました。しかし、結果は予選落ちとなり、なんとも表現しがたい感情だけが募っていきました。
昨年3月、かっつくんとアジア予選のYes/Noをdiscordでしゃべりながら見ていました。来年は二人ともここに出られたらいいね～って話をしていたと思います。
その後、ばやしこくんとすずけんくんに誘ってもらいチームを組み、今年は再び国内予選を通過することができました。
今日のアジア予選まで、モチベーションが低下していたのもあり、あまり精進できていませんでしたが、何とか40チーム中13位という、とりあえずはいい結果を残せました。残り5分で2問を通し、Yes/Noで少しわかせることにもなりました。
しかし、ずっとライバル視していたgive usチームには、国内予選・アジア予選ともに勝つことはできませんでした。
J問題のClarがどうとか、なんとかかんとかいろいろありましたが、現在の自分の実力だとここからさらに+1問をそれなりの速度で解くのは難しいなと思います。結局、完敗でした。
いろいろありましたが、再びアジア予選の舞台に立って、ある程度の結果が残せたのはよかったです。現在の自分の実力を出し切ることはできたと思っているので、満足しています。
自分は早生まれなので、修士2年の来年度も出場することができますが、まだ出るかどうか決めていません。自分のモチベーションとも相談しつつ、のんびり考えていこうと思います。
ここまで読んでくださった方々、誘ってくれたばやしこくんとすずけん君、一緒に戦った早稲田のチームの方々、応援してくださった皆様、懇親会で話してくださった皆様、そしてコンテストを運営してくださった皆様、本当にありがとうございました。

ABC231 G - Balls in Boxes

問題
提出コード

解法

の総和を求めて、最後に全パターン数で割れば答えです。総和の求め方について考えていきます。

は、個の箱にあるボール個からそれぞれ1個ずつ選ぶパターン数と一致します。
ということです。

個目の箱にあるボールからボールを選ぶパターンは2パターンあります。
最初から入っている個のボールを選ぶパターンと、新しく追加された個のボールを選ぶパターンです。
前者は明らかに通りです。

個の箱の中で、前者を選ぶグループを決めていきます。すると、前者を選んだ箱におけるに、回のボールの入れ方、および後者を選んだ箱のボールの選び方をかけたものを足していけば答えです。
新しく追加するボールの入れ方や選び方は、前者を選んだ数に依存します。なので、をあらかじめまとめて足しておきます。
これは、

• 番目の箱までみて、個の箱を前者として選んだ状態における、の総和

として計算していくことができます。

では、にかけるべき数を計算していきます。やることは2つで、

1. 個のボールのうち、個の選ばれるべきボールの位置を決める

2. 残ったボールを箱に振り分ける

です。

1つめについて考えます。まだ選ばれてない箱の番号がだったとします。この時、回の操作のうち3つをとってきて並べた列を作ると、前から順番にに割り当てることで、過不足なく数えることができます。つまり、個の中から個選んで並べるパターン数になり、となります。

あとは2つめの操作です。残っているボールは、どの箱に割り当てても問題ありません。なので、残っているボールの手前から順に、個の箱の中から1つ選んでいけばよいので、が答えです。

よって、を計算して足していけば答えになります。

感想

をボールの選び方に帰着させる問題は今まで解けたことがなかったので、今回初めて解けてうれしいです。　

ICPC2021国内予選 参加記

解法への言及があります、ご注意ください
suzuken君、bayashiko君と「MSB」で出ました。AtCoderにおけるIDの頭文字をとってきたものです。
前日になって何故かスポンサーが突如ついたらしいです。

今気づいたんですがなんですかこれは？？？ pic.twitter.com/3OFw3XqL9W

— おふとんらぼ@プロコン用 (@MohutonLab_comp) 2021年11月4日

コンテスト前

コンテスト前日はPCを22時くらいにカバンにしまっていたので、手持ち無沙汰になりました。高校からの親友に電話して、一緒にスマブラをしていました。彼は最近競プロを始めたので、ICPCについて語りながらプレイしていると、スマブラでボコボコにされていました。

コンテスト当日、開始は16:30なのですが、お昼は外で食べようと思い、12時に着きました。が、全くお腹がすかないので、散歩をすることにしました。
理工キャンパスから本キャンパスへ行き、ふらふら歩いていました。
明日は早稲田祭があるらしく、いろんな学生が忙しそうに移動していました。僕には縁のない話です。
そんなこんなで1時間ほど歩き続けました。
帰り道、ドン・キホーテに寄り道をすると、アルフォートが70円弱で売っていました。ここに毒を盛れば、弊学の5チームを全て闇討ちできる！そう思い、ニコニコして購入しました。

14:00あたりから、ぽつぽつと人が集まり始めます。自分は、一旦同期の人達と雑談をしていました。その後、コーチをしてくださっているとまとさん、るぎうさんがいらっしゃって対応していると、同期に「敬語使えるんだ」と煽られました。そら使えますよ。
さらにしばらくして、1年生のserpent君が到着したので、感動しておー！となっていましたが、自分が名乗るのを忘れており、同期に笑われました。敬語は使えますが、自己紹介はできないみたいです。

人がたくさん集まり、それぞれの部屋で準備を始めている頃、お菓子交換会が始まりました。
自分も先ほど買ったお菓子を渡し、「毒入りです！」とニコニコしながら渡していると、誰もが口をそろえてこう言います。
「AGCのA問題であったよね、懐かしい…」
自分も同じことは思っていましたが、全員で意見が一致するのは、異常集団としか思えませんでした。

コンテスト直前、家から持ってきたリゼロコラボの紫色のボールペンをsuzuken君に見せて自慢していました。反応は暖簾に腕押しでした。
勝負ボールペンの準備も万端なので、国内予選は通過間違いなし！

コンテスト本番

コンテストが始まります。
…問題が見えません。
この流れは去年もやっていたので、特に焦りはありませんでした。
しばらくすると問題が見えたので、bayashiko君はA、suzuken君がB、僕はCを読みました。
C問題は、構文解析ということがわかりました。が、散歩の疲れか、問題文が頭に入ってきません。しばらくぽけーっとして読んでいるフリをしていました。
その間にA,Bが読み終わったらしく、流石に自分も足を引っ張るわけにはいかないので、Cを真面目に読み終えました。
読み終えた感想は「なにこれ？」です。明らかにおかしい難易度の予感がしたので、先にD問題へ移行しました。
D問題もよくわかんないなーと思い、適当に二人に声をかけます。二人とも実装を始めているらしく、僕はC問題に戻りました。

C問題は、数式が木で表現されており、その木をうまくパズルすることで、スコアを最大化する、というものです。
とりあえず、パターンがどうなっているか、手元でこねくり回すことにしました。
が、一行に解法が見えてきません。しばらくは何もわからず、うんうん唸っていました。
すると、突然「やばい…やばい…」という声が聞こえてきました。どうやらbayashiko君のようです。声をかけると、A問題で炎上しているようです。直後、「こっちもやばいです」という声が聞こえてきました。B問題も炎上しているようです。終わった…

とはならず、今日の僕はとても冷静でした。散歩で疲れていただけかもしれません。こういうパターンの場合、3人全員が焦り始めると、誰も消火活動ができないので、自分は一つ一つ解決することにしました。

A問題をまず解決することにしました。bayashiko君に聞くと、コードは書けているのですが何故か実行がうまくいかない、とのこと。問題概要を一度聞きましたが、まぁAだし考察が間違っていることはなさそうだったので、あと10分くらい様子を見よう、ということにしました。bayashiko君はすごく謝っていましたが、僕は問題無い、とニコニコしながら対応していました。結果、suzuken君の対応をしている間に無事に通すことができました。入力ファイルにケースをコピペした後保存し忘れていたらしいです。
このようなミスは誰もが一度はすることですし、アジア通過がかかっているA問題は、確実に・素早く通すことを要求されるため、実は下手なB~D問題より難しい可能性もあります。自分もAを担当していた時はとても緊張していたため、bayashiko君が焦っていたのはとても共感できました。ここで変なイメージを付け、そのままずるずる行く方がマズいので、一旦自力でなんとか通しきる、ということができたのはかなり大きい出来事だったと思います。この世の終わり、といったような死にそうな顔をしていたbayashiko君は、なんとかC問題へと押し付けられ移動していきました。


さて、B問題はというと、考察で少し詰まっているようでした。
問題を教えてもらい、適当に自分の思考フローを垂れ流していると、suzuken君にかけそうな雰囲気が出てきたので、実装してもらうことになりました。しばらくすると、そのまま通り、無事2完することができました。
2完はしましたが、もちろんこのままで終わるわけにはいきません。
C問題は明らかにやばい雰囲気があるので、一度順位表をきちんと確認することにしました。
すると、D問題は数チームが通しているのに対し、Cは誰も通していませんでした。
おとなしく、D問題へいくことにしました。

C問題はbayashiko君にそのまま突破口を見つけてもらい、Dを僕とsuzuken君で片づけることにしました。
D問題は、風船を配る回数を最大化する問題です。
自分は、この問題を思い出していました。
で馬鹿でかいものが2つあると、上記の問題に帰着できるよね～、というと、suzuken君は頷きました。
そのあたりで、3分割をするのかな？という発想が出てきました(馬鹿でかいがあるとき、その2つはそれぞれ1つで1グループ、残り全部を最後の1グループとするあたりから発想が出ていたと思います)。すると、ポールを3つのグループに分けた結果、そのグループの最小値が操作回数となるような並び替えの仕方が必ず構築できることを証明できました。
この内容をsuzuken君に伝え、実装をしてもらおうかなと思っていたのですが、実装方法が伝わりませんでした。ので、自分が実装することにしました。
実装はとても軽く、そのままACすることができました。
終わってから話をしたところ、suzuken君はそもそも問題を誤読していたらしいです。通りで話がかみ合わないわけでした。

さて、ここまででA,B,Dの3完です。もちろんこのままで予選が通過できるほど甘いとは思っていません。僕がD問題を通してる間に、2人がC問題を整理してくれているようでした。そこで、実装が比較的得意な僕とsuzuken君はC問題へ行き、その間にbayashiko君はE問題でエスパーを狙う、という方針を立てました。
どうやら、が書かれた頂点は全て根になり得るらしく、また、頂点ごとに繋がっている辺は切れたり加わったりすることはありません。なので、あとはminmaxでDPをした後、全方位木DPをすればよい、ということになりました。
構文解析パートをsuzuken君にお願いしようという話もありましたが、お互いの実装をすり合わせるのが難しそう、ということになり、自分が実装をすることになりました。
実装中、「マジ？」「助けて～」「こんなのおかしいよ～」「ほんとに？」といった独り言を無限につぶやいていました。うるさくてごめん。
実装を完了すると、149行の壮大なコードができあがりました。
コンパイルをすると…なんと通ります。サンプルを試すと…なんと合います。
suzuken君に出していい？と聞くと、OKが返ってきたので出します。
すると…ACしました。バグ無しで通せたのは、我ながら天才だと思いました。褒めてくれる方、募集中です。

僕「やっぱりおかCよ…」
bayashiko君「ダジャレですか？」
僕「し～っ！」

4完して順位表を見てみると、ぽつぽつE問題が通されていました。
Eに取り組んでいた2人に話を聞くと、考察が終わってあとは実装するだけ、という状況らしいです。4完でも通過できるかなー、とは思っていたのですが、確実に突破をしたいので、真面目に取り組むことにしました。
コードはある程度できていましたが、かなり複雑で、デバッグ役として自分が参戦するのは難しい状況でした。そのため、スペアとして、1から実装を行うことにしました。
そして、3人で同時並行で実装する時間が始まりました。

ACしたのは、bayashiko君でした。
bayashiko君はダイクストラ法をライブラリとして持っているため、ソラで書くことができないと聞いていました。
聞いていた情報と違うんですけど！！(歓喜)
bayashiko君がテストケースを通すとき、明らかに手がプルプル震えているのが見えました。緊張するの、わかります。

5完すると、なんと20位以内に自分のチームの名前が書いてありました。
この後、3人とも問題文が頭に入ってこない、と言い訳しながら感想戦をしていました。
UHISHIROを始めとする他のチームが5完すれば3チーム出場できる可能性もあったので、ひたすら祈り続けていました。

コンテスト結果

5完で、16位になりました！考え得る最高レベルの結果をたたき出すことができたと思います。早稲田の学内では2位だったので、その点のみ悔しいです。

コンテスト後

ラーメンを食べに行きました。自分が高校の頃から通っている、一番好きなラーメン屋です。

高田馬場 焼麺 劔(つるぎ) | オフィシャルサイト

帰り道、1時間電車で浮かれていました。
同期が集まっているdiscordで聞き専になりながら通話に入っていたのですが、眠くなったので落ちる、といい落ちました。
しかし、気づいたら順位表を眺めており、1時間ニヤニヤし続けました。はたから見たら変な人だったと思います。

家に着き、カバンの中身を整理していると、大事なものが見当たりません。
なんと、リゼロコラボの勝負ボールペンを部屋に忘れていました。
エミリアたん…

思ったこと(おわりに)

正直なところ、自分の競技プログラミングに対するモチベーションは万全と言える状態ではありませんでした。去年、予想外の大敗をして、立ち直るのに時間がかかりました(表面上は元気そうに振舞っていた気がしますが)。自分の周りには、かつて一緒に競技プログラミングに取り組んでいた同期がたくさんいました。しかし、今もまだ続けている人は自分一人です。後輩がたくさん頑張っているのを目にしていましたが、どうしても、競技プログラミングに力を入れられない自分がいました。
今年の6月になって、suzuken君とbayashiko君にチームを組んでもらうことを快諾してもらいました。その直後あたりは、少しだけ精進をしていた気がします。
当初、ライバルチームのメンバーを含めたAOJ-ICPCのランキングでは、自分がダントツTopになっていました。しかし、最終的には、自分はTop争いのレースからかけ離れた位置にいました。
また、自分は一時期競プロにおける自信を失っていました。9月のABCでは水パフォ相当の順位、さらにはARCで0完をし、レートを100失いました。

それでも、チームメイトは一緒に練習をしてくれていました。
加えて、同期の多くが、応援し続けてくれていました。時には僕のブログをネタにされたり、冷やかしを受けている日もありましたが、なんだかんだでAtCoderの順位表を見てくれていたり、最近の調子を聞いてくれたり、激励の言葉を添えてくれたりしていました。
本番中、チームメンバーがピンチな状況になった中でも、自分が常に冷静でいられて、最高のパフォーマンスを発揮できたのは、こうしたまわりの支えがあったからこそだと思います。
また、早稲田の競プロdiscordでは、2018年度で世界大会に通過した、yamadさん、imulanさん、ryoissyさんが通話で応援してくださっていました。コンテスト後、まずここへ報告しに行き、お祝いしてもらったのはとても嬉しかったです。今回、かなりいい順位が取れたので、少しでもこの先輩方に近づけたのかなと思っています。少しでもアジア予選でいい順位を取れて、あわよくば世界大会に…今の実力のままでいけるのでしょうか？

同期とdiscordで通話しながら今こうしてブログを書いていますが、改めて通過できたのだと思うと、今にも泣きだしそうになってしまいます。泣いたら確実に笑われるので、絶対に声は出しませんし、直接応援ありがとうとも恥ずかしくて言えないです(実は応援してませんって日にはこの世の終わりが来ます)。今後も応援してくれたら嬉しいです。頑張ります。

改めて、(まだ正確には確定していませんが)アジア予選に通過できて、本当に良かったと思います。2019年、アジア予選でも大敗しているので、その借りを返しに行かなければなりません。まだまだできることはあるので引き続き頑張って行こうと思います。

ここまで読んでいただき、ありがとうございました。

AOJ 1637 色の切り替え

問題
提出コード
解説見たらやっていることが少し違ったのでメモしておきます。

まず、同じ頂点のボタンを2回押すと元に戻るので、それぞれのボタンについては"押す"か、"押さない"かの2通りだけ考えれば良いです。
そして、全ての頂点を1度押すことを考えます。すると、全ての辺について、色が変わる回数は2回になります(辺に繋がっている頂点が2個なので)。
つまり、ある頂点集合について考えると、その補集合を押した時と結果は同じになります。このことから、頂点を押す、として最適解を探した時も頂点を押さない、とした時も結果は同じです。
よって、頂点は押さない、と確定させることができます。
今回作りたいのは全域木です。頂点と頂点を繋ぐ、としましょう。
頂点については押さないことが確定しているので、の辺が赤になるよう、頂点で調整をする必要があります。この時点で、の押す/押さないが確定します。
以外の頂点について見てみると、

• を押す/押さないで、頂点のどちらと繋がっているかが切り替わる

• を押す/押さないで、頂点の両方と繋がっている/繋がっていないが切り替わる

の2パターンに分かれます。後者については、繋がっているを選択すると、の閉路ができるので、繋がっていないを選択するしかありません。よって、このパターンについては操作が一意に決まります。
前者のパターンの頂点集合をとしましょう。
について、押す/押さないを決めてみます。すると、のそれぞれについて、と繋がっている辺が赤くなるパターンと、黒くなるパターンが、押す/押さないで決まります。赤いパターンを選択してしまうと、頂点を含んだ閉路が必ずできてしまうので、黒くなるパターンを選択するしかありません。
ここまでで、全ての頂点の押す/押さないが確定しました(が空の場合もありますが、そのときは空とわかった時点で、全ての頂点の押す/押さないが確定しています)。
あとは、押した結果グラフが全域木になっているか確認してペナルティを計算すれば良いです。
を決めるので、について押す/押さないを確認するので、押す操作を実際に行うのでで、結局です。
チェックするパートについても、全ての辺を愚直に走査すれば良いです。たかだか回しかチェックしないので、こちらもになります。

感想

昔見た時は全く歯が立ちませんでしたが、今解いたら順調に考察が進んだので面白かったです。
昔一度解説を見て感動した記憶がありますが、全然違う考察ルートを辿ったので、記憶に残っていないことがバレました。