ICPC 5 度目、ついにラストイヤーです!
開始前
チーム決め
一昨年・去年に引き続き、 through, kAsA02 と 3 人でチームを組みました。
チーム名は「Maximum Masters」。
みんな M1 なので Masters です。
早生まれ + コロナ禍特例で、自分は来年も出れると思っていたんですが特例が廃止されるらしく、今年でラストイヤーです。
ほか 2 人は早生まれではないので、みんなラストイヤーです。
ちなみに埼玉大学からは計 8 チーム参戦です。
【チーム名】
Maximum Masters
【メンバー】
a01sa01to (M1)
through (M1)
kAsA02 (M1)
【意気込み】
最後の挑戦、最高の仲間と、悔いなく戦い抜く。
これまでのすべてを、この 3 時間に懸ける。
終わりじゃない、集大成だ。
信じるのは、自分のコードと、隣の仲間。
我々の最終章、ここから始まる。
ICPC、埼玉大学からは 8 チーム出ます!
私は @through__TH__ , @kasa_ame__ と Maximum Masters で出場します!
ついにラストイヤーです、ぜひぜひ応援してください!!
意気込みとして
最後の挑戦、最高の仲間と、悔いなく戦い抜く。
これまでのすべてを、この 3 時間に懸ける。
終わりじゃない、集大成だ。
信じるのは、自分のコードと、隣の仲間。
我々の最終章、ここから始まる。
が書かれているんですが、実は through が Gemini に投げて生成されたスローガン 5 個をそのまま concat しただけです。 (3h が 5h になっていたので、さすがにそれは直した)
準備
一応 Maximum の活動で何回か過去問を解いていました。
また、最近 VSCode の Copilot Integration が本格的になってきているので設定を変えないとまずい!ということで ICPC 用の Profile を作成し、拡張機能を必要最小限に + Copilot 無効化をしておきました。
キーボードショートカットもいろいろ設定されていたので、事故らないように Chat とか Copilot とか書かれているものはすべて消しておきました。
Maximum 向けに設定の Gist を上げたので、一応こっちにも置いておきます。
https://gist.github.com/a01sa01to/af5aff9eb2a74147abd47fc6969526b2
拡張機能は、
- C/C++ (
ms-vscode.cpptools
) - Better C++ Syntax (
jeff-hykin.better-cpp-syntax
) - GitHub Theme (
GitHub.github-vscode-theme
) - Material Icon Theme (
PKief.material-icon-theme
) - Trailing Spaces (
shardulm94.trailing-spaces
)
の 5 つだけ。 もちろん Copilot は入れてないし、これだけで十分。.clang-format
も用意しておき、 Format on Save を有効にしておきました。
今回は AC Library の expander.py
と oj-bundle
が使えるとのことで、 ACL と expander.py
を作業ディレクトリにコピーしておきました。
いつも通り Asa の PC を使うことになったので、コマンドエイリアス群をいろいろ整備しました。
具体的には、 template.cpp
を
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) inline void solve() { int n; cin >> n; if (n == 0) exit(0); vector<int> a(n); rep(i, n) cin >> a[i]; } int main() { cin.tie(nullptr)->sync_with_stdio(false); while (true) solve(); // solve(); }
こんなかんじで書いておいて、 funcs.ps1
に
function global:c() { param ($file) Write-Output ">>> Compile $file.cpp" g++ -x c++ -g -O2 -std=gnu++20 -static -o "a.exe" "$file.cpp" -lm if ($LASTEXITCODE -ne 0) { Write-Output ">>> Compile Error" return } Write-Output ">>> Compile Success" } function global:x() { param ($file) Write-Output ">>> Create $file.cpp" Copy-Item template.cpp "$file.cpp" code "$file.cpp" Write-Output ">>> Create Success" } function global:t() { Write-Output ">>> Test" .\a.exe if ($LASTEXITCODE -ne 0) { Write-Output ">>> Test Error" return } Write-Output ">>> Test Success" } function global:ti() { Write-Output ">>> Test (input)" Get-Content stdin.txt -Raw | .\a.exe if ($LASTEXITCODE -ne 0) { Write-Output ">>> Test Error" return } Write-Output ">>> Test Success" } function global:to() { Write-Output ">>> Test (output)" .\a.exe 1> stdout.txt 2> stderr.txt if ($LASTEXITCODE -ne 0) { Write-Output ">>> Test Error" return } Write-Output ">>> Test Success" } function global:tio() { Write-Output ">>> Test (input, output)" Get-Content stdin.txt -Raw | .\a.exe 1> stdout.txt 2> stderr.txt if ($LASTEXITCODE -ne 0) { Write-Output ">>> Test Error" return } Write-Output ">>> Test Success" } function global:ba() { param ($file) Write-Output ">>> Bundle ACL" python expander.py "$file.cpp" if ($LASTEXITCODE -ne 0) { Write-Output ">>> Bundle Error" return } Write-Output ">>> Bundle Success" } function global:bl() { param ($file) Write-Output ">>> Bundle My Library" $path = "\\path\\to\\my-library" oj-bundle -I $path "$file.cpp" > bundle.cpp if ($LASTEXITCODE -ne 0) { Write-Output ">>> Bundle Error" return } while ($true) { try { # パスを置換 (Get-Content bundle.cpp) -replace [regex]::Escape($path), "my-library" | Set-Content bundle.cpp # コメント削除 (Get-Content bundle.cpp) -replace "// .*$" | Set-Content bundle.cpp # 空白のみの行を削除 (Get-Content bundle.cpp) -replace "^\s*$" | Set-Content bundle.cpp # 行末スペース削除 (Get-Content bundle.cpp) -replace "\s+$" | Set-Content bundle.cpp # 空白行削除 (Get-Content bundle.cpp) | Out-String -Stream | Where-Object { $_ -ne "" } | Set-Content bundle.cpp break } catch {} } Write-Output ">>> Bundle Success" }
こう書いておきます。
これを PowerShell のターミナルで読み込むことで、例えば x a
とすればテンプレートから a.cpp
を作成し、 VSCode で開いてくれます。c a
とすれば a.cpp
をコンパイルしてくれ、 t
とすれば実行できます。ba a
で expander.py を実行し、 bl a
で oj-bundle を実行してくれます。
極力タイプ数を減らすためにこんな形にしました。
前日の練習で整備して compile a.cpp
とか cp-test
とかやっていたんですが、タイプ数多いな... ということで c a
, t
とかに変更。
一応自分で忘れてはいけないので (funcs.ps1
を見ればわかるが、時間短縮のため)、使い方を書いたドキュメントもプリントしておき、準備万端。
模擬
JAG 模擬、 team001 でびっくり
JAG おつかれさまでした~
5 完 32 位、本番でもこのくらい行きたいね
こちらも例年通り、 JAG の模擬国内予選にも出た。
なんか申し込みが一番早かったらしく、 team001
が割り当てられた (!?)
順位は 5 完で 32 位 (現役チーム中 20 位)。
DOMjudge は横浜 (+ Maximum の活動で一時期使っていた) で慣れているので、 DOMjudge の使い方は問題なし。
模擬でわざわざ集まるのも...となっていたので、 Discord で VC つなげてやった。
自分は前述の Profile を使って一応本番と同じ環境 (コマンド群は未整備) でやりました。
A
なんか VC でグダグダしてたら始まった。
誰が解く~?とか話してたら速読力 + 実装力のある Asa が A を担当したほうがいいよね、ということになり実装。 (まあ例年通り)
mex をやればいいことが分かったのでやるだけ。
一応 mex のライブラリはあるものの、それを出すほどでもないなと思い、適当に実装。
先頭に 0
と末尾に 1e9
を追加するとただの隣接比較で「a[i] + 1 != a[i + 1]
なら a[i] + 1
が mex」みたいなコードを書いて提出。
問題なく AC 🎉
最初グダってたので 0:04 でした。
B
他メンバーが先に読んでいたので、説明を受ける。
まあ Greedy でいいのではということで実装。
適当に先頭のフライトからスタートして、その飛行機を追跡していくことを繰り返した。
0:11 AC 🎉
C
through が先に読んでいて考察も終わっていたので、 B を AC 後に through が実装。
0:17 AC 🎉
D
C を実装してもらっている間に Asa, kasa が読む。
先頭から 2 文字のペアで聞いて行けばいいのでは?となる。? 1 2
で 1
が返ってきたら ()
が確定して ? 3 4
から再スタートし、 0
が返ってきたら ((
が確定して ? 2 3
から~というもの。
でも kasa が挙げた ((()(())))
のケースで困ってしまったので、仕切り直し。
括弧の深さで対応させていって stack で管理すればいいのでは?と思いつき、説明するより書いたほうが早いなと判断し、実装。
int main() { int n; cin >> n; string ans = "("; stack<int> st; st.push(1); int idx = 2; while (idx < n) { assert(!st.empty()); cout << "? " << st.top() << ' ' << idx << endl; int res; cin >> res; if (res == 1) { st.pop(); ans += ')'; if (st.empty()) { ans += '('; st.push(++idx); } } else { st.push(idx); ans += '('; } idx++; } while (!st.empty()) { ans += ')'; st.pop(); } cout << "! " << ans << endl; return 0; }
サンプルも通ったし先ほどのケースも通ったので提出。
0:37 見事 AC 🎉
E
through が先に読んでいたので説明を受ける。
が、あまりよくわからなかったので細かい実装は through に投げることにして、自分はただやるだけの構文解析と modpow の実装を担当した。
実装してもらっている間にめんどくさいケースを考えることに。
if_x_then_if_x_then_1_else_2_else_3
: 4if_x_then_if_x_then_1_else_2_else_if_x_then_3_else_4
: 5
を挙げ、なんかよくなさそう。
見てみると変数の状態がうまくできてなさそうだったので、そこを直してもらい、提出。
1:27 AC 🎉
F, H
なんか読んでいくと見るからに DP だよね~となり、遷移を考える。
dp[i][j][k]
: i 文字目まで見て、A
をこれまでに j 個使ったときの (B 使用数 max, prev state)。 k は末尾 2 文字の状態。
として through が書いてみる。
その間に Asa, kasa で H を見てみる。
最初の列は 0 じゃなきゃダメだよね~とか、実は全行同じ配置で行けるんじゃね? ( を考える) とか話していたが、全然見通しが立たず F に戻る。
through が書き終わったが、 WA。
時間がないのでどんどん投げちゃえ~ (負荷をかけてすみません...) となったがダメらしい。
自分も別で実装してみたものの、復元がうまくいかずダメっぽかった。
ここで時間切れ。
後々解説を見ると後ろから B の個数を状態で持つ DP だったらしく、なるほど~~~になっていた。
当日
リハーサル
DOMjudge、 ACL を include して展開してない main.cpp と ACL の本体を提出したら AC 出た、こんなことできるんだ...
前日に、
DOMjudge って複数ファイル提出できるけどさすがに C++ だとできないよな...?
#include "foo.hpp"
とかして main.cpp と foo.hpp で提出すると CE になりそう?
とか思ってリハーサル P 問題 (数列が与えられ、 max を求める) で無理やり ACL の modint を使って試してみたところ、なんか AC した。
当然 include path は適宜変更しているが、複数ファイル想定されているとは思っていなかったのでびっくり。
で一応、かなり上に書いたコマンド群とかに慣れてもらうため through, kasa に何問か実装してもらう。
作戦も去年と同じく、
- Asa が A, B くらいを読みながら実装し、 kasa, through はそれ以降を先に読み進めて考察
- 実装は基本的に Asa が担当し、 2 人はコーナー探しとかコードレビューとか
- 実装・考察に時間をかけてもいいから、ペナは極力出さない
でいいよね、ということを確認。
リハーサル招集されて時間が余ったのでマリオカートワールドをしています (?)
ICPC ぞい! 横浜行くぞ!
どうせ暇になるだろと予想していたので Switch 2 を持ち込み、マリカーをしていた (???)。
さすがによくないだろと思い 30 分くらいでやめ、その後は寿司打でタイピングしたり雑談したりしていた。
いざ開始 💪
A
テンプレはこれ。
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) inline void solve() { int n; cin >> n; if (n == 0) exit(0); vector<int> a(n); rep(i, n) cin >> a[i]; } int main() { cin.tie(nullptr)->sync_with_stdio(false); while (true) solve(); // solve(); }
開始してすぐ問題を開き、瞬時に掛け算表と が見えたので完全に理解した。
しか与えられないらしいので泣く泣く (?) a
の入力を削除...
ふつうに二重 for を書いて、一応テスト。
int でオーバーフローしないことを確認し提出、 AC 🎉
0:01 でした。
すでに数チーム通していて早すぎ!
B
これもなんとなく理解。
まあどれくらい overlap させるかを全探索すればよさそう~となり、適当に実装。
string ans = ""; for (int i = n - 1; i > 0; --i) { if (s.substr(n - i) == s.substr(0, i)) { ans = s.substr(n - i) + s; break; } } cout << ans << '\n';
こんな感じに適当に実装しすぎてサンプルが合わないのでデバッグし、修正。
(ans = s + s
で初期化する / ans = s.substr(0, n - i) + s
にする)
サンプルが通ったので投げて AC を獲得 🎉
0:07 でした、時間かけすぎ!
C
少し C を読んでいた through から説明を受ける。
まあ大きいけど算数やるだけで、まず平日は でいいよねと through と確認。
与えられた追加の休日も、
- 範囲内か ()
- すでに休日か ()
をチェックして、「範囲内 かつ 休日でない」ならデクリメントしていくということで実装。
が、サンプルが合わない。
確認してみると、「 は同じ値が 2 回以上含まれることがある」とのこと。
ざっくりしか読んでいなくて「 は同じ値が 2 回以上含まれることが ない」と勘違いしていたので、 sort + unique で重複削除。
サンプル通ったので投げると AC 🎉
0:13 でした。
もう 15 分近く経過してるの!? と少し焦る。
E, D
この辺で問題文の印刷が届く。
D を一目見てやりたくね~~~と 放棄して、 kasa に考察を投げる。
自分はその間に E を読んでみることに。
こっちのほうが簡単そうだな~と思い、少し考察をすると、 最終搭乗期限 - 移動時間 がタイトなものに向かっていったほうがよさそうだと考える。
実装はどうしようかな~と片隅に置いておいて、 D に戻る。
D は相変わらずめんどくさいな~となり、 kasa もいい感じの実装があまり出ない様子。
長い辺のほうを見れば正方形の長さ求まらないかな~と言い残してほんとか?をする。
E は through が制約から多始点 BFS で行けるのでは?となり、考察を教えてもらい Asa が実装を始める。
E
次から次に必要そうなデータが出てくるので実装しながら考えてみる。
まあまず「 に行くときに の次はどこに向かうのがいいのか?」というルーティングテーブルがあったほうがいいかとなり、 BFS で適当に実装。
辺集合だけを管理する実装をしていたので、隣接リストも構築することに。
map<pair<int, int>, int> edges; vector Graph(n, vector<int>()); rep(i, n - 1) { int p, e; cin >> p >> e; --p; edges[{ p, i + 1 }] = edges[{ i + 1, p }] = e; Graph[i + 1].push_back(p); Graph[p].push_back(i + 1); } vector table(n, vector<int>(n, -1)); rep(i, n) { queue<int> q; vector<int> dist(n, 1e9); dist[i] = 0; table[i][i] = -1; for (int u : Graph[i]) { table[i][u] = u; dist[u] = 1; q.push(u); } while (!q.empty()) { int u = q.front(); q.pop(); for (int v : Graph[u]) { if (dist[v] > dist[u] + 1) { dist[v] = dist[u] + 1; table[i][v] = table[i][u]; q.push(v); } } } }
そして多始点 BFS をして、最短距離を求める。
どこが始点かも持っておいて、 (最終搭乗期限 - 移動時間 - 現時刻) が最小のものを選ぶ。
もし (最終搭乗期限 - 移動時間 - 現時刻) がマイナスなら不可能で、そうじゃなければルーティングテーブルから行くべき場所を求めていく。
// 入力 + ルーティングテーブルの処理 // ... vector<int> ans; vector<int> visited = { 0 }; vector<bool> visflag(n, false); visflag[0] = true; while (visited.size() < n) { queue<pair<int, int>> q; vector<int> dist(n, 1e9); vector<int> st(n, -1); for (int x : visited) { q.push({ x, x }); dist[x] = 0; } while (!q.empty()) { auto [u, from] = q.front(); q.pop(); for (int v : Graph[u]) { if (dist[v] > dist[u] + 1) { dist[v] = dist[u] + 1; st[v] = from; q.push({ v, from }); } } } tuple<int, int, int> ans = { 1e9, -1, -1 }; rep(i, n) { if (visflag[i]) continue; assert(st[i] != -1); int nxt = table[i][st[i]]; int e = edges[{ i, nxt }]; if (get<0>(ans) > e - (dist[i] + (int) visited.size() - 2)) { ans = { e - (dist[i] + (int) visited.size() - 2), i, st[i] }; } } auto [minim, to, sta] = ans; if (minim < 0) break; int ins = table[sta][to]; visited.push_back(ins); visflag[ins] = true; } if (visited.size() != n) { cout << "no" << '\n'; } else { cout << "yes" << '\n'; rep(i, n - 1) { if (i) cout << ' '; cout << visited[i + 1] + 1; } cout << '\n'; }
実際にはいろいろバグらせてデバッグしてたり、 through のやりたいことがあっているのかを確認しながら実装してたりした。
サンプルも通っていそうなので投げちゃえ!と投げると無事 AC 🎉
1:04 で時間がかかりましたが、ペナがないのはかなり心理的負担が少なくてうれしい。
D
E を実装している間に through, kasa の間でかなり考察が進んできたようなので、聞く。
- まず、ランレングス圧縮をする。 左端・右端を除いた部分から正方形の長さがわかる。 もし異なるものがあれば、矛盾。
- これを縦横でやる。
- これで長さがわからなければ一意に特定できず、そうでなければ矛盾なく特定できる。
これをひとまず実装してみる。こんなかんじ。
は求めた正方形の長さ。
vector Grid(h, vector<char>(w)); rep(i, h) rep(j, w) cin >> Grid[i][j]; int n = -1; rep(_, 2) { // yoko rep(i, n) { vector<pair<char, int>> rle(1, { Grid[i][0], 0 }); rep(j, n) { if (rle.back().first == Grid[i][j]) rle.back().second++; else rle.push_back({ Grid[i][j], 1 }); } if (rle.size() >= 3) { for (int k = 1; k < rle.size() - 1; ++k) { if (n == -1) n = rle[k].second; else if (n != rle[k].second) { cout << -1 << '\n'; return; } } } } // tate // 同様に } if (n == -1) { cout << 0 << '\n'; } else { cout << n << '\n'; }
が、サンプルが合わない。 全部 0 になる。
よく見ると、 rep(i, n)
としていた。 おばか。
ちゃんと rep(i, h)
と rep(j, w)
に直すと、サンプルの 1 ケースが通らない。
具体的には、
4 3 #.# #.# #.# #.#
で -1
を出力すべきところを 1
と出力してしまう。
through が「ランレングス圧縮の左端・右端から を求められはしないが、矛盾のチェックはすべき」と指摘してくれた。
例えばこの例では、横に見たときに が確定するが、縦に見たときにはランレングス圧縮すると (#, 4)
のようになる。
なら矛盾するので、これはチェックすべきだった。
あと怪しいケースとして、 kasa が
2 6 ....## ###...
を挙げていた。-1
なのに 0
が出力されてしまっていたが、これは縦・横それぞれのランレングス圧縮の長さパターンが一致するかチェックすればよくない?と気づき、それを組み込むことに。
一応コードを確認してもらって、 through, kasa に挙げてもらった怪しいケースも一通り通ったので投げてみると無事 AC 🎉 1:23。
ペナ出しているチームが多い中、ペナ出なかったのはかなり大きい。
F
みんなで一斉に読み始め、いち早く自分が理解し、説明する。
回の操作ができて、しかも最小化する必要がないというのがポイントだと思った。
操作をよく見てみると、
A
: 最初のa
と、それ以降で最初のb
が swap されるB
: 最初のb
と、それ以降で最初のa
が swap される
ということに気づく。
そこからまあ (各文字の出現回数が一致) が自明な必要条件にはなるよねぇとなる。
ここでパッとひらめいた、 A
を何回も繰り返すと b...ba...a
にできそう。
前からどんどん b...ba...a
の形になっていくので、後ろから揃えていくのがよさそう。
これを 2 人にざっくり説明して、実装はできそうなので G に進んでもらう。
まあ制約が小さめなので愚直にシミュレーションしていく。
A, B の操作を逆にして無限ループにハマったが直し、サンプルが通ることを確認する。
提出すると、 AC 🎉 1:53。
こういう構築問題、 WA になるとなんもわからなくなりそうなので通ってよかった。
G, H
G は kasa から問題を教えてもらう。
幾何嫌だなぁと思いつつ、少し考察してみる。
なんかオイラーの多面体定理 が思い浮かんだので一応共有してみるが、 がわからないので困る。
kasa がグラフに帰着できないかな~と平面的グラフを書き出したので、自分が研究室で学習していた内容を引っ張ってくる。
偶然にも研究室で読んでいる本の日訳 (Markdown) がローカルにあったので、それを見ながら考えてみるも、あまりいい方針は見つからなさそうだった。
かなり脇道に逸れた気がする。
一応 H も読んでみて少し考えはしたが G に戻ることに。
いろいろ試してみると、平行な辺を結ぶと面が四角形になって、そうじゃなかったら三角形 2 つになるので、「2 つの多角形の辺ペアをどれだけ平行にできますか?」に言い換えられそうだな~と気づく。
がどうすればいいんだ... と詰まり、始点ペアを 個全探索しても間に合うのかな~と思ったが、サンプル 1 で困る。
through が のケースは少しずらせば絶対平行にならないように作れるから考えなくていいと指摘してくれたので、少し実装をしてみる。
が、すでに残り数分まで迫っており、もう実装しきれないやとなった。
この時点で 30 位台かつ埼大内最上位だったので予選突破はほぼ確実だろうということで、雑談タイムに入ってしまった。
終了
ICPC お疲れさまでした~!
6 完 40 位!通ったかな~
ICPC2025 Prelim
A: はい
B: 実装めんどい!
C: さんすう
E: 多始点 BFS して適当に時間タイトなほうから
D: いい感じに縦横ランレングスすると矛盾が見つかる
F: 個数が一致すればいける、 A をたくさん呼べば b...ba...a ができて、後ろから合わせる
ICPC国内予選、6完40位で横浜進出!やった~
ICPC 6完 40位でした!
お疲れさまでした~ 6 完 40 位でした。
終了後 rian さんの拡張機能を入れた icpcsec 側の順位表から確認し、無事横浜に行けそうだと確認。
全完チームが多すぎて、全完予選落ちチームが現れる大波乱になるんじゃないかと思ったけど、そんなことはないらしくよかったねとなる。 (東科大がホストじゃなかったら発生していたらしい、そんな)
ラストイヤーで無事横浜行けるようでよかった~!
今年の国内予選は去年一昨年と比べてめちゃくちゃチーム戦をした感じが出ていてよかった。
Regional は今年こそ成績残すぞ!
ICPC国内予選お疲れ様でした!
Maximum からは Maximum Masters が6完!
どのチームも健闘しました…!
Yokohama を見据えて精進していきます💪✨
応援よろしくお願いします!
打ち上げ
今年も去年と同じく、大学近くの某飲食店で打ち上げ。
例年の店は工事中らしく、別の店に。
"デザートは別腹" を担当しました
✅ ホテルを予約した
いつもホテルがなくなるので、打ち上げ中に Regional のホテルを予約した。
例年同じところの同じような部屋を予約しているので、今年も同じように予約...
打ち上げ終了後、 1 駅ごとに数分停車するくらいには埼京線がトンデモ遅延していて、宇都宮線の終電に間に合うか心配だったが、なんとか帰宅した。