Analysis

http://topcoder.g.hatena.ne.jp/evima/20131025

Div.2に落ちました。大いに反省します。

Easy LittleElephantAndIntervalsDiv1
Div.1 Easyにしてはかなり簡単だったはず。塗りつぶす時に何故か逆の順番で塗って死亡。
答え: 2^最終結果に残っている操作の種類数
以下、コーディングの勉強。
2^numの仕方。

1LL << num // (long long)2^num;

種類の数え方。

set<int> s;
set.insert(1):
set.insert(1):
set.insert(2):
set.insert(2):

cout << set.size() << endl;

Medium
手も足も出なかった感じ。まぁDiv.1 Medはいつもこんな感じ。
問題自体について
「S[a..b] + S[ c..d] にGがm回連続で現れる」とは、次のうちどれか1つ以上が成り立つこと
条件A: S[a..b]にGがm回連続で現れる
条件B: S[ c..d]にGがm回連続で現れる
条件C: S[a..b]の終わりの部分と、S[ c..d]の始めの部分をつなげるとGがm回連続で現れる」
「#(AorBorC) = #(A)+#(B)+#(C)-#(AandB)-#(BandC)-#(CandA)+#(AandBandC)」
ということを整理した上で、a, bを固定して、c, dの場合の数をO(1)で求める方法を考える。

戦略的な問題
・問題は部分分解すべき。条件AorBを満たす場合の数、などはべん図が利用可能。
・AorBに応じてCをする、みたいな計算は、本当は4つ実装しなければならないが、効果が一致するならば場合分けをまとめてよい。しかし、思考過程では場合分けしていなければならない。
・欲しいもの駆動でトップダウンに考えるべき。
・欲しいものがあったら全て置いてしまう。そこで初めて漸化式が書けるようになる。
・漸化式を書くために描く模式図は、既知前提部分をボックスにするとよい。ボックスの性質がかける程度に大きめに。

アルゴリズムの問題
いわゆる「前処理を頑張る」という奴。
O(N^2)の処理の中でO(N^2)の処理をするとO(N^4)になるが
二回目のO(N^2)をO(1)で参照可能なテーブルを作るための、O(N^2)が存在すれば、全体もO(N^2)となる。

漸化式で扱われているものは、そのループは漸化的な方向に回す。

逐次的なDPについて。
DPは必ずしも全部メモリに取っておかなければならない訳ではなく、むしろ計算に最小限のバッファとしてメモリを利用することが望まれる。
一方で、本当はO(1)でいいDPを後の計算の事情でO(M)にしたりすることができる。
漸化的な変数と漸化的でない変数が含まれるとき、これのループの順番をうまくコーディングすれば、
・外で回している方のメモリサイズNに対してM(N)を利用できる。
・外側のループのスコープで、DPの計算結果をO(1)で利用できる。その後の計算に何が必要なのかとの兼ね合い。

これは、以下のような考え方から導かれる。
図で考える。-|が回ったループ、cが計算された値、*が未計算の値だとする。
漸化的変数を先に持ってくると、
c****
c****
c****
↓
cc***
cc***
cc***
↓
ccccc
ccccc
ccccc

逆に、漸化的でない変数を後に持ってくると、
c****
c****
c****
↓
ccccc
c****
c****
↓
ccccc
ccccc
ccccc

以下はforの順番を逆にしても計算量に影響を出さずに、メモリオーダを調整可能であることを例示するコード。

#include <iostream>
#include <vector>

#define NUM 5
using namespace std;

void print_vec(vector<int>& v)
{
    for (int i = 0; i < v.size(); i++) 
            cout << v[i] << " ";
    cout << endl;
}

int f(int a)
{
    return a * 2 + 1;
}

void dp_ji(void) 
{
    cout << "#ji" << endl;
    vector<int> tj = {1, 2, 3, 4};
    print_vec(tj);
    for (int j = 0; j < NUM-1; j++) {
        for (int i = 0; i < tj.size(); i++) 
            tj[i] = f(tj[i]);
        print_vec(tj);
    }
}

void dp_ij(void) 
{
    cout << "#ij" << endl;
    vector<int> tj = {1, 2, 3, 4};
    vector<int> ti(NUM);
    for (int i = 0; i < tj.size(); i++) {
        ti[0] = tj[i];
        for (int j = 0; j < NUM; j++) 
            ti[j+1] = f(ti[j]);
        print_vec(ti);
    }
}

int main(void)
{
    dp_ji();
    dp_ij();
    return 0;
}