概要
2026-06-21 14:00-17:05(JST) に開催されたICPC2026年度模擬国内予選にチーム kokuu として参加しました。
ABCDEの5問を解き、45位(学内10位)でした。
目標よりだいぶ悪くてつらい！
チームメンバー
黄色を3人あつめました。
開始前
プリンタ使用不可になってしまい、問題文を読むのにもデバッグにも不利で厳しい。
コンテスト中
A
Nzt3
はい。
min_elementを使ったけどsortでよかったですね。
B
cho
C
Nzt3
「実現可能性に単調性があるので二分探索」と方針を話したら普通に尺取り法でした。
実装にミスがあり1ペナ。
D
Sotatsu
実装が重いらしいです。
手元で実行が終了しなくて無限ループを疑っていたら普通にとかでクソ遅いだけだったらしい。
高速化して提出するとCE。
DFSの再帰でthis autoを使ったのが不味かったらしいです。
E
cho,Nzt3
2進数で下の桁から特定できそう。
4クエリで1bitとれるので以下なら特定できますね→なので情報量不足です。
9クエリで1tritとれるのでCRTで並列で質問すれば以下なら特定できますね。情報量十分。
やります。
F (わからず)
Nzt3,Sotatsu
4乗のDPがあり、3乗には落とせました。
これを2乗に落としてください。
→ 1時間後……
G (通らず)
cho,Sotatsu
BinaryTrieが必要らしいので渡しました。
二分探索+Trieでlog2つを提出するとTLEになり、手元だと5secくらい。
logが1つ落とせるが、それの実装は終わらなさそう。分割の大きさをいじっても速くならない。
終了後
Eは3クエリで1bit取れるらしいです。賢い。
Fは天才で、3乗の遷移を無限に眺めても2乗にはならない。CPのグループは何をしたら見えるんですか？と思ったけど良い文字列を列挙したら見えてそう。
Hがいけるらしいと聞いて考えると石の数が奇数の頂点だけで部分森を作りたくなる。次数の偶奇を数えるとゲームクエリのがギャグであることがわかるが、を計算するには更新クエリを高速にする必要があってちょっと難しい。でも可能枠。
可能枠がFGHの3問あるならどれかは通すべきですね〜。苦しい。
