ymduu+2

初心を忘れないのでツンデレとPSPが今でも好き、技術メモとか制作物とかそういうの

競プロでツイートしたものをスクラップする場所

名前がついてないけど典型っぽいやつ 置き場所だけ作る 適宜追記していく

N2 の区間全探索を高速化したい

  • 実はN2のまま間に合う
    • 単調性 で二分探索するときもあるあるだが、左端を固定して右端を全探索すると見通しがよい
    • 高速化とは違うけど、これを忘れると茶diffでハマったりするので持っておこう
    • Mandarin Orange https://atcoder.jp/contests/abc189/tasks/abc189_c
      • TLと制約が厳しくて、logを付けると落ちるので、累積minしながら区間全探索するとよい
  • 単調性
    • なんかあるだろ、しゃくとりが使える問題全般
  • Zero Sum Ranges 系
  • 変数分離 + 内側のΣを事前計算
  • 実は特定の小さいケースだけみればよい
    • アンバランス https://atcoder.jp/contests/arc059/tasks/arc059_b
      • ある長さ4以上の文字列がアンバランスであるとき、かならずアンバランスな部分文字列 oo か oxo を含むので、長さ 2 or 3 だけ見ればよい
      • TODO: 大きいケースは小さいケースに何かを付け足したもの であるので、小さいケースに帰着できる みたいなのは典型な気がするけど抽象化がうまくいっていないので、いつか抽象化する
  • 寄与
    • https://atcoder.jp/contests/abc091/tasks/arc092_b?lang=ja
      • これ寄与かな……(？)
    • Second Sum https://atcoder.jp/contests/abc140/tasks/abc140_e
      • これは完全に寄与、ある x が2番目になる区間がいくつあるかを数え上げる。 "自分より大きいもの"のインデックスがわかれば計算できるので、これは大きい順に index を set に入れていくことで計算できる(更新順を工夫)
      • ↓の制約が2つ にも該当(Pi の値が x より大きい && i に一番近いインデックスのものを検索)
  • 制約(不等式とか)が二つ -> 片方を処理順 もう片方をデータ構造で解決

区間 * 大量が与えられた

区間もしくは締め切りがたくさんある

区間や締め切り(例: 時刻tまでに終わらせなければならない仕事)がたくさん与えられたら区間スケジューリング問題的な貪欲を疑う
区間 * 大量を見たら終端でソートする、という典型があるが、それ
締め切りがはやいものを選ぶと後に残せる選択肢が多くなる、という気持ちらしい

algo-method.com

知ってれば簡単だからか難易度のわりにdiff低くなりがち、気づけないとガチャガチャやっても解けないので破滅の原因になりがち(個人の感想)
亜種として大量の区間を全部切る Islands War がある(TODO: 書く)

連続部分列を取る操作、連続部分列に関する情報が与えられている

連続部分列を取る操作をグラフの辺とみなす

  • 操作で[l, r)の連続部分列(部分文字列)を取るとき、 l -> r のような有向辺を追加したグラフを考えるとよいことがある。
    • Strings of Eternity https://atcoder.jp/contests/abc135/tasks/abc135_f
      • 上記考察をすると、有向グラフの最長パスを求める問題になり、これは有名問題(トポロジカルソート + DP でとける)
    • Range Sums https://atcoder.jp/contests/abc238/tasks/abc238_e
      • 累積和上で考えると2点関係になる -> グラフと発想できるが、連続部分列を辺とみなす の気持ちでいると思いつきやすいかも、本番では未証明でエスパーしてグラフを作った人もいた様子

区間和が与えられた時も累積和(区間和を求めるときだけじゃない)

累積和の上で考えると区間和は2点関係になって、2点関係 * 大量 = グラフとみなす のテクがつかえることがある

区間に対して加算したい

区間に対して加算したいときはセグ木、imos法などがよくあるが、それらは自明なので割愛

区間に対して加算したいが、インデックスの範囲が巨大(1e9とか)

