ymduu+2

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

コミックマーケット100参加します！(ファミコンエミュレータ本目次 & サンプル)

参加します！サンプルギリギリになってすみません！ファミコンエミュレータを自作する本です。おしながきは以下に貼ったツイの通りです。
エミュレータの実装のうち、コントローラ、カセット、CPU、PPU、APUの5つをそれぞれ解説してます。なかなか丁寧な解説になった & インターネット上で情報収集してて情報が足りず困った(特に APU)箇所を補完できる技術書になったと思いますので、メインの買い物のついでにお立ち寄りいただければと思います！
基本的には C/C++ がある程度書ける方を対象としていますが、ファミコンにおける各モジュールの挙動を解説してから実装に入るようにしていますので、ファミコン、ひいてはコンピュータがどう動いているんだろう？というところに興味のある方なら楽しんでいただけると思います。

エミュレータ本体のリポジトリは以下になってますので、筋力がある人はこのコードを読み解くことでもエミュレータ作れると思います。(雑)
cmake でビルドできるようになっているので、 Visual Studio のソリューションを cmake で生成して Visual Studio でコード読んだりビルドしたりする想定です。

github.com

以下目次 & サンプルになります。簡単ですみませんが、当日はよろしくお願いします！

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

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

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以下だと気づけるかも
    • 厳しい重複除去が必要になったら負け筋かも

典型90で自力できなかった問題リスト

2週目やらねばならぬリスト的な。多分もっとあるはずだけど、とりあえず今残ってるのだけ。(ほんとは★7はほぼ全部解説ACな気がする)
005 Restricted Digits（★7）
023 Avoid War（★7）
049 Flip Digits 2（★6）
057 Flip Flap（★6）
062 Paint All（★6）
065 RGB Balls 2（★7）
083 Colorful Graph（★6）

するめうめ

これはなに

docs.google.com

をやる

SRM 715 MaximumRange

max(+ の個数, - の個数)

class MaximumRange {
    public:
    int findMax(string s) {
        lint p = 0, m = 0;
        for (char c : s) {
            if (c == '+') {
                p++;
            }
            else {
                m++;
            }
        }

        return max(p, m);
    }
};

SRM 735 PalindromeSubsequence

aのみ、bのみを取り出すとそれは回文なので、答えのサイズは 2 以下。 1になるのは s が回文の時だけなので、その通り実装する。

class PalindromeSubsequence {
    public:
    vector<int> optimalPartition(string s) {
        auto t = s;
        reverse(ALLOF(t));

        if (s == t) {
            return vector<int>(s.length(), 1);
        }

        vector<int> ans;
        for (auto c : s) {
            if (c == 'a') {
                ans.push_back(1);
            }
            else {
                ans.push_back(2);
            }
        }

        return ans;
    }
};

SRM 729 MagicNumberThree

dp[i][j] := i 番目まで見て、余りが j になる場合の数として素直にDP

mint dp[100][3];

class MagicNumberThree {
    public:
    int countSubsequences(string s) {
        rep(i, 100) {
            rep(j, 3) {
                dp[i][j] = 0;
            }
        }

        int len = s.length();
        s = "*" + s;
        dp[0][0] = 1;

        rep(i, len) {
            int si = s[i + 1] - '0';
            si %= 3;
            rep(j, 3) {
                // いれる
                dp[i + 1][(j + si) % 3] += dp[i][j];
                // いれない
                dp[i + 1][j] += dp[i][j];
            }

        }


        return dp[len][0].x - 1;
    }
};

SRM 748 EraseToGCD

dp[i][j] := i 番目まで見て gcd が j である場合の数。 空集合の gcd は 0 である(gcd の単位元は 0 ) とすると都合がよいことに注意する

mint dp[510][1010];
class EraseToGCD {
    public:
    int countWays(vector<int> S, int goal) {
        rep(i, 510) {
            rep(j, 1010) {
                dp[i][j] = 0;
            }
        }

        int N = S.size();

        dp[0][S[0]] = 1;
        dp[0][0] = 1;
        rep(i, N - 1) {
            rep(j, 1010) {
                // 入れる
                dp[i + 1][euclidean_gcd(j, S[i + 1])] += dp[i][j];
                // 入れない
                dp[i + 1][j] += dp[i][j];
            }
        }

        return dp[N-1][goal].x;
    }
};

SRM 755 OneHandSort

  • Each element of target will be between 0 and N-1, inclusive.
  • All elements of target will be distinct.

なので、 i は i 番目(0-indexed) にくることがわかる。

よって、
i 番目にある値を 空きマスに退避
i を↑で開けたマスに移動

を繰り返せば OK。(idx[i] := i のインデックス の実装で頭を壊してしまったが、N <= 500 なのだから、テーブルを持たずに愚直をやってもよかった……)

class OneHandSort {
    public:
    vector<int> sortShelf(vector<int> target) {
        int N = target.size();

        vector<int> ans;
        vector<int> idx(N);
        rep(i, N) {
            idx[target[i]] = i;
        }

        auto processed = target;
        processed.push_back(-1);
        int blank = N;
        rep(i, N) {

            if (processed[i] != -1) {
                // i えらぶ
                ans.push_back(i);

                // 今入ってる数の場所を更新
                idx[processed[i]] = blank;
                swap(processed[i], processed[blank]);
                blank = i;
            }

            // idx[i] えらぶ
            ans.push_back(idx[i]);

            // 今入ってる数の場所を更新
            swap(processed[idx[i]], processed[blank]);
            blank = idx[i];
            idx[i] = i;

            //cout << processed << "\n";
        }

        return ans;
    }
};

精選100問をやる

これはなに

ABC の 400 500 が埋まり、 experimental でない 水 diff が埋まり、experimental でなく AGC でもない 青diff もだいぶ埋まり、蟻本類題も中級までやったため精進の方向性が迷子になってしまった…… 次はなにをやろうかなと思ったところで、今足りていないのは何かを考える。

  • 知識はある程度身に着いた気がする
  • 思いつく能力みたいなのは全然足りていないけど、これは粛々と数をこなすしかない気がするので保留
  • なんとなく現状速さと正確さがが足りない気がしている
    • 今の知識セットのまま速くなればレート200は盛れる気がするし、正確さを得れば爆死が減って精神によい(ハードル走の反省……)

その辺を色々考えて、イカの精進が思いついた
(要するにちょっと下くらいの問題を時間を計って短時間で解いてみようという試み)

  • experimental な 水 青 diff埋め
    • experimental difficulty は一色ぶんくらい高く出ているような気がするので、下埋めの狙い
  • 平成ABC(ABC041以前)の D 埋め
    • 実は実質 experimental な 水 青 diff埋め
  • 精選100問 埋め
    • 目指せ水色コーダー の記事なので、やっぱり下埋めの狙いなのだけど、"100 問全部解けたら、水色コーダーどころか青色コーダーくらいの実力が付くと思います。"らしいんで、信じるのだ……

思いついた中で、現環境に合わなかろう古い問題を埋めるよりも赤い人のおすすめ100問のほうがコスパがよかろうということで精選100問をやることに。

