Mitsubachiのメモ

組合せ論をしています

ICPC 2026 国内予選 参加記 (CCXX)


チーム結成経緯

去年のチーム 217 のうち 1 人が今年は出ないそうで,穴埋めとして入った.

去年の命名規則に沿った 220 を提案すると微妙だったのでローマ数字の CCXX を提案したらウケが良かったので採用された.

 

模擬国内

私が D で大沼をした.パソコンを計 1 時間ぐらいは占有してしまった.反省.

 

本番

東大は学内のパソコンとして ECCS 端末が用意されているが,ICPC に出るには様々な欠点があった.色んな参加記を漁ると出てくると思います.(bits 使用不可,実行が遅いなどなど)

今年は ECCS 端末が Mac から Chromebook に変わり環境構築がやり直しの上,利点であったコードの印刷がプリンターで可能というのが消えたため,自前の PC で出ることにした.

 

大きなディスプレイを使うかという話になり,私はブラインドタッチができないため,実装の際に目線の上下移動が辛いかもということで,普通のノートパソコンで出ることにした.(私は何も実装しなかったんだけど ...)

 

構築があったらやりますとしたが,構築がなかったので私は色んな問題の考察を協力した.

 

D

s = 6 で前半のお絵描きが終わった頃に anmichi さんが後半のお絵描きを終えていたため合体.添字や細かいミスがありそうなので実装を横でかなり見守った.割とスムーズだったと思う.

 

F

座圧した矩形の角でグラフを作る感じですねとなった.なぜか始点も固定されていないと思って悩んでいたが,もちろん他の 2 人は先の考察で解けているので実装をしてもらった.

 

G

2 人揃って「交互に」を読み飛ばしていた.しかも実装までしてしまっていた.DP が一部共通していたり,包除などは同じなのでタイムロスはあったが不幸中の幸いではあった.

 

H

どの棒に何色を集めるかを固定すると閉路を避けるみたいな話になり,気づいたら Forested さんが解けたと主張されていた.sum (nCi)^2 ってどれくらいですかね〜 → 2^n と 4^n の間で 3^n ぐらいじゃない?みたいな会話をしたが実際は 4^n / √n ぐらいらしい.

 

I

減速する方針でまず考えたが,anmichi さんが加速する方針で考えていて,そちらの方が楽そうということに.cartesian tree や有利数二分探索を持っている Forested さんに実装をしてもらった.

ペナが解消されないのでコードを見ると if と else if で同じ条件が書いてあるのに気づき,修正してギリギリ AC.

 

J

s を固定したあと,くっつける P の辺と Q' の点を固定すると 2 乗か 3 乗 log ぐらいにはなっていそうということになった.

I が解き終われば実装するかと思ったが,もちろん 4 分で実装が終わる見込みもなく,順位表を観戦した.

 

結局どの問題も実装しなかった.幾何を見て全員嫌な顔になっていた感じはあるので,私が幾何や構文解析や変な問題などを鍛えるといいのかもしれないと思った.

個人としては誤読や読み飛ばしが多かったので反省.英語になるとより危険が増すので注意していきたいと思った.

 

 

余談 (東大のチームに関して)

UTPC での空気感を見ると,書かないのは秘匿よりかは怠惰の面が強い気がする.ただ,潜伏と言われ始めると「どうせ JAG 夏合宿や Universal Cup に行けばわかるしもう書かなくていいか」と考える人は一定数いそう.

yukicoder No.3561 Collect KCPC 別解

問題文

yukicoder.me

 

C を 2 文字目で使うか 4 文字目で使うかを判定するのが難しい.そこで,C の各文字を C か C' に変更して KCPC' を作るものとして考える.いわゆる color coding というテクニック.

全ての文字が異なる場合,自然に拡張ダイクストラが行える.

 

よって,C の各文字をランダムに C か C' に変更して KCPC' を作る問題を何回か解き,最小の答えを元問題の答えとすれば良い.\frac{1}{4} の確率で正しい割り当てを引けるため,20 回も行えば十分高い確率で正解することができる.

JOI/JOIG 2025/2026 ファイナルステージ参加記(チューター視点)

3/20

午前の表彰式(交流会第一部)に行った。参加者2人から「WAIPC最終予選のDが解けないのはちょっと...」と言われた。若さってすごい。

午後の交流会(交流会第二部)に行ったら脱葉が司会をしていた。

みんなと交流をしていたのでまい泉のカツサンドを少し食べた。美味しかった。

おにぎりがあまりにも小さかった。美味しかった。

SOY JOYというのがあったので食べてみた。美味しかった。

でも総じてご飯は少なかったと思った。