インデックスの範囲が巨大なとき、セグ木に乗らず困ってしまう。座圧してもいいが、実装とデバッグが大変になりがち
問題によってはイベントソート(index, 加算値)のペアを保持してシミュレーションすることでうまくいくことがある。 変化点に着目 の亜種でもある
このとき、半開区間で処理するとうまくいく。(複数のイベントが同時に起こることがあるが、その区間は長さ0の区間として処理されるため)

  • Snuke Prime https://atcoder.jp/contests/abc188/tasks/abc188_d
    • 座圧 + imos でも解けるが、イベントソートなら実装が軽い。これくらいの問題を爆速で解けると勝ちやすいので……
    • 座圧ってバグったときしんどいし……

DP

選択を繰り返す → DP

独立でない(過去の選択によって状況が変わる)選択を繰り返して最適化(例: 最小化、最大化)をするとき、保持しておかなければならない条件を添え字にした DP ができることがある(ナップザック問題とかもそうだな)
各選択が独立なら、各選択で最適なものを選ぶ貪欲法ができる

貰うDP にすると都合がよくなることがある

普段は dp[S] := 開始状態 Init から状態 S まで到達した時の最大スコア などとするが、 dp[S] := 状態 S から目標状態 T まで到達した時の最大スコア とすることで遷移を簡単に書けることがある。 多分要件は今の状態のスコアが未来に依存する(ゲーム) or 未来の状態で記述した方が楽(等確率に遷移する期待値の問題で、未来から貰うなら等確率なので楽だが、過去から配るならその状態に到達する確率を求めなければならないなど)とかなんだけど、どう使い分けるのがいいかはまだよくわかっていない

ゲーム → 後ろから DP

後ろから DP というのは難しく見えるんだけど、dp[S] := S から目標状態 T まで遷移したときのゲームのスコア(↑の一種) という貰う DP を書くと、各プレイヤーは S から遷移できる状態の中からスコアが一番よいものを選ぶ、という遷移が書けて解ける。

  • Game in Momotetsu World https://atcoder.jp/contests/abc201/tasks/abc201_d
    • スコアを高橋君の得点 - 青木君の得点 として、高橋君は最大化、青木君は最小化するような選択をすればよい。右と下の遷移先のスコアがわかっていれば、どちらが最適化は大小比較で求まる。

DP の更新を時がくるまで保留したい

  • https://atcoder.jp/contests/abc224/tasks/abc224_e
    • 考察すると、a の降順に r と c のそれぞれの最大値を更新していけばいいという気持ちになるが、 a が unique でない かつ問題の条件より、同じ a を見ている間は dp テーブルを更新したくない。 差分を貯める nr, nc を用意して、ある a についての処理が終わった後に差分を適用する。

桁 DP で leading-zero が許容されない時のテク

桁 DP で leading-zero が許容されないとき、以下の点に注意する必要がある。以下、すでに小さいことが決まっているかのフラグを smaller と呼ぶ。1-indexed。

  • 左から 1 桁目を決めているとき、0を使ってはならない。
    • 配る DP をしているとき、条件が i + 1 == 1 の時 になることに気を付ける(i は i 桁目まで決定しているときを表す)
  • 2 桁目以降のとき、そこから始めることができる。
    • 実装上は 2 桁目以降なら入れられる任意の値を smaller = true で入れてよい、とするのがらく。
  • 実装例

順列全探索高速化 → bitDP

順列全探索を要求されるが N=16 のとかのとき。末尾だけ など限定された属性が次の状態に影響するとき、今まで訪れた集合と末尾だけ保持して状態数を圧縮する。「過去を忘れる」
TSP の bitDP とかそんな感じだけど、キモは 順列 → 集合 + 追加情報 にすることで順列に含まれていた順番情報を忘れて状態数を圧縮すること。追加情報がいらないこともある。

  • Magical Ornament https://atcoder.jp/contests/abc190/tasks/abc190_e
    • Ci -> Cj にいくときのコストは適当にダイクストラとかで計算できる。あとは C1...CK の並び順を全探索すればよいが、これは順列全探索なので、 TSP の bitDP と同じようにできる。 dp[S][i] := 集合Sの石を含んでいて、末尾が i になるときの最小個数。

bitDP で集合を分割したい、部分集合を全探索したい