レギュレーション

  • 時間を計る
    • 速さを定量的に評価するため。
  • ライブラリ禁止
    • 実装の筋トレも目的のひとつなので。
    • ただし非本質部分(ダイクストラに対するグラフテンプレート部分とか)はオッケー
    • 蟻本写経はオッケー
      • 自己流の悪い実装をしてもしかたないので……
  • 解いたら時間、自力 or not、感想をここに書く
  • できれば朝やる
    • 基礎力トレーニング
    • とか言いつつ、おせんべいが やや難問 とか言って登場したりするのでできる限りで
  • できれば疑似コードを手で書く
    • バックスペース禁止はむりだけど……

結果

num time submit                                                                                感想(どういうバグらせをしたか等)                                                                               
1　 4:30 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4556791#1 重複NG とかを読み飛ばしてちょっと戻った
2　 7:56 https://atcoder.jp/contests/abc106/submissions/14085318 奇数 を読み飛ばして合わず、変数名を間違えて合わず をした(考えながら実装をするな)
3　 5:55 https://atcoder.jp/contests/abc122/submissions/14085853 疑似コードを書くようにした 一度も戻らずAC
4　 7:51 https://atcoder.jp/contests/pakencamp-2019-day3/submissions/14086112 疑似コードというか C++ のコードを手書きしているんだけど……
5　 8:32 https://atcoder.jp/contests/abc095/submissions/14086472 max と min を間違えて1回休み
6 11:03 https://atcoder.jp/contests/sumitrust2019/submissions/14104743 3桁決め打ち、フラグ立てる時どこまで埋まっているかを見ず1回戻り
7 21:27 https://atcoder.jp/contests/joi2007ho/submissions/14148247 面白い、頂点 P, Q, R, S のうち2点を決めれば正方形が定まるので、全探索するのはN2でOK
8 15:33 https://atcoder.jp/contests/s8pc-6/submissions/14169626 興味があるのは 人が行きうる座標だけなのでそれを全探索 手戻りなし(のわりに遅い？)
9 16:04 https://atcoder.jp/contests/joi2008yo/submissions/14190764 手戻り無し のわりに遅いかなあ。 JOI、座標好きがちなのでベクトルのライブラリがほしくなってくる
10 4:05 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4572490#1 手戻り無し
11 10:07 https://atcoder.jp/contests/abc128/submissions/14401968 条件が若干複雑なので紙で条件を整理すると事故らなくてよいですね
12 11:45 https://atcoder.jp/contests/abc002/submissions/14422184 集合の中にいる人の組を全探索するときに同じ人間の組み合わせを許容してしまい1回戻り
13 10:10 https://atcoder.jp/contests/joi2008yo/submissions/14442890 手戻り無し
14 23:34 https://atcoder.jp/contests/s8pc-4/submissions/14462776 累積 max を持っておくと実装が楽。編集していいビルを全探索するか見えるビルを全探索するかで迷った、コストを計算する式を間違えてコストが負になった
15 11:30 https://atcoder.jp/contests/abc145/submissions/14601298 添字を2回間違えて時間を食った、1回目は1->2->3 のルートの長さを6回足してた(なんで)
16 6:35 https://atcoder.jp/contests/abc150/submissions/14626459 フラグを書き換える場所と辞書順の値を誤って1回戻った
17 31:56 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4625270#1 言われて見れば順列全探索だなあ、と思い next_permutation を書き、バグらせて結局dfsを書いた。グリッド上の斜めはx座標とy座標の和または差が一定。
18 6:09 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4628621#2 手戻り無し、次の数の場所を探すときにupper_boundが使える
19 23:37 https://atcoder.jp/contests/joi2009ho/submissions/14875840 各クエリで二分探索して 家 の左右の店を見つければよい。(番兵として距離dにも店を置いておく)、== と = を間違える古典的なやつをして1バグ
20 7:23 https://atcoder.jp/contests/abc077/submissions/14894821 固定するのは直接影響する要素が多いもの(今回はB)がよい、 + と * を間違えて1バグ
21 19:39(+2WA) https://atcoder.jp/contests/abc023/submissions/14958761 H_i > k なる k は達成不可能なのを見落として1WA、デバッグ中に1WA
22 41:11 https://atcoder.jp/contests/arc054/submissions/15034683 謎の定数(迫真) 二分法は初めてだったので時間がかかった 追記: 2.164042560698 は3 / (2log2) で、fx = x + P(2x/1.5) の第二項目にあたる
23 13:52 https://atcoder.jp/contests/joi2008ho/submissions/15057057 N = 1000 なので半分全列挙して相方を二分探索。全列挙した配列をソートし忘れて1バグ
24 32:17 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4651272#1 問題の読解が難しかった、出次数0の点を展開するのに1かかるなどを見逃してハマった(適当に時間を増やしたり減らしたりして通してしまった節がある、問題文から何をすると時間が経つのか読み取れなくない？)
25 10:08 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4656192#2 手戻り無し
26 9:23 https://atcoder.jp/contests/abc138/submissions/15214611 手戻り無し
27 43:21(+3WA) https://atcoder.jp/contests/joi2009yo/submissions/15232708 x と y を間違える、nx と x を間違える、そのマスの探索が終わったらそのマスの visitedフラグを折る(これが本質)を忘れるなどしてハマった、depth を最初引数にしなかったのも混乱を助長した、多少冗長でもわかりやすさを優先した方がよい
28 5:55 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4671578#1 while の条件書き忘れ(そんなことある？)と != と == を間違えて(そんなことある？)2回バグらせたけどどちらも一瞬で解決できた
29 8:38 https://atcoder.jp/contests/abc007/submissions/15249845 壁かどうかを見るのを忘れて1回バグった(そんなことある？)
30 16:38 (+ 1TLE) https://atcoder.jp/contests/joi2011yo/submissions/15325682 visited な場所はキューに入れない から大丈夫と思ってキューから出したもののvisitedチェックをサボったらTLEした(同じマスに同じ距離で到達するパスが複数ある場合、同じマスからのパスを複数回数えてしまう)
31 42:54 https://atcoder.jp/contests/joi2012yo/submissions/15340713 W と H を取る順番を間違えて1回戻った、純粋に六角形の遷移を考えるのに時間を食った
32 24:59 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4692845#1 普通に bfs だけど壁の扱いが厄介、h と w を 1か所間違えて1回戻り
33 13:10 https://atcoder.jp/contests/abc088/submissions/15373165 普通に bfs 、スタートとゴールのことを忘れて1回戻り
34 1:53 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4704355#1 手戻り無し
35 23:06 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4704427#1 ナップザックの大きさを勘違いしていて1WA、デバッグに苦労した
36 4:38 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4706743#1 手戻り無し、個数制限がない場合は遷移の方法を少し変えることで対応できるのであった。
37 8:01 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4706794#1 手戻り無し、36 の個数制限なしナップザック問題の気持ちになるとOK
38 18:29 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4706913#1 1-indexed にする時にstring::length を先頭にダミー文字を追加した後に使ってしまいバグらせた。蟻本の「どれかであるので」という考え方が重要なのであった
39 14:47 https://atcoder.jp/contests/joi2011yo/submissions/15484514 手戻りなし、dp[i][j] := i 番目まで計算して、結果が j になる場合の数。先頭と末尾を特別扱いするのでインデックス注意
40 44:54 https://atcoder.jp/contests/joi2012yo/submissions/15485657 配るDP にしたら i 日目 は パスタ k しか食べてはならぬ の条件を i + 1日目 に適用してしまいバグらせた。 前日と前々日の食事さえ分かっていればよいので、それらを添字に持つ
41 18:48 https://atcoder.jp/contests/joi2013yo/submissions/15496981 手戻りなし、dp[i][j] := i 日目 にフク j を着るときの最大スコア
42 19:11 https://atcoder.jp/contests/joi2015yo/submissions/15513581 M 日目 にも移動できることを忘れて答えが合わなかった。 dp[i][j] := i 日目 に j に居る時の最小疲労度
43 21:17 https://atcoder.jp/contests/pakencamp-2019-day3/submissions/15532988 手戻り無し。結局 i 列目 の塗り方は i-1 列目の塗り方にのみ依存するので、 dp[i][c] := i 列目 を色 c で塗る時の最小コスト。i 列目 を色 c で塗る場合を全てまとめて考えてよいことに対応する。
44 (時間を計っていないけれど合計1hくらい？) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4727213#1 個数制限なしナップサック問題なのだけど、普通にやるとMLEする。配列を使いまわすとOK
45 20:33 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4730700#2 素直に dp[i][j] := i番目のデータがjに復号される時の最小コスト
46 33:58 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4730839#2 素直な区間DP、[m, r) をマージした行列の行数を間違えて1回戻った
47 40:01 https://atcoder.jp/contests/joi2015ho/submissions/15655523 円形 -> 二周分配列(今回はDPテーブル)を持つ。手番の存在を忘れて1回戻り、メモ化を忘れて1TLE
48 - (自力できず) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4736472#1 dp[l][r] := [l, r) にできる操作の回数 なのだけど、2つの区間の和になる遷移 と 長さが2小さい区間の外側の差が1以下の遷移 を同時にやろうとして迷走してしまい解説AC
49 38:20 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4738606#2 始点が定まっていない。と思ったら始点を0にする大嘘が通ってしまうので笑う。と思ったがそれはそうか*1蟻本を見ながら頑張って書いた。dp[S][v] := Sに含まれる頂点を訪問済みで、vにいるとき、そこから残りの頂点を訪問して start に帰ってくるときの最小コスト。初期値(再帰の停止条件)が全頂点を訪問し終わった時であることに注意する
50 101:11 https://atcoder.jp/contests/s8pc-1/submissions/15803043 dp[S][v] := 訪問済み頂点集合がSでvにいる時の(最小コスト, 場合の数) のペア として下から配る DP をする、蟻本版でやろうとして無限に迷子になった
51 29:40 https://atcoder.jp/contests/joi2014yo/submissions/15815045 手戻りなし、 dp[i][S] := i日目に集合Sの人が参加する場合の数、SからS'に遷移するときに S & S'が0でないこと、各日の責任者を含むことを確認する
52 33:43 https://atcoder.jp/contests/joi2017yo/submissions/15818888 手戻りなし、 dp[S] := ぬいぐるみを左から詰めていくとしたとき、集合Sを置き終わった時の最小コスト。TSP 同様 n! を 2n に落とす系。 bitDP と言われてなければ解けなかった気がする……
53 31:43 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4754100#1 手戻りなし、セグ木の方しか知らないので貼ってしまった、dp[i] := ai を左端としたときの最長の LIS で更新はchmax(dp[i], [0, ai) の最大値 + 1)、aの範囲が広いので座圧がひつよう
54 14:51(+ 1WA) https://atcoder.jp/contests/abc006/submissions/15838521 i 番目までソートする手順から i + 1 番目までソートする手順を構築しようとするも嘘なのでWA、よく考えると LIS の場所は変えずにそれ以外の場所だけ変えると最小コストになることがわかるので昨日書いた LIS のコードを貼ってAC
55 15:23 https://atcoder.jp/contests/abc134/submissions/15865751 手戻りなし(が、すでに解いたことがあったため……)、作られる増加列の先頭に注目すると、広義単調減少になっていることがわかるので、LISの要領で最長減少部分列の長さを求めるとGG
56 10:45 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4760053#1 手戻りなし、素直なdijkstra
57 17:07 https://atcoder.jp/contests/joi2008yo/submissions/15881676 ダイクストラをソラで書く縛りをしているのでキューに入れる不等号を逆にしてバグらせた
58 48:13 https://atcoder.jp/contests/joi2016yo/submissions/15882860 手戻りなし、普通に実装が重かった、bfs パートは素直に bfs をすると TLE するのでそのノードにより近いゾンビ町が存在するときは探索を打ち切る枝刈りをいれるとO(N)になる気がする。
59 83:39 https://atcoder.jp/contests/joi2014yo/submissions/15984809 グラフ構築パートで dfs を書いて1回戻り(dfs では最短経路は求まらないのであった)、bfs をなんとなく書いたらめちゃくちゃバグって苦しくなった。visited はキューに入れる時に true にしないとほかのノードからそのノードに到達したときに最適でない経路が記録されてしまうのでNG。幅優先探索なんもわかってなかった
60 9:39 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4765542#1 負閉路検出は2回目で更新があったらでOKなのであった。(ベルマンフォードと同じ) 蟻本の実装だと負辺がある場合 INF から引かれてしまうので、 INF からは遷移しない、出力時に INF の範囲を広くする(あり得る最大パス長を超えたらINF)などの工夫が必要。
追記: WF の負閉路検出は dist[i][i] < 0 でもできるらしい。たしかに……
61 11:02 https://atcoder.jp/contests/abc012/submissions/16014119 手戻りなし、問題文の読解が難しいけど WF して全始点について調べたらOK
62 5:42 https://atcoder.jp/contests/abc079/submissions/16021273 手戻りなし、グラフに見えるまでが大変な問題な気がするけど流石に最近は見えるようになった気もする
63 64:11 https://atcoder.jp/contests/abc074/submissions/16022335 与えられたAを完全グラフの隣接行列と見るまではよかったものの最小全域木を求めたり辺を小さい順に入れようとしたりして迷走した、迂回路がある辺は取り除いてよいので、A[i][j] == A[i][k] + A[k][j] なる k があったらその辺を除けばOK
64 7:57 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4772473#1 手戻りなし。今まで クラスカル の方が簡単なのでクラスカル を書いていたが、ここでは経験のため プリム を書いた。このプリム は ElogE な気がするけど、どうするとElogV になるんだろう(蟻本のダイクストラ同様の議論ができる？)
64_2 4:19 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4772504#1 プリム法。こちらの方が実装が楽なので以降こちらを使う。(UnionFInd はまだ貼ってる)
65 28:42 https://atcoder.jp/contests/joisc2010/submissions/16039928 手戻りなし。K = 1 のときは普通に最小全域木を求めたらよくて、そうでないときは最小全域木から自由に辺をK-1本除ける(会場と会場の間の辺を自由に1本除去できるので、好きな辺を除去するための配置を構築できるはず)
66 30:55 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4775067#1 int と double を間違えて何度か戻った。 基本はセル？をノードとしたグラフを考えて MST するだけ
67 11:07 https://atcoder.jp/contests/abc065/submissions/16068331 手戻りなし。3回目なので流石にネタを知っている、この問題設定では MST に含まれうるのは x座標とy座標でソートした時に隣り合う点を含む辺のみ。
68 2:34 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783941#1 + と * を typo して1回もどり(そんなことある？)
69 10:59 https://atcoder.jp/contests/abc084/submissions/16175469 1 を素数にしてしまい1回戻り、これ本質は 累積和 なのでは……
70 2:28 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4784031#1 かけた時に mod 取り忘れて1回戻り、毎回蟻本版非再帰はかしこいなあとなる
71 14:06 https://atcoder.jp/contests/s8pc-1/submissions/16178360 今いる場所を更新するのを忘れて1回戻り、これも本質は累積和……
72 8:39 https://atcoder.jp/contests/abc034/submissions/16178666 H+W が 105 を超えうるのを忘れて1回戻り
73 13:09 https://atcoder.jp/contests/abc145/submissions/16179230 手戻りなし、基底ベクトルがちょっと変な座標平面で経路数える問題をやるだけ
74 63:04 https://atcoder.jp/contests/abc021/submissions/16182256 O(nk) DP の計算量の見積もりを間違えて1TLE、その後DPテーブルを見るとパスカルの三角形になっていることに気づいてAC
75 解説AC https://atcoder.jp/contests/abc149/submissions/16202402 むずい、期待値の線形性から各ノードの寄与度を個別に計算してよい、全方位木DP が必要そうな気持ちになって手が止まるんだけど、根つき木にした時に子側のノード数は木DP、親側のノード数は全体から引けば求まる(典型)(CF665 Div2 Dでも出た)
76 8:18 https://atcoder.jp/contests/nikkei2019-final/submissions/16214202 手戻りなし、累積和で区間和を高速化するとO(N2)で全探索できるようになる
77 15:25 https://atcoder.jp/contests/joi2010ho/submissions/16233240 区間和を累積和で高速化するだけ、あまりを取り損ねて1回戻り
78 31:11 https://atcoder.jp/contests/joi2011ho/submissions/16253199 実は2D累積和ははじめて、けんちょん氏の記事を見ながら頑張って書いたものの半開区間の感覚がバグってクエリ時の +1 を忘れてバグらせた(ちなみにけんちょん氏の記事の2D累積和はクエリ時のxとyが逆？)
79 26:59 https://atcoder.jp/contests/abc106/submissions/16272131 2D累積和を構築するときに0-indexedと1-indexedを間違えて1回戻り、1回解いてネタを知ってる + 累積和という情報あり、というかなりのズル、包含される区間の個数は2D平面にプロットすると累積和で高速に求められるのであった。
追記: 実装に若干嘘を埋めていて、入力が L <= R を期待しているコードになっている(L > R なる区間を足してしまっているが、そこが0であることを期待している)。今回の制約はそうなので、通る。
80 31:18 https://atcoder.jp/contests/gigacode-2019/submissions/16463172 素直に2D累積和すると全探索できる。試しにライブラリ形式で実装してみた、べた書きだとインデックスを間違えがちなので相性はよさそう
81 3:43 https://atcoder.jp/contests/abc014/submissions/16475363 素直な imos 法するだけ
82 23:15 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4813839#1 素直な imos 法するだけ、時刻のパースがヘタクソすぎる
83 22分程度(CEDEC見ながら) https://atcoder.jp/contests/joi2015ho/submissions/16478616 imos をすると各路線を何回通るかわかるので、どちらがお得か計算可能
84 たくさん https://atcoder.jp/contests/joi2012ho/submissions/16489765 三角形のいもす法をいもす研ガン見しながらやった、変な座標系に対するいもす法の構築は目新しかった
85 7:55 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4816695#1 UF のライブラリを再実装してから解いた、 root の else 節で値を返し忘れておりデバッグした
86 4:02 https://atcoder.jp/contests/abc075/submissions/16500077 除く辺を全探索できる
87 15:46 https://atcoder.jp/contests/abc120/submissions/16521383 UnionFind は分離できないので手順を逆回しして併合にする。最初の0が要らないのに気づかずちょっとデバッグした
88 19:06 https://atcoder.jp/contests/joi2008ho/submissions/16534292 (色, 個数)のペアを保持する。置き換えが発生したとき、置き換えによって2つ手前の集合と同じ色になる場合マージする必要があることを忘れて1回戻った。毎回適切にマージすると保持される区間の色は交互になる(ex: 0, 1, 0, 1...)はずなので、計算量は悪化しない。
89 82:12 https://atcoder.jp/contests/joi2013ho/submissions/16537069 ランレングス圧縮した後同じ色が{2, 3, 4以上}連続する時について丁寧に場合分けする、2の場合が複雑でつらかった
解説を読むと交互列の長さでランレングス圧縮しており、かしこい
90 24:00 https://atcoder.jp/contests/s8pc-5/submissions/16550535 最小値の最大化なので二分探索(二分法)をする。最小半径 r を固定するとそれが可能かどうかはO((N+M)2) で判定できて十分高速。
91 27:49 https://atcoder.jp/contests/abc144/submissions/16558668 平面図形の問題に落とせる、2回計算ミスした
92 48:20 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4820842#1 y座標ごとに始点をリセットするのを忘れて1バグ、デバッグに苦労した
93 40:10 https://atcoder.jp/contests/s8pc-3/submissions/16587818 落下処理とスコア計算処理を 92 から使いまわしたものの結局バグっていた、定数倍気にしなければ各行をランレングス圧縮してK以上だったら消える、とするのがいいのかも
94 38:38 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4824261#1 計算量はたいしたことないので vector::erase を使ってサボれる。
95 6:33 https://atcoder.jp/contests/abc149/submissions/16604842 貪欲
96 5:52 https://atcoder.jp/contests/abc139/submissions/16604984 i mod j (i < j) は i なので、1, 2, ..., N を1反時計回りにずらした Pi を考えると良い、適当にいじっていればすぐに思いつくけど、こういうのを直感以外で思いつくのはどうすればいいんだろうね
97 43:33 https://atcoder.jp/contests/abc150/submissions/16622766 式変形すると ak の奇数倍が 2X になればよいことがわかるので、全体の lcm の奇数倍が 2X 以下であるものを数えればよい。ただし、 ak の偶数倍が lcm になるときは解がなくなることに気を付ける。(lcm の奇数倍が ak の奇数倍ではないため)
98 7分くらい https://atcoder.jp/contests/sumitrust2019/submissions/16648910 各人を独立に考えてよくて、前から見て人iを見た時に A_i-1 の登場回数 - Ai の登場回数 通りの色があることがわかる。
99 155:24 https://atcoder.jp/contests/ddcc2020-qual/submissions/16666763 操作の順番は回数に寄与しないという考察はそこそこ早く出たものの、へんなバグらせをして無限に時間をかけてしまった
100 31:40 https://atcoder.jp/contests/tenka1-2018-beginner/submissions/16749495 集合を頂点、共通の数を辺とみなすと完全グラフの辺にちょうど1-Nの数字を振れればいいことがわかるので、その通りに構築する、出力フォーマットを間違えて1WA

