Facebook Hacker Cup 2011 Bonus Assignments

昔まったく分からなかった問題を解いてみた。

問題を要約すると、

『整数をN個選べ。ただし選ばれた整数は以下のすべての条件を満たす。

1. N個の整数の最小値は、[A, B]の間。

2. N個の整数の最大値は、[C, D]の間。

3. N個の整数をすべて割ることができる2以上の整数は存在しない。

N個の数の選び方のパターン数を求めよ。』

包除原理を使うと解けるが、よく見てみると

• square-freeではない（＝perfect squareで割れる）
• prime factorsの個数が偶数個
• prime factorsの個数が奇数個

でパターンが足されたり、引かれたり、結果に反映させなかったり、が決まるのでメビウス関数を使えばいいことが分かる。エラトステネスの篩を応用することで、n log (n) で[1, n]までのメビウス関数を計算することができる。（もっと速い方法があるかも）

以上をふまえて書いてみたソース。

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

const long long MOD = 1000000000+7;
int mu[1000000+1];
int pr[1000000+1];

void init() {
    REP (i, 1000000+1)
        mu[i] = pr[i] = 1;
    pr[0] = pr[1] = 0;

    for (int i = 0; i <= 1000000; i++) {
        if (!pr[i])
            continue;

        for (int j = i; j <= 1000000; j += i) {
            mu[j] *= -1;
            pr[j] = 0;
        }

        long long sq = (long long) i * i;
        for (long long j = sq; j <= 1000000; j += sq)
            mu[j] = 0;
    }
}

long long mpow(long long x, long long p) {
    long long ret = 1;

    while (p) {
        if (p & 1)
            ret = ret * x % MOD;
        x = x * x % MOD;
        p >>= 1;
    }
    return ret;
}

long long cnt(int n, int l, int r) {
    long long ret = 0;

    for (int i = 1; i <= r; i++) {
        int ll = (l+i-1) / i;
        int rr = r / i;

        if (rr >= ll) {
            ret += mu[i] * mpow(rr-ll+1, n);
            ret %= MOD;
        }
    }

    return ret;
}

long long solve() {
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    
    long long ret = cnt(N, A, D) - cnt(N, A, C-1) - cnt(N, B+1, D) + cnt(N, B+1, C-1);
    ret %= MOD;
    if (ret < 0)
        ret += MOD;
    return ret;
}

int main() {
    init();

    int T;
    cin >> T;

    REP (i, T) {
        cout << "Case #" << (i+1) << ": ";
        cout << solve() << endl;
    }

    return 0;
}

知ってると便利なSTL（11） partial_sum

その名のとおりpartial sumを計算してくれる関数です。
以下の処理と同様のことをしてくれます。

template <class InputIterator, class OutputIterator>
   OutputIterator partial_sum ( InputIterator first, InputIterator last,
                                OutputIterator result )
{
  iterator_traits<InputIterator>::value_type val;
  *result++ = val = *first++;
  while (first!=last)
    *result++ = val = val + *first++;
  return result;
}

これは便利。

#include <iostream>
#include <numeric>

using namespace std;

int main() {
    int x[] = {0,1,2,3,4,5,6,7,8,9,10};
    int y[11];
    
    partial_sum(x, x+11, y);

    for (int i = 0; i < 11; i++)
        cout << y[i] << " ";
    cout << endl;

    return 0;
}

のように書くと、

0 1 3 6 10 15 21 28 36 45 55

のように出力されます。

月間PV10,000達成

　月間PVが初めて10,000を越えました。ブログを読んでくれた皆さん、ありがとうございました。

何の実用性もないおれおれ系ブログですが、これからも自分の好きなことを書きつづけていきたいと思います。

Google Code Jam 2013 Round1C The Great Wall

　本番はwordyなproblem statementに翻弄されてパニクった結果、smallしか解けませんでしたが、落ち着いて考えるとただの一次元の座標圧縮 + セグメント木でした。

　sampleにあるように端点はdiscreteだけど区間内に含まれる値はcontinuousというのがいやらしい感じですが、[a, b]を攻める => [a, b)を攻めると読み替えてもOKと気づくと素直に実装できます。本番中はこれに気づかず、0.5刻みの区間を整数の区間にマッピングして解くという無駄なことをしていました。

