ICPC2026 国内予選にチーム Phantasm として参加して 3 位（学内 1 位）でした！12 月に横浜で開催される regional 級のコンテストに出場します。

チームメンバー

• simasima
• noya2
• ponjuice

模擬国内予選の参加記にチームの詳細が書いてあるかもしれません

科学大事情

この大会には科学大からは 38 チームが出場しており、予選を突破するにはこの中でだいたい 4 位に入る（または全体で 10 位に入る）ことが必要です。学内に有力チームが 8 チームくらいいて、その中で 4 位に入る必要があるということで、大混戦です。

~ 0:00

印刷までに 30 分かかるらしい（！？）

simasima,ponjuice はめちゃくちゃ緊張していた（明らかな学内 1 位チームとして参加するのは初めてだった）(noya2 視点)

(noya2)開始 10 分前に食べ損ねた朝ごはんを調達しにセブンへ行って心配された。ウイダー in ゼリー（ラムネ味）（身内では「受験ドーピング」と呼ばれている）を買った。

A noya2

int rnk(int x){ return x >= 3 ? x : 100+x; } における max、AC (0:02)

B ponjuice

左からから順番にみていって近くに自販機がないのであれば、その場所+d に自販機を設置するをすればいい (0:04)

C noya2

左右からの累積 min を持って、水柱のどの部分が切り取られるかを求める。AC (0:09)

D ponjuice

紙に書いていると、いい感じの規則性が見えてくるので、それを書く。
s=1 を場合分けして書いており、そのテストをしていなかったためにミスに気づけず1ペナ (多分場合分けしなくて良い)
適切に修正してあげるとAC (0:28)

E simasima

最初、ジェムを1個得た後ジェムがあるものを全部取ると思ったが普通に嘘だと気づく。素直にジェムを高い方に適用しようとすると解ける。(0:31)

F noya2

適当に座圧すると $O(m^2)$ マスのグリッドになってくれるので，各マスの四隅までの距離を求めて、クエリ毎には与えられた座標を含むマスの四隅からの距離を見る。ダイクストラの部分はライブラリに任せるので、グラフを作ればよい。これも機械的にできるので頭はつかわなくてOK、AC(0:58)

あとで指摘されたが、これを短時間で通せたのがアツかったらしい

G simasima & ponjuice

常にある一列で重なる。後はやるだけ。Hを自分がやった方が良さそうなのでponjuiceに実装をパス。

(pon) 渡された通りに書くだけだが、普通にDPの遷移順をミスりサンプルが合わず慌てる。印刷をしじっくり眺める+Hを解き終わった後にデバッグをすることで解決。(1:31)

H simasima & noya2

どの棒にどの色を集めるかを固定する。さらに集める順序を指定する。すると簡単な計算で解ける。これだと $O((N!{)}^2)$ だが、bitDPで$O(2^{2N})$ に落ちてnoya2に実装をパス。

(noya2) 考察が完成していてありがとう...実装はできるのでやる。紙でほとんど実装してしまったので、全くバグらなかった、AC (1:25)

I simasima & ponjuice

下から順に貪欲に速度を盛っていくと解けそうだけど実装が大変そう。とponjuiceにざっくりした方針を渡したら書けると言われたのでパス。1時間を残してsimasimaの今日の仕事は終わり。

(pon) 貪欲で良さそうと言われたのでカーテシアンツリーの気持ちになると、二分探索しつついい感じに書けそう。ちょっと実装ミスが起こりつつも大きな問題なくAC (2:14)

J simasima & noya2 (not AC)

ついにラスボスとの対戦かと思いきや考察が自明。noyaさんに自明ですねと伝える仕事をする。

(noya2)まず、Halfplane Intersection を貼ると解ける。しかし、ライブラリを持っていないため、その場で再現することを試みる。偏角ソートして円環だと思って隣接 3 つを縮めていくとできるはずなので、それを書く。1h 以上あったのに全然合わなくて終了。

あとで分かったことだが、三分探索でもよいはず。そもそも、halfplance intersection 自体を求める必要はなく、それが空であるかどうかの判定さえできればよいことを活用すべきだった。たとえば、halfplane intersection が空ならば、高々 3 つの halfplane intersection が空であることが従う。よって、自明な $O(n^3)$ time は存在していて、まずはこれと比較する、などの戦略を取れたはずであった。

コンテスト終了

科学大から国内予選を突破したのは次の 4 チームとなった：

• Phantasm (全体 3 位)
• Chronus (全体 9 位)
• kokuu (全体 11 位)
• zer0shiki (全体 15 位)

(noya2) 私含め 22B(last year) の暖色は全員突破していて良かった

感想

simasima: 今回Hの考察くらいしか活躍していない。活躍できなかったというより、活躍しなくても良かったという感じなので良い結果だと思う。

noya2: J 以外の出来は良かった。C で変な形式の入力だったが頭を破壊せずにできたのが良かった。

ponjuice: 負けられない戦いすぎてめっちゃ緊張してたが、中盤あたりからは割とリラックスしつつできてよかった。
コンテスト終了後すぐにMCCに行くための飛行機があり、感想戦をブッチ。俺もシッダールタ行きたかった