bitDP で dp[S] を求めたいとき、部分集合 T を用意して T と S ^ T に分割した結果を全探索して最適解を求めたくなることがある。
これはうまく実装することで O(3N) の計算量になる。

EDPC U のフレンズさん解が実装楽 & 割とそのままコピペして使える感じで良

kyopro-friends.hatenablog.com

更新順を工夫する

自分より{小さい, 大きい}何かだけが操作の候補になる みたいな状況はよくある。そういう時は適切な順番で集合に追加していくとうまくいくことがある。

追い越しが起きない

操作をして要素を動かしたりする場合、要素同士の追い越しが起きない(もしくは、しても損をするだけ)ことがある。 その場合、操作前と操作後のある値について、1対1対応をつくれることがある。

最大化最小化問題は初手で二分探索を考える

{最大値, 最小値} を求める問題は 解を K {以上, 以下} にすることができるか？という判定問題にすることで無料で二分探索でとける形にすることができる。
判定問題の方が真に易しいので判定問題で考えて損をすることはないという気持ち？
二分探索は思いついたけれど、判定問題を5分考えてわからないので捨てちゃう、みたいな負け筋がある(もっと掘り下げるべき)気がするので、判定問題のほうが易しいという気持ちを持っておくのは有効そう

(その他メモ)

  • Average and Median https://atcoder.jp/contests/abc236/tasks/abc236_e
    • 判定問題に落としても難しいので二分探索をすててしまった回
    • 中央値 平均値 は解({中央値, 平均値}そのもの)を固定すると有利になりがち(TODO: 書く)

二分探索 Tips

問題文から二分探索の気配がする(例えば、最大化 or 最小化問題で、単調にできる場合など)のに判定関数が思いつかない場合、解を決め打ったときに都合のいい圧縮ができることがある。

中央値を見たら二分探索

https://atcoder.jp/contests/abc203/tasks/abc203_d
↑の都合のいい圧縮 の亜種(というかそのもの)だけど、よく言われてるので独立させとく。
解 X を決め打ったとき、 X より大きいかどうか？ の 01に潰すことができて、うれしくなりがち

ARC101 参加記録 - ARMERIA

が詳しいんだけど、一個誤植？があって、「中央値は X 以下である」ことと、「 X 以上の要素が半数以上存在する」ことは同値 ではない。このことは、

1,1,1に対して中央値は1000以下だけど1000以上の数は0個である

が反例。 (Thanks iry)

グリッド / 座標平面

x 軸と y 軸を独立に考える

問題文に x y が出てきたらそれが (行, 列) なのか (列, 行) なのかを気を付ける

二部グラフにする

操作が定義されている

操作によって2状態の入れ替えや flip が起こる(カードの裏表が変わるとか)

操作によって過去の結果が上書きされる

操作が k 回行われる

操作が何度も行われるとき、{変,不変}量に着目するとうまくいくことがある。
特に不変量に着目するパターンは多い気がする(TODO: 探す)

区間に対して範囲攻撃を行う

ゲーム

暫定解が簡単に作れそうなら暫定解をつくって更新してみる

数学

n が巨大な nCr(r <= 105くらい)

n が巨大な nCr を計算するときは n! を前計算することができないのでこまってしまう。
小学校とかで組み合わせを計算するときは

\binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1}

みたいな公式で習った気がするけど、それをするとO(k)でいける。正確には

\binom{n}{k} = \frac{n}{1} \times \frac{n-1}{2} \times ... \times \frac{n-k+1}{k}

もっといろんなのがあるページ

drken1215.hatenablog.com

二項係数に対してシグマを計算したいときは式変形でpowの形にできることがあり

\sum_{k=0}^{n} \binom{n}{k} = 2^n

証明は二項定理から。

二項係数の和，二乗和，三乗和 | 高校数学の美しい物語

知ってるかゲーではあるので知ってればOK

最大公約数

  • 数列 A の最大公約数を g にできる ⇔ Ai は g の倍数

条件式が合同式で表せて、法が変数(k)