今年は交流に参加した。シール交換をした。そこそこの人とお話しできたと思う。間の時間には「神経が衰弱するデスクトップゲーム」を遊んだ。0ペアで最下位だった。

ガイダンスの諸注意スライドを流した。

3/21

遅刻しなかった。

昼食の弁当は崎陽軒の「かながわ味わい弁当」だった。美味しそうだった。

私の分はチューターが思ったより来たようで1つ足りなかったらしい。12時過ぎに遅刻して来た人が食べられたのに、8時に来た私が食べられないのは不条理を感じた。

仕方ないので、ざるそばと団子を買って昼食とした。美味しかった。

解説した。

3/22

遅刻しなかった。

昼食の弁当はまい泉の「黒豚しぐれヒレかつ重」だった。美味しかった。

何人かに「参加記を見ました!今年の交流会ではまい泉のカツサンドをたくさん食べました!」と言われた。来年以降はまい泉の争奪戦が予想されると思った。

解説した。Open Problemを提示したらその日のうちに解決した。

3/23

遅刻しなかった。

昼食の弁当は海苔弁ごっつ食べなはれの「甘塩銀鮭の炙り焼きと鶏つくねのこだわり醤油照り焼き弁当」だった。美味しかった。

飲酒したので覚えていないが、帰宅中にぬいぐるみを1つロストした。

3/24

遅刻しなかった。

朝の駒場野公園の桜が綺麗だった。

昼食の弁当は鳴海屋の「博多明太子と豚の生姜焼き弁当」だった。美味しかった。

表彰式で写真の撮り方やちいかわとサンリオについて詳しくなった。

algocomp26 予選出場記

偶然発見した謎のトルコオンサイトの予選に出た

3位で決勝に行けるが交通費が出ないので棄権

 

コンテスト HP / ジャッジシステム / 順位表

algoComp 2026

algoleague | competitive programming platform in Turkey

algoComp'26 Leaderboard

 

ホームページには書いてないが

  • 海外参加 OK
  • ただし交通費は出ない
  • チーム名は一度決めると変えられない
    • 運営に言うと変えられるっぽい

 

多分アカウントを作らないと問題文が見れないっぽいのでメモ

 

A: Triangulization

正整数 N が与えられる.各辺の長さが整数となる直角三角形で,一番短い長さが N であるものが存在するか判定し,一例を構成せよ.

  •  1 \leq N \leq 10^9

 

B: Arranging Circular Cans

正の偶数 N が与えられる.(1, 2, \cdots, N) の順列で以下の条件を満たすものが存在するか判定し,一例を構成せよ.

  • 円環と思った際に
    • 隣接 2 要素の和が奇数
    • 隣接 2 要素の差が 1 でない
  •  2 \leq N \leq 2 \times 10^5

 

C: Baseball Career

2 次元座標上の点が (X_i, Y_i) の形で N 点与えられる.(おそらく distinct) 4 点選ぶ方法で,長方形をなすものを数え上げよ.

  •  4 \leq N \leq 10^3
  •  0 \leq X_i, Y_i \leq 500

 

D: Maximum Impossible Order

正整数 N, M が与えられる.非負整数 a, b を用いて  aN + bM と表すことのできない整数の中で最大のものを求めよ.上限がない場合は -1 を出力せよ.

Q ケースに答えよ.

  •  1 \leq Q \leq 10^5
  •  2 \leq N, M \leq 10^9

 

E: The King's Hidden Treasure

ヒストグラムを考える.n 個の長方形からなり,i 番目のものの高さは h_i である.このヒストグラムの部分長方形を \mathrm{mod} で数え上げよ.

  •  1 \leq n \leq 10^6
  •  1 \leq h_i \leq 10^9

 

F: まだ

ARC115-E LEQ and NEQ 別解

問題文

atcoder.jp

 

dp_{i,j} を X_i = j なる個数とする. \sum_j dp_{N,j} が答え.

遷移を考えると 1 \leq j \leq A_{i+1} について dp_{i+1,j} = \sum_{j'} dp_{i,j'} - dp_{i,j} になる.

よって,dp_{i,j} を lazy segmenttree の j 番目の要素に保存しつつ i を増やしていく方針を考えると区間に一次関数を代入する形になる.

 

しかし,これでは配列の長さが \max_i A_i 必要となる.そこで,B を A の unique として取り B の区間についてまとめて dp を取ることを考える.

よって各ノードにはその区間の長さと対応する dp の総和を管理する.各 dp について一次関数を適応した後の状態はうまく管理できる.f(x) = ax + b として f(x)+f(y) = a(x+y) + 2b となるイメージをすると簡単.

 

よって全体で O(N \log N) 等で解ける.

実装例