Tech Tips

2011年3月8日火曜日

標準入出力をファイルと連結

前にC++とJAVAでやりましたが、Pythonでも。

以下のようにすると、標準入出力をファイルとリンクさせることが出来ます。

Code Jam JapanというCode Jamの日本人限定の大会が来週あるみたいなので、

それの対策です。。

予選は、C++/JAVA/Pythonって3言語でやってみようかな。。


import sys

INPUT_FILE = "C:\Users\xxx\Desktop\in.txt"
OUTPUT_FILE = "C:\Users\xxx\Desktop\out.txt"

sys.stdin = open(INPUT_FILE, "r")
sys.stdout = open(OUTPUT_FILE, "w")

for x in sys.stdin:
   print x.rstrip()

2011年3月7日月曜日

ショートコーディング: Not演算

チルダみたいな記号「~」ってC/C++にあるけど、いつ使うのだろう。。

ショートコーダーは日常茶飯事に使う。

例えば、EOF。

EOFは多くのコンパイラでは-1である。そして整数の中で優一ビットをすべて反転した場合に0になるのが-1である。

while (scanf("%d", &n) != EOF)

を

while (~scanf("%d", &n))

と書いたりする。

最近、私がよく使うのは、bool値を配列に格納したい場合である。普通なら0で初期化して、0でなければ値が設定されているとすればいいが、boolの場合はFalseを設定すると0とみなされる。

なので、char型にboolをぶちこむ。そして、char配列は-1で初期化しておく。

すると、not値が0の場合は、値が未設定となるので、スマートなコーディングが可能となる。

boolをcharに入れるなんてメモリの無駄と思う人もいるかもしれないが、実は、C/C++ではboolはほとんどの環境では1byteである。。なので実は無駄じゃない。

で、boolをchar配列に入れて、not演算を使ってエレガントに値の設定を判別したコードがこちら。。

Nimという数取りゲームの一般形において先手に必勝手が存在するかどうかをゲーム木で判定しています。注目すべきは、solveの3行目です！


int n;
VI nums;
char memo[1<<15][22];

bool solve(int turn, int s) {
   if (!s) return true;
   if (~memo[s][turn])
       return memo[s][turn];

   turn %= (2*n);
   int ret = false;
   FOR (x, 1, nums[turn]+1)
       if (s-x >= 0)
           ret |= !solve(turn+1,s-x);

   return memo[s][turn] = ret;
}

int main() {
   while (scanf("%d", &n), n) {
       int s;
       scanf("%d", &s);
       nums.clear();
       memset(memo, 0xFF, sizeof(memo));
       int x;
       REP(i, 2*n) {
           scanf("%d", &x);
           nums.push_back(x);
       }
       printf("%d\n", (int)solve(0, s));
   }

   return 0;
}

2011年3月5日土曜日

Emacs 入門（３）

2011年3月4日金曜日

KMP -- String Search Algorithm --

Today I'm gonna write about KMP algorithm, which is an algorithm for string search designed by three researchers: Knuth, Morris and Pratt.

There are several string search algorithm out there. I know about BM method and KR method besides KMP.

But it seems like KMP method is the most common, and it is used more often than other algorithm.

The idea is quite simple.

This Wikipedhia page explains it quite well:

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

But it's not smart to implement the algorithm exactly same way as it's mentioned in the site above. You're so near but so far if you have a good grasp of the algorithm but cannot implement it well.

There's simpler implementation many algorithmers are using.

I was thrilled when I saw this implementation first. So simple and so smart!!

Here's my solution to a POJ problem with the implementation:


char text[1000000+1];
char word[10000+1];
int fail[10000+1];

void mkFail() {
    int n = strlen(word);
    int j = fail[0] = -1;

    for (int i = 1; i <= n; i++) {
        while (j >= 0 && word[j] != word[i-1])
            j = fail[j];
        fail[i] = ++j;
    }
}

int kmp() {
    int n = strlen(word);
    int l = strlen(text);
    int cnt = 0;

    for (int i = 0, m = 0; m < l; m++) {
        while (i >= 0 && word[i] != text[m])
            i = fail[i];
        if (++i >= n) {
            ++cnt;
            i = fail[i];
        }
    }
    return cnt;
}

int main() {
    int n;

    scanf("%d", &n);

    while (n--) {
        scanf("%s", word);
        scanf("%s", text);
        mkFail();
        printf("%d\n", kmp());
    }

    return 0;
}