法が変数(kとする)のとき、条件式を N ≡ 0 mod k の形で表せれば、k は N の約数となり、O(sqrt(N))でもとまる

  • Division or Subtraction https://atcoder.jp/contests/abc161/tasks/abc161_f
    • 一度割り切れなくなったらそこから新たに割り切れるようになることはないので、Kの候補は
      • N ≡ 1 mod K (つまり、 N - 1 ≡ 0 mod K)
      • Nの約数のうち、NをKで割れるだけ割ったものをMとして、 M % K == 1
    • それぞれ O(sqrt(N-1))個、O(sqrt(N))個なので間に合う

N を割り切るものだけが候補になる

N を割り切る -> N の約数(それはそうだろ)

  • Division or Subtraction https://atcoder.jp/contests/abc161/tasks/abc161_f
    • 一度割り切れなくなったらそこから新たに割り切れるようになることはない
      • つまり、割り算パートが入るのは K が N の約数の時だけ
      • こっちはおまけだと思う

包除: x 個以上の条件を満たすものの個数を数え上げるのは簡単だが、重複を除くのが難しい → 包除

題の通り、条件 * 大量があって、 x 個以上の条件を満たすものの個数を数え上げることはできるが重複を除くのがたいへんなときは包除がつかえることがある。
普通に x 個の条件を満たすものの個数を数え上げると、 "x個の条件を満たし、他の条件を満たさない" ものを数え上げることになる。
数え上げのときに条件を満たさないというのは扱いづらいがち。
そこで、包除を考えると、 x 個の条件を満たし、残りの条件はドントケア(満たしても満たさなくてもよい) にすることができる。ドントケアになることによって見通しがよくなり、問題がとけることがある。
ABC172-Eの解説動画がわかりやすくておすすめ https://www.youtube.com/watch?v=v8ppNGf49Nk

  • NEQ https://atcoder.jp/contests/abc172/tasks/abc172_e
    • そのもの。とりあえず k 個一致するものの個数を数え上げたくなるが、素直にやると k 個一致するように配置したあと、のこりの N - k 個を一致しないように配置する必要があり、厄介。そこで、k個以上一致するものの個数を数え上げることにすると、前半の k 個一致する だけ考えればよくなって楽。 それらの重複を除くのに包除原理が使える。
    • 撹乱順列 というキーワードも覚えておくと吉そう

約数系包除: パラメータが k の倍数

でぐわーさんの pdf の受け売り

「数え上げテクニック集」を公開しました - DEGwerのブログ

数え上げ問題を解くとき、 あるパラメータが k の倍数であるときの個数を数え上げられる場合、簡単に重複を除くことができる
降順に、あるパラメータが k の倍数であるときの個数を求める -> 既に求まっているはずの 2k, 3k...の個数を引く を繰り返す、計算量は調和級数から NlogN

  • Sum of gcd of Tuples (Hard) https://atcoder.jp/contests/abc162/tasks/abc162_e
    • そのもの
    • gcd が k の倍数になる ⇔ k の倍数のなかから N こ選んだものの個数(これは単なる組み合わせ) -> それにこの典型を適用すればOK

mod N の世界で M を足していくやつ

通称"プラベで9人3ルールで回していると毎回同じ人が同じルールで観戦になってしまうやつ"
M と N が互いに素なら kM mod N(kは整数)で [0, N) のすべての値が出てくるが、そうでない場合は mod gcd(M, N) が同じ値しか出てこない。
証明がむずくて、後ろに多分拡張ユークリッドの互除法がある。(雰囲気で式変形をしているのでまさかりを投げないでほしい)

拡張ユークリッドの互除法についてはこの辺も見るとよい。　(∵拡張ユークリッドの互除法 の部分で下の議論を使っている)

拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 - Qiita

{i, j | i < j} なもののシグマを求めたい と言われたら条件 i < j を除いて考えられる

\sum_{i=1}^{N-1} \sum_{j=i+1}^N hoge_{ij}

みたいなのを見かけたら、

\sum_{i=1}^{N} \sum_{j=1}^N hoge_{ij}

を求めて、

\sum_{i=1}^{N} hoge_{ii}

