プログラミングコンテスト のバックアップ(No.21)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• プログラミングコンテスト へ行く。
  • 1 (2016-02-15 (月) 23:29:53)
  • 2 (2016-02-16 (火) 01:11:05)
  • 3 (2016-02-24 (水) 04:42:58)
  • 4 (2016-02-24 (水) 08:16:33)
  • 5 (2016-02-24 (水) 19:11:16)
  • 6 (2016-02-24 (水) 20:41:26)
  • 7 (2016-02-25 (木) 02:16:40)
  • 8 (2016-02-26 (金) 11:05:52)
  • 9 (2016-02-26 (金) 11:34:50)
  • 10 (2016-02-27 (土) 01:52:38)
  • 11 (2016-02-27 (土) 05:15:33)
  • 12 (2016-03-01 (火) 23:55:32)
  • 13 (2016-03-17 (木) 10:03:08)
  • 14 (2016-03-22 (火) 07:36:11)
  • 15 (2016-04-01 (金) 08:41:05)
  • 16 (2016-04-09 (土) 05:55:00)
  • 17 (2016-04-24 (日) 16:47:40)
  • 18 (2016-04-24 (日) 17:56:55)
  • 19 (2016-04-25 (月) 07:28:29)
  • 20 (2016-04-25 (月) 09:26:40)
  • 21 (2016-05-02 (月) 18:03:59)
  • 22 (2016-05-02 (月) 19:32:09)
  • 23 (2016-05-04 (水) 03:26:34)
  • 24 (2016-05-04 (水) 06:14:04)

---

TODO

概要 †

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

記録 †

• Topcoderのはむこと分布
• Atcoder ABC D問題勉強会
• プロコン記録

下位ページ †

• 初心者向けプロコン?

目次 †

参考 †

• Div2 Hard 講評
• 診断人さんのDP
• 非公式難易度表
• Spaghetti
• tubo28
  • 現代的な書き方

勉強すべきこと †

• しゃくとり法
• 強連結成分分解
• 2-SAT
• Nim
• Grundy数
• Treap, RBST(k-th tree), 平衡二分木
• デク・優先度付キュー
• 二部マッチング
• Link-Cut Tree（木で最強）
• Lazy Segment Treeの設計

まとめと例題 †

講評 †

• 簡潔に。
• 勉強になりそうなもの

• やったけど簡単だったもの

• 解説ありDP Med
  • http://kmjp.hatenablog.jp/entry/2015/10/15/1000
  • http://www.amazing-create.com/topcoder/srm-div2/srm-555-div2-medium/2/
  • http://yumandroid.blogspot.jp/2015/08/srm-422-div2-medium-div1-easy.html

プロコンサイト †

Topcoder †

• div2 Hard は難易度的には div1 medium より簡単なイメージ
• CodeProcessor
• Challenge [#e9ce53e8]
  • vectorのチャレンジの仕方

    hoge,foo,test

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

Codeforces †

Atcoder †

問題の見方 †

流れ †

1. google翻訳に問題文を突っ込む
2. 実験
   1. 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
3. 求められる情報量の確認
   • yes-noか、max-minか、numかなど。少ない情報ならまとめられる。
4. 計算機特有の発想
   1. 特性関数の作りやすさ。この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
   2. 半分全列挙
5. 計算量
   • アルゴリズムに要求される計算量のキツさを確認する。
6. 頑張って実装
7. テスト
   • 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。

チェックリスト †

コーディング中の注意 †

入出力 †

• cinは遅い。
  • 30万変数読み込みで、scanfだと50ms, cinだと150ms

• 同期を切ると早くなる
  • 切ったらもうcinとscanfを混ぜて使ってはいけない

計算量 †

• 1秒とは？＝3千万くらいは行ける。1億は無理。

• 制約2秒程度だったら、逆にどんな計算量が求められている？

グラフ理論 †

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

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

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

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

ライブラリ †

• TODO
  • エラトステネスのかわりに区間篩を使って実装。

アルゴリズム各論 †

バケット法 †

• バケット法=平方分割＝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によって実現）

• 単位元を持つ二項結合演算とは？

• Fenwick Tree=BIT=Binary Indexed Tree
  • 実装が簡単で高速。

• セグメント木
  • 応用力が高く、自分で考える部分が大きい。
  • 平衡処理が必要ないので、計算量・実装量的に有利
  • 使う時
    1. クエリ
    2. （平面）走査系
    3. DP加速＝漸化式に区間minが入ってるなど

• 具体的には？

  op	使い道
  max, min	RMQ、DP加速
  (+)	DP加速、オイラーツアー

木 †

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

• 木のクエリ処理
• Link-Cut Treeは最強

DAGからフロンティア †

• フロンティア法の長い解説
  • C++プログラムも
  • 資料
• DAG
  • Directed acyclic graphとは、閉路のない有向グラフ。
• トポロジカルソート
  • DAGを列に変換すること。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B&lang=jp
• BDD
  • 何に使えるか？http://www.ai-gakkai.or.jp/my-bookmark_vol27-no5/
  • n変数0/1論理関数を効率良くグラフとして表現するデータ構造である。
• 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)

メモ化再帰 †

• 大きく分けて2種類のメモ化再帰がある。

• 返り値をメモするタイプの再帰（異常条件→メモ条件→遷移→メモ→return）

int f(int i, int j) {
	if (i < 0 || j < 0 || i >= n || j >= n) return 0; // 入力異常条件
	if (memo.count(P(i, j))) return memo[P(i, j)];	// もう答え知ってる

	int ret = 0;
	rep(d, 4) ret+=f(i+di[d], j+dj[d]);

	memo[P(i, j)] = ret;
	return ret;
}

