Asa's Website

ICPC2024 Regional 参加記 (a01sa01to 視点)

icpccompetitive programmingparticipation log

作成日 / 最終更新日

Table of Contents
準備Day 1会場まで会場リハーサルチーム紹介ホテル (1)中華街ホテル (2)Day 2ホテル (3)会場着コンテストAB (1)I (1)B (2)E (1)B (3)E (2)C (1)K (1)C (2)K (2)結果懇親会まとめおまけ

ICPC2024 Regional に進出しました！

ICPC2023 はあと 3 チーム上行っていれば...のところで予選落ちしてしまったんですが、今年は 31 位と割と余裕をもって進出しました。
予選当日にホテルを予約していざ参戦。

through, kAsa と一緒にチーム「executive is deprived」で出場。
去年「Maximum-executive」(Maximum 執行部) で、世代交代したので「executive is deprived」(執行部剥奪) です。
2021 の「seica is gone」にも倣ってます。

ICPC2024 Prelim や ICPC2022 Regional の記事も併せてどうぞ。

準備

Google 創業祭セールで Pixel Watch 3 (5 万くらい) を分割 (月 5,000 くらい) で買ったが、どうやら分割でもクレジットカードの枠は残りの金額すべて (5 万分) を圧迫するらしく、これはまずいと前月に完済手続きをした。分割にした意味...
学生として情報登録されていて、カード枠が引き上げられないらしい。 カス！

Regional に向けた準備としては、何もしてない。というか、何もできなかった。
ISUCON やら研究やらで忙しくて、チームでまとまった時間が取れなかった。。。

今週末 ICPC だ～～となっている中、コーチの先生から風邪気味で休むという連絡が。かなしい。

前日に ICPC2024 Yokohama 参加者のリストが作られていたので、すかさずピン留めした。

まあ何とかなるか～と思いつつ、当日を迎える。

Day 1

いくぞ！

会場まで

服装: 一目でわかるように MHC T シャツといろいろネームプレート。
その下に長袖のシャツを着ていた。 2022 で寒いのは経験済み。
オンサイトということで弊学マスコットキャラクターのメリンちゃんぬいぐるみを持参。

電車: through と路線が同じなので、 Asa の最寄り駅で合流。その路線で横浜まで行けるので、 kAsA も乗り換えで合流した。

昼食: 横浜駅ルミネのマルモキッチンというお店で海鮮出汁茶漬けを食べた。おいしかった。

会場

会場着

周りを見渡すと他大学のチームが Maximum-Cup で配布した埼玉大学クリアファイルを使っていてくれてうれしかった～
ちなみに弊チームのチーム紹介はこんな感じ。

  __  __    _    __  _____ __  __ _   _ __  __
 |  \/  |  / \   \ \/ /_ _|  \/  | | | |  \/  |
 | |\/| | / _ \   \  / | || |\/| | | | | |\/| |
 | |  | |/ ___ \  /  \ | || |  | | |_| | |  | |
 |_|  |_/_/   \_\/_/\_\___|_|  |_|\___/|_|  |_|

    Programming Circle @ Saitama University

Team: executive is deprived

Members:
- Asa (X, AtCoder: a01sa01to)
- through (X: through__TH__, AtCoder: through)
- kAsA (X: kasa_ame__, AtCoder: kAsA02)

Origin of team name:
  ICPC2021: "seica is gone"
+ ICPC2023: "Maximum-executive"
+ We've been eliminated executive authority
    by generation change