を引いて2で割れば OK、長方形領域の対角線より上の範囲の和を求めたいとき、長方形領域を求めて、対角線部分を引いて、2で割るイメージ

  • Xor Sum 4 https://atcoder.jp/contests/abc147/tasks/abc147_d
    • とある桁が 1 になる組み合わせの個数着目するが、これをすると見通しがよくなる(これってこの数と組み合わせていいんだっけ？を考えなくてよくなる)
  • TODO: なんか ARC のむずめのやつであった気がするのを思い出して書く

平均値を見たら総和に言い替える

  • n 個の平均値が a といわれたら、 n 個の総和が na と言い替えると見通しがよくなることがある

偶奇に着目する

  • 〇〇が偶数である、とか奇数である、とか言われたら疑う

0 xor 1 xor ... 2N-1 == 0 である

  • 2べきまで xor で疑うといい？
  • ビットごとに、[0, 2N) に含まれる 1 の数の総和は偶数なので、[0, 2N) までの xor をとると0になる。構築で使ったりするほか、この性質を問う問題を見たことあるような(TODO: 探す)

xor (ビット演算全般も？)を見かけたら1桁ずつ独立に考えてみる

見たら真っ先に考えるようになっているとは思うけどかなりよく見るので一応
and, or, xor あたりのビット演算は二進数の桁ごとに独立に考えられる、そうすると見通しがよくなることがある

xor は繰り上がりのない足し算

二進数において、 xor は繰り上がりのない足し算とみなすことができる。a + b == a xor b みたいな時に役に立つ。(これが成り立つのは、くりあがりがない ≒ a と b で両方立っているビットがない とき)

floor(N, i) が大量に出てきたら floor(N, i) の値で分類して状態を潰してみる

{floor(N, i) | Nは適当な定数、 1 <= i <= N} をたくさん(1012個とか)扱いたくなった時のテク。 理由は以下のツイート。

floor(N, i) の種類数はO(√N)なので、単純に全列挙できなくても種類ごとになら全列挙できる。
実装方法はけんちょんブログが詳しくて、けんちょんさんのコードをライブラリ化してコメントをつけたものが以下

// {floor(N, i) | 1 <= i <= N} は O(sqrt(N)) 個しかないことを利用して、 整数 [1, N] について、floor(N, i) の値で分類する。
// (floor(N, i) の値, [1, N] の間にそのような値がいくつ含まれるか) のペアの vector を返す。
// 計算量: O(sqrt(N))
vector<pint> ClassifyByFloor(int N) {
    vector<pint> res;

    for (int i = 1; i <= N;) {
        // intfloor(N, i) の値で分類
        int j = N / i;
        if (i <= j) {
            // 前半
            // (i <= N / i) つまり、 i * i <= N つまり、 i <= sqrt(N) のとき、該当の値は1個しかない
            res.push_back({ N / i, 1 });
            i++;
        }
        else {
            // 後半
            // (i > N / i) つまり、 sqrt(N) より大のとき、該当の値は複数個あるかも
            // ここで、 i は N / x == j なる最初かつ最小の x 、 N / j は N / x == j なる最後かつ最大の x になってるはず(文字のまま考えるといまいちピンとこないが、具体的な値で実験してみるとピンとくるはず)
            // N/x == j なる最大の x は　N/j ですよね(floor だからややこしい感じがするけど)

            // 閉区間になっていることに気を付けつつ個数をかぞえる [i, N/j]
            int cnt = N / j - i + 1;
            res.push_back({ N / i, cnt });
            // i を次の最小値(今の最大値 + 1)にする
            i = N / j + 1;
        }
    }

    return res;
}
  • Fraction Floor Sum https://atcoder.jp/contests/abc230/tasks/abc230_e
    • そのもの、↑のコードを貼るだけでとける
  • Small Products https://atcoder.jp/contests/abc132/tasks/abc132_f
    • 素直な DP を書いてテーブルの中身を眺めると、上記の圧縮をしたい気持ちにはなる。 圧縮した後手で実験すると、確かにレイヤー(N/x が同じ数の集合をこう呼ぶことにする) i の次にこれる数はレイヤー M - i 未満の数である となっていることがわかり、これは DP を BIT とか累積和で高速化すればOK
    • 本質は i * j <= N ⇔ N / i * N / j >= N かなあ(これは問題固有の考察な気もするけど)

