ICPC 2024 Asia Yokohama Regionalに参加しました

ICPC 2024 Asia Yokohama RegionalにTECHNICOLORZで参加して42位(/55)でした。

メンバー

  • Qitoy : AtCoder青色で学内で一番ratingが高い。
  • Kei83 : 自分。先週AtCoder水色になった。
  • haruki4936 : AtCoder青色で自分の学科の先輩。

コンテスト前

自分がPCのセッティングをして，ABをharukiさんとQitoyさんで分担することにしました。もはや作戦かどうかわかりませんが，QitoyさんのDP力が明らかに抜けていたので，DPぽい問題はQitoyさんにやってもらうことにしました。（自分がやるのが完全に無駄になるくらい早い）

コンテスト

問題文はこれ
封筒を開いて，パスワードを入力します。リハーサルでは，自分はやらなかったので，このpwを打てばいいんですよね？とharukiさんに確認してログインしました。先ずは，.bashrcを開いてコンパイルのaliasを設定しました。

alias g=’g++ -Wall -Wconversion -Wfatal-errors -g -std=gnu++20 -fsanitize=undefined,address’

次に，チームのライブラリはkactlを使用することになっていたので，そのテンプレートを書きました。

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
}

後は，VSCodiumのauto saveをオンにして，PCのセッティングは終わりました。ついでに，自分はインデント幅2が好みなので，Tab sizeを2にしておきました。
大体これで10分くらいかかったような気がします。

二人がA, Bを読んで解いているので，他の問題を読みに行くことにしました。どこから読んでも良かったのですが，とりあえずDから読むことにしました。Dは読むのにも時間が結構かかって，問題文が分かっても解けそうな感じは全くしなかったので，スルーして，次にEを読みに行きました。E問題を読み，少し考えていたら，ちょうどABをどっちもACしたくらいで，なんだか解けそうな感じのE問題を二人と共有しました。

それでE問題は，harukiさんが書くことになって，じゃあまた別の問題を読もうかなと思って，順位表を見て解かれている問題を確認してKを読みに行きました。見た目的には，結構解けるんじゃないかなーとか思ったんですが，結局具体的な方針が立たないまま時間を使うことになりました。この途中でharukiさんがEのサンプルが合い，提出するもREだったので，自分もそのコードを見ることにしました。

dfsのコードが，こんな感じで来た方向に戻らないようにしていたところで，根の時にpredir = -1としているために，(-1 + 3 == 2)となってcontinueしてバグることに気付きました。本当にこれを直すだけで通ってびっくりしました。

dfs(座標, int predir) {
  for (int nowdir = 0; nowdir < 4; nowdir++) {
    if (predir + nowdir == 2) continue;
    処理~~    
  }
}

EをACした後は，F, Hをとりあえず読んだりしましたが，解けそうな感じは全くしませんでした。自分は特に進展がないまま時間が経過し，いつの間にかQitoyさんがCを通していました。その後は自分がKを考えて，QitoyさんがIを考えていて，どちらもあまり進んでいなさそうだったので，自分もIを考えてみることにしました。

Moで出来ないかなーと思うと，Aの約数dに関して，追加はcnt[d]++, 削除はcnt[d]—とすれば，その区間の最大のGCDはcnt[i]が2以上のとなるi中で最大の値とすればよく，結構単純に出来そうでした。cnt[i]が2になった時にiをsetに入れて，最大を取り出す実装にして提出するとTLEしました。とりあえずvectorを生配列に出来るところは全部生配列にして，#pragma GCC target("avx2")を付けたりしてみて，何回か提出してみましたが変わらずTLEでした。（AOJだと3.6 secでACだったので本番の環境はちょっと遅そう。提出）

結局setを使わない方法にしないと，どうにもならなそうといった話をQitoyさんとしていました。自分はセグ木で何とかならないかなーとか思っていましたが，QitoyさんがBITと二分探索で出来そうなことに気付き，教えてもらうと出来そうでした。この時harukiさんがGと格闘していたので，ひと段落するまでに実装の詳細を確認していました。

kactlのfenwicktreeにlower_boundが付いていて，おーまさにこれが欲しくて助かる～となっていました。harukiさんにPCを空けてもらい，書いて手元でも速度を確認すると，相当早くなっていてさすがにこれはいけるんじゃないかと思って提出すると通りました。（AOJだと1.08 secで3倍以上早くなっていました。提出）

残りはharukiさんがGと格闘しながら，自分はQitoyさんとKについて話していて最後まで解き切ることは出来ずに終了でした。

終了15分前くらいにこうやれば出来そうだねとQitoyさんと話していたことを，終わってから書いてみたらAC出来たので，これをちゃんと書いて通しきれればなといった感じでした。(それでもビットが全部立っているやつと場合分けの漏れで3WAしました。提出)

終わりに

簡単枠のABをお二方に解いてもらうことにしたため，自分の実力的には，残った問題がどれも全く分からない可能性は全然あるなと思っていたので，5時間椅子を温めるような状況は回避できて，悪くなかったのではないかと思っています。 また，Mo's algorithmはJAG夏合宿day1のA問題（Static Range Mode Query）で初めて見て，そこから使えるようになったので，ICPCに向けた練習の成果が出せたような気がして，その点個人的には満足しています。 自分はあと2回？ICPCに参加できると思うので，もう1回横浜に行けたらいいな～。

おまけ

Yokomaha Regionalに参加するにあたって，とりあえず会場に近いホテルに泊まろうと思って，ホテルJALシティ関内横浜という会場から徒歩3分のところにあるホテルに宿泊しました。朝8時30分くらいに会場に到着したいことを考えると，思ったよりも朝が早くて，近いホテルにしておいて良かったなと思いました。このホテルは朝食を7時から食べることが出来て，結構美味しかったので，朝食をしっかり食べたい人にはおすすめです。

食べた朝食