C++でハフマン符号にチャレンジ

　蟻本のコラムに載っていた「ハフマン符号」がおもしろそうだったのでチャレンジしてみました。
アルゴリズム自体はとてもシンプルですが、コーディングにハマってしまいました。
priority_queueのコンテナの中にポインタ変数を突っ込みたいとき、どうするの？ 「・・・・・」 そういや、やったことないな。。木を構築するときにnewするのはやめて、あらかじめ確保したメモリプール（vertexの配列）から値を取ってきて、left、rightには配列の添字を入れるという技で対応しようかと思いましたが、比較関数用のFunctor作ってあげればいいだけみたいです。

　比較関数を自分で定義しなくても、priority_queue<vertex *>でコンパイルエラーが出なかったのがハマってしまった原因でした。ポインタ変数なので、operator<が定義されてたってことか。。

アルゴリズム

wikipedia参照。

ソースコード

※今回はアルファベット小文字のみをエンコーディング対象としました。

#include <iostream>
#include <queue>
#include <map>
#include <cstdio>

using namespace std;

struct vertex {
    char c;
    vertex *left;
    vertex *right;
    int cost;

    vertex(char _c, vertex *_left, vertex *_right, int _cost) 
        : c(_c), left(_left), right(_right), cost(_cost) {}
};

struct vertexComp {
    bool operator()(const vertex *x, const vertex *y) const {
        return x->cost > y->cost;
    }
};

void getEncode(map<char, string> &encode, vertex *vp, string s) {
    if (vp == NULL)
        return;
    if (vp->c)
        encode[vp->c] = s;
    getEncode(encode, vp->left, s+'0');
    getEncode(encode, vp->right, s+'1');
}

void huffmanCoding(int cnt[]) {
    priority_queue<vertex*, vector<vertex *>, vertexComp> Q;
    for (int i = 0; i < 26; i++)
        Q.push(new vertex((char)('a'+i), NULL, NULL, cnt[i]));

    while (Q.size() > 1) {
        vertex *v1 = Q.top(); Q.pop();
        vertex *v2 = Q.top(); Q.pop();
        Q.push(new vertex(0, v1, v2, v1->cost + v2->cost));
    }
    
    map<char, string> encode;
    getEncode(encode, Q.top(), "");

    for (map<char, string>::iterator itr = encode.begin(); itr != encode.end(); itr++)
        printf("%c [%6d] -> %10s\n", itr->first, cnt[itr->first-'a'], itr->second.c_str());
}

int main() {
    int c, cnt[26] = {0};
    while ((c = getchar()) != EOF) {
        if ('a' <= c && c <= 'z')
            ++cnt[c-'a'];
    }

    huffmanCoding(cnt);
 
    return 0;
}

実行結果

適当なWEBページの文章を読み込んで、符号化してみました。頻度が高いものほど、コードが短くなっていることが確認できました。

a [  3255] ->       1101
b [   702] ->     010111
c [  2845] ->       1010
d [  1712] ->      11100
e [  4337] ->        001
f [   715] ->     110000
g [   855] ->     111110
h [  1760] ->      11101
i [  2962] ->       1011
j [   236] ->   11000101
k [   300] ->   11111111
l [  2022] ->       0100
m [  1563] ->      11001
n [  2700] ->       0111
o [  2664] ->       0110
p [  1869] ->      11110
q [    43] ->  110001000
r [  2734] ->       1000
s [  2801] ->       1001
t [  4153] ->        000
u [  1242] ->      01010
v [   666] ->     010110
w [   514] ->    1111110
x [   282] ->   11111110
y [   511] ->    1100011
z [    45] ->  110001001

連鎖行列積を動的計画法で解く

連鎖行列積の問題を解きました。
両端の距離が小さい部分問題から解がうまっていくタイプのDPの典型問題です。

問題

Optimal Array Multiplication Sequence

ソースコード