2つの数列 A, B においてマッチングを考えて、 Ai * Bj の和を最小化したい場合、A を昇順、 B を降順にして組み合わせると最適

A と B の長さが2の場合について 大-大、小-小 のように組み合わせた時、大-小 小-大 のようにすることで改善できることが証明できる。
直感的にそうだけど、無証明だとバグった時にノイズになるので証明できるとよい
(雑な証明、中学校の証明問題っぽい感じ)

x > y, z > w の時、 xz + yw > xw + yz を示したい。 (xz + yw) - (xw + yz) > 0 を示す。 \begin{eqnarray} (左辺) &=& x(z-w) + y(w-z) \\ &=& x(z-w) - y(z-w)\\ &=&(x-y)(z-w) > 0 (∵最初の条件より、 x - y > 0, z-w > 0) \end{eqnarray}

  • 貪欲の証明において、交換することで必ず改善することができるので最適性が言えるパターン

  • Change a Little Bit https://atcoder.jp/contests/abc150/tasks/abc150_e

    • 直感的に Ci が小さい順にやっていくと最適だが、その証明ができていないと不安になる
      • その先の式変形が大変

負数あり & 公差1の等差数列の和を考える時、負数のことは考えなくてもよいことがある

公差1のとき、負の区間は正の区間で打ち消せるはず。
例:

-2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 = 3 + 4 + 5 = 12

よって、負数のことを考えなくて済む。個数を数え上げたいときは最後に2倍すればOK

  • Staircase Sequences https://atcoder.jp/contests/abc190/tasks/abc190_d
    • 負数のことを考えなければ、数列の長さはO(sqrt(N))なので全探索できる
    • 素直に立式すれば約数列挙に落とせて、そちらの方が筋がいいですね……

幾何

偏角

座標平面上で点や図形がたくさん与えられるとき、偏角に着目すると有名アルゴリズムを適用できることがある

平面グラフのs-tカットをしたいときは双対グラフの連結性判定

ABC181-F の円で通路を埋め尽くす問題で出会ったので幾何にいれとく。グラフかも。まあ直下がグラフだからいいよね
図形で道を塞ぎたい(≒平面グラフのような形)時は、双対グラフ(グラフの辺でかこまれた部分(面)を頂点、面に接する辺を辺と見たグラフ)の上で連結性判定をすればよい。
解説動画の 2:07:00 あたりがわかりやすい
https://www.youtube.com/watch?v=b0VIYIYB5v0
どういうときに使えるかというと、

  • ABC181-F みたいに平面図形で何かを通行不可能にしたいとき
  • 最小カットを求めたいけどいつものアルゴリズム(フロー)だと間に合わないとき平面グラフじゃないかを考える

くらい？

  • Silver Woods
    • ↑の初めて出会った問題、釘を半径rの円、動かす円を点とみなすようにすると上記のテクニックが使える。

グラフ

変形

2つの関係 * 大量が与えられたときグラフにできないか疑う

条件として奇閉路がない が与えられた

奇閉路がない ⇔ 二部グラフ。

木

木はつよい条件

部分木を考えたとき、その部分木に含まれない残りのほうも木だし、一意

あたり前なんだけど出てこないがち……これが出てこないと難しい問題を解こうとしてハマりがち
とくに "ある辺を切って木を2つに分割" みたいなシチュエーションでよく見る

  • Through Path https://atcoder.jp/contests/abc187/tasks/abc187_e
    • ある辺で切って、片方の部分木に含まれる頂点に数を足すみたいなクエリがやってくる。木を切ったら木 * 2 になるのでできる。
    • 根つきにして部分木の根(部分木のうち、根にもっとも近い頂点)に足す -> 木DP が常套手段だが、根側に足すときは 根に足す -> 部分木の根から引く ことで達成できる
    • 一時期のコドフォでよく見た

部分木クエリはオイラーツアー