メモ

19: こういう「二分探索して自分以下の数があれば返す」みたいなクエリはライブラリ化してもいいかもしれない(upper_bound -> begin じゃなければ一個もどす)

感想

  • 1日1問やるにはちょうどいい難易度だった
  • 簡単すぎ、と思うこともややあったけれど、全体的に見れば簡単すぎ、と言ってはいけないくらいの時間がかかっている問題が多いのでやっぱりちょうどいい難易度だった気がする
  • 実装がやや複雑そうなときだけ疑似コードを書いたけれど、しょうもない添え字バグとかは減った……気がする
  • それでも全体的にしょうもないバグ埋める率は高め……
  • DP の部分がめちゃめちゃいい練習になった
  • ライブラリ縛った意味はそこそこあった気がする、少なくともここに上がっているアルゴリズムとデータ構造で理解に不安が残るものはなくなったはず

*1:一筆書きの閉路なので、どこが始点になろうが解が存在するなら長さは同じはず

蟻本をする2(中級編)

ymduu.hatenablog.com
の続き、こんどは中級編だ
例題 3-1-1　lower_bound
自力: 〇
lower_bound やるだけ
類題
自力: 〇
https://atcoder.jp/contests/abc077/submissions/10357158
Bを決めた時に使えるCの場合の数を累積和しておけばA固定でも解ける、Bを固定するとそういう小細工をしなくても解ける
3つの変数がうごく -> 真ん中(のこり2つの両方に直接影響する) を固定すると嬉しいことが多い