Maximum の宣伝もかねて Maximum のアスキーアートと、チーム名の由来などを入れておいた。
ちなみによく画像を見てみると、ダブルクォーテーションの部分がなぜか 2 つ連続されています。 (" が "" になってる)
これは仕様ですか？

説明受けてリハーサルへ

リハーサル

開始時間タイマーが 1h とかあってめちゃくちゃ待たされるやーんとか思ったら急に時間短縮されて開始した。

事前の打ち合わせでまあエディタは VSCodium でええやろ～ということで、 VSCodium で開始。
今年は DOMJudge ログインがワンクリックでできて便利。
F12 を押したい衝動に駆られていたが、抑える。

問題はこんな感じ。

  • A: ただの総和を求める問題
  • B: Hit and Blow を interactive で解く問題
  • C: 2022 A (サンタがプレゼント届けるやつ)
  • D: 2021 A (球体の union 部分の体積求めるやつ)

全部見おぼえあった問題なので、 A は kAsA に、 B は through とペアプロした。
C は区間スケジューリング問題なのは知っていて自分が担当。
なぜかめちゃくちゃバグらせ、なんとか AC。
C 解いてる間に D も 2 人に丸投げし、包除むずくね！？とか言っていたところに「問題をよく読みましょう」と助言して、 2 つしか重ならないよということに気づかせた。 US 配列に慣れてない through が実装し、 AC。
clar として「B に interactor のサンプルがないよ！ - 直しました」、「エディタの設定は保存されますか？ - 使い方資料をよく見てね」と「無をプリントしてメモ用紙にしてもいいですか？ - はい」(その後白紙 10 枚が配られることを知る) を投げた。

チーム紹介

しばらくしてチーム自己紹介。何を話すか吹っ飛んでチームメンバー紹介と頑張ります～くらいしか言ってない。
チーム紹介スライドはこんなかんじ。結構こだわった。
コメントに Open more onsite contests! I'm starving!! とか書いたけど starving ではないな...
でもまあもっとオンサイト生やしてください

Asa
Asa
@a01sa01to
·Follow

応援してね〜！！

埼玉大学 プログラミングサークル Maximum
埼玉大学 プログラミングサークル Maximum
@Maximum03400346

いよいよ明日、ICPCアジア地区横浜大会のコンテスト本番が行われます。 我がサークルからは、7月の厳しい予選を勝ち抜いた 『executive is deprived』が参加します！ メンバーから 「暴れ回ってきます。 Maximumの名を轟かせてきます。」 と、強い意気込みをいただきました！ 健闘を祈ります！

Image
6
Reply
Read 1 reply

ホテル (1)

チーム紹介は 18 時までかかる想定だったのに 17:10 くらい。 やっぱりチーム紹介 30sec / team も使わなくない？ とりあえずホテルに向かいます。
ホテルは 2022 と同じスーパーホテル。わかりやすいところにあって近くてうれしいね。
1 人 14000 円くらい。 IISF からの補助が 7000 円だったのでうーん... 通るかわからないけど大学に補助申請してみることにする。
チェックインのときにほかの ICPC チームもいくつかいて、やっぱりここにするチーム割といるんだな～と

ホテルは 2 部屋が中でつながってるタイプの禁煙ルーム。
そのことを数日前に伝えると

kAsA
🚭 !?
過酷な二日間になりそうですね

というメッセージが返ってきた。ノーコメントで

ベッドは 2 段になっていて、みんな下がいいらしいのでじゃんけんをして負けた kAsA が上に。 Asa | through & kAsa という部屋割りに。

部屋割りを決めるなり Wi-Fi + VPN に接続。が、隣の部屋から「繋がんないよ～」と悲鳴が。
同じ SSID なのに、部屋をまたぐとなぜかつながったりつながんなくなったりする。これはもうどうしようもできないので Wi-Fi が必要なときは Asa 部屋を使うことで合意。

中華街

18:50 ごろご飯を探しに中華街へ。
やっぱりホテルから徒歩 1 分で中華街の門にいける立地、なに？ (褒め)

kAsA がホテルのエレベーター内で急遽探してくれたお店へ行ってみると、高級コース中華料理店だったことが判明。
そこで近くにあった龍翔記というお店へ。
食べ放題で色々食べた。最後のほうみんな苦しくて押し付けあう状況になってしまっていてよくないなぁとなった。
ちなみに 2022 の参加記を見てみると、食べ放題で 2000 円弱だったらしく、今回は 3000 円強だったのでうーむになっていた。
しかも当時も食べ過ぎて苦し～～～になっていたので、歴史は繰り返すものだなぁと

ホテル (2)

20:30 ごろホテルに帰還。
ふと机の上に置いていた、ホテルから渡されたアンケートの紙を見てみると中華街のお店の 10% 引きクーポンがあり、こっちでよかったねという話に。渡されたものはよく見ましょう (反省)

そろそろ ABC なのでみんなで出るか～という流れになっていたが、 Wi-Fi の件もあり 3 人 1 部屋は狭すぎて、しかも次の日の朝が早くておふろの待機列ができるとよくないので、問題だけ見ておふろにすることに。

ABC ぞい！
A - E をざっと読んで、 10 分くらいでなんとなく方針がわかった。実装はしてないので正しいかはわからないけど、解説を見た感じあってそうだった。
F を見てすぐに思いつきそうになかったので、おふろで考えることに。
やっぱりユニットバスよくわからんし狭いし苦手だなぁになっていた
なんとなく解法が浮かんだところで体も温まってきたので上がる。
着替えやらドライヤーやらをして、 22 時くらい。
ABC 出なくてもええやろとか思ってたけど、せっかくなので賞金ガチャに参加するため、 A で AC を獲得。

through が岩井星人並みに「なんで通らんねん！？」とキレ散らかしていた (見てておもしろかった) 1 ので、 F を実装してみることに。
long double で計算して 3 WA / 27 cases が出たのでどうせ誤差だろうなぁということで、できるだけ整数上で計算するように変更。
すると 19 WA になってしまったので、よく見てみるとオーバーフローをしていたことに気づく。修正して AC を獲得し、撤退。

Tweet not found

The embedded tweet could not be found…

Maximum では ABC 後に感想会をしているので参加してみたが、 through はまだ F を通せずキレていたし自分は全然コード書いてない + through の解法に助言をしていたので聞くだけになっていた。

その後も雑談したりとか 22 日の streak もつなげたりとかして、就寝。 24:30 くらい。

Day 2

ホテル (3)

あまり深い眠りにはつけず。完全に起き上がったのは 7 時くらい。
着替えて solved.ac の streak をつなげておきます。
それとなーく 2 人が起きてきた。
問題を解き終わったところで朝食に向かいます。

07:30 くらい。朝食会場はふつうに混んでいて困った。
寝る前に、明日朝食 8 時くらいでいいか～みたいな話をしていたので、 8 時くらいに来ていたら危なかった。
2022 は荷物を朝食に持ってきて場所をとってしまったという反省を生かして、荷物は部屋に置いてきた。
いろいろ食べて部屋に戻った。 08:10 くらい。

出る準備をしながら Twitter を見ていると、 08:40 予定の入場開始がもうすでに始まっているとの連絡が。早い！
なんだかんだ 08:35 くらいにホテルから出発！
涼しくて気持ちの良い朝。

会場着

徒歩 10 分くらいで到着。
会場のトイレがそれなりに混んでいて、入場は 09:00 ちょいまえ。

スマホとスマウォ(?)の電源を落として、バッグにしまっておきます。
09:10 オープニング映像が流れて、いろいろ説明があった。
その後急にタイマーが表示されて、あと 2 分で始まるよ！とか言われみんな ⁉️ になってた。 Day 1 で早まるかもよ～とは言ってた気もするけど、さすがにもっと心の準備をさせてくれませんか？

コンテスト

そんなこんなで 09:15 にコンテスト開始。
セットアップは kAsA に任せて、自分は封筒を破いて A を見ます。

A

まあ簡単そうなので、適当に実装します。
配列に含まれる小さい値から順番に、連続している部分を見つけて塗っていく感じ。
サンプル通ったので提出。 WA です。
こんな感じのコードを書きました。 (よく覚えてないので違うかも)

vector<int> a(n); // + 入力
set<int> st(a.begin(), a.end());
int ans = 0;
for (int x : st) {
  vector<int> idx(0);
  rep(i, n) {
    if (a[i] >= x) idx.push_back(i);
  }
  idx.push_back(-1);  // 番兵
  rep(i, idx.size() - 1) {
    if (idx[i + 1] != idx[i] + 1) ++ans;
  }
}
cout << ans << endl;

いろいろ試してみると、 1 3 1 2 1 のようなケースでは、全部 1 で塗って、 3, 2 の部分を 2 で塗って、 3 の部分を 3 で塗るという感じのことをしており、無駄が発生していました。
そこで、今見ている値が含まれないような区間は無視するようにしました。

vector<int> a(n);
set<int> st(a.begin(), a.end());
int ans = 0;
for (int x : st) {
  vector<int> idx(0);
  rep(i, n) {
    if (a[i] >= x) idx.push_back(i);
  }
  idx.push_back(-1);
  bool flg = false;
  rep(i, idx.size() - 1) {
    if (a[idx[i]] == x) flg = true;
    if (idx[i + 1] != idx[i] + 1 && flg) ++ans;
  }
}
cout << ans << endl;

直ったことを確認してから提出しなおすと、 WA が取れません。
この時点でもうやる気が失われ、萎えた... と連続して呟いていました。
いったん印刷してメンバーに見てもらうことに。 9:30。

B も見ながら A の対処を考えると、 through が flg = false し忘れてね？と指摘。
めちゃくちゃしょうもなさすぎるミスでした。ヤバすぎる。

vector<int> a(n);
set<int> st(a.begin(), a.end());
int ans = 0;
for (int x : st) {
  vector<int> idx(0);
  rep(i, n) {
    if (a[i] >= x) idx.push_back(i);
  }
  idx.push_back(-1);
  bool flg = false;
  rep(i, idx.size() - 1) {
    if (a[idx[i]] == x) flg = true;
    if (idx[i + 1] != idx[i] + 1 && flg) {
      ++ans;
      flg = false;  // 追加
    }
  }
}
cout << ans << endl;

提出して AC を取得。 09:42。
これで 2 ペナしてるのめちゃくちゃ申し訳ない気持ちになりました。

B (1)

読解は任せていて概要を教えてもらう。
なんとなく解法は思い浮かんでいるようだったので、 through に実装を任せる。
いったん任せて、すでにいくつかのチームが解いていた I を見てみます。

I (1)

09:45 見始めて、 kAsA と問題概略を共有。
約数列挙とかすればいいのかな～とか考えていたが、あまり具体的な案は見えてこず、どうやら詰まっていそうだったので B に戻ります。

B (2)

09:52 自分も解法を考えて、まあ 2 進表記したときに上から見ていけばよくね？という結論に。
実装を交代してもらったが、なんかうまく実装できておらず through が下から見ていくいい感じの実装を思いついたらしいので、交代。 10:03。

E (1)

through に実装を任せている間に、解かれていた E を見てみる。
なんか ICFPC みたいな問題だなぁとか思いながら読んでいた。
kAsA とも問題共有とサンプルチェックをして、めんどくさそうだなぁとなっていた。
問題をよく読むと、盤面は適切 (隣接マス数 = (input 数 + output 数) が守られている) ということで、まあ print P のマスから DFS すればいいよねになった。 10:11。
B の実装を待ちながら I を考えてみます。

B (3)

10:19 サンプル 3 つを試して、通っていそうなので提出、しかし WA でした。
サンプルをすべて試してみると、 1,10181, 10^{18} のケースで落ちていました。 ちゃんとサンプルは全部試しましょう (反省)
2 進表記したときに桁数が違うなら、 2 の (桁数の min) 乗を答えるようにしていましたが、どうやらこうすると 2 の累乗が与えられたときに落ちるみたい。
そこで bit_ceil 関数の存在を教えて書き換えました。
サンプルは全部通ったので、提出すると AC を獲得。 10:22。

E (2)

すかさず E を実装することにしました。
オーバーフローに気を付けて、 DFS を書いていきます。
サンプル打つのめんどくさいな～となったので DOMJudge からダウンロードして試すと、なんか assert で落ちていました。
見てみると空きマスと P の処理を忘れており、修正すると問題なくサンプルは通っていました。
提出して、無事 AC を獲得。 10:37。

C (1)

I はよくわからんし、どうやら C が解かれているので見てみます。
うーんふつうに読解が大変。
問題を共有して、いったん K に移動します。 10:54

K (1)

ざっと読んでみると、 m≤20m \le 20 ということで、まあ明らかに O(2m)O(2^m) の何かを使うんだろうなぁという感じに。
集合が与えられたときに、その補集合の上位集合を求められればうれしいよね、という感じになっていたが O(3m)O(3^m) くらいかからない？間に合わなくない？となって手詰まりに。

いったん C, I, K を同時並行で考えることにしました。

C (2)

11:32 C を見つめていると、おぼろげながら浮かんできたんです 最短経路問題が。
実際にサンプルを試してみると、やっぱり合ってる。
そこでダイクストラ法を提案してみると、半信半疑の様子。
自信があったわけではないが、まあ最短経路木 (?) が求まると total risk severity が最小になるよねぇみたいなことを話して、いったん実装してみる。
落ちるケースを探してもらいながら、実装をしていく。

11:37 サンプルが通ったので提出してみると、 WA。
困ったので蟻本を見てみると、なんか自分の書いたダイクストラ違くないか？となっていた。
具体的には、 priority_queue のループ内で dist[v] < d なら continue するべきところを、何を思ったか break していた。

priority_queue ...;
while (!pq.empty()) {
  auto [d, v] = pq.top(); pq.pop();
  if (dist[v] < d) break;  // ココ
  for (auto [to, cost] : Graph[v]) {
    // ...
  }
}

修正して提出、 11:54 に AC。

しょうもないミス多発しすぎじゃないか？

K (2)

K に戻ります。
ワンチャン枝刈りして O(n2)O(n^2) が通らないかな～と思って提出するも、 2 回 TLE 出しました。
まあ TL が 1 sec で n≤2×105n \le 2 \times 10^5 なのできついよねぇ。

いろいろ試行錯誤している様子が一瞬 公式ライブ中継 で晒されていました...

公式ライブ中継の映像
公式ライブ中継の映像

晒されていることを知らずグダグダやっていると 12:30 くらいになっていたので、ごはんを食べながら考えます。
ふと DP っぽく前計算できるんじゃね？と思いつき、実装しました。
O(2m⋅m2+n)O(2^m \cdot m^2 + n) くらいに落とせたので、提出してみると、まだ TLE が取れず。
そこからいろいろやって O(2m⋅m+n)O(2^m \cdot m + n) にしてみると、 TLE が取れるも WA。
through が思いついたみたいなので任せてみることに。すでに 13:31 となっていました。

そこから何も進展がなく、終了...

結果

凍結から何もできていないので、まあ 40 位以下は確定していました。

解説が始まると、どうやら K は同じ方針で行けたらしい。困った。
そして Yes/No の時間に。私たちはすぐ読み上げられ、結果 47 位でした。
当然企業賞もなしです。

とても悔しいので、次回に向けて頑張ります！

懇親会

いろんなスポンサーブースを回りました。
Huawei さんのブースでバッグとぬいぐるみをもらったり、いい生活さんのところで 2021 にいい生活賞いただいたんですよ～的なことを話したりした。

近くに chokudai さんがいたので写真撮影してもらった。
YouTube で見るまんまだった。
せっかくなのでメリンちゃんを布教 (?) してきた。
緊張のあまり、写真撮影のときには顔が死んでるし、その後の雑談で「埼玉大学ってどこにあるのー？」って聞かれて「埼玉県さいたま市にあります」とかいう変な回答をしてしまった...ありがとうございました！

「そろそろご飯食べないと食べるものなくなっちゃうのでこの辺で！」といって chokudai さんが去って行って、その数秒後後ろを見るとまた写真撮影に応じていて優しいなぁ + 大変そうだなぁになっていた

その後は、 UTPC で一緒にチームを組んだ北大の Today03 さん とか、上智大チーム (にころさん、 Suzux さん、 Cecil さん) と雑談してました。

別れると、チーム内でこのあとどうするー？という流れになり、 through はいろんな人を探す旅にでて、 kAsA は 🚬 へ。
自分はスポンサーブースを一通り回ることにして、入口集合ねーと言って一時解散。
freee さんのブースでは好きなアルゴリズムを書いてください～と言われて、せっかくなのでまだ書かれていなかった Miller-Rabin Primality Test と書いてみた。
Recruit さんのブースでは、去年インターンのときにお世話になった人事担当の方がいて、覚えてくださっていてうれしかった。「データ推進室知ってますー？」「去年そこにいましたーw」なんて話をして、便利グッズもいろいろもらった。
ほかのところも見回ってみたけど、待たせるのも申し訳ないので入り口に向かった。

そして帰宅。

まとめ

来年度は頑張ります！ めざせ暖色！ めざせ Playoff！
through と kAsA は来年でラストなので、せめて悔いのない結果を残したい！

おまけ

中華街あたりの部分の下書きを書いているときに、フリーズして吹っ飛びました。
Discord 上の textarea で送信せずにメモしていたことが原因です。
ちゃんと定期的に保存しましょう。

Footnotes

  1. メンバーは離れていて互いのコードは見れない状況で、かつ順位表から得られる情報しか話してないということを補足しておきます (一応) ↩