2011年2月23日水曜日

フェルマーの小定理

LayCurseさんの日記を見て面白そうなのでチャレンジした問題。

http://www.codeforces.com/contest/57/problem/C

①重複組み合わせ（Homogeneous Combination）と

②包除原理（Inclusion-exclusion principle）

の練習にと解いてみたが、見事にhogeりました。。

LayCurseさんのソースと睨めっこすること約2日、どうやら素数pと自然数aに対して

a^p = a (mod p)

が成り立つのではないか？？と気付きました。

これは「フェルマーの小定理」と呼ばれているようです。

別の書き方をすれば、

a^(p-1) = 1 (mod p)や

a^(p-2) = 1/a (mod p)

です。

上の問題は、この定理を用いて重複組み合わせを計算します。

普通、組み合わせはパスカルの三角形を利用してDPで出せますが、この問題の場合は抽出対象の個数が大きいためメモリーオーバーとなり、NGです。

フェルマーの小定理を利用すると、法の世界の割り算ができます。

普通に

nCk = n! / (n-k)!k!

を計算しましょう。

pが大きいので、累乗の計算は繰り返し二乗法で行いましょう。

以下ソースです。


const int MOD = 1000000007;
long long int f[200001];
long long int rf[200001];

long long int pw(long long int x, long long int y) {
    long long ret = 1LL;

    REP(mask, 50) {
        if (y >> mask & 1)
            ret = ret * x % MOD;
        x = x * x % MOD;
    }
    return ret % MOD;
}

long long int homoComb(int x, int y) {
    int n = x + y - 1;
    int k = y;

    rf[0] = f[0] = 1;
    FOR (i, 1, n + 1) {
        f[i] = f[i-1] * i % MOD;
        rf[i] = pw(f[i], MOD-2);
    }

    long long int ret = f[n];
    ret = ret * rf[k] % MOD;
    ret = ret * rf[n-k] % MOD;

    return ret;
}

int main() {
    int n;

    cin >> n;
    memset(f, 0x00, sizeof(f));
    memset(rf, 0x00, sizeof(rf));

    long long int ret = homoComb(n, n) % MOD;
    ret = 2 * ret % MOD;
    ret -= n;
    if (ret < 0) ret += MOD;

    cout << ret << endl;

    return 0;
}

2011年2月19日土曜日

Google+Facebook=??

Facebookアプリを作成しよう！と思いついたが、どうやら自分でサーバーを立てないとダメみたい。

ホスティングサービスしてくれ。。と思いつつも、

よく考えると、、、

Google App Engineがあるじゃん！！

これに気付いた自分はかなりの天才では！？

と思いましたが、すでにやってる人結構いるみたいですね。。

実は、GAEは昔ちょっとやってました。

そのときはJavaでやってたのですが、FacebookのAPIが簡単に使えるPythonに乗り換えてチャレンジしました。

PythonのGAEは、簡単すぎます。。。

必要な設定ファイルは、一つだけ。

使用するコマンドは、

テスト用にローカルサーバーをあげて画面確認する
GAEにソースをアップロードする

の2つだけ。

これは、楽すぎるのでは。

あとは、FacebookでアプリケーションIDを取得し、自作のGAEサイトをコールバックするように設定するだけ。

今日作ったのはここまで（少っ。。笑）

http://apps.facebook.com/kenjih-test-eleven/

VMwareでUbuntu

最近VMwareをインストールして、Ubuntuを試している。

VMwareとはOSのエミュレータ。windows上でunixやMac OSを動かすことができます。

cygwinでもいいですが、いろいろなOSを試せるというのがVMwareの利点。

下から、VMware playerをインストールできます。

もちろん無料。

http://www.vmware.com/jp/products/player/

そして、VMware上で、OSをエミュレートするにはゲストOSと呼ばれる"動かしたいOS"をダウンロードしなければいけません。

今回は、ubuntuを入れてみました。

下のサイトに、VMware用のubuntuがありましたのでそれを落としました。

http://www.ubuntulinux.jp/products/JA-Localized/vmware

ダウンロードしたファイルを解凍すると、「Ubuntu.vmx」というファイルが出来ます。このファイルをVMwareにドラッグすると、Ubuntu OSが立ちあがります。

ちょー簡単。。

ちなみに外観はこんな感じになります。

いやー便利ですねー。

僕のようなunix初心者にはありがたい限りです。

登録: 投稿 (Atom)