例題 3-1-2　Cable Master (POJ No.1064)
自力: 〇
解を仮定して二分探索シリーズ
類題:
自力: 〇
https://atcoder.jp/contests/abc023/submissions/10373489
受けるペナルティを固定すると、各風船を何秒以内に破壊すべきかがわかるのでソートすれば可能かどうかをNlogNで判定可能

例題 3-1-3　Aggressive Cows (POJ No.2456)
自力: 〇
上と同様に最小値を決め打ちすればOK
類題:
自力: 〇
https://atcoder.jp/contests/code-festival-2015-quala/submissions/10421073

例題 3-1-4　平均最大化
自力: ×
解xを固定すると、その解が可能かどうかは式変形により貪欲に判定できるようになるパターン
類題:
自力: 〇
https://atcoder.jp/contests/abc034/submissions/10422151

例題 3-2-1　Subsequence (POJ No.3061)
自力: 〇
oldskool しゃくとり
類題:
自力: 〇
https://atcoder.jp/contests/abc032/submissions/10506572

例題 3-2-2　Jessica's Reading Problem (POJ No.3320)
自力: 〇
ある要素aの個数が0になった時は次のaが現れるまでrを進める、とすると実装が楽になる
類題:
自力:〇
https://atcoder.jp/contests/arc022/submissions/10524534
上に同じ

