概要

2026-06-21 14:00-17:05(JST) に開催されたICPC2026年度模擬国内予選にチーム F357iNA として参加しました。

チーム名の由来はそれぞれの名前の一部からです。

ABCDEGの6問を解き、全体32位(学内6位)でした。
6完できたので他のチームよりもなかなか高い順位を出せています。

チームメンバー

• n3：Pythonと数学を担当しています
• AK_Mi：おそらく実装を担当することになりそうです
• fken_57：バイトで出れずすみません！考察を担当する予定です

コンテスト前

バイトのため fken_57 が来れなくなり、n3 と AK_Mi の2人での参加になりました。およー。

コンテスト中

A

n3

A問題は実装を考えて、Python使いのn3が担当。とりあえず問題を見て AK_Mi にB問題を見てもらう。B問題の問題文の把握が終わったらすぐさま実装。

0:04 AC

B

AK_Mi

与えられた文字列Sを並び替えて、異なる文字列を作る問題。Sに含まれる文字が1種類かどうかで作成可能かが決まる。先頭の文字と異なる文字が存在するかを調べ、存在していた場合に入れ替えるという方針で実装した。

0:11 AC

C

n3

まず何も考えずに「_に対して右にK番目の_は何か？」みたいなのを考える、実装をバグらせそうになって全消し。
累積和を考えて二分探索をすることを考える、よくよく考えればあらかじめ x で区切る必要があることに気づき全消し。

ということで、まず入力をxでsplitした後、区間の左端を固定してどこまで取れるかを_の個数の累積和テーブルを二分探索することで右端を求める。

実装に迷い時間を使ってしまったし、二分探索の判定をバグらせ1ペナ。

0:43 AC

D

AK_Mi

各箱について使うかどうかと向きを決める単純な全探索だと計算量が厳しそうだと判断した。そこで、各側面に現れる数字の大小関係に着目した。具体的には、各箱について側面の数字を座標圧縮した結果でグループ分けをし、同じグループの置き方だけで考えるという方針を取った。このグループの管理に4次元vectorを使うなど、かなり変な実装になってしまった。重実装問題だったとはいえ、実装とデバッグに時間をかけすぎた。ペナを出さずにACできたことだけは良かった。

2:27 AC

E

n3

数学っぽいインタラクティブだよ～と n3 に渡される。最初は mod 2, mod 3 などを求めてCRTで復元しようとしたが、$\text{mod}p$ の特定に $p^2$ 回手数がかかりデカすぎる、というかそれでできるなら $x,y$ が $10^{18}$ なのはなんでだ？として方針転換。少し考察をすると、最大公約数の値が大きい場合を想像すると、2の素因数が何個も含まれる可能性がある。これを情報として取り出せないかと考えると、$(x,y)=(0,0),(0,1),(1,0),(1,1)$ の4つの質問をすることで1 bit 目を特定できる。頑張れば2bit目、3bit目、も特定していける。どうやら30bit特定する必要があって1bitの特定に4bit必要であるが、まあ質問の順場を乱択すれば2.5回で求められるし計算すると100回を超えるのは3σなのでまあいけるやろとD問題からPCを奪って実装。インタラクティブの!を忘れて1ペナ。ここでついでに $(0,0)$ のパターンはいらなくて 3回の質問で 1bit 決めれることに気づく。

1:18 AC

F

n3, AK_Mi

分からん、オートマトンに変換できないな～、くねくね、以上。

G

n3

とりあえずパスの重さの列挙がしたいので、パスの中心からの半分全列挙を考える。
そのあとは XOR convolution っぽい分割統治ことを考えると、「パスで総XORがある数以上のものは何個あるか？」を $O(N\log W)$ で判定できる、これで二分探索すれば答えが求まるが、Pythonにlog2つは厳しい。ここで「分割統治と二分探索を同時に行えないか？」と考えると、「総XORが2^X以上のものは $K$ 個以上あるか？」みたいな感じで順位を決めていくとlogが1つ落ちる。イメージとしてはセグ木二分探索がlog1つで済むのと同じ。D問題の実装が終わるまで時間があるので紙コーディングをし、Dが終わったら40分ぐらいで気合いで実装する。デバッグ用に分割回数の上限の個数を小さくしてたのを忘れて1ペナ。

2:59 AC ← ギリギリ！
まあトラブルで延長されて3:05までだったんですが、それでもギリギリで心拍数激上がりしてました。

H

AK_Mi

G問題の実装中に軽く見た。見ただけでほとんど考察はできていない。

終了後

感想(n3)

序盤の立ち回りも良かったと思う。本番もA問題はn3が担当しそう？あと自分の苦手な重実装をこなしてくれたAK_Miには感謝です。C問題の立ち回りでも、実装の下手さが現れていますね...
G問題に関して、Python使いの僕は、過去のABCで二重二分探索してTLEを出した経験があり、logを落とす方針にすぐさま切り替えれたのが良かったです。実際c++でもlog落とさないと厳しいらしい。本番もこれぐらいうまくいくといいですね。
あとケアレスミスによるペナを無くしたいです、マジで。本番は気をつけます。

感想(AK_Mi)

n3がE問題を実装してくれている時間があったとはいえ、C問題のACからD問題のACまでに100分以上かかってしまったのはさすがに実装が下手すぎて申し訳なかったです。重実装問題をペナなく通せたとはいえ、もっと簡便な実装方針を取るべきだったと思います。話を聞く限りG問題の実装も決して軽くはなさそうなので、自分がパソコンを長く占有してしまったにも関わらず時間内にG問題をACしてくれたn3には頭が上がらないです。

おわりに

本番は3人いるのでこれ以上のパフォが出ると思います（諸説）。