Mitsubachiのメモ

組合せ論をしています

コンテスト中に注意すべきメモ(随時更新)

立ち回り

  • 誤読しない
  • 制約は丁寧に見る、ヒントがあるかも AGC012-B / ABC179-D

問題考察

全般
  • 実験する
  • 必要条件の列挙で十分条件になるテク
  • 0,1,2,...は0,1以上(あるない)にできないか? ARC107-D
  • A xor B <= A + B
  • 区間 [l, r) が条件を満たす を f( [0, l) ) = f( [0, r) ) の形に言い換えられないか?例:文字の個数を累積和でやるやつ ARC188-A

DP
  • A_i < 2^18 とかで,A_i ごとに最適な値を持って DP したいかつ,遷移に xor(A_i, A_j) が入る → 配る時は上半分,貰う時は下半分を全探索 Ucup4-12-I
操作
  • 不変量
  • 逆操作できるか?
  • 連続 k 個は mod k で考える,k = 2 なら flip とか AGC040-C
  • 考えた必要条件が十分条件にならないか?
  • 操作回数の上限が最悪ケースでの回数より遥かに大きくないか? AGC037-E
  • 操作の最適化は操作によって得られる状態の条件を考える
  • 区間への操作 → 端点での変化を利用できないか?
クエリ
  • 一点更新のクエリ → prefix と suffix を持つ Ucup1-0-B
グリッド
  • 行/列に対応する頂点を持ってきて二部グラフにする JSC2019-qual-E
グラフ
  • オイラーグラフなら次数列の議論 これ
  • 深さごとに独立 → Auxiliary Tree Ucup1-0-E
  • 全域木が取りたいなら BFS-tree や DFS-tree をとってみる ABC251-F
  • ランダムウォークは x か y のどっちかを inc の後に何もしない or 両方 dec と同じ yuki2406
  • 最小全域木でN^2辺ある設定の時、クラスカル(マトロイド)や分割統治的な方法で辺の数を削れないか考える(両端を迂回して作る場合のほうがコストが小さくならないか?)
数え上げ
  • 和の期待値 = 期待値の和
  • N以下全てに対する総和を求めるとき、Nを固定してNのみについて考える
  • 主客転倒
  • 同一視して数え上げしたいとき、代表元の存在がないか?Learning Algorithms
  • 条件を満たす個数の2乗和 → 2個が同時に条件を満たすときどうなる?
  • 頻度の2乗和 → 同じものを2つ選ぶ方法(重複ok)と言い換える CFHello2026-F
Tips
  • 2つの連続部分列が同時に回文になる確率 → 中心が同一でなければ独立になる CF1069-div1C

実装

  • 値が一定以上になるかを調べるdpでは一定以上になったらmin関数などを使ってオーバーフローを防ぐ
  • 掛け算をFFTで行うとき、底をできるだけ大きくした方がいい(100とか1000とか)
  • bool x,y に対してx != yは ACLの two_sat で ts.add_clause(x,true,y,true),ts.add_clause(x,false,y,false); として x == yts.add_clause(x,true,y,false),ts.add_clause(x,false,y,true); として実現できる mod2で値を割り当てたいとき使う
  • mod を取った値で 2 を割った「商」を求めたい時は mint を使ったり余りの可能性に気をつける
  • DFSとかで手元で動かないときはスタックオーバーフローの可能性があるので -Wl,-stack,10485760 をつけてコンパイルしてみる
  • 配列で x 「以上の中で最小/ より大きい中で最小/ 以下の中で最大/ より小さい中で最小」を知りたい → lower_bound(all(v),x), lower_bound(all(v),x+1), lower_bound(all(v),x+1)-1, lower_bound(all(v),x)-1
  • set の lower_bound は set.lower_bound(値) を使う
  • (*map.try_emplace(key,v).first).second で map[key] が存在すればそれを、存在しなければ v が得られる

不正解になったとき

  • オーバーフロー/配列外参照はないか?(intで二分探索するとき上限を2e9にするとオーバーフローすることがある)
  • (REの場合)ゼロ除算をしていないか?
  • (TLEの場合)定数倍と計算量のどっちでひっかかってるか
  • 探索回数が少なすぎることはないか?
  • A*B<CはA<C/Bとするとオーバーフローを避けれる
  • 二分探索の境界は本当に正しいか?ngとした値で実は可能だったりしないか?
  • mod 関係は TLE したら mint 使うか mod 取る回数を減らす
テクニック別実装例
trie 関連
分割統治関連

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 必要となる.そこで,BA の unique として取り B区間についてまとめて dp を取ることを考える.

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

 

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

実装例