例題 3-2-3　Face The Right Way (POJ No.3276)
自力: ×
ライツアウトの結果は操作を行う場所の集合にのみ依存し、順番には依存しないことに気を付ける。
これさえ分かっていれば、左から順番に決めていくことで問題のサイズを1ずつ小さくすることができる。
ただし、この問題はそれだけではだめで、数列 f において、区間 [l, r] の和は、[l-1, r-1] + f[r] - f[l-1] で表せることを利用して差分だけ更新していく必要がある。
-> 長さNの数列において、固定長の区間を全走査したい場合は差分更新することでO(N)にできる
類題:
自力: 〇
https://atcoder.jp/contests/arc064/submissions/10538540
端から順番に決めていく系
例題 3-2-4　Fliptile (POJ No.3279)
自力: ×
今度は上1行を固定すると全体のひっくり返し方が決まるパターン
類題:
自力: 〇
https://atcoder.jp/contests/joi2008yo/submissions/10544690

例題 3-2-5　Physics Experiment (POJ No.3684)
自力: 〇
蟻と同じ考察をすればオッケー
類題:
自力: ×
https://atcoder.jp/contests/agc013/submissions/10667472
蟻の考察をすると蟻の順番は変わらないことがわかるけれど、その先で0番の蟻がどこにいくのか分からずgg
けんちょんさんのブログを見て、原点を左右に通過する蟻の数を数えると最初の位置からいくつズレたかが分かるのでOK

例題 3-2-6　4 Values whose Sum is 0 (POJ No.2785)
自力: 〇
くじびきと同じ
類題:
自力: 〇
https://atcoder.jp/contests/joi2008ho/submissions/10756669

例題 3-2-7　巨大ナップサック
自力: ×
類題: 〇
実装が重くてしんどい、DPの方のナップザック問題はソラで書けるようになっていたので成長をかんじる
https://atcoder.jp/contests/abc032/submissions/10771038

例題 3-2-8　領域の個数
自力: ×
線がある座標の±1の場所も含めて座圧するのがポイント
類題:
自力: 〇
AOJ で解いたんだけどURLがどっかいってしまった

例題 3-3-1　Crane (POJ No.2991)
自力: ×
つらい
類題:
自力: 〇
https://atcoder.jp/contests/arc008/submissions/10939720
手で試すとちゃんと結合則が成り立ってエモいです、ついでに座圧の復習もできてアド

例題 3-3-2　バブルソートの交換回数
自力: ×
類題:
自力: 〇
https://atcoder.jp/contests/chokudai_S001/submissions/10963786 転倒数、こわそう、と思っていたけど前から順番にセグ木で出てきた数を覚えておいて今見ている数より大きい数の個数を数えるだけだった、こわくない

例題 3-3-3　A Simple Problem with Integers (POJ No.3468)
自力: 〇
類題:
RSQRAQ
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4270233#1

例題 3-3-4　K-th Number (POJ No.2104)
自力: 〇
類題:
自力: 〇
https://atcoder.jp/contests/arc033/submissions/10982608
平方分割はセグ木の深さを1にして各ノードの区間長をsqrt(N) にした感じ、実装が軽いのに一点更新区間取得が超定数倍軽いsqrt(N)でできてえらい

例題 3-4-1　巡回セールスマン問題
自力: ×
類題:
自力: △(ソラで書けず)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4281785#1

例題 3-4-2　Traveling by Stagecoach (POJ No.2686)
自力: 〇
bitDPというよりも拡張ダイクストラのような？
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4282437#1
脳内でなく例題をAOJでACしたので類題は無し

例題 3-4-3　ドミノ敷き詰め
自力: ×
dp[i][j][S] := i行j列まで埋まっていて、下端の状態がSの時の場合の数 なるbitDPをする
類題:
自力: 〇
https://atcoder.jp/contests/code-festival-2014-quala/submissions/11078114

例題 3-4-4　フィボナッチ数列
自力: ×
漸化式のn番目は漸化式を一つすすめる行列を定義してその行列をかけることで求められる。
は、という感じだけど言われればまあそうだね、という感じだし行列積の手続きからも自明
類題
自力: 〇
https://atcoder.jp/contests/abc009/submissions/11369837
演算が特殊でも演算が半環をなしていれば行列積が計算できるのでgg

例題 3-4-5　Blocks (POJ No.3734)
自力: ×

http://poj.org/showsource?solution_id=21536909

DP 高速化 としての行列累乗、結局赤の偶奇と緑の偶奇で4通りしか状態がないので O(N) のDPは自然に思いつくはずで、それを行列累乗で高速化する。
最初 2 * 2 の 行列を考えてハマったけどこういうのは1列の行列で考えると見通しがよくなりがちっぽい
類題
POJ で実装までやったのでなし

例題 3-4-7　Matrix Power Series (POJ No.3233)
自力: ×

