SRM BrushUp: FoxPlayingGame (501 div2 Middle)

SRM501。狐さんの回。

こんこん♪

平日なので参加できなかったので、今日解いてみた。。

が、ダメでした。

250は、sequenceが与えられるので、これにある整数nを加ると、arithmetic progression または　geometric progressionになるときのnの個数を求めよ。

という感じ。（やばい、日本語へたい。。笑）

500はかなりトリッキー。DPで解いたけど、マイナスの場合ダメじゃんと気付いて、じゃあ

• 整数の大きさ
• 整数の絶対値

2つでDPじゃん。って思ったけどこれもダメ。。

こういうときは、例題をよく読むといい。

なるほど。。先に足すか、先に掛けるかをやればよさそう。書く。サブミット。テスト。落ちる・・

で、(paramA, paramB)が

• {正 or 負}^2 の4分岐
• paramBが{1000以上、未満}の2分岐

の8分岐くらいのソースを書く。通った。。でもこんなややこしいのか。。。

後でシンプルに書けることに気付く。

class FoxPlayingGame {
public:
    double theMax(int nA, int nB, int paramA, int paramB) {
        double a = paramA / 1000.0;
        double b = paramB / 1000.0;

        if (!nA) return 0;
        if (!nB) return nA*a;

        double ret = nA*a;
        ret = max(ret, nA*a*pow(b, nB));
        ret = max(ret, nA*a*pow(b, nB-1));
        ret = max(ret, nA*a*b);

        return ret;
    }
};

この問題は、新しい思考パターンを教えてくれます。

分岐がいくつあるのかを考えるのではなくて、最終的に最大値を取りそうな値はどんなパターンがあるか最終段のみ考えればよいです。

入力があって、マッピング先だけに目を向けるという発想。。。

なるほど。良い準備をさせてもらいました。

もうちょっと分析すると、

paramA/1000.0は全部足した方がいい。（足せば足すほど、絶対値は大きくなる）

paramB/1000.0は以下の4つの選択肢がある

• 掛けない（掛けると小さくなる）
• 全部掛ける
• （全部-1）掛ける（符号の都合で）
• 1回だけかける（掛けると絶対値は小さくなるが、符号を逆転できる）

まあでも、This is what they call "hindsight is 20/20."

SRM BrushUp: probabilityToLose (500 div2 Middle)

正答率5%以下の難問だったらしい。

私も本番では解けなかった。。（ちょっと言い訳をすると、飲みに行った後のSRMだったので・・。笑）

今日、落ち着いて解いてみたら普通に解けました。

でも反省すべきところはあります。

本番は、問題の意味を追うのに必死になって問題文を何回も読んでいました。

これは明らかに時間の無駄。

問題文がよく分からないときは、サンプルを読んで、紙と鉛筆でシミュレーションすればどうすればいいのか分かります。

これは、大事なSRM攻略法の一つな気がしますね。。

この問題のポイントは、

• 決定権のある人が投票し終わった時点で、最大票を集めた人の投票数が1の場合は無限ループ
• 決定権のある人が投票し終わった時点で、最大票を集めた人が1人しかいない場合はその人が絶対選ばれる
• それ以外の場合は投票対象が縮小される。⇒縮小はモジューロ演算を使えばよい

です。下手に難しく考えすぎるとhogeってしまうので、div2の500なんでそんな難しくはないだろうっていう気持ちで臨むことも大事だと思いました。

ソースはこちら。最近よく見るrngさんのコーディングスタイルにちょっと影響された（笑

class MafiaGame {
public:
    double probabilityToLose(int N, vector<int> decisions) {
        int M = decisions.size();
        int point[N];

        fill(point, point+N, 0);
        REP(i, N) REP(j, M) if (decisions[j] == i) ++point[i];

        int mx = *max_element(point, point+N);
        if (mx == 1) return 0.0;

        int cnt = 0;
        REP(i, N) if (point[i] == mx) ++cnt;
        if (cnt == 1) return 1.0;

        double ret = 1./cnt;
        while (1) {
            int rm = N - mx * cnt;
            if (rm % N == 0) return 0.0;
            cnt = rm % cnt;
            if (cnt == 1) break;
        }
        return ret;
    }
};

Emacs 入門（４）

最近、Emacsのカスタムが面白い。