　あと、要素数が10^6くらいになるので、set/map（unordered_set/unordered_mapなら大丈夫だと思います。）ではなくvectorを使って処理しています。

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

struct attack {
    int d;   // day
    int w;   // westmost
    int e;   // eastmost
    int s;   // strength

    attack(int d, int w, int e, int s) : d(d), w(w), e(e), s(s) {}
    
    bool operator<(const attack &x) const {
        return d < x.d;
    }
};

int seg[1<<22];

void init() {
    memset(seg, 0, sizeof(seg));
}

void update(int k, int l, int r, int a, int b, int x) {
    if (b <= l || r <= a)
        return;
    if (a <= l && r <= b)
        seg[k] = max(seg[k], x);
    else {
        int mid = (l + r) / 2;
        update(2*k+1, l, mid, a, b, x);
        update(2*k+2, mid, r, a, b, x);
        seg[k] = max(seg[k], min(seg[2*k+1], seg[2*k+2]));
    }
}

const int oo = 1<<30;
int query(int k, int l, int r, int a, int b) {
    if (b <= l || r <= a)
        return oo;
    if (a <= l && r <= b)
        return seg[k];
    else {
        int mid = (l + r) / 2;
        int x1 = query(2*k+1, l, mid, a, b);
        int x2 = query(2*k+2, mid, r, a, b);

        return max(seg[k], min(x1, x2));
    }
}

void solve() {
    int N;
    cin >> N;

    vector<int> pos;
    vector<attack> attacks;

    // read input data
    REP (i, N) {
        int di, ni, wi, ei, si, delta_di, delta_pi, delta_si;
        cin >> di >> ni >> wi >> ei >> si >> delta_di >> delta_pi >> delta_si;

        REP (j, ni) {
            attacks.push_back(attack(di, wi, ei, si));
            pos.push_back(wi);
            pos.push_back(ei);
            di += delta_di; wi += delta_pi; ei += delta_pi; si += delta_si;
        }
    }

    // axis compression
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    int L = pos.size();
    int M = attacks.size();
    REP (i, M) {
        attacks[i].w = lower_bound(pos.begin(), pos.end(), attacks[i].w) - pos.begin();
        attacks[i].e = lower_bound(pos.begin(), pos.end(), attacks[i].e) - pos.begin();
    }
    
    // simulate attacks
    sort(attacks.begin(), attacks.end());
    init();
    int cnt = 0;
    REP (i, M) {
        int j;

        // attack
        for(j = i; j < M && attacks[j].d == attacks[i].d; j++)
            if (query(0, 0, L, attacks[j].w, attacks[j].e) < attacks[j].s)
                ++cnt;

        // build the Wall
        for(j = i; j < M && attacks[j].d == attacks[i].d; j++)
            update(0, 0, L, attacks[j].w, attacks[j].e, attacks[j].s);

        i = --j;
    }

    cout << cnt << endl;
}

int main() {
    int T;
    cin >> T;

    REP (i, T) {
        printf("Case #%d: ", i+1);
        solve();
    }
    return 0;
}

読書「人間失格」

　太宰治の人間失格を読みました。

作中で、主人公が友人と言葉遊びをします。
その中で、「罪」のantonymは何か？という問いがされます。
その答えによって、その人のすべてが分かると主人公は言いますが、結局その場面では答えにたどり着くことは出来ません。

「罪」のantonymは、「死」ではないかと思います。
「生きていくことは罪なのか？」と主人公が自問する場面があります。「生きること」 = 「罪」であれば、罪のantonymは「死」です。
そして作者は自身の人生で罪とは正反対の決断をしました。この作品が太宰治の遺書だとすると、それが答えなのではないでしょうか。

知ってると便利なC++のstringテクニック

charからstringへの変換

みなさんどうやってますか？

僕はよく以下のように書きます。（ここでは、char型のcをstring型のsに変換したいとします。）

#include <iostream>

using namespace std;

int main() {

    char c = 'a';
    string s;
    s += c;

    return 0;
}

以下のように書く人をよく見かけますが、これは無駄にソース量が多いのではと思います。

#include <iostream>
#include <sstream>

using namespace std;

int main() {

    char c = 'a';
    string s;
    stringstream ss;

    ss << c;
    ss  >> s;

    return 0;
}