http://poj.org/showsource?solution_id=21552608
知ってるかゲーって気はするけど
類題
POJ で実装までやったのでなし

例題 3-4-8　Minimizing Maximizer (POJ No.1769)
自力: ×
POJ だと C++ の新しい機能バリバリの抽象化セグ木が使いづらいので、1点更新区間min のセグ木を写経した、よい復習になった

http://poj.org/showsource?solution_id=21553375
類題: POJ で実装までやったのでなし
てか類題が赤 diff ばっかりなんだが

ついにフローにたどりつきました
例題 3-5-1　最大通信量
例題はなし
類題:
自力: △(蟻本のF-Fを使ってるライブラリに合わせて改変しつつ写経した)

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4329720
自力: 〇
マークしてる人から辺を張るノードを一つ用意してそこにたどり着けなくするための最小カットを求めればOK -> 最大流最小カット からフローを流せばOK

例題 3-5-2　仕事の割り当て
自力: 〇
二部グラフの最大マッチングは知っていたのでフローを持っていれば解けるね

類題:
自力: 〇
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4330160#2
自力: 〇

https://atcoder.jp/contests/abc091/submissions/11633199

例題 3-5-3 はたいへんなのでパス(は)
例題 3-5-4 最小費用流
自力: ×
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4336350#1
残余グラフにおいて、辺に流すときのコストを距離と見て最短経路問題を解き、その最短経路(つまり、最小コストで s-t に流せる経路)に流せるだけ流すことを繰り返す。

例題 3-5-5　Asteroids (POJ No.3041)
自力: ×
http://poj.org/showsource?solution_id=21562701
X 座標と Y 座標 をグラフのノードとみなし、隕石があるところに辺を張った二部グラフを構成する
そのようなグラフの最小点カバー問題を解けばよく(点 = ビームを撃つ X or Y座標)、これは二部グラフの最大マッチングに等しい
類題:

https://atcoder.jp/contests/soundhound2018/submissions/11692524
- グリッドグラフは市松模様に塗ると二部グラフ
- (x + y) もしくは (x - y) の偶奇でどちらに属するかを判定可能
- 二部グラフの最大マッチングをするときには、2つの集合をU, V として U -> V みたいに向きを付けておかないとフローを流すときに戻れてしまい終わる
- 最大安定集合(ノード同士が隣接しないようになるべく多くのノードを取る) -> 最大マッチングから計算できる、蟻本P199参照

例題 3-5-6　Evacuation (POJ No.3057)
自力: ×
この辺からくるしくなってきた
時間を固定すると(各時間,各ドア)から出られうる人間 という 二部グラフが作れるので、最大マッチングが人間の数だけあればOK
類題:
自力: ×
https://atcoder.jp/contests/arc013/submissions/11709738
作れうる各重さに関して高橋君のノード、青木君のノードを作成し、それらと鉄塊を表すノードを繋いだ二部グラフに始点終点を追加したもの に対してフローを流そうとしたが嘘なのでGG
正しい方法は、各重さについて2個以上作れればよいので、各重さを表すノードを2個ずつ作り、それらが同時に作れる場合(≒一つの鉄塊から切り出せる場合)に辺を張る。
そうして構成したグラフは二部グラフになり、「各重さが2つ以上作れる」 とは、このグラフの辺を適切に選んで、どの頂点も選んだ辺に接続している 状態にできればよい。
これは最小辺カバー問題であるので、最大マッチングから求めることができる。(蟻本P199参照)

なんだかお気持ちは Asteroids と同じ気もする
二部グラフに落としたいなあという気持ちがあって、{XY, 作れる重さ}を二部グラフの集合として、{隕石がある, 同時に作れる}を辺として、それの{最小点カバー, 最小辺カバー}を求める。

例題 3-5-7　Dining (POJ No.3281)
自力: ×
(食べ物, 牛), (飲み物, 牛) の同時割り当てを求める問題。
食べ物 -> 牛 -> 飲み物 のフローを流したくなるが、それはだめ。
なぜなら、一つの牛に対して複数のフローが流れてしまう可能性があるから(蟻本の例: s->食べ物1->牛1->飲み物1->t とs->食べ物2->牛1->飲み物3->t が同時に流れうるが、これを2頭の要求を満足すると数えてしまう。)
食べ物側と飲み物側のマッチンググラフを分け、同じ牛同士の間に容量1の辺を張ることで、一つの牛には一つの割り当てが行われるようになり(P192 頂点に容量がある場合 の考え方と同じ)、正解となる。

http://poj.org/showsource?solution_id=21566325

例題 3-5-8　Dual Core CPU (POJ No.3469)
自力: ×
燃やす埋める問題、診断人さんのスライドがマジでわかりやすい。

www.slideshare.net
小問題一つに対し、コストのかかる選択肢が2つあってそれを選ぶ、さらにその選択肢間に依存関係がある(グラフに見えてくる)場合は適切なグラフを作り最小カット(=最大流)を計算するとうまくいくことが多い。
気持ちとしては、始点sと終点tを用意して、s -> 選択肢1に対応する辺 -> 小問題に対応する頂点 -> 選択肢2に対応する辺 -> t なるグラフを作って、適切な方をカットする(≒選択肢を選ぶ)ことでs-tカットをつくるぞ、というもの。
蟻本の構築方法を後から見ても若干 ？？？ という感じだったので先に診断人さんのスライドを見てよかった

http://poj.org/showsource?solution_id=21566683

ところで、Dinic の計算量ってO(EV2)だけど、この問題はV = 2 * 104、E = 2 * 105 で、4 * 1013 で明らかに適用できないサイズに見えるんですけど……
Dinic は速い！とは聞くものの105倍速くなったりするものだろうか、それとも計算量の見積もりを間違えている？

例題 3-5-9　Farm Tour (POJ No.2135)
自力: 〇

http://poj.org/showsource?solution_id=21566867
容量2の最小費用流を流すだけ、逆向きの辺も追加する必要があることに注意(最大流と同じような議論で無向の時は逆辺を張ればいいことがわかる)

この辺全部 POJ で解いているけど、フロー系の問題は Dinic と Ford-Fulkerson と Primal-Dual さえあればあとは個別のアドホックなので、ライブラリを C++03 に対応させる手間が少なくてらくだった

例題 3-5-10　Evacuation Plan (POJ No.2175)
自力: ×
二部グラフの最小重みマッチングは最大マッチングの時みたいに最小費用流を流すことで解ける。

類題:
自力: ×

https://atcoder.jp/contests/abc004/submissions/11717678

例題 3-5-11　The Windy's (POJ No.3686)
自力: ×

http://poj.org/showsource?solution_id=21579994
非直感的な式変形をする問題、工場iでj個のおもちゃを作る時、k番目(0-indexed)に到着した依頼は終了時間の総和にj-k回効いてくることから、工場の頂点を倍加して工場iでk回目の依頼を処理する、というノードを作り、おもちゃlからコスト(j-k) * Z[l][i] とした辺を張る。

例題 3-5-12　Intervals (POJ No.3680)
自力: ×

http://poj.org/showsource?solution_id=21580272
言いたいことは分かるけど自力で思いつくのは無理だなあ、最後だし撤退するのも気持ち悪いので写経AC
蟻本P205のFが一定の時負辺を除去するテクを使っている
これは負辺を除去するために、負辺に目一杯流す≒負辺(u, v)のコストを最初から計上して、代わりにコスト0でu->t, s->v (sは新たに追加した始点、tは新たに追加した終点)に流せる辺を追加するというもの。(これを飲み込むのに2時間くらいかかったので元気が出たらまとめる)