自分の好きなように設定して、自分オリジナルのエディター環境が作れるというのがいいところだと思う。

お勧めは、

compile-dwim

これを使うと、プログラムのコンパイル＆実行が簡単にできる。

しかも複数の言語に対応しているという優れもの。キーバインドを設定すれば、eclipseみたいに楽にbuild and runが出来る。

あとは、画面の色とか分割とかの初期設定をいじってみた。

ついに私のemacsも、エディタからIDEへの進化を遂げましたね。

jsdo.it

I tried an interesting Japanese site called "jsdo.it", where you can develop HTML, javascript and CSS online:

http://jsdo.it/

Is this a pun of "js(javascript)" and "just do it"???

Anyway, it's a mainstream to utilize a library called "jquery" these days when you code javascript.

• simplify cross-browser development
• simplify DOM manipulations

Above are the main selling points of jquery.

What's more, "server-side" javascript and "native" javascript have received much attentions lately.

You might be able to anything you like with javascript in the future!

After reading the article of gihyo, a Japanese online magazine for engineers, I've developed a stuff like this.

forked from: お題（連載第二回目） - jsdo.it - share JavaScript, HTML5 and CSS

When you hover a menu, sub menus come out.

I was surprised the fact that javascript is supporting a feature from functional programming languages like "filter" and "anonymous function."

SRM BrushUp: GeometricProgressions (500 div2 Hard)

昨日（おとといか。。）SRM 500があった。

記念すべき500回目ということで賞金付き。

しかし、div 2はいまいち納得できない結果となった。Hardの問題を解いてsystem testをpassしている人たちの回答が、なんか微妙。。。

ハッシュを使ってるんですけど、たまたまsystem test通っただけで、正規の解答とは異なるのでは？？という疑問がちらほら。。

私も、そう思います。確かに、実入力10^5程度に対して、{10^9}^2のサイズのhashを使えば衝突が起こることは非常にまれと言えますが。。。

納得いかん。。。

てことで、がんばって解いてみました。

私の解法は、素因数分解を使用しています。一応system testは通ったけど、あっているかは不明。。。

こんな感じっす。。

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

typedef map<int, int> MII;

set<MII>seq;

class GeometricProgressions {
public:
    int count(int b1, int q1, int n1, int b2, int q2, int n2) {
        if (!seq.empty())
            seq.clear();

        setFactorizedSeq(b1, q1, n1);

        return checkFactorizedSeq(b2, q2, n2) + seq.size();
    }

private:
    MII nextElemFactors(MII curr, MII mul) {
        EACH(itr, mul) {
            if (curr.count(itr->first)) {
                if (itr->first != 0 && itr->first != 1)
                    curr[itr->first] += itr->second;
            }
            else {
                if (itr->first == 0) {
                    curr.clear();
                    curr[0] = 1;
                }
                else if (itr->first != 1)
                    curr[itr->first] = itr->second;
            }
        }
        return curr;
    }

    int checkFactorizedSeq(int b, int q, int n) {
        int ret = 0;
        MII facb = factorize(b);
        MII facq = factorize(q);

        FOR (i, 0, n) {
            if (!seq.count(facb)) ++ret;
            if (!b) break;

            MII fact = nextElemFactors(facb, facq);
            if (fact == facb) break;
            facb = fact;
        }
        return ret;
    }

    void setFactorizedSeq(int b, int q, int n) {
        MII facb = factorize(b);
        MII facq = factorize(q);

        FOR (i, 0, n) {
            seq.insert(facb);
            if (!b) break;
            facb = nextElemFactors(facb, facq);
        }
    }

    MII factorize(int n) {
        MII factors;

        if (n == 0 || n == 1) {
            factors[n] = 1;
            return factors;
        }

        FOR (i, 2, sqrt(n)+1)
            while (n % i == 0) {
                if (factors.count(i)) factors[i]++;
                else factors[i] = 1;
                n /= i;
            }
        if (n != 1)
            factors[n] = 1;

        return factors;
    }

};

Started a new contest!

I've started a new contest, called "Code Golf," where you compete in the size of source code.

http://codegolf.com/

You are given a not-so-difficult program, and all you have to do is write a code as short as possible :)

They allow you to submit in a couple of programming languages: PHP, Python and Perl.

It doesn't help at all in everyday's coding lol

But people on the site are keen on just shortening their codes. Talk about a computer hacker lol

I will hack too, haha.

Here's a simple problem I solved today.

http://codegolf.com/competition/browse

This is my (first) code.

Nothing special, an ordinary code on which no shortening effort is done.

I'll make this shorter somehow!!!

a=[1]
for i in range(34):
   for x in a:
       print x,
   print
   a = map(lambda x:sum(x),zip([0]+a,a+[0]))

(追記)

がんばって10バイト減らした。不毛な努力（笑）

でも、そこがいい。

SRM BrushUp: BestView (436 div2 Middle)

引き続き、SRMの復習。

n個のビルが等間隔に直線状に並んでいる。i番目のビルの高さをheights[i]とする。

あるビルの屋上からは、一番多くのビルの姿を見ることができる。そのビルから見ることのできるビルの数を求めよ。

ビルxからビルyが見えるためには、xからyを結ぶ直線より上にあるビルが区間(x, y)に無ければよい。

しかしここで注意。

x, yはintだが、普通に傾きを取って計算するとdoubleになる。

doubleとintの比較。。

これはNG。

例えば、

if (a1 + 1.*b/c *a2 <= d)

という式は、

if (a1*c + b *a2 <= d*c)

と書くのが鉄則。

あと、この問題では、掛け算した結果が10^10オーダーになるのでlong long intを使わないといけない。が、こんな引っかけにはもう引っかからない。

class BestView {
public:
   int numberOfBuildings(vector<int> heights) {
       int n = heights.size();
       vector<long long int>h(n);

       REP(i, n) h[i] = heights[i];
       int ret = 0;
       REP(i, n) {
           int val = 0;
           REP(j, n) if (i != j){
               bool ck = true;
               if (j < i) {
                   FOR (k, j+1, i)
                       if (h[i] * ABS(i-j) + (h[j] - h[i]) * ABS(k-i) <= h[k] * ABS(i-j)) ck = false;
               } else {
                   FOR (k, i+1, j)
                       if (h[i] * ABS(i-j) + (h[j] - h[i]) * ABS(k-i) <= h[k] * ABS(i-j)) ck = false;
               }
               if (ck) ++val;
           }
           ret = max(ret, val);
       }

       return ret;
   }
};

余談になるが、doubleの最大値、精度について、

• 符号部 1bit
• 仮数部 52bit
• 指数部 11bit

なので、最大値は2^1024 ~ 10^300、精度は2^52 ~ 10^15くらい。

実はこのビット数は簡単に覚えられる。

まず、doubleは64bit。符号部が1bit必要。

指数部は切りの良い値にしたい。⇒1000くらいかな。でプラマイにふるから2000。2^11 ~ 2000だから指数部は11bit。

じゃ仮数部は、64-1-11=52bitか。

という具合。

SRM BrushUp: BirdsCounting (435 div2 Hard)

鳥がn匹いる。

毎日ランダムにm匹の鳥を捕まえて、印を付ける。

x日後に、印が付いた鳥がy匹になる確率を求める。

実際の問題：

http://www.topcoder.com/stat?c=problem_statement&pm=10243&rd=13697

典型的なDP。

d日後にi匹の鳥に印が点いている確率をdp[d][i]とおくと、

dp[d][i] = dp[d-1][i-m] * comb[i-m][0] * comb[n-i+m][m] / comb[n][m]

+ dp[d-1][i-m+1] * comb[i-m+1][1] * comb[n-i+m-1][m-1] / comb[n][m]

+ .....

+ dp[d-1][i] * comb[i][m] * comb[n-i][0] / comb[n][m]

が分かる。

あとは、実装するだけ。

double dp[8][32];
int comb[32][32];
class BirdsCounting {
public:
    double computeProbability(int birdsNumber, int caughtPerDay, int daysNumber, int birdsMarked) {
        memset(dp, 0x00, sizeof(dp));
        init();

        dp[0][caughtPerDay] = 1.0;
        for (int d = 1; d < daysNumber; d++) {
            for (int i = 0; i < birdsNumber+1; i++) {
                for (int k = 0; k < caughtPerDay+1; k++) {
                    dp[d][i+k] += dp[d-1][i] * prep(birdsNumber - i, k)
                            * prep(i, caughtPerDay-k) / prep(birdsNumber, caughtPerDay);
                }
            }
        }

        return dp[daysNumber-1][birdsMarked];
    }

private:
    double prep(int n, int k) {
        if (k > n)
            return 0.0;

        return comb[n][k];
    }