const long long INF = 1LL<<60;
int n;
int r[16], c[16];
int mid[16][16];
long long dp[16][16];

inline string toString(int x) {
    ostringstream os;
    os << "A" << x;
    return os.str();
}

string printResult(int left, int right) {
    if (right - left == 0)
        return toString(left+1);
    return "(" + printResult(left, mid[left][right]) + " x " + printResult(mid[left][right]+1, right) + ")";
}

void solve(int &t) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = INF;
    
    for (int i = 0; i < n; i++)
        dp[i][i] = 0;
    
    for (int k = 1; k < n; k++) {
        for (int i = 0; i + k < n; i++) {
            int j = i + k;
            for (int m = i; m < j; m++) {
                long long tmp = dp[i][m] + dp[m+1][j] + r[i] * c[j] * c[m];
                if (dp[i][j] > tmp) {
                    dp[i][j] = tmp;
                    mid[i][j] = m;
                }
            }
        }
    }
    
    cout << "Case " << ++t << ": " << printResult(0, n-1) << endl;
}

int main() {
    int t = 0;
    while (scanf("%d", &n) == 1) {
        if (n == 0)
            break;
        
        for (int i = 0; i < n; i++)
            scanf("%d %d", r+i, c+i);
        
        solve(t);
    }
    
    return 0;
}

Pythonでnext_permutation

PythonにもC++のnext_permutationと同等の標準ライブラリ関数がある。

import itertools

for x in itertools.permutations("abcd"):
    print x

とすると、

('a', 'b', 'c', 'd')
('a', 'b', 'd', 'c')
・・・・・
('d', 'c', 'a', 'b')
('d', 'c', 'b', 'a')

と表示される。

知ってると便利なSTL(10) set_intersection, set_union, set_difference

何をするものか？

２つの集合の和集合、積集合、差集合を計算し、別のコンテナに格納します。

使い方

演算対象となる２つの集合はソート済みでなければいけません。（ソートされていなければ、まずソートしてください。）
それぞれ以下のように使います。まずは、積集合を計算するset_intersectionの使用例。第５引数には結果の出力先となるコンテナのイテレータを指定します。back_inserter(v)とすると、vの最後尾に結果が挿入されます。

// set_intersection
int main() {
    int x[] = {2, 4, 6, 8, 10, 12, 14};
    int y[] = {3, 6, 9, 12, 15, 18};

    vector<int> v;
    set_intersection(x, x+7, y, y+6, back_inserter(v));
    
    for (int i = 0; i < (int)v.size(); i++)
        cout << v[i] << endl;     // 6 12

    return 0;
}

次に、和集合を計算するset_unionの使用例。

// set_union
int main() {
    int x[] = {2, 4, 6, 8, 10, 12, 14};
    int y[] = {3, 6, 9, 12, 15, 18};

    vector<int> v;
    set_union(x, x+7, y, y+6, back_inserter(v));
    
    for (int i = 0; i < (int)v.size(); i++)
        cout << v[i] << endl;    // 2 3 4 6 8 9 10 12 14 15 18

    return 0;
}

最後に、差集合を計算するset_difference。

// set_difference
int main() {
    int x[] = {2, 4, 6, 8, 10, 12, 14};
    int y[] = {3, 6, 9, 12, 15, 18};

    vector<int> v;
    set_difference(x, x+7, y, y+6, back_inserter(v));
    
    for (int i = 0; i < (int)v.size(); i++)
        cout << v[i] << endl;   // 2 4 8 10 14
 
    return 0;
}

Codeforces Round #141 The Road to Berland is Paved With Good Intentions

最近、蟻本で学習したばかりの2-SATの問題を解いてみました。

問題概要

ある国にはN個の町がある。また、M本の道路があり、それぞれの道路は２つの町を結んでいる。道路にはアスファルト舗装されている道路と、されていない道路がある。
国王が、「ある町xに繋がる道路をすべてアスファルト舗装せよ。」と命令をすると、労働者（海外からの移民で現地の言葉をうまく理解できない）たちは、アスファルト舗装されていない道をアスファルト舗装し、アスファルト舗装されている道からアスファルトを剥ぎ取る。 すべての道路をアスファルト舗装することはできるか？できるなら国王はどの町を工事対象として選べばよいかを出力せよ。

方針

以下では、町xを工事対象にすることをx、工事対象としないことを¬xと表す。
すべての道路をアスファルト舗装するためには、
(i)初期状態で道路(v, w)がアスファルト舗装済みだった場合は、

• v → w
• ¬v → ¬w
• w → v
• ¬w → ¬v

(ii)初期状態で道路(v, w)がアスファルト舗装されていなかった場合は、

• v → ¬w
• ¬v → w
• w → ¬v
• ¬w → v

が成り立たなければならない。
ということで、2-SATが使えます。

・・・・・

と普通に解いてしまいましたが、よく考えると2-SATなので、和積標準形の形じゃないとダメなのでは？何でうまくいったのだろう？と少し考えてみました。

・・・・・

そうか、a → b と ¬a∨bの真理値表は同じだから和積標準形に直せますね。

ソースコード

強連結成分分解の実装は、省略。

int n, m;

int main() {
    cin >> n >> m;

    V = 2*n;
    REP (i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;

        if (c == 1) {
            add_edge(a, b);
            add_edge(a+n, b+n);
            add_edge(b, a);
            add_edge(b+n, a+n);
        }
        else {
            add_edge(a, b+n);
            add_edge(a+n, b);
            add_edge(b, a+n);
            add_edge(b+n, a);
        }
    }

    scc();

    REP (i, n) {
        if (cmp[i] == cmp[i+n]) {
            puts("Impossible");
            return 0;
        }
    }

    vector<int> cities;
    REP (i, n) {
        if (cmp[i] < cmp[i+n])
            cities.push_back(i+1);
    }

    cout << cities.size() << endl;
    REP (i, cities.size())
        cout << cities[i] << " ";
    cout << endl;

    return 0;
}

Codeforces #149 XOR on Segment

問題概要

n個の正数a₁, a₂, ..., a_nからなる配列aに対して、以下の2種類のクエリーが複数回投げられるので高速に処理せよ。

1. (l, r)が与えられるので、[a_l, a_r]の和を求める。
2. (l, r, x)が与えられるので、a_i := a_i xor x, i = l, l+1, ..., rのようにaの値を更新する。

タイプ1.のクエリについてのみ結果を出力せよ。

方針

とりあえず、雰囲気的にセグメント木を使うのは分かる。あとビット毎に独立して処理すればいいのも分かった（TopCoderで似たような問題といたため）。更新系の処理をうまく書く方法がすぐには浮かばなかったけど、

• 小さなセグメントにupdateをかけて、それを含む大きなセグメントにreadが投げられたらどうするか？
• 大きなセグメントにupdateをかけて、それに含まれる小さなセグメントにreadが投げられたらどうなるか？

を考えて、うまく行くようにいろいろ書いていたら、出来てた。

セグメント木、得意ではないですが好きです。

ソースコード

#include <iostream>

using namespace std;

int n, m;
int segsum[30][1<<18];
int segflip[30][1<<18];

void update(int pos, int k, int l, int r, int a, int b) {
    if (r <= a || b <= l)
        return;
    if (a <= l && r <= b) {
        segflip[pos][k] ^= 1;
        segsum[pos][k] = r-l-segsum[pos][k];
    } 
    else {
        int c = (l+r) >> 1;
        update(pos, 2*k+1, l, c, a, b);
        update(pos, 2*k+2, c, r, a, b);
        segsum[pos][k] = segsum[pos][2*k+1] + segsum[pos][2*k+2];
        if (segflip[pos][k])
            segsum[pos][k] = r-l-segsum[pos][k];
    }
}

int read(int pos, int k, int l, int r, int a, int b) {
    if (r <= a || b <= l)
        return 0;
    if (a <= l && r <= b)
        return segsum[pos][k];
    int c = (l+r) >> 1;
    int ret = 0;
    ret += read(pos, 2*k+1, l, c, a, b);
    ret += read(pos, 2*k+2, c, r, a, b);
    if (segflip[pos][k])
        ret = min(r, b) - max(l, a) - ret;
    return ret;
}

void insert(int pos, int k, int l, int r, int x) {
    if (x < l || r <= x)
        return;
    if (r - l == 1)
        segsum[pos][k]++;
    else {
        int c = (l+r) >> 1;
        insert(pos, 2*k+1, l, c, x);
        insert(pos, 2*k+2, c, r, x);
        segsum[pos][k] = segsum[pos][2*k+1] + segsum[pos][2*k+2];
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        for (int j = 0; j < 30; j++) {
            if (a & 1 << j)
                insert(j, 0, 0, n, i);
        }
    }
    
    cin >> m;
    while (m--) {
        int type, l, r, x;
        cin >> type;
        if (type == 1) {
            cin >> l >> r;
            long long ret = 0;
            for (int k = 0; k < 30; k++)
                ret += (long long)read(k, 0, 0, n, l-1, r) << k;
            cout << ret << endl;
        }
        else {
            cin >> l >> r >> x;
            for (int k = 0; k < 30; k++)
                if (x & 1 << k)
                    update(k, 0, 0, n, l-1, r);
        }
    }

    return 0;
}

codeforces #148 World Eater Brothers

問題概要

n個の節点がn-1個の有向枝で結ばれている。枝の方向を考えなければこのグラフは連結である。節点集合から2つの節点を選び、その2点を始点とすればすべての節点へ到達できるようにしたい。2つの節点を最適に選んだときに、向きを変更しなければならない枝の数の最小値を求めよ。

方針

節点集合をVとして、Vを2つの集合に分ける。これをU, Wとする。 Uから最適な節点を選び、その節点からU内のすべての節点へ到達できるようにした場合にかかるコスト（変更すべき枝の向き）を計算する。Wも同様のことをする。
すべてのV -> {U, W}分割について上記を行い、（Uにかかるコスト + Wにかかるコスト）の最小値を求めればよい。
問題のグラフは辺の方向を考えなければ木なので、V -> {U, W}の分割の方法は枝の数だけある。
U, Wからそれぞれ最適な頂点を選ぶ処理は、O(|U|), O(|W|)なので、全体として、O(n²)で計算できる。

ソースコード

int n;
vector<pair<int, int> > G[3000];

int dfs(int v, int p) {
    int ret = 0;

    REP (i, G[v].size()) {
        int u = G[v][i].first;
        int dir = G[v][i].second;

        if (u == p)
            continue;

        ret += dfs(u, v) + (dir == -1);
    }
    return ret;
}

int chRoot(int v, int p, int acc) {
    int ret = acc;
    
    REP (i, G[v].size()) {
        int u = G[v][i].first;
        int dir = G[v][i].second;

        if (u == p)
            continue;
        
        ret = min(ret, chRoot(u, v, acc + dir));
    }

    return ret;
}

int solve() {
    if (n < 3)
        return 0;

    int ret = 1<<30;
    REP (v, n) REP(i, G[v].size()) {
        int u = G[v][i].first;
        int acc1 = dfs(v, u);
        int acc2 = dfs(u, v);
        
        ret = min(ret, chRoot(v, u, acc1) + chRoot(u, v, acc2));
    }
    return ret;
}

int main() {
    cin >> n;
    REP (i, n-1) {
        int a, b;
        cin >> a >> b;
        G[--a].push_back(make_pair(--b, 1));
        G[b].push_back(make_pair(a, -1));
    }

    cout << solve() << endl;

    return 0;
}