蟻本をする

やりかた: 蟻本読解と類題解きを非同期でやっていく(読みたいときにさくさく先に進むため)
類題を前から1問ずつ解いていってダメだったら適宜戻る、コンテスト中に解いたことがある場合はサボります(最悪)
類題の出典: https://qiita.com/drken/items/e77685614f3c6bf86f44
特別に断りがない限り例題の自力 or notは脳内AC(POJはつらいので)、類題は該当submitを併記

2-1 全探索

グリッド -> グラフライブラリのverifyがてら暇なときに埋めていく予定
例題 2-1-1　部分和問題
自力: 〇
類題: https://atcoder.jp/contests/arc061/submissions/9672420
自力: 〇

bit全探索だね
例題 2-1-2　Lake Counting (POJ No.2386)
自力: 〇
類題: https://atcoder.jp/contests/atc001/submissions/9673321
自力: 〇

例題 2-1-3　迷路の最短路
自力: 〇
類題: https://atcoder.jp/contests/abc007/submissions/9676680
例題 2-1-4　特殊な状態の列挙
自力: 〇
類題: https://atcoder.jp/contests/abc150/submissions/me
自力: 〇
コメント: next_permutationを使う問題というだけ

2-2 貪欲

例題 2-2-1　硬貨の問題
自力: 〇
AtCoder上に類題なさそうだしパス

例題 2-2-2　区間スケジューリング問題
自力: ×
区間スケジューリング問題 -> 末尾でソートして貪欲
区間を見たら先頭 or 末尾 でソート
知らなかったら無から思いつくのはかなりつらくないですか
類題: https://atcoder.jp/contests/keyence2020/submissions/9565253
自力: 〇
コメント: 蟻本やるかーって言いだした直後のこれだったのでラッキー

例題 2-2-3　Best Cow Line (POJ No.3617)
自力: 〇
辞書順最小 -> 先頭から貪欲
先頭と末尾が同じ場合は reverse して比較することで同じ区間を無視して比較できる かしこい
類題: https://atcoder.jp/contests/abc076/submissions/8885620
自力: 〇

例題 2-2-4　Saruman's Army (POJ No.3069)
制約が厳しい順に貪欲(あるある)
類題: https://atcoder.jp/contests/abc083/submissions/9697785
自力: 〇

Fence Repair (POJ No.3253)
自力: ×
小さい順に合成していけばよいというのが非自明だった、言われてみればそれはそうなのだけど
類題: https://codeforces.com/contest/462/submission/69303070
自力: 〇
ほぼ例題そのまんまだった、手順逆回し、大きい集合がたくさん出てくると有利なのでその通りにする

2-3 DP

例題 2-3-1　01ナップサック問題
自力: 〇
知っていたので……
類題: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4130992#1
自力: 〇
コラム:
貰うDPと配るDPの話、遷移元を意識するか遷移先を意識するか、という気持ちで理解している
個人的には"貰う" でメモ化再帰するのが一番らく(再帰関数が遅延評価っぽく解決してくれるため更新順序を考えなくて済むので)だと思うけど気がついたら配ってたりするのでわからんちん

例題 2-3-2　最長共通部分列問題
自力: ×
知っていたけど覚えていなかったので……
類題: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4131284#1
自力: △
解説見ながら写経しちゃった

例題 2-3-3　個数制限なしナップサック問題
自力: ×
ナップザック問題の、取得できる品物の個数が無限になったバージョン
dp[i+1][j] := i番目の品物から重さの総和がjイカになるように選んだ時の価値の最大値
とすると、 dp[i+1][j] を計算するとき、k(>=1)個品物iを取得する場合、dp[i+1][j-w[i]] を計算するときにk-1個選んだ場合と同様である と考えることができる。(<- 天才)
よって、dp[i+1][j-w[i]] (一つ以上の品物iを取得するかもしれない場合) とdp[i][j] (品物iを取得しない場合) から"貰う" ことでDPの更新とできる。
ふつうの(01)ナップザック問題では dp[i][j-w[i]] (品物iを取得する場合) とdp[i][j] (品物iを取得しない場合) から"貰う" ことでDPの更新とすることに注意する。(添え字が違う)
添え字の違いは遷移元の違いなのだなあ、という気持ち
類題: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4131387#1
自力: 〇
知ってればそれはできるね、という感じ

例題 2-3-4　01ナップサック問題その２ 自力: ×
類題: https://atcoder.jp/contests/abc032/submissions/9813660
自力: △
半分全列挙のところだけ×

例題 2-3-5　個数制限付き部分和問題
自力: ×
類題: https://atcoder.jp/contests/maximum-cup-2018/submissions/9830320
自力: 〇
DPの値にbool以上の意味を持たせる、って言われていれば素直に思いつく系

例題 2-3-6　最長増加部分列問題
自力: ×
類題: https://atcoder.jp/contests/chokudai_S001/submissions/9839984
まあ りす はDPでNlogNで求められるということを覚えていればよさそう

例題 2-3-7　分割数
自力: ×
解説が不親切シリーズ1
ここが詳しい

techtipshoge.blogspot.com

dp[i][j] := jのi分割(jのi分割、とはjをi個"イカ"の集合に分割する場合の数、であることに気を付ける、jをi個の集合に分割する場合の数、ではない) としたとき、分割した数の集合をa_k (0<=k<=i) とおくと、
1. a_k == 0 なるk が存在する場合
これはjのi-1分割に含まれるので、 dp[i-1][j]
2. そうでない場合 これは、jをi個の空でない集合に分割する必要があるので、集合が空集合にならないことを保証するためにi個の集合に先に1つだけ振り分けると(大学入試でよく見るヤツです)、dp[i][j-i]で表される
結局、 dp[i][j] = dp[i-1][j] + dp[i][j-i] で更新できる
類題: https://yukicoder.me/submissions/424992
自力: 〇
先に必要数だけ振り分けるという思考をついでに事前計算でもやる問題だった
例題 2-3-8　重複組合せ
自力: ×
解説が不親切シリーズ2
ここが詳しい

emtubasa.hateblo.jp 自分でもちょっと真面目に考えた

類題: https://atcoder.jp/contests/abc021/tasks/abc021_d
自力: 〇
素直な重複組み合わせなのでDPせずnCrのライブラリで殴っちゃった(演習の意味)

2-4 データ構造

例題 2-4-1　Expedition (POJ No.2431)
自力: 〇
類題: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/9867313
自力: 〇

例題 2-4-2　二分探索木 (set, map の練習) 流石に無 + 蟻本に対応する例題がないためパス

例題 2-4-3　食物連鎖 (POJ No.1182)
自力: ×
類題: https://atcoder.jp/contests/arc036/submissions/9868509
自力: 〇 グラフ上で「ある状態で」(今回の場合、移動距離が偶数の状態で)場所Nに到達できるか？ -> 拡張ダイクストラ(頂点倍加)
今回は接続性さえわかればいいので、今までの移動距離が偶数であるノードと奇数であるノードを用意してUnionFindでOK