部分木に対してなんかしてくれと言われたらオイラーツアーをすることで、部分木クエリを区間クエリに落とすことができたりする、実装たいへんなのでライブラリ化したい

maspypy.com

木の上でおいかけっこをするとき捕まらないための条件

高橋君と青木君が木の上で追いかけっこ(自分も相手も1Tに1手うごくことができる みたいな)をするとき、高橋君が青木君に会わずに行ける頂点の条件は (高橋君からの距離 < 青木君からの距離) である。
木の上で相手に会わずすれ違うことはできないのでそうなる

木(数直線でも)上で追いかけっこをするとき、距離のパリティが保存

相手も自分も動かなければならない場合、{両方離れる方向に移動: +2 両方同じ方向に移動: +0 両方近づく方向に移動: -2}なので、そうだね

木DP 根から埋めるか葉から埋めるか

木で、再帰的に各ノードに対する結果を求められそうなときは木DPが使えることがよくあるが、根から埋めるパターンと葉から埋めるパターンがある。両方あることを意識しておかないと解ける問題を落としがち
親兄弟の情報だけで子が求められる: 根から
子が全部分かれば親が求められる: 葉から
というイメージ(こう書くと それはそう だな……)。根からの時は木DPと呼ばない宗派もある？？？

根からすべての頂点までのパスについて何かを計算するとき、あるノードの計算が終わった後に巻き戻すテクニックが使えることがある

本質はスタックの dfs と同じだと思う……差分更新とそれを戻すことを繰り返すイメージ？
LIS みたいな列に対するアルゴリズムを木に使いたいとき、行きがけ順に普通に計算、帰りがけ順に結果を1手戻す、とするとうまくいくことがある。"計算"と"戻す"がそれぞれO(1)でできる必要がある

全方位木 DP が必要そうなときは葉から決める木DP を考える

全方位木 DP の実装とその使い方は

null-mn.hatenablog.com

が詳しい。ここの実装を使うと、子の情報から親の情報を求める DP を全方位木 DP に拡張できそうだということがわかる。
全方位木 DP が必要そうだと思ったら(≒木のすべての頂点を根としてなにかの値を求める必要があるなら)葉から決める木 DP を疑うとよい

DAG

DAGも強い条件、トポロジカルソートできるぞ
トポロジカルソートできれば超実装軽い DP とかできることがあるので、有向辺(u, v) で u < v とかの見慣れない制約があったら疑ってみるとよい
依存グラフ解析系の問題は DAG じゃなかったら解なしとかある(循環依存になってしまうので)

グラフに対する操作

  • 条件を満たす頂点間に辺を追加する操作
    • 再帰的に辺を追加していくと実は 完全グラフ とか完全二部グラフ になることがある

境界全探索

  • ある条件を満たすか満たさないかで扱いが変わる時(表現がむずい)、その境界を全探索できることがある
    • Max GCD https://atcoder.jp/contests/abc136/tasks/abc136_e
      • 最大公約数 g を全探索するとき、 mod g の値をソートすると、ある場所より左は0に寄せて、ある場所より右は g ≡ 0 mod g に寄せるのが最適
        • mod g の値でソートして、ポインタ二つ(l, r)用意して、l が 0 になるまで、 r が g になるまで操作することを繰り返すと解けるけど、これは正当なのかな

構築

グラフを構築しろと言われた

  • パスグラフ、スターグラフ、二部グラフ、完全グラフなど特徴的なグラフから「暫定解を改善」して作れないか考える
    • Friendships https://atcoder.jp/contests/abc131/tasks/abc131_e
      • 直感的にスターグラフの時最大になる気がする。(これを思いつくのがつらい)スターグラフなら葉(？)を繋ぐことで距離2の頂点対をひとつ減らせる

クエリ(もっといい分類あるかな……)

数列のうち一つだけを消す→左右から累積