• 一度来たところをメモするタイプの再帰（異常条件→メモ条件→メモ→自分→遷移→return）

int f(int i, int j) {
	if (i < 0 || j < 0 || i >= n || j >= n) return 0; // 入力異常条件
	if (field[i][j] != 'o') return 0;	// 探し物じゃない
	if (memo.count(P(i, j))) return 0;	// もう来てた
	memo[P(i, j)] = true;			// 次からは来ない

	int ret = 0;
	ret += point[i][j]; // 自分を取って
	rep(d, 4) ret+=f(i+di[d], j+dj[d]); // 近くのを取りに行く

	return ret;
}

DP †

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

DPの漸化式 †

• コツ
  • 「i未満の添字を使って」という表現をする
  • 「〜が確定している時」という表現をする

DPの種類 †

DPのデバッグ †

• コツ
  • 変更後の状態を
  • 別のループで
  • 自明でないものだけ出す！

DPはメモ化再帰のループ版 †

• メモ化からの漸化式構築＝動的計画法
  • 「これまでに得られる〜」をメモ化する
  • 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
  • 「ありえない組み合わせ」というものが存在する

• DPは指数計算量探索の合流である
  • 探索の「状態」と「合流法則」を抽出したものがDPとなる
  • まず指数計算量探索を図示してみる
  • 丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
  • すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
  • 状態と合流から自動的にDPが計算できる

• 初期条件は初めが決まっていることも、深いところの拘束条件があることもある
  • DPでは深いところしか決まっていないとやりづらい
  • 場合の数も、初めに自明に決まる場合の数から始めるとDPが楽になる

何を考えるべきか †

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

全探索との対応 †

例：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となる．

一方向に依存するDP †

• DPで漸化式が前にのみ依存している＝ループを逆に回せば、後にのみ影響するDPを実現可能
  • 一方向にのみ依存するDPは、用意する配列を1つだけに抑えることができる＝漸化式が後にのみ依存している場合、i+1->iとして同じ配列を使いまわしていい（なぜかというと、DPの材料が必ず新鮮だから）
• d[i+1][j] = d[i][j]+d[i][j+1];
  1. i: 0 1 2 3 4 5
  2. 0: 0 2 7 5 3 2
  3. 1: 2 9 12 17 20 22
  • ↑を0の配列のみを使って更新してみよ

累積和 †

• コツ
  • n要素配列の累積和なら、n+1個用意して0番目を単位元にする。
• 二次元でも累積和できる。
• imos法
  • 範囲和が実現可能
  • 多次元・多字数・特殊座標への拡張が容易

Priority Queue †

• クエリ突っ込みながらソートしたい！という時のため。
  • これだけだと、二分探索木(STLのmap)もできるが、これはもっと静的でクエリ解消はできない
• priority_queue
  • 何も指定しないと最大がtopになる。普通のソートとは直感が逆なので注意。

priority_queue<ll, vector<int>, greater<int>> q; // topが最小
priority_queue<ll> q; // topが最大

• デバッグ
  • 出力は、イテレータが使えないので、コピーして全部取り出さないといけない。auto q_tmp = q; while (!q_tmp.empty()) {cout << q_tmp.top() << " "; q_tmp.pop(); } cout << "#" << endl;

二分探索 †

• デバッグ
  • 特性関数だけまず確認したほうがいい

   while (1) {
       ll t; cin >> t;
       cout << check(t) << endl;
   }

Link Cut Tree †

• Spaceship。これはとんでもない量の解説がある。
  • http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-review.pdf
  • http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-sample2.cpp
  • http://joisc2013-day4.contest.atcoder.jp/submissions/605906
• 木のパスのクエリ

Segment Tree †

• コツ
  • 非遅延セグメントツリーは、結合二項演算と単位元だけあればできる。
• Do Use Segment Tree
  • （セグメントツリー＋重軽分解）
  • http://d.hatena.ne.jp/simezi_tan/20140624/1403554584
• 遅延評価
  • 範囲に対する更新を可能にする
  • 遅延平衡二分木
• 永続ってなに？
  • 遅延評価＋永続平衡二分木
  • 永続平衡二分木
  • 永続セグメントツリー
  • 永続セグメントツリー
• セグメントツリー中級に良さそう

しゃくとり法 †

• 「ある区間で特性関数を満たすならば、区間を右に伸ばしても必ず満たす」時、条件を満たす区間をO(n)で全列挙するアルゴリズム
• 例題

Union Find †

• 盤面問題をUnionFindで

FFT †

• 結構自然な問題

三角数乗 †

• 2^(n*n)は、三角数乗を順に求めるとO(n), 二分累乗だとO(n log n)？

ビームサーチ †

• n個残す貪欲法

よく使うデータ構造と関数と注意点早見表 †

命名規則 †

• 添字の逆引きはinvをつける。
  • 例えばvector<int> a;に対しては、unordered_map<int, int> ainv;
• int dx={0,0,1,-1}; dy={1,-1,0,0};は、使う添字の名前を借りてdi, djに。

イディオム †

• int a = -1;を異常値とすると、~a==1で正常値となる
• 2で割れるだけ割る: n/(n&-n)
• 一番下に立ってるbitだけを残して0にする: (n&-n)
• 最後に続いている0の数。NLZ(x) = count_bits*1-1)
• 最初に続いている0の数。NTZ(x) = 32 - NLZ*2