2-5 グラフ

例題 2-5-1　二部グラフ判定
自力: 〇
類題: https://atcoder.jp/contests/maximum-cup-2018/submissions/9898898
例題 2-5-2　Roadblocks (POJ No.3255)
自力: ×
https://atcoder.jp/contests/abc035/submissions/9926603
複数の街に滞在する意味がないことはすぐにわかる。
帰り道の最短経路がわからないが、単一終点最短経路をしたいときは辺の向きを逆転させたグラフに対して単一始点最短経路をすればよい(賢すぎか？)
例題 2-5-3　Conscription (POJ No.3723)
自力: 〇
類題: https://atcoder.jp/contests/abc065/submissions/9954687
所見の時は思いつかなかった記憶があるけど今回は見た瞬間x軸y軸における両隣に辺を張ればよいことがすぐに思いつけたので、成長

例題 2-5-4　Layout (POJ No.3169)
自力: ×
牛ゲーム、不等式がたくさんあって、それを満たしながら最適化する問題は最短経路問題に落ちるかもということだけ覚えておく
類題: https://atcoder.jp/contests/utpc2013/submissions/9966659
自力: △
よくわかってないところがあり

例題 2-6-1　線分上の格子点の個数
自力: △
(すぐ下にある解説を見てしまった)
類題: https://atcoder.jp/contests/abc070/submissions/9970561
オーバーフローがめんどうでPythonしてしまった

例題 2-6-2　双六
自力: 〇
拡張ユークリッドの互除法やるだけ
類題: https://codeforces.com/contest/1244/submission/71210362
自力: 〇
拡張ユークリッドの互除法でごり押しできる(オーバーフローするので多倍長整数が必要だけど)
試合数に制限があるので、なるべくたくさん勝ったほうが有利であることを考える。
y の範囲は w 未満である(w 回 引き分けるなら d 回勝ったとするほうが試合回数的に有利であるため)ことを考えれば全探索できる
例題 2-6-3　素数判定
自力: 〇
類題: https://atcoder.jp/contests/arc017/submissions/10126400
はい
例題 2-6-4　素数の個数
自力: 〇
類題: https://atcoder.jp/contests/tenka1-2012-qualc/submissions/10127486
自力: 〇
例題 2-6-5　区間内の素数の個数
自力: 〇
類題: https://atcoder.jp/contests/jag2017autumn/submissions/10320359
自力: ×

言われてみれば区間篩なのだけど初見では全然わからんかった、区間[l, r] についてすべての素因数を処理したかったら sqrt(r) までの素数を列挙しておいてエラトステネスの篩っぽく飛び飛びに処理をする(語彙力)とよい
sqrt(n) までの素因数を列挙しておけばlogで素因数分解ができるので、たくさん素因数分解をしなければならぬ ときには有効かも
例題 2-6-6　Carmichael Numbers (Uva No.10006)
自力: 〇
類題: https://atcoder.jp/contests/joisc2007/submissions/10322004
くりかえし二条城
類題はTL0.5sec で p = 104 なのに p2 が通るのでびっくりしてしまう(logがつくとダメ、というレベルでTLが厳しいので、すべての数についてn乗を計算しておく、とかvectorを使わない、とか涙ぐましい最適化が必要)

GCJの問題に挑戦

Minimum Scalar Product
自力: 〇
大きい奴には小さい奴をマッチングさせる貪欲なんだけど、どこかで全く同じ問題を見た気がする。
Crazy Rows
自力: ×
先に最右の1の位置(ダジャレ)を計算しておいて転倒数を計算したらいいじゃん、と思ったが嘘で死亡
制約がめちゃめちゃ小さいので1行目からシミュレートして確定させていってもよい
Bribe the Prisoners
自力: 〇
区間DP、これを自力できたのはかなりうれしいので記念に(？)コードを貼っておく

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <stack>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#include <numeric>
#define BIT(nr) (1UL << (nr))
#define int long long
#define ll long long
#define double long double
#define mod 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807    //ない環境用
#define LL_HALFMAX 9223372036854775807 / 2   //ない環境用
#define MIN -(9223372036854775807 / 2)
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define mp make_pair
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }


using namespace std;

int dp[10010][10010];
int A[101];



void solve() {
    int P, Q;
    cin >> P >> Q;

    rep(i, P + 5) {
        rep(j, P + 5) {
            dp[i][j] = LL_HALFMAX;
        }
    }

    vector<int> A(Q);
    rep(i, Q) {
        cin >> A[i];
    }
    sort(ALLOF(A));

    // [left, right) の解を返す
    function<int(int, int)> rec = [&](int left, int right) -> int {
        if (dp[left][right] != LL_HALFMAX) {
            return dp[left][right];
        }

        int cost = LL_HALFMAX;

        auto lit = lower_bound(ALLOF(A), left);
        // もしも区間に開放すべき囚人がいなかったら、0
        if (lit == A.end() || !(*lit < right)) {
            cost = 0;
        }

        while (lit < A.end() && *lit < right) {
            int n = *lit;
            chmin(cost, rec(left, n) + rec(n + 1, right) + (right - left - 1));
            lit++;
        }

        return dp[left][right] = cost;
    };

    cout << rec(1, P + 1) << "\n";

}

signed main() {
    int T;
    cin >> T;
    rep(i, T) {
        cout << "Case #" << i + 1 << ": ";
        solve();
    }

    return 0;

}

Millinaire
自力: ×
解説が不親切シリーズ
解説を読んでもなにもわからないのでツイッターでググったりしながら頑張って読解した 蟻本のソースにガンバってコメントをつけてみたのでツッコミを募集します

int M, X;
double P;
double dp[2][(1 << 15) + 1];

void solve(){
    cin >> M >> P >> X;
    int n = 1 << M;
    double *prv = dp[0], *nxt = dp[1];
    memset(prv, 0, sizeof(double) * (n + 1));

    // 尻からたどる想定、最後には $1000000 を持っているものとする
    prv[n] = 1.0;

    for (int r = 0; r < M; r++) {
        // 所持金がiから勝てる確率を求める、prv[i] := 今ラウンド後所持金iから勝てる確率、 nxt[i]:=今ラウンド前所持金がiから勝てる確率(尻から見て行ってるので実装上の prv nxt と時系列の前後が逆転することに注意)
        for (int i = 0; i <= n; i++) {
            // 所持金がnを超える必要はないので、最大掛け金はi(所持金全部)かn-i(nになるのに不足するぶんの掛け金)
            int jub = min(i, n - i);
            double t = 0.0;
            // jだけかける
            for (int j = 0; j <= jub; j++) {
                // 確率Pで勝ち、1-Pで負けるので、確率Pで勝った未来から、確率1-Pで負けた未来から遷移してくる(尻から見ていることに注意)
                t = max(t, P*prv[i + j] + (1 - P) * prv[i - j]);
            }
            nxt[i] = t;
        }
        swap(prv, nxt);
    }
    int i = (int)X*n / 1000000;
    printf("%.6f\n", prv[i]);
}

signed main() {
    int T;
    cin >> T;
    rep(i, T) {
        cout << "Case #" << i + 1 << ": ";
        solve();
    }

    return 0;

}

試行錯誤の記録
ググってもなにも出てこないし蟻本の解説から実装を理解できないので最後の望み†Twitter†をする