ちょっと考えてみましたが、下のように書くのが一番いいのでは。

#include <iostream>

using namespace std;

int main() {

    char c = 'a';
    string s(1, c);

    return 0;
}

母音判定

普通に書くとこうなります。

#include <iostream>

using namespace std;

int main() {

    char c = 'a';

    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
        cout << "vowel" << endl;
    else
        cout << "consonant" << endl;

    return 0;
}

ifの中が多くて面倒くさいです。以下のように書くとスマートになります。

#include <iostream>

using namespace std;

int main() {

    char c = 'a';

    if (~string("aeiou").find(c))
        cout << "vowel" << endl;
    else
        cout << "consonant" << endl;

    return 0;
}

少し長くなってしまいますが、以下のような書き方もあります。

#include <iostream>

using namespace std;

int main() {

    char c = 'a';

    if (~string(1, c).find_first_of("aeiou"))
        cout << "vowel" << endl;
    else
        cout << "consonant" << endl;

    return 0;
}

George Orwellでも読んでみようかしら。。

George Orwellの「Animal Farm」と「1984」を買った。

「Animal Farm」はlang-8で進められたから。「1984」は「1Q84」つながりで。

しかしKindleの書籍は安いなー。

「Animal Farm」は紙だと943円なのが100円。

「1984」は紙だと1046円なのが100円。

Code Jam 2013 Round 1B Garbled Email

 前回復習したときに単純なDP解で解けたけど、上位陣の解答がおもしろそうだったのでrngさんのソースを見てみた。

あらかじめ辞書の単語でトライ木を作っておいて、（トライ木のどの節点にいるのか、間違った文字からの距離） -> 異なる文字の数をマップにいれて、それを毎回更新していくという処理をしている。

とりあえず一回写経して理解した後で、同じ解法を何も見ずに自分のスタイルで書いてみるという練習をしてみた。

最近きれいなソースを写経したり、どういうことを考えて実装されたソースなのかを考えたりするのが楽しくなってきた。これは良い練習方法かもしれない。

#include <algorithm>
#include <iostream>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

struct node {
    int next[26];
};

int ptr;

node trie[3000000];
bool goal[3000000];

void update(const string &s) {
    int cur = 0;
    REP (i, s.length()) {
        int c = s[i] - 'a';
        if (trie[cur].next[c] == -1)
            trie[cur].next[c] = ptr++;
        cur = trie[cur].next[c];
    }

    goal[cur] = true;
}

#include <fstream>
void init() {
    ptr = 1;
    memset(trie, -1, sizeof(trie));
    memset(goal, 0, sizeof(goal));

    fstream file("garbled_email_dictionary.txt");
    string s;
    int cnt = 0;
    while (file >> s) {
        update(s);
        ++cnt;
    }
    
    cerr << "dictionary size: " << cnt << endl;
}

void solve() {
    string s;
    cin >> s;
    int N = s.length();

    map<pair<int, int>, int> dp[4010];
    dp[0][make_pair(0, 4)] = 0;

    REP (i, N) {
        EACH (j, dp[i]) {
            REP (k, 26) {
                int st = j->first.first;
                int dist = j->first.second;
                int val = j->second;
                
                st = trie[st].next[k];
                if (st == -1)
                    continue;

                if (s[i] - 'a' == k) {
                    dist = min(dist+1, 4);
                } else {
                    if (dist < 4)
                        continue;
                    dist = 0;
                    ++val;
                }

                pair<int, int> p(st, dist);
                if (dp[i+1].find(p) == dp[i+1].end() || dp[i+1][p] > val)
                    dp[i+1][p] = val;
                if (goal[st]) {
                    p.first = 0;
                    if (dp[i+1].find(p) == dp[i+1].end() || dp[i+1][p] > val)
                        dp[i+1][p] = val;
                }
            }
        }
        dp[i].clear();
    }

    int ret = 1<<30;
    REP (i, 5) {
        pair<int, int> p(0, i);
        if (dp[N].find(p) != dp[N].end())
            ret = min(ret, dp[N][p]);
    }
    cout << ret << endl;
}

int main() {
    init();
    int T;
    cin >> T;
    REP (i, T) {
        printf("Case #%d: ", i+1);
        solve();
    }

    return 0;
}