今年も ICPC2025 Yokohama Regional に進出しました！
ICPC2025 Prelim や ICPC2024 Regional の記事もぜひです。
ICPC スレッドはこちら:
🧵 ICPC2025 Yokohama
チーム編成
- Asa a01sa01to
- through through__TH__
- kAsA kasa_ame__
いつもの 3 人です。 3 年目。
みんな M1 なので "Masters"。
ほか 2 人は早生まれではないのでラストイヤーです。
自分は早生まれ + コロナ禍特例で、来年も出れるのか？ よくわからん！
__ __ _ __ _____ __ __ _ _ __ __ | \/ | / \ \ \/ /_ _| \/ | | | | \/ | | |\/| | / _ \ \ / | || |\/| | | | | |\/| | | | | |/ ___ \ / \ | || | | | |_| | | | | |_| |_/_/ \_\/_/\_\___|_| |_|\___/|_| |_| Programming Circle @ Saitama University Team: Maximum Masters Members: - Asa (X, AtCoder: a01sa01to) - through (X: through__TH__, AtCoder: through) - kAsA (X: kasa_ame__, AtCoder: kAsA02) Why "Maximum Masters"?: - Maximum: the Programming Circle we all belong to - Masters: A nod to our status as M1 (Master's) students
↑ チーム紹介ドキュメント
チーム紹介スライド・ドキュメントはほぼ去年の使いまわしです。
来年度以降も引き継ぎます (決意)
去年の Yokohama ではあまり良い結果を残せなかったので、今年こそは！ という気持ちで臨みます。
12/5 まで
ホテルは Prelim の打ち上げ中に予約していたので、これと言ってやることはなかった。
事務局からの連絡メールに黙々と返信するだけ。
チーム全体の練習もあまりできていない。
1 週間前に研究の中間発表があったりで、それどころではなかった。
個人では ABC や Codeforces のコンテストに何回か参加していたくらい。
ABC433 で -44 でかなり落ち込んでいたが、 ABC434 で +38 とれたのでまあヨシ。
CF は Rated 1 年ぶりに参加したが、 R1066 で -49 からの R1067 で -50、爆散！ かなしい...
いろんな人が CF 上で AI 対策がどうのこうの言ってるけど、実際どうなんですかね...
そういえば MHC もあったっけ。 Round 2 で 2375 位で T シャツもらえず。 ざんねん。
まだ購入してなかったので 除霊グッズ (?)を購入。
アクスタに加えて ジャンピング chokudai キーホルダーも購入した。
"ぁあ悪霊退さーーん！！" にならないように頑張りたい。
Day 1
深夜にあった CF R1068 に参加してしまった。
結果は +18 (1655 → 1673)。
-99 の負けを取り戻すにはまだまだだが、勝っただけいいか。
ICPC 直前わくわくであまり寝れず、結局寝不足に...
ICPC 前日なのに CF ぞいぞいしてきた
会場まで
今年も埼玉大学マスコットキャラクターのメリンちゃんぬいぐるみを持参。
せっかく購入したので chokudai アクスタ・キーホルダーも一緒に。
電車は同じ路線なので through とは Asa の最寄り駅で合流し、電車に揺られること約 1 時間半、 kAsA とは横浜で合流した。
昼食は横浜駅ルミネの利久というお店で牛たん定食を食べた。
2 人は 3 枚 6 切れの定食にしていたが、 2 枚 4 切れの定食で十分満足。
会場
13 時くらいに横浜駅を出発し、 13:30 ごろ会場到着。
みんな ICPC 関連ツイートをスレッドにしていたので、自分も建てた。 (このページの一番上を参照)
受付を終え、荷物を預けようとすると、今年の荷物置き場は会場内のスペースらしい。 (明日どうなっているかはわからないが)
しかも荷物にタグをつけて管理する方式らしい。
安心安全でいいね (ほんとに？)
席に着くと、いつも通り T シャツとネームプレートがあった。
T シャツは大きければ大きいだけいいだろという思考でいつも大きめサイズを選んでいるが、 4XL を選んでいたらしい (記憶になかった)。
さすがにでかすぎた。 反省。
今年は謎トランプと謎シャツもあった。
シャツは 5 枚あって、配分がよくわからん。
説明ほしいよ～～
机に置いてあったチーム紹介ドキュメントを見てみると、 AA がめちゃくちゃ崩れていることが判明。
Note: Some teams made ASCII arts for their introduction. The ICPC Yokohama Organizers have done their best to reproduce the submitted documents. We apologize if any of the ASCII arts do not appear as originally intended.
とのこと。
さすがに _ 前の \ (エスケープ？) はどうにかできたんじゃないか？とも思ったが、まあ印刷されてしまったので妥協。
記憶になかったけど 4XL にしてたらしい、デカすぎ
え、チーム紹介ドキュメントの _ がエスケープされていて AA が崩れてる、そんな...
リハーサル
リハーサルは去年とまったく同じ。
- P: ただの総和を求める問題
- Q: Hit and Blow を interactive で解く問題
- R: 2022 A (サンタがプレゼント届けるやつ)
- S: 2021 A (球体の union 部分の体積求めるやつ)
最初 kAsA が環境構築するか～となっていたが、実際やってみて Asa が担当したほうがよくない？となり、明日はそうすることに。
P 問題は Asa が担当し、 Q は through が担当。 その後クエリ関数は切り分けると便利だよ～と少しリファクタリングして、 R は Asa、 S は kAsA が担当した。
今年は風船があっていいね 🎈🎈🎈
暇になってしまったので、 printfile コマンドを試すことに。
遊びで以下のコードを書いて printfile した 🤔
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < (n); ++i) int main() { while (true) { string s; cin >> s; if (s != "WJ") break; cout << "yiwiy9: Akuryou taisan!" << endl; } cout << "yiwiy9: Akuryou taisaaaan!" << endl; }
バイナリを printfile しようとするとバイナリはプリントできないよ！と言われた。えらい。
DOMjudge でもバイナリを投げようとしたら Too Large 的なステータス (覚えてない) が返ってきた。えらい。
kAsA がガム食べてていいかな？と聞くので練習ついでに clar を投げた。
終了後に言っていた話によると、コンテスト情報のしおりに書いてあったらしい。 実際「これら以外は持ち込み禁止！」って書いてあったので、だめっぽい。
Tech Talk & チーム紹介
Tech Talk、面白かった。
JetBrains IDEA がオープンソースになっている？みたいな話は初耳。
動画作ってる人はタイアップしましょう！みたいなのもあって、そんなこともしてるんだ～になった。
が、隣を見てみると両方とも寝息を立てていてうーん...
チーム紹介は A08 の席にいたので 8 番目。
まあスライドは上のほうに載せたので割愛。
2 人は何も話したくないというが、せっかくなので最後一言くらいはとマイクを渡した。 話したのは "I will enjoy the contest (too)!" だけだった、うーん...
今年もあっという間に終わってしまった。
ホテル
終わったのでホテルへ直行。
ホテルは毎年同じスーパーホテル。
1 人 14,000 円くらいだが、昨年度大学に補助申請出して通ったので、たぶん今年も実質 0 円 (となることを願ってます)。 とてもありがたい。
移動中、いとこの Ryoga.exe (チーム Intercastellar; Ryoga_exe ) が前を歩いていたので様子を観察していたが、どうやら同じホテルらしい。びっくり。
ギリギリに予約したらここしか空いてなかった...とのこと。
チェックインを済ませて部屋に入ると、 YouTube 対応のテレビがあった。
せっかくなので悪霊退散をした。 (なんか部屋暗くない？？)
明日に向けて悪霊退散してきた
その後夕飯どうしようね～～の話をしながらなんだかんだ 19 時ごろ。 1 時間近く経っていた。
夕飯
いつも夕飯どうしようか悩んで結局中華街に行くのが恒例行事となっている。
全チーム中華街に行ってるんじゃないかと思うくらいには中華街の写真が回ってくる。
夕飯どうしようかな～ (毎年恒例)
やっぱり全チーム来てるな
部屋で探して、ここにするか～となったところは完全予約制だったらしく、近くの「海南之家」というお店に行くことに。
安くて美味しかったが、提供が少し遅かったかな？というかんじ。
時間制限がないらしく、残り時間表示が "1440 分" になっていて面白かった。
何を思ったかリハーサル中に蒸しパンを食べてしまったので、あまりお腹が空いておらず、あまり食べられなかった。
ホテル 2
その後ホテルに戻った。
ふとスーパーホテルアプリを見ると去年宿泊分のポイントが溜まっていた。
何に使えるか調べてみたところキャッシュバックが受けられるらしいので、 1,000 円もらってきた。
手続きを機械で済ませると後ろで Ryoga.exe がアメニティを探していたので声をかけ、自分もアメニティをもらってきた。
1 人 1 泊あたり 5 個まで無料でもらえる (ぱっと見ただけなので嘘かも) らしく、せっかくなのでトリートメントなどをもらってきた。
1F のファミマでトリートメントでも購入しようかと思っていたところだったので、提供されていてちょうどよかった。
毎年恒例、ユニットバスよくわからん問題が発生。
とりあえず適当に使った後に調べてみると、全然使い方が違っていて申し訳ない気持ちに。
いい加減覚えなさーい！
明日は朝食も混むから 7 時起きで余裕持っていこうという話をした。
そしてここまでブログを書き、 24:30 ごろ就寝。
Day 2
いよいよ明日、ICPCアジア地区横浜大会のコンテスト本番が行われます!!!
我がサークルからは、7月の厳しい予選を勝ち抜いた、
『Maximum Masters』が参加します!!
Maximumが誇る最強チームが、今年もこの大舞台へ挑みます。
メンバーの健闘を心より祈ります…!!!
6:45 ごろ目が覚めた。
準備をして、 7 時に朝食を食べに行った。
エレベーターの待ちが長かったので、運動がてら階段で降りた。
早く行ったおかげかそこまで混んでなくてたすかった。
8 時すぎまで暇になってしまったのでここまでブログを書き、 8:20 ごろホテルを出発。
会場
会場に着くと、やっぱりめちゃくちゃ混んでいた。
準備はできていたのでスタッフに話しかけ、中に入れてもらったが入口で立ち往生してしまった。
受付の手前で荷物預かり行列が進路を阻んでおり、どうすることもできなかった。
これで受付締め切りの 9 時過ぎてもさすがに disqualify にはならないよね？と少し不安になった。
数分待って受付を済ませ、荷物置き場へ。
昨日とは違い、コンテストエリアで預かるみたいな感じではないらしい。
荷物整理をしていると through が時計をホテルに忘れた！とか言っていた。
そんな時間はないので、終了後に取り行くか～ということになった。
コンテストエリアに入るため、持ち物チェック (コンテストエリアに持ち込めないものを持ってないかのチェック) を受ける。
紙を束ねていたクリアファイルごと持ち込もうとしていたがダメだったらしく、戻された。
コンテストエリアに入り着席し、配信用カメラに向けてマスコットたちを並べた。
が、コンテスト前にはモニターが置いてある机にはまだ物を置かないでね！と注意を受けてしまった。
どうやら全チーム受付が終わったらしく、例年通りつもいさん作のオープニングムービーが流れる。
9:15 からコンテストスタートとのこと。 気合が入る。
コンテスト
昨日打ち合わせた通り、 through, kAsA が問題文に目を通し、 Asa が環境構築をする。
ユーザーログインして、 DOMjudge 開いて、 VSCodium 開いて、テンプレ作って、 a.cpp - l.cpp まで作成。
9:18。 終わったのでいったん C を 1 分読んでみたがよくわからなかった。
through が D 簡単そうじゃない？と言ったので D を見る。
D
が与えられるので、 なる であって を最大化したいという問題。
の一番上の桁がが 1 なら を、そうじゃなければ を にすればいいよね、ということになった。
サンプルに加えて とか とか試してみてよさそうだったので 9:25 に提出するも、 WA。
ほかのチームもめちゃくちゃペナってたので想定内。
いろいろ試してみると、 のケース違くない？になった。
より がいい。
ということで、 をすべて探索する方向に変更。
サンプルが合わず困ったが、文字列を単に辞書順比較にしていて、文字数を比較していなかったのが原因。
9:36 提出、 WA。
だいぶ困ったが、小さいケースで試してみようと 2 を入力すると無が出力された。
いろいろやってみると 10 以下で無になった。 なんか の構築をミスっていた。
サンプルと 10 以下のケースが通ったので 3 度目の正直を投げると、無事 AC 🎉
9:40。だいぶ詰まってしまった。
E
順位表を見ると、次に通されていたのが E だったので見る。
の豆腐と整数 が与えられるので、同じ大きさのブロックに切って 個以上にしたとき、辺の最大値は？という問題。
同じ大きさのブロックって立方体なのか？となった。
cube とは書かれていたけど立方体の意味あったっけ？とド忘れしたので、まあどうせ立方体だろ！と読み進める。
一瞬 Stern-Brocot 木上の二分探索？持ってないが？？になったが、ほかのチームこの速度でそれやるには早すぎない？というのと、分母が のケースがサンプルに置かれていたので違いそうだと判断。
問題を整理することにした。
w.l.o.g. として答えを としたとき、 で ？？？ 有理数どうすんの？？になって困ってしまった。
あ、でも辺の最大化目指すなら どれかの (整数とは限らない) 約数になってないとだめなのか、となる。
そこで を何分割すれば 個以上になるかを二分探索する方針に。
分割するとき、個数は になる。
これでよさそうだと実装してサンプルを試してみるも、サンプル 2 で合わない。
で が答えなのに が返ってきてしまう。
through がどう？と聞いてきたので説明すると、 だけ分割だとだめじゃない？と指摘を受ける。
実装がめんどくさかったので順列全探索で決め打つ場所を試してみると、なんとゼロ割りで困ってしまった。
コードを読み直してみると、 satulating_mul (飽和乗算) のオーバーフローチェックで起きてしまっていた模様。
などのケースで発生するが、もうそのケースは「もっと細かく分割してね、 NG!」とみなせばいいので continue するようにした。
サンプルが全部あったので投げると AC 🎉
10:17、 19 位まで上がりました。
H
並列して読んでもらっていた H を見る。
のグリッドで -U 字型タイルをうまく配置して、与えられた状態にできるか？という感じの問題。
だとこういうケースでとてもめんどくさいが、 の制約から、 U 字の空いている部分を見たら連続 3 マス以上が埋まっていることはないと言われたので、そこで計算量削減できると考えた。
つまり、 U 字の空き方向候補について、任意の 3 マスを見たときに . があれば、空き候補に加える、ということをした。
そのロジックを through に説明したが、全然伝わらなかったので説明は理解していた kAsA に任せ、実装に集中することに。
U 字の埋まっている部分は 2D 累積和を使えば妥当性を高速にできるよねということで実装。
空き方向の連続 3 マス以上が埋まっていることはないと見抜いた through に、なんで 3 マスしか見てないんだ？と無限に聞かれて同じことを無限に説明するということをやっていた。
空き方向候補が 1 通りならそれで確定して、左上からどんどん置いていくようにした。
実装できたのでサンプルを試すと、セグフォで落ちる。
テンプレでメモしていた -D_GLIBCXX_DEBUG でデバッグしてみると、 sum の取得で困っていた。
すべてをコピペしたせいで累積和の添え字を変え忘れたらしい。
添え字を直した気になっていたが実際には直っておらず、サンプルは WA になって、 printfile するなどして原因を特定するのに少し時間がかかってしまった。
11:03 サンプルがあったので提出すると、 WA。 いったん散歩ついでにトイレに行ってその間に考えてもらう。
戻ってくると、こういったケースでうまくいってないよ、という話になった。
もうすでに使われているマスに overlap して U 字を置いてしまっても yes になってしまう、というものだった。
##### ....# ....# ##### ##### ....# ....# #####
まあこれは実際に置くときに、すでに置いたものと重なってないかをチェックすればいいかとなり、実装。
サンプルやハンドメイドケースも通ったので 11:17 提出、 AC 🎉
J, I
J を見る。
の ICP? からなるグリッドが与えられたときに、 ? を ICP のどれかに変えることで、含まれる任意の の部分を ICPC にできるか？という問題。
最初からダメなケースはダメでよくて、それ以外ならどうするんだ？
valid な は 12 状態しかないからそれで頂点倍加とか？ でもすべての状態を持たないと無理だよなぁ...
十字が定まればそこの長方形は全部定まるなぁ...
bitDP？ これもすべての状態を持たないと無理っぽい...
といろいろ考えてみたが、結局椅子を温め続けた。
I もいい感じの性質が見つかったというので I を任せてみる。. は Alice の勝ちで .., ..., ... は Bob の勝ち、 a....a は Bob、みたいな区間を見つけて評価値をつけていく方針らしい。 (あまり理解してない)
時間もないのでサンプル・ハンドメイドケースがあったらどんどん投げる方針に。
結局通らず。
一瞬 A だけ読んでみたがいい方針が思いつかず、 J に戻るも解けず。
コンテスト終了
お疲れさまでした～
コンテスト終了後、すべての荷物を持って移動しろと言われたが、 "すべての荷物" がコンテストエリアの荷物を指しているのか、荷物置き場の荷物も含めるのかよくわからずウロウロしていた。
Closing Ceremony 会場に行くと、解説がアップロードされていたので見る。
J は簡単な必要十分条件があったらしい、難しく考えすぎたかも...
審判団想定難易度は DEHJICALBGFK とのこと。 凍結前は HJ に崖があった。 うちらもその崖から落ちた。
すっかりやるのを忘れていたが、凍結後全部提出するやつをやっているチームが 2 チームあった。
どっちも全部ペナがついていたので CE じゃないんだ... と思った。 (CE でもペナになった？ そんなことない気がする)
結果は 43 位 / 64 チーム。
去年 47 位 / 55 チームだったのでまあ上がったが IJ は通しておきたかったな～という気持ち。
懇親会
いろいろスポンサーブースを回った。
Huawei ブースで昨年同様バッグをもらったり、 JetBrains ブースでバッジをもらったりした。
モノグサブースでは tsutaj さんから話聞いたり Forcia ブースでは問題に挑戦したりした。 問題は期待値を求める問題だが、上限と下限が分かったので、適当にその真ん中を答えたら正解してしまった。
その後 Ryoga.exe, through, kAsA で固まってしまった。
through と kAsA はもういいかな～と言って先に帰る (+ ホテルに時計を取りに行く) ことになった。
1 人で飲食していると、ケータリングスタッフの人からアンケートに回答して Google Maps にレビュー書いたらお菓子あげるよ！と言われたが、これって ダメなやつじゃないか？と思ったので一応レビューは書いてすぐ消した。
明日もあるので閉場より少し早めに帰路についた。
撤退、ありがとうございましたー！
帰路・帰宅
電車内では少しこのブログを書き進めた。
E 問題くらいまで書いたところで PC バッテリー切れ。
その後目を閉じて (寝れず)、最寄り駅に到着。
本日、Maximum MastersがICPCアジア地区横浜大会に出場し、
全63チーム中43位という結果をおさめました!!
先輩方の意志を受け継ぎ、来年はより沢山のチームがこの舞台に立てるように、新生競プロ班皆で頑張ってまいります✨
出場したメンバーの皆さん、本当にお疲れ様でした!!!
いよいよ明日、ICPCアジア地区横浜大会のコンテスト本番が行われます!!!
我がサークルからは、7月の厳しい予選を勝ち抜いた、
『Maximum Masters』が参加します!!
Maximumが誇る最強チームが、今年もこの大舞台へ挑みます。
メンバーの健闘を心より祈ります…!!!
Maximum 広報担当に「43 位！」とだけ丸投げしたらこれを書いてくれた。
来年はコーチか？ (コロナ特例あれば) 選手か？ 悩むな〜
新生競プロ班皆で頑張ってまいります✨
とのことで、来年はコーチが濃厚になってきた。
一度でいいからコーチをやってみたい気持ちもあるし、 6 回も出場してしまっていいのか？というのもある。
ただコロナ禍特例が有効になった場合にはもしかしたら数合わせで出るかもしれないので、念のため jag-icpc.org/?Join はしばらく先延ばしに。
帰宅し、昼食を夕食として食べた。
消費期限 17 時と書かれているが、うちはそんなの特に気にしてないので普通に食べた。
夕飯
消費期限？気にしません
その他
何か言及されてないかな～と帰ってから配信を見てみた。
今年は ふつうの実況 (Broadcast)に加えて Multi Camera Streamなる配信があったらしい。
Broadcast は H を通したときに映ったくらい。
Multi Camera Stream はすべてのチームを巡回しているらしい。
コンテストエリアに入り着席し、配信用カメラに向けてマスコットたちを並べた。
の努力 (?) もむなしく、かろうじてメリンちゃんの耳しか映っていなかった。
が、 ICPC 公式 Twitter ではマスコットたちのポストで撮られていた上、 chokudai さん本人含めいろんな人に言及されていてうれしかった。
chokudai さんに去年メリンちゃんを布教したのに覚えていないようでかなしい... (大量の人の写真撮影に応じていらっしゃったので仕方ない)
1 枚目、うちです
本大会ではマスコットの持ち込みが認められており、ぬいぐるみやアクスタなど大小様々なものが見られます。
1枚目のチーム応援したいけどどこだかわからんw
本大会ではマスコットの持ち込みが認められており、ぬいぐるみやアクスタなど大小様々なものが見られます。
これにて (たぶん) (選手として) 最後の ICPC 参加記を締めくくります。
来年以降の Maximum の活躍を乞うご期待！
みなさんお疲れさまでした + ありがとうございました～～！