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がよいと思う。この中で一番苦手な言語。（勉強し出し始めたくらい。。）

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