TODO

概要 †

  • プロコンで考えるべきこと
  • 解いた問題数を増やすのは良い事なんだけど、解いた問題数を増やすためだけに、簡単な問題を解きまくるのってすげえ時間の無駄
  • はむこと分布
↑

下位ページ †

  • 初心者向けプロコン?
↑

目次 †

↑

参考 †

↑

勉強すべきこと †

  • しゃくとり法
  • 今日連結成分分解
  • 2-SAT
  • Nim
  • Grundy数
  • フロンティア法のライブラリ使ってみた
  • デク・優先度付キュー
  • 二部マッチング
  • Link-Cut Tree（木で最強）
  • Lazy Segment Treeの設計
↑

まとめと例題 †

方針説明例題
DPテーブルを書いてみて、混み合っている場合は無駄な計算がないか考える2-3 漸化式を工夫する, 個数制限なしナップザック問題
boolのDPは一般に非効率2-3 漸化式を工夫する, 個数制限付き部分和問題
DPの双対性「状態に対して評価値がどうなるか」⇔「固定された評価値（＝ここでの状態）に対して、最も良い状態（＝ここでの評価値）は何か」(2-3 漸化式を工夫する, 01ナップサック問題その2, 最長部分増加部分列問題）
「fの最大化」⇔「命題C(x)=『fがx以上である』が判定可能ならば、xの探索的最大化」3-2 平均最大化
n回の掛け算はO(log n)で計算可能3-1 べき乗を高速に計算する
漸化式は行列演算に変換可能3-5 行列累乗
modはどこでしても同じ3-5 行列累乗, SRM 502 Div2 Hard
集合を、整数型のビット演算を用いてDPの状態に組み込む3-5 ビットDP
DPは適切なデータ構造を用いると高速化3-5 データ構造を用いて高速化
問題を同値な数学に置き換える牛が云々とかいう状態で考えたくないSRM 502 Div2 Hard
DPのデータ型のパターンはいっぱいある6次元配列だろうが何だろうがビビらないSRM 551 Div2 Hard, 桁DP
一つ前にしか依存しないDPテーブルは2テーブルを使いまわすint prev=i%2,next=prev^1; memset(dp[next], 0, sizeof(dp[next])); dpdp[next][(x+i)%N][y-1] += dpdp[prev][x][y];.絶対，dp[next]を初期化すること！！最後のテーブルの添字は毎回きちんと考えなければならない．SRM 502 Div2 Hard
最小手数といえば幅優先探索SRM 509 Div2 Hard
A以上B以下のものf(n):=n以下の条件を満たす非負整数の総数とすればf(B)-f(A-1)桁DP
n進数の不定長データ列の生成はqueueを使う(A, B, C, AA, AB, ...など)サンプルコードSRM 682 Div2 Medium
マジックナンバーは消すバグの温床になる
負のDPconst int MAX = 1000; int ary[2*MAX + 1]; int *dp = ary + MAX; // [-MAX, MAX]にアクセスできる!
二段DPSRM 523 Div2 Hard
DPは問題の制約を気にせず解いて，後でまとめるときに制約を考える円卓テーブルで隣り合って同じ色はダメ→同じ色も許容するDPを組んで，後で違う色の場合の数だけ集めるSRM 551 Div2 Hard
単調増加DPは変化分だけを追うDPに変換するYukicoder 269
↑

講評 †

  • 簡潔に。
  • 勉強になりそうなもの
問題どんな問題か理解度
SRM 502 Div2 Hard簡単な動的計画法。メモリ節約法。o（解答）
SRM 551 Div2 Hard基本の動的計画法。o.欲しい情報は定義してしまえ(解答)
SRM 509 Div2 Hard簡単め動的計画法、幅探索。x. 分かってない。ダイクストラとDPと幅探索と幅探索でいけるっぽい
SRM 682 Div2 Mediumn進数データ列のqueueによる生成o. 通った
SRM 682 Div2 Hard動的計画法．O(n^4), n=300が愚直だが計算追いつかないので工夫．x. 計算量が追いつかないところまでは分かったが，どう単純化すればいいか
SRM 547 Div2 Hard動的計画法+素数+ちょっと工夫x(なんか実装ミスってるっぽい). bit操作、set, 解説読むのをやる
SRM 523 Div2 Hard動的計画法+bit集合+2段DPx, 状態設定ミスった。分からない。解説
  • やったけど簡単だったもの
問題どんな問題か理解度
SRM 502 Div2 Medium確率と文字列操作o（bits/stdc++.hとforallを導入）
↑

Topcoder †

  • div2 Hard は難易度的には div1 medium より簡単なイメージ
  • CodeProcessor
↑

問題の見方 †

  1. google翻訳に問題文を突っ込む
  2. 原始的順像
    1. 具体的な簡単な問題を自分の手で解こうと試みる。問題の概要を把握する。
    2. 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
    3. その他、貪欲でいけるかなど、発想重視で色々考える。
  3. 求められる情報量の確認
    • yes-noか、max-minか、numかなど。
  4. 特性関数の作りやすさ
    • この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
  5. 計算量
    • アルゴリズムに要求される計算量のキツさを確認する。
  6. 頑張って実装
  7. テスト
    • 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
↑

Challenge †

  • vectorのチャレンジの仕方 
    hoge,foo,test
  • とすると、vector[3]={hoge, foo, test};となる。
  • 変なスペースはつけてはならない。
  • 最後にカンマをつけてはならない。
↑

虎本まとめ †

  • 探索
    • n次元の全探索
    • グラフの幅優先、深さ優先の全探索
      • しかし、格子状の道の最小ステップ経路の場合の数などでは、h*wの格子について$2^{h+w}$の探索をすることになる→メモリを使ってメモ化することで余分な探索を省く
    • 幅・深さ優先のメモ化可能性
      • まず、指数関数計算量の探索方法を考えることが重要。その後、複数のルートから同じ計算を行なっていないか（グラフ上で合流する部分はないか）をチェックする。
      • 返り値がある形でないとメモ化できない
      • 「それ以降に得られる〜」をメモ化する
    • メモ化からの漸化式構築＝動的計画法
      • 「これまでに得られる〜」をメモ化する
      • 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
      • 「ありえない組み合わせ」というものが存在する
  • DPは指数計算量探索の合流である
    • 探索の「状態」と「合流法則」を抽出したものがDPとなる
    • まず指数計算量探索を図示してみる
    • 丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
    • すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
    • 状態と合流から自動的にDPが計算できる
  • 初期条件は初めが決まっていることも、深いところの拘束条件があることもある
    • DPでは深いところしか決まっていないとやりづらい
    • 場合の数も、初めに自明に決まる場合の数から始めるとDPが楽になる
↑

DP †

  • 難しさ
    • 分かったつもりで実際に問題をといても、アクセプトされない。
    • デバッグできないので、しかも何でアクセプトされないかわからない。
↑

何を考えるべきか †

  • 1セット
    • 状態を適当に定めてみる
    • 今の状態から次の状態がどう決まるかを考えてみる
    • 次の状態が今の状態から統合されるかを考える
    • 何の情報が足りないかを考え、情報を状態に追加する
↑

対応 †

グラフ分析メモ化探索DP
状態ノード引数DPテーブル添字
値ノードに付属する値返り値DPテーブル
遷移上から下への操作再帰関数（更新）漸化式（代入演算）
結合法則二つ以上のノードから一つへのリダクション再帰関数（結合）漸化式（左辺値）
初期条件初めのノード関数呼び出し境界条件
↑

例：A未満の非負整数を数える †

  • 桁DPが入門に非常によいと思う。
  • A: N桁の数字
  • dp[i][j]: 以下の状態の時の場合の数
    • i: 上からi桁目の自然数集合において (i=0, 1, ..., N, inclusive. つまりi=0では空集合を見ている)
    • j: A未満であることが確定している (j = 0, 1)
#include <iostream>
#include <string>
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;

const int mod = 1e9 + 7;
int dp[101010][2]; // pos, less

int main() {
    string A;
    cin >> A;
    int n = A.length();

    dp[0][0] = 1;
    rep (i, n) rep (j, 2) { // DPテーブルの結合則の数 「DPテーブルから決まっていく様子を想像する」というのはこれを思い浮かべること。
        int lim = j ? 9 : A[i] - '0';
        rep (d, lim + 1) { // DPテーブルの結合則の具体的な計算数。「DPテーブルから決まっていく様子を想像する」というのはこれを思い浮かべること。
            (dp[i + 1][j || d < lim] += dp[i][j]) %= mod;
        }
        // dp[i + 1][0] = dp[i][0]; d[i + 1][1] = (A[i] - '0') * dp[i][0] + 10 * dp[i][1];
        // でもいいはず。でも与えられたdによってDPテーブル添字が一意に決まるので、上のようにdで全探索している
    }

    int ans = 0;
    rep (j, 2) (ans += dp[n][j]) %= mod;
    cout << ans << endl;
    return 0;
}
↑

実装の構造 †

dp[初期状態] = 初期値;
for (状態) {
    for (遷移) {
        次の状態 = 遷移(状態);
        dp[次の状態] = dp[状態];
    }
}
  • 何となく再帰関数で考えると最後から埋めていきたくなるけど、その必要はない
// ↓のようにコメントを書いておくとよい
dp[i + 1][k][j] = (dp[i][k][j] //i番目は選ばない
                 + dp[i][k - 1][(j - i + N) % N]) % MOD //i番目を選ぶ
↑

初期値 †

  • 探索がベースの DP はどこから始めれば全列挙ができるか考えると自然に初期値が定まる
    • 初期値を定めることは探索ベースの時の関数呼び出しに相当する！初期値
    • 初期値はDPの定義外．（そうじゃないと，空集合に対する場合の数みたいなのって扱われるべき？i=0, つまりAが空集合の時の場合の数が自明になる？A未満であることが確定している(j = 1)、「空集合」の元である自然数の場合の数は？→0A未満であることが確定していない(j = 0)、「空集合」の元である自然数の場合の数は？→1？？？本当に？？？みたいな悩み方をすることになる）
  • ナップザックのような数え上げの問題では，初期値は0となる．
↑

入出力 †

  • cinは遅い。
    • 30万変数読み込みで、scanfだと50ms, cinだと150ms
  • 同期を切ると早くなる
    • 切ったらもうcinとscanfを混ぜて使ってはいけない
↑

計算量 †

  • 1秒とは？＝3千万くらいは行ける。1億は無理。
計算量安全無理
O(n)3000万1億=10^8
O(n log n)100万400万
O(n^2)500010000
O(n^3)300450
O(n^4)75100
O(2^n)2527
O(3^n)1517
  • 制約2秒程度だったら、逆にどんな計算量が求められている？
制約アルゴリズム
10^6O(n)以下、軽いO(n log n)
10^5O(n log n)以下
3000O(n^2)
500軽いO(n^3)
100O(n^3)
30O(2^n)の半分全列挙
20O(2^n)、O(n 2^n)
↑

グラフ理論 †

頂点n辺n-1かつ連結なら必ず木構造 木構造はどこから見ても木構造、おぼえましたし

このスライドめっちゃいい 本「離散凸解析の考え方」

http://www.slideshare.net/tmaehara/ss-17402143 なんか関数定義をして、それが凸かどうかを判断して、云々している。とてもよい。

頂点は難しい、枝は簡単 葉を指定した最小全域木→Kruskalの変形 分散最小全域木、比最小全域木などは、パラメータ化して何かを止めると凸にする k-th最小全域木 辺を共有しない最小全域木を求めよ

名前計算量アルゴリズム特徴
ベルマンフォード法O(VE)前提：負の閉路がない連結グラフ。全辺を見て、現状より辺を通じたほうが良ければ更新。更新するものがなくなるまで行う負のコストを許容。負の閉路がなければOK。また、すべての負の閉路の検出も可能（更新が規定回数で止まらなかったら）
ダイクストラ法O(ElogV)前提：負のコストがない連結グラフ。コスト最小の未確定頂点を選び、そこから行ける頂点を更新して未確定頂点とする。これを未確定頂点がなくなるまで続ける。priority queueを使って実装する場合は「確定」の概念が明示的には入らず、コストが同じなら一番初めに処理した頂点が強いことで弾く負のコストを許容しない。
経路復元O(E)かO(V)O(V)は以前の道を記憶する。O(E)は以前の道をあとから探すE: d[j]=d[k]+cost[k][j]なるkを探す。V: 更新時prev[j]を記録する。
プリム法O(ElogV)統合頂点群から未統合頂点への最小距離をメモする。未統合頂点のうち統合頂点群に最も近い頂点を探す。統合頂点群に追加する。頂点追加によって、最小距離が変わるので更新する。最も近い頂点を貪欲的に追加する方法
クラスカル法O(ElogV)辺をコストの小さい順に並べる。コストの低い順に見て、閉路ができないならば連結していく。閉路ができることは連結先と連結元がUnion-Findで同一かによって検知可能最もコストの小さい辺を貪欲的に選び続ける方法
↑

ライブラリ †

  • TODO
    • エラトステネスのかわりに区間篩を使って実装。
アルゴリズムとリンク概要計算量
二分探索単調関数の境界面をlog(N)で計算。Nは探索空間。
Union Find「xとyの集合をまとめる」「xとyの集合が同じか判定」分割はできないのが重要な制約構築O(n), union, findは両方O(A(n))
BFS on tree幅優先探索で頂点rを始点とする最短距離を求める。O(V)
Bellman Ford1点から全点への最小コスト。負の閉路がない連結グラフを入力。あった場合は検出できる。O(V E)
Johnson前処理 O(V E)． 中間処理 O(V E log V)． 後処理 O(V^2)．
Warshall Floyd全点から全点への最小コスト。O(V^3)、だが漸化式が単純なので速い。
Dijkstra1点から全点への最小コスト。コストは正でなければならない。O(E log V)
K ShortestO(k E log V)
Prim最小重み無向全域木＝重みつき無向グラフの全域木の中で、重みが最小のものを求める。根は指定する。O(E log V)
Kruskal最小重み無向全域森＝重みつき無向グラフの全域木の中で、重みが最小のものを全て求める。O(E log V + A(r))
Cuninghame-Green最小直径無向全域木＝重みつき無向グラフの全域木の中で，直径が最小のものを求める前処理O(V^3), 端点計算O(VE)
Chu-Liu/Edmond最小重み有向全域木＝重み付き有向グラフの全域木の中で、重みが最小のものを求める。根は指定する。O(VE)
Dreyfus-Wagner最小重みシュタイナー木＝頂点群Tを通る木の中で、重みが最小のものを求める。t=11が限界。時間O(n 3^t + n^2 2^t + n^3)．空間計算量 O(n 2^t)．
Ford Fulkerson有向最大流辺容量が1ならこれ。F(E MAXFLOW)
Edmonds-Karp有向最大流O(E^2 V)
Dinic有向最大流O(E V^2)
Goldberg-Tarjan有向最大流O(V^2 sqrt(E))
Nagamochi-Ibaraki無向グラフ最小カットO(VE + V log V)
Primal Dual最小費用流＝費用と容量が定義された有向単純グラフの2頂点と、そこに品物を流す量が与えられた際，流すために掛かる総費用を最小にするためにはどのように輸送するとよいのかを決定する問題O(V^2 U C) Uは費用の総和、Cは容量の総和
Gomory-Hu最大流O(V MAXFLOW)
木の高さの最大値木の直径が最小になるような根を計算O(E)
Double Sweep＝木の直径葉と葉の最大距離を計算O(E)
有向オイラー路存在判定すべての辺をちょうど一度通る閉路があるか判定O(E)
無向オイラー路存在判定すべての辺をちょうど一度通る閉路があるか判定O(E)
無向中国人郵便配達問題O(o m log n + o^2 2^o), o=18が限度
最短ハミルトン路すべての頂点をちょうど一度通る閉路を求める。判定もNP困難。O(V^2 2^V), V=18が限度。全探索はO(V!)なので少し落ちてる
Fenwick Tree配列に、ある要素にvを足す・ある範囲の和を求める、をlog nで計算。構築O(n)、位置和更新O(log n)、範囲和参照O(log n)
Segment Tree（和）配列に、ある範囲にvを足す・ある範囲の和を求める、をlog nで計算。Fenwickの上位互換構築O(n)、範囲和更新O(log n)、範囲和参照O(log n)。範囲和のためには遅延評価を実装する必要あり。
Segment Tree（最小値・最大値。Starry Sky木）範囲和更新O(log n)、範囲最大最小参照O(log n)。範囲和のためには遅延評価を実装する必要あり。
Segment Tree（加群）範囲一般和更新O(log n)、範囲一般和参照O(log n)。範囲和のためには遅延評価を実装する必要あり。
Interval Tree与えられた点 x を含む半開区間を全列挙, 与えられた半開区間 [a,b) と重なる半開区間を全列挙構築O(n log n)．クエリO(log n + k), kはヒット数
レンジ木
AVL木平衡二分木
Splay木平衡二分木
赤黒木平衡二分木
Treap木平衡二分木
Next ConminationnCrのループを回す前処理O(n log n), 点クエリO(log n + k), 区間クエリO(log n + k)、kはヒット数
Prime(エラトステネス・区間篩の構築)エラトステネスを用いて、素因数分解する構築O(n log n)、参照O(log n)、素因数分解・約数計算O(log n)
Prime(構築なし)2^64までのオンライン素数判定O(1)*200
RMQ配列を与えて構築する→範囲クエリを与えると最小値を返すようになる。構築後は変更不能構築O(n log n)、クエリO(log log n)
Linear Programming
Tarjan's OLCAグラフを構築すると、(u, v)の最小共通祖先をO(1)で計算できるようになる構築O(E A(V))、参照O(1)
Big Num多倍長演算
Rational分数
Mod割り算、combinationはmodが素数を前提。法での累乗O(log n)、等差数列和O(log n)、階乗O(n)、掛け算、足し算、割り算を安全に計算
Geometry幾何ライブラリ直線・線分・点間の距離、多角形と線分の包含判定、点群の凸包O(n log n)、凸多角形の直線切断O(n)
Interval Tree
imos法範囲和更新から累積和構築範囲和O(1), 累積和構築O(n)、構築後累積和参照O(1)
範囲和[i, j)の累積和累積和構築O(n), 範囲和参照O(1)
二次元範囲和二次元で[i, j)から[h, k)までの累積和累積和構築O(n), 範囲和参照O(1)
↑

バケット法 †

  • バケット法=平方分割＝sqrt(n)分木
    • 範囲を扱う時に、平方に分割して記憶することで前処理O(n)、各クエリO(sqrt(n))を実現
    • 応用力が高く、自分で考える部分が大きい。各バケットが2分探索木やBITを持ってたりする。
    • 応用範囲は、バケット法>セグメント木。
    • 速度はバケットO(sqrt(n))<セグメント木O(log n)
↑

BIT・セグメント木 †

  • 「データ型T, 二項結合演算op、単位元T0」が定義できると、構築O(n), 更新O(log n), 範囲参照O(log n)のデータ型が定義可能
    • Fenwickは、「点更新」「範囲参照」
    • Segment Treeは、「範囲更新」「範囲参照」（範囲更新はlazyによって実現）
  • 単位元を持つ二項結合演算とは？
opTT0
maxint0
minintinf
(+)int0
(*)int0
sort.(++)[int][]
^（累乗）int1
andbool1
orbool0
xorbool0
(++)string""
集合和[int][]
集合積[int]全体集合
gcdint0
lcdint1
  • Fenwick Tree=BIT=Binary Indexed Tree
    • 実装が簡単で高速。
  • セグメント木
    • 応用力が高く、自分で考える部分が大きい。
    • 平衡処理が必要ないので、計算量・実装量的に有利
    • 使う時
      1. クエリ
      2. （平面）走査系
      3. DP加速＝漸化式に区間minが入ってるなど
  • 具体的には？
    op使い道
    max, minRMQ、DP加速
    (+)DP加速、オイラーツアー
↑

木 †

  • オイラーツアー [#e2df2bd8]
    • bfsの経路を添え時に直したもの
    • 木を列で扱える！
      • しかも、各頂点番号が最初に登場するインデックスと最後に登場するインデックスの間が部分木に。
      • 上から下への辺の重みも、上から下への経路で無向グラフ辺を足したものとして表現できる。
    • セグメント木などのデータ構造を扱えるようになる！
      1. 部分木のコストを変える・部分木のコストのsum, min, maxを求める。（無向辺のコストを両方向正にして実現）
      2. 辺（上から下へに限定）のコストを変える・u から v へのパスのコストのsum, min, maxを求める（無向辺のコストを片方1片方-1にして実現）
↑

DAGからフロンティア †

  • フロンティア法の長い解説
  • DAG
    • Directed acyclic graphとは、閉路のない有向グラフ。
  • トポロジカルソート
  • BDD
  • ROBDD
    • Create Reduced Ordered Binary Decision Diagram (ROBDD)
    • 変数に全順序関係が定義されている＆限界まで簡約化されている
    • BDDというとROBDDを指すことも。
    • 構築は二つのルールを適用し続ければROBDDになる。冗長な接点を全て削除。等価な接点を全て共有。
    • BDD 同士の演算 (Family Algebra) and, or, xor, not, ... みたいな色々な BDD 同士の演算ができる，便利
  • 組合せ集合（集合族）を表現する ZDD（Zero-Suppressed BDD）
    • 「計算爆発お姉さん」の問題が、O(nB)(n: fのビット数、B: BDDの頂点数)
    • お姉さん本
    • 集合族を表現するZDD
    • BDDと違うのは、頂点削除のルール
      • BDDは「ここが0でも1でも結果が変わらない→頂点削除」
      • ZDDは「ここが1だったらどうやっても結果が0になる→頂点削除」
    • 疎な部分集合族を表現するのに適している
    • BDD同様、ZDD 同士の演算がそのままできる（Family Algebra）
  • フロンティア法
    • ZDDはめちゃめちゃメモリ食う（1頂点当たりO(V)）
    • 実は、フロンティアの連結と次数だけ覚えれば十分
  • その他
    • 文字列集合を表現する SeqBDD (Sequence BDD)
    • 置換の集合を表現する πDD (PiDD, Permutation DD)
↑

未整理 †
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS