Category Archives: ProCon

C++0xのLambda式による量化関数

Posted on by
Reply

Lambda式の勉強をちょっとしたので、衝動的に量化関数を実装してみた。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
using namespace std;
#define vi vector<int>
#define vit vector<int>::iterator
#define all(a) begin(a),end(a)
 
template <class T, class LAMBDA>
bool forall(T b, T e, LAMBDA l) {
    int faf = 1;
    for (T it = b; it != e; it++) {
        if (!l(it)) {
            faf = 0;
            break;
        }
    }
    return faf;
}
template <class T, class LAMBDA>
bool thereexists(T b, T e, LAMBDA l)
{
    return !forall(b, e, [l](T it) {return !l(it);});
}
 
main()
{
    vi a = {3, 6, 9, 12};
 
    // for all it in a there exists j in [4, 5], *it can divided by j -> 0
    cout <<
        forall(all(a), [](vit it) {
            return thereexists(4, 5, [&](int j) {
                return !(*it % j);
            });
        })
    << endl;
 
    cout << forall(2, 3, [&](int it) {return it > 2;}) << endl; // 0
    cout << forall(3, 4, [&](int it) {return it > 2;}) << endl; // 1
    cout << forall(all(a), [&](decltype(begin(a)) it) {return !(*it % 2);}) << endl; // 0
    cout << forall(all(a), [&](decltype(begin(a)) it) {return !(*it % 3);}) << endl; // 1
    cout << thereexists(all(a), [&](decltype(begin(a)) it) {return !(*it % 5);}) << endl; // 0
    cout << thereexists(all(a), [&](decltype(begin(a)) it) {return !(*it % 12);}) << endl; // 1
}

どれくらい意味がわかりやすくなるかというと、こんな感じ。量化記号をそのまま実装できる点で、書きやすく意味が一目瞭然。
before

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int flag = 0;
for (auto itj = candidacy.begin(); itj != candidacy.end(); itj++) {
    if (iti == itj)
        continue;
    int faf = 1;
    for (int h = 0; h < COLOR_NUM; h++) {
        if (!((*iti)[h] >= (*itj)[h])) {
            faf = 0;
            break;
        }
    }
    if (!((*iti)[8] >= (*itj)[8]))
        faf = 0;
    if (!faf) {
        continue;
    } else if (faf) {
        flag = 1;
        break;
    }
}
if (flag)
    iti = candidacy.erase(iti, iti + 1);
else
    iti++;

after

1
2
3
4
if (there_exists(all(candidacy), [&](itr(candidacy) itj) { return iti != itj && (*iti)[8] >= (*itj)[8] && for_all(0, (int)COLOR_NUM, [&](int h){ return (*iti)[h] >= (*itj)[h]; });}))
    iti = candidacy.erase(iti, iti + 1);
else
    iti++;

Code Processor

Posted on by
Reply

http://gulfweed.starlancer.org/d/index.php?itemid=10

https://apps.topcoder.com/wiki/display/tc/How+to+install+The+Arena+plug-ins

CodeProcessorはver 2.0ではいけない。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;
static const double EPS = 1e-5;
#define EQ(a,b) (abs((a)-(b))<EPS)
 
#define pb push_back
#define rep(i,n) for(int i = 0; i < n; i++)
#define re return
#define all(x) (x).begin(), (x).end()
#define mp make_pair
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<string> vs;
 
template <class T, class L> bool for_all(T b, T e, L l) { int f = 1; for (T q = b; q != e; q++) { if (!l(q)) { f = 0; break; } } return f; }
template <class T, class L> bool there_exists(T b, T e, L l) { return !for_all(b, e, [l](T q) {return !l(q);}); }
class $CLASSNAME$ {
 
public:
    $RC$ $METHODNAME$($METHODPARMS$) {
        $RC$ result;
        return result;
    }
 
    $TESTCODE$
};
 
// BEGIN CUT HERE
int main() {
    $CLASSNAME$ ___test;
    ___test.run_test(-1);
}
// END CUT HERE

ビット演算まとめ

Posted on by
Reply

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation

n & (n-1)
long long n;
there exists m in N n = 2^mの判定。

__builtin_ctz(n)
unsigned int n;
count trailing zeros
__builtin_ctz(n) = k * 2^m, k and 2 are coprimeなるm
__builtin_ctz(n) = LSB(n)

__builtin_clz(n)
unsigned int n;
count leading zeros
sizeof(n) – __builtin_clz(n) = argmin x < 2^i

SRM 597

Posted on by
Reply

1184->1214(Blue)
SRM 597 (div2), ox-, +50/-0, 264.1pts, 174th

Div.1に戻りました。

Easy
for all elem = a {
amin = minelem(a), there exists m in N elem / amin = 2^m
}
を判定する。
どうでもいいけど、given nに対して、there exists m in N n=2^mの判定方法として、(n & n – 1)がある。

Med
result -1はソートして同一かチェック。
result m ⇔ B[m:end]がAの部分列
これだけで良いのだが、下の部分列として存在の実装をミスった。馬鹿です。部分問題に加えます。
ミスった原因。
-forやwhileがこんがらがる問題は、きちんと紙で構造を確かめなければならない。
-終端条件から考えると楽
-条件が網羅的であることを確認しなければならない
-終端条件が更新条件によって変わる場合がある。下の解法2参照。
-whileとbreak, continueの構造は極めてミスりやすいので、他の関数を作ったほうが良いと思われる。インクリメントの変数の取り扱いが面倒。

部分問題、string A, Bについて、AがBを部分列として持つかを判定せよ。
解法0:
B[i]がA[j:end]に存在するかを逐一チェック。
終端条件
i: last && A[j:end]にB[i]がある→true
i: last && A[j:end]にB[i]がない→false
i: not last && A[j:end]にB[i]がない→false
更新条件
i: not last && A[j:end]にB[i]がある→jをfind(A[j:end], B[i]) + 1に設定

解法1:
B[i]がA[j:end]に存在するかを逐一チェック。
終端条件
j: done →false
更新条件
j: not done && A[j] == B[i]→j++, break
j: not done && A[j] != B[i]→j++

解法2:
whileとforの混成は面倒なので、while(1)でi, jを自分で管理する。
終端条件
i: not done && j: done→false
i: done && j: not done→true
i: done && j: done→？？？
更新条件
i: not done && j: not done && A[j] == B[i]→i++, j++
i: not done && j: not done && A[j] != B[i]→j++
？？？は、更新条件1行目によって更新された時にのみ発生。これは？？？＝doneとして扱うべき。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
bool ans0(string A, string B)
{
    int j = 0;
    for (int i = 0; i < B.length(); i++, j++) {
        int tmpj = A.substr(j, A.length() - j).find(B[i]);
        if (tmpj == string::npos) {
            return false;
        } else if (i != B.length() - 1) {
            j += tmpj;
        } else {
            return true;
        }
    }
    return true;
}
 
 
bool ans1(string A, string B)
{
    int j = 0;
    for (int i = 0; i < B.length(); i++) {
        while (1) {
            if (A[j++] == B[i])
                break;
            if (j >= A.length())
                return false;
        }
    }
    return true;
}
 
bool ans2(string A, string B)
{
    int i = 0, j = 0;
    while (1) {
        if (i >= B.length())
            return true;
        else if (j >= A.length())
            return false;
        else if (A[j] != B[i])
            j++;
        else {
            i++, j++;
        }
    }
}

Hard
わけがわからないよ。
勉強します。

プログラミングコンテスト部分問題集

Posted on by
Reply

コーディングの問題
string A, Bについて、AがBを部分列として持つかを判定するコードを書け。A, Bの長さは100以下． (SRM 597 Div.2 Med)

DPの問題
bool配列Sについて、部分列S[a..b]に含まれる部分列の中で連続した1の最長の長さmaxlen(a, b)を考える。maxlenに関する漸化式を構成せよ。 (SRM 595 Div.1 Med)

DPの問題
bool配列Sについて、以下を満たす部分列S[a..b]の場合の数を求めよ。条件: 最後にi回以上Trueが連続する、もしくはm回以上連続したTrueが存在する。 (SRM 595 Div.1 Med)

SRM 595

Posted on by
Reply

Analysis

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

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

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

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

種類の数え方。

1
2
3
4
5
6
7
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の順番を逆にしても計算量に影響を出さずに、メモリオーダを調整可能であることを例示するコード。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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;
}

AOJ 0042: A Thief

Posted on by
Reply

A Thief
コード

ただのナップサック問題。だったので、紙を使わずに暗算で漸化式を立てて解きました。

dp[j][i] = i個目までの美術品をjの重さで盗んだ時の価値の最大値
初期状態は、dp[j][0] = 0 for all j
漸化式は、dp[j][i] = max(dp[j][i], dp[j-w][i]))で更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <stdio.h>
  
using namespace std;
  
#define WMAX 1000
#define NMAX 1000
int main(void)
{
    int W, n;
    int cyc = 0;
    while (cin >> W && W && cin >> n) {
        cyc++;
        int dp[WMAX+1][NMAX+1] = {};
        for (int i = 0; i < n; i++) {
            int v, w;
            scanf("%d,%d", &v, &w);
            for (int j = 0; j < W+1; j++)
                dp[j][i+1] = max(dp[j][i], (j-w >= 0 ? dp[j-w][i] + v : 0));
        }
        cout << "Case " << cyc << ":" << endl;
        for (int j = 0; j < W+1; j++) {
            if (dp[j][n] == dp[W][n]) {
                cout << dp[j][n] << endl << j << endl;
                break;
            }
        }
    }
}

AOJ 2301: Sleeping Time

Posted on by
Reply

Sleeping Time
コード

難易度Blue 350 (非公式難易度表)

「k回の睡眠でR=r, L=lとした時のPP」を返す関数retを考えて、深さ優先探索を行う発想は自然。
だが、これだけでは2^30で計算が間に合わない。

なので、l, rとP, Eの関係に枝刈り条件を加える。
ret内のl-rを呼び出し回数に関して指数関数的に収束させていくので、この条件はかなり強い枝刈りが可能である。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
using namespace std;
#define abs(a) ((a) > 0 ? (a) : -(a))
  
double P, E, T;
double ret(double k, double r, double l)
{
    double h = (r + l) / 2;
    if (k == 0)
        return (abs(h-T) < E ? 1.0 : 0.0);
    if (l < T - E)
        return 0.0;
    if (r > T + E)
        return 0.0;
    if (T - E < r && l < T + E)
        return 1.0;
    if ((r+l)/2 >= T)
        return P * ret(k-1, r, h) + (1.0 - P) * ret(k-1, h, l);
    else
        return P * ret(k-1, h, l) + (1.0 - P) * ret(k-1, r, h);
}
  
int main(void)
{
    double K, R, L;
    cin >> K >> R >> L >> P >> E >> T;
    P = 1 - P;
  
    printf("%.6f", ret(K, R, L));
    return 0;
}

AOJ 2015: Square Route

Posted on by
Reply

Square Route
コード

縦横で生成しうる辺の長さをそれぞれ全て求める。
それをソートしてしゃくとり法によって同じ長さの辺をかけて足し算していく。
でも、mapを使ってベクトルの内積をすればいいだけでは…と後で気づいた。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;vector&gt;
 
using namespace std;
#define NUMMAX 1500
#define CMAX (NUMMAX * (NUMMAX + 1) / 2)
 
void makecvec(vector&lt;int&gt;&amp; in, vector&lt;int&gt;&amp; out)
{
    for (int ni = 0; ni &lt; (int)in.size(); ni++) {
        for (int pi = 0; pi &lt; (int)in.size() - ni; pi++) {
            int sum = 0;
            for (int si = 0; si &lt; ni + 1; si++)
                sum += in[pi + si];
            out.push_back(sum);
        }
    }
}
 
int main(void)
{
    int n, m;
    while (cin &gt;&gt; n &gt;&gt; m) {
        if (!n &amp;&amp; !m) break;
        vector&lt;int&gt; h(n), w(m);
        for (int i = 0; i &lt; n; i++) cin &gt;&gt; h[i];
        for (int i = 0; i &lt; m; i++) cin &gt;&gt; w[i];
 
        vector&lt;int&gt; hs, ws;
        hs.reserve(CMAX), ws.reserve(CMAX);
        makecvec(h, hs), makecvec(w, ws);
        sort(hs.begin(), hs.end()), sort(ws.begin(), ws.end());
 
        int result = 0;
        int hi = 0, wi = 0;
        while (hi != (int)hs.size() &amp;&amp; wi != (int)ws.size()) {
            if (hs[hi] == ws[wi]) {
                int hn = 0, wn = 0;
                while (hi != (int)hs.size() &amp;&amp; hs[hi] == hs[hi-hn])
                    hi++, hn++;
                while (wi != (int)ws.size() &amp;&amp; ws[wi] == ws[wi-wn])
                    wi++, wn++;
                result += wn * hn;
            } else if (hs[hi] &lt; ws[wi])
                hi++;
            else
                wi++;
        }
        cout &lt;&lt; result &lt;&lt; endl;
    }
 
    return 0;
}

AOJ 0557: 1年生 (A First Grader)

Posted on by
Reply

1年生 (A First Grader)
コード

DP強化週間

num[j] = j項目の数字
a[i][j] = j個目までの数字を使ってAOJ君が計算可能な数式によって、iを作る時の場合の数

とすると、以下のような漸化式が立てられる。

a[j][i] = a[j + num[i]][i-1] (もしj + num[i] < 21なら) + a[j - num[i]][i-1] (もしj - num[i] >= 0)

i番目までで作れる0から20の数字を記憶する。何を展開して漸化式を立てるか、という問題は、もともと少ない自由度をわざわざ大きくする、という点で発想的だよなー。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void)
{
    int n;
    cin >> n;
    int num[101];
    for (int i = 0; i < n-1; i++)
        cin >> num[i];
    int dest;
    cin >> dest;
 
    long long a[21][101] = {};
    a[num[0]][0] = 1;
    for (int i = 1; i < n-1; i++)
        for (int j = 0; j < 21; j++)
            a[j][i] += ((j + num[i] < 21) ? a[j + num[i]][i-1] : 0) + ((j - num[i] >= 0) ? a[j - num[i]][i-1] : 0);
    cout << a[dest][n-1-1] << endl;
 
    return 0;
}