数列が与えられて、ある一つの要素を消した時のナニカ(gcd とか)を求めてくださいみたいな問題、ありがち
左と右から累積ナニカを計算しておいて、それをうまく合体させると解になることがある

  • Yutori https://atcoder.jp/contests/abc161/tasks/abc161_e
    • あるマスについて、左右からそのマスを除いた最適解を事前計算しておいて、それらの和が K 未満ならそれは必須
  • GCD on Blackboard https://atcoder.jp/contests/abc125/tasks/abc125_c
    • 数列において、ある数 Ai を削除したときの最大公約数の最大値を求める。
    • 左右から累積 GCD を計算しておいて、あるマスの左右の 累積 GCD を合体(gcd をとる)させればよい。セグ木でも OK

その他言い替えなど

必ず使われる要素を求めよ → 消してみて不都合がないか？を調べる

表題の通り、必ず使われる要素 → 消して不都合が出る。背理法的な感じ
必ず使われる は難しい条件なのでこういう言い替えをするといいって感じ？ 1つ以上使う は難しいから余事象を考える の亜種みたいな？

  • Yutori https://atcoder.jp/contests/abc161/tasks/abc161_e
    • この言いかえが難しい、この言いかえができれば、ある o の日に働かないことにして働き方を構成できるか？という問題になって、まだ取り付く島がありそうな気がする
    • ここから 数列のうち一つだけを消す→左右から累積 の典型を使うのが天才を要求されなくていいと思う

問題が解けない時に考えること

実は数や探索空間がすくなくて全探索できないか？

  • ABC-D ABC-E くらいで詰まったら
    • https://atcoder.jp/contests/abc235/tasks/abc235_d
      • まさにABC-D、出てくる数は全部 106 未満(106 を超えたら解になりえない)なので BFS で全探索できる
    • Many Requirements https://atcoder.jp/contests/abc165/tasks/abc165_c
      • 要素が M 以下、長さNの単調増加列は NM ではなく、枝を狩ることで減らすことができる。
      • 全探索できないか？と思ったら最大ケースでの計算量を計算するプログラムを書いてみるとよい、サボらない
    • I hate Factorization https://atcoder.jp/contests/abc166/tasks/abc166_d
    • 同上、探索範囲を絞って X になりうる かつ X が 109 以下である値の個数を調べる -> 探索範囲を広げてもその個数は増えないことを観察できれば、ワンチャン投げられる
    • 式に n乗 が出てきてたら探索範囲は n乗根 で抑えられることがおおい気がする

1変数固定できるならしてみる

1変数固定して全探索すると見通しがよくなることがある。見えない時は見えない。
3変数のときは真ん中(AとB、BとCが影響しあっているならB)を固定すると都合がよくなったりする。裏技ちっく。
こういうの割と強い人でもハマるので、持ってると稼げるかも。

ハッシュ(mod N とかも含む)を衝突させる組を一つ見つけよと言われたら鳩ノ巣原理

ハッシュを衝突させる組を一つ見つける問題は鳩ノ巣原理を考えると楽になることがある。ハッシュの集合の元が N 個あったら、 N + 1 個のハッシュを生成すればどれか一つは衝突している。

1対1の割り当て(例: アルファベットに数字を入れる)の場合、種類が少ない方を全探索すればよい

(特にABC-Dくらいまでの低難易度で)1対1の割り当てを考える場合、種類が少ない方を全探索できることがある。例えば、a-zに互いに異なる0-9を割り当てる場合、アルファベット側が11個以上ある場合は割り当てを作れないので考えなくてよい。(例外処理は必要) こうすることで実は全探索することができることがある。

  • Send More Money https://atcoder.jp/contests/abc198/tasks/abc198_d
    • アルファベットに互いに異なる0-9を割り当てる問題。アルファベットが11種類以上ある場合割り当てられず、10種類なら順列全探索でいける。

思いつかない時は数え上げ対象を可視化して特徴を探す

数え上げで方針が見えない場合、賢い言い替えが必要なことがある。賢い言い替えは睨んでいても出ないがちなので、可視化して攻めると良い

  • Roaming https://atcoder.jp/contests/abc156/tasks/abc156_e
    • 構成できる条件は、空き部屋の個数が min(n-1, k) 以下 と言い替えられる。これに気づくのはけっこう大変なので、k回操作したときの状態を列挙すると空き部屋はk以下だと気づけるかも
    • 厳しい重複除去が必要になったら負け筋かも