    void init() {
        REP(i, 32) comb[i][0] = 1;
        FOR (i, 1, 32) FOR (j, 1, 32)
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
    }

};

Div.2 Hard、Div.1 Middleレベルがようやく解けるようになってきた感じがする。

本番ではhogeりまくってますけど・・・。

32bit v.s. 64 bit CPU

I was not perfectly sure about what the difference between a 32bit CPU and that of 64-bit.

But all things have cleared away.

There are two differences between them.

1. The maximum size of number that each CPU can deal with.

I found an interesting site:

The below explains quite well about the difference.

http://stackoverflow.com/questions/3072444/long-long-int-on-32-bit-machines

2. The maximum size of memory size that can be effectively used.

This is because of 1., I think.

Since the maximum number 32 bit can express is up to 2^32 ~ 4*10^9,

it makes no sense to mount more-than-4GB memory on PC with a 32bit CPU.

And you can effectively use 2^64 ~ 10^19 byte memory on 64bit machine, theoretically.

Notice that ONE address is assigned to memory by ONE byte.

学ぶべき言語

最近なんか調子が悪い。。あんまり頭が働かない。

アルゴリズムの勉強は一時ストップして、新しい言語の勉強を勉強しようと思う今日この頃。

私が勉強したい言語をまとめてみた。

1. C++
2. Java
3. Python
4. Php
5. Haskell

1. C++

　現場では古い技術とか言われているが、アルゴリズマーにとっては最強言語だと思っている。今一番使っている言語でもある。家でも仕事でもC++。。

2. Java

　コテコテのオブジェクト指向言語。コードの量が多くなってしまうのが難点だが、オブジェクト指向をきちんと学ぶには最適の言語だと考えている。昔仕事で書いたことがある。

3. Python

　私が知っている中で一番手軽で楽な言語である。その場限りのプログラムを書くときに重宝する。現在、復習中。

4. Php

　HTML埋め込み式のスクリプト言語。昔バイトで書いていた。Web開発において重宝される。セキュリティの問題はあるらしいが・・。

5. Haskell

　コテコテの関数型言語。関数型言語を本気で学ぶならHaskellがよいと思う。この中で一番苦手な言語。（勉強し出し始めたくらい。。）

他にお勧めの言語とかあったら教えてください。

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

前に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()

ショートコーディング: 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;
}

Emacs 入門（３）

最近、

TopCoder -> eclipse

Webアプリ開発 & サンプルプログラム -> emacs

という感じにemacsへシフトしつつあります。

elispによる設定も充実してきて、使えるコマンドも少しずつ増えてきました。

最近覚えたコマンドリスト。

• 「C-space」 マーキングセット
• 「M-w」 選択リージョンコピー
• 「C-w」 選択リージョンカット
• 「C-y」 貼り付け
• 「M-;」 選択リージョンをコメントアウト/コメントアウト解除
• 「C-s」 キーワード検索（順方向）
• 「C-r」 キーワード検索（逆方向）

まー、こんなところです。Emacs初心者から初級者ぐらいにはなったでしょうか・・・。

ちなみに、emacsでは「copy and paste」を「kill and yank」と言うそうです。

.emacsの設定はこんな感じです。次はオートコンプリートを強化するために、TAGを覚えたいところ。

(add-to-list 'load-path (expand-file-name "~/.emacs.d/elisp"))

; font, style, design
(global-font-lock-mode t)
(setq display-time-day-and-date t)
(display-time)
(setq transient-mark-mode t)               ; high-light active regeon


; auto-install
(require 'auto-install)
(setq auto-install-directory "~/.emacs.d/elisp/")
(auto-install-update-emacswiki-package-name t)

; auto-complete
(require 'auto-complete)
(global-auto-complete-mode t)

; wb-line-number
(require 'wb-line-number)
(wb-line-number-toggle)
(custom-set-faces
'(wb-line-number-face ((t (:foreground "LightGrey"))))
'(wb-line-number-scroll-bar-face
((t (:foreground "white" :background "LightBlue2")))))

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;
}