## 2011年1月30日日曜日

### Facebook Hacker Cup Round 1C

えーと、Round 1Cがありました。
ドラゴンボールとワンピースを見たいという誘惑に耐えて、ちゃんと真面目に解きました。

ちょっと難しかったです。数学的な問題が多かったです。

1. Polynomial Factoring

2.を解いて、じっくり考えると、簡単な割り算に帰着できることに気付く。

2. N-Factorful
まず、この問題に取り掛かる。
[a, b]内の整数xの中で素因数の数がちょうどn個である数がいくつあるか数えるだけです。
が、、
Straight-forwardなやり方は通じません。1 <= a, b <= 10^7なので、まともに毎回素因数分解していては間に合いません。
で、思いつかず。。取りあえず、エラトステネスで素数リストを作って、sqrt(x)までまわしてみるという方法を試みるも上手くいかず。これでも、O(x*sqrt(x))なのでキツイのか。。

で、漸化式を思いつく。dp[x]をxの素因数の数とすると、

dp[x] = 0 (if x == 1)
dx[x] = 1 (if x is a prime number)
dp[x] = dp[x/p] + (x/p % p) (else)

で行けるじゃないか！ここで、pはxの素因数です。あとは、メモ化再帰にすれば時間どおりに間に合いました。（メモ化すれば、各xに対して定数時間で解が出るので、O(x)。）答えはあってるかどうかまだ不明～。

3. Risky Slide
2. が無理そうだと思い、ちょっと3.を読む。
これは、DFSかDPっぽいと思う。PKUの「滑雪」と同じような雰囲気だ。。
これは解けそう！
と思って、テストケースを見るが、意味不明。。

[追記]
やった～。1.2.とも通ってました！

### Code Name "Tiger"

Oops, seems I'm completely ignorant.
I didn't know JAVA's new features adopted in J2SE5.0 -- auto-boxing--.

This new feature introduced in "Tiger", which is the code name for J2SE5.0, is quite amazing.
Truth be told, I was under the impression that wrapping primitive types to Wrapper types was the biggest fault in JAVA.
But the drawback was removed so long ago, it seems.

Haha, what a pity.
It's just my luck, when I was using JAVA at work, the version was "Kestrel."

Here, I'll post the code utilizing the feature "auto-boxing" along with the feature introduced in Tiger, the "for-each" iterator.

`public class Main {   public static void main(String args[]) {       ArrayList<Integer> x = new ArrayList<Integer>();            x.add(1);       x.add(100);       int n = 2;       x.add(n);            for (int i : x)           System.out.println(i);         }  }`

Now that I learned JAVA's new selling points, I'm getting willing to switch to JAVA more than ever~~.

## 2011年1月29日土曜日

### Javaで文字列チェック

Javaで文字列が数値かどうか判定したい場合。
こういうテクニックがある。
`private static boolean isDigit(String s) {  try{      Integer.parseInt(s);      return true;  }catch(NumberFormatException e){      return false;  }}`

このテクニックは結構使えます。

## 2011年1月28日金曜日

### 分割数を考える

『プログラミングコンテストチャレンジブック』で挑戦した問題。

n個の互いに区別できない商品を、m個以下に分割するパターンの総数を求めよ。

まず、dp[i][j]を整数jをi個以下に分割するパターン数とする。
jをi個以下に分割するパターンは、jをi-1個以下に分割するパターンとjをi個に分割するパターンの和である。ここで、前者の「jをi-1個に分割するパターン」はdp[i-1][j]と書ける。

ちょっと、ややこしいので例題を。
10個を4個に分けるパターンは、まず集合が4ついるので、それぞれの集合に1個ずつ割り当てる。
1, 1, 1, 1
あとは、残った6個をこの4つの集合に割り振るパターン数を考えればよい。

6, 0, 0, 0
1, 1, 1, 3
2, 2, 0, 2
などが考えられる。
これを、予め作っておいた集合
1, 1, 1, 1に加えれば4つに分割するパターンが出来ることがわかる。よって、「jをi個に分割するパターン」は、dp[i][j-i]と書ける。

dp[i][j] = dp[i-1][j] + dp[i][j-i]
という漸化式が得られる。これはDPを使えば、O(n*m)で解けます。

ソースは、・・・・・

ソースを見たい人は、この本を買おう！（笑）

## 2011年1月26日水曜日

### C++で行列計算

C++で行列計算をしてみましょう。
オペレータのオーバーライドを使用すれば、結構簡単に行列の計算を行うためのクラスを作成することが出来ます。

では、ソースです。
`class MTX {public: vector<vector<int> > val; MTX(int n, int m) {     vector<int> zeros;     REP(i, m)zeros.push_back(0);     REP(i, n)val.push_back(zeros); } MTX operator+(const MTX mtx) {     int n = this->val.size();     int m = this->val.size();     MTX ret(n, m);     ret.val = this->val;     REP(i, n)REP(j, m)         ret.val[i][j] = this->val[i][j] + mtx.val[i][j];     return ret; } MTX operator*(const MTX mtx) {     int n = this->val.size();     int l = this->val.size();     int m = mtx.val.size();     MTX ret(n, m);     REP(i, n)REP(j, m)REP(k, l)         ret.val[i][j] += this->val[i][k] * mtx.val[k][j];     return ret; }};`

`int main() {  MTX a(3,3), b(3, 3);  REP(i, 3)REP(j, 3)      cin >> a.val[i][j];  REP(i, 3)REP(j, 3)      cin >> b.val[i][j];  MTX c = a + b;  MTX d = a * b;  REP(i, 3)REP(j, 3)      printf("%d%c", c.val[i][j], j==2 ? '\n' : ' ');  REP(i, 3)REP(j, 3)      printf("%d%c", d.val[i][j], j==2 ? '\n' : ' ');}`
と、こんな感じです。

## 2011年1月25日火曜日

### An impressive code(1)

Now I'm studying DP.
And I encountered a wonderful code.

It's a solution to LIS, longest increasing sequence, which is a classic DP problem where you are to find the longest subsequence {a_{i1}, a_{i2}, .... a_{im}} from a given sequence {a_0, a_1, a_2, .... a_n}, such that i1 < i2 < , ..., im and a_{i1} < a_{i2} < , ...., a_{im} hold.

I was able to solve the problem, but the sample code in my textbook was so great. I was thrilled!!
Here's the source code.
In this manner, You can solve LIS at the order of nlog(n).
Notice that the STL function lower_bound() works at log(n) since the internal structure is a binary tree.

`#define MAX_N 64int x[] = {4, 2, 3, 1, 5};int dp[MAX_N];int main() {    fill(dp, dp+MAX_N, INF);    REP(i, SIZE(x))        *lower_bound(dp, dp+MAX_N, x[i]) = x[i];    cout << lower_bound(dp, dp+MAX_N, INF) - dp << endl;}`

## 2011年1月19日水曜日

### Facebook Hacker Cup Round 1A

Hacker Cup本戦が始まった。

とりあえず、問題解説。

1問目。
オーソドックスなBFSの問題。
グラフに帰着させても解けるが、すべての枝の重みが1のときはBFSで解く方がよい。

2問目。

とりあえず、解いてみるがサンプルと合わない。てか、サンプルより良い解が出るのですが・・。サンプル間違ってるんじゃ疑惑。そして何故か現在2問目はサイトから消滅している・・・。
⇒疑惑が確信へと変わる。

【追記】

3問目。

DPで解けるなと思ったが、これまた手計算でサンプルと合わない。なぜ！？
でも、黄色い人の情報によるとDPで解けるようです。もしくはGreedyでも解けるみたい。まあ大局観はずれてなかったということで。

そしてサンプルはなるべく手計算できるような簡単なものを入れて欲しいのですが。
てか、1Aの結果早く欲しいのですが。

まー、ぐだぐだ言わずに

って話ですね。

## 2011年1月15日土曜日

### Connect a Standard I/O to Files

Today, I'll write about the skill acquired from preparations for Algorithm contests such as HackerCup and CodeJam.

It's about how to connect a standard I/O to designated files. In Java terms, I'd say how to substitute file streams to standard I/O streams.

By using these skills, you can use printf() and cout when writing outputs to files, and you can also use scanf() and cin when reading from files. It's useful, right?
I'll put source codes for both C++ and Java. Before running these codes, make sure that you have made two files, INPUT(containing some integers) and OUTPUT, on your machine.

（Japanese）

これを使うと、ファイル出力にprintf(), coutが使えます。ファイル入力にはscanf()、cinが使えます。かなり便利です。
C++、Javaそれぞれでサンプルコードを載せておきます。
INPUTファイルとOUTPUTファイルを作成してから、このソースを実行してください。INPUTファイルにはいくつかの整数を記入してください。

[C++ version]
`#define INPUT "C:/input.txt"#define OUTPUT "C:/output.txt"int main() {  // connect I/O streams to files  freopen(INPUT, "r", stdin);  freopen(OUTPUT, "w", stdout);  int x;  while (cin >> x) {      cout << x << endl;  }  cerr << "done." << endl;  return 0;}`

[Java version]
`public class Main {  static private final String INPUT = "C:/input.txt";  static private final String OUTPUT = "C:/output.txt";  public static void main(String args[]) {      // open I/O files      FileInputStream instream = null;      PrintStream outstream = null;         try {          instream = new FileInputStream(INPUT);          outstream = new PrintStream(new FileOutputStream(OUTPUT));          System.setIn(instream);          System.setOut(outstream);      } catch (Exception e) {          System.err.println("Error Occurred.");      }         Scanner in = new Scanner(System.in);      for (;in.hasNext();) {          int x = in.nextInt();          System.out.println(x);      }         System.err.println("done.");      return;  }}`

## 2011年1月12日水曜日

### Hacker WorldCup 2011 -the qualification round-

I got the result of the qualification round of Hacker World Cup 2011, run by facebook, which determines who is the best hacker in the world.

It seems I'm qualified to advance to round 1, with the perfect score :D

The problems are kind of easy.
One can be solved just by using next_permutation() in STL.
Another can be solved by implementing just as it was described in the problem.
The other is a little difficult. It's DP problem, which is similar to the Pascal's Triangle.

Here, I'll post my solution to these problems.

Double Square:
`int main() {    ifstream in(INPUT);    ofstream out(OUTPUT);    int n;    long long int x;    in >> n;    REP(i, n) {        in >> x;        int ret = 0;        for (long long int j = 0; j*j*2 <= x; j++) {            long long int y = x - j*j;            long long int y2 = sqrt(y) + .5;            if (y2 * y2 == y)                ++ret;        }        out << ret << endl;    }    cout << "done." << endl;    return 0;}`

Peg Game:

`double dp, dpt;char bd;void solve(int r, int c) {    REP(i, r) {        memset(dpt, 0, sizeof(dpt));        REP(j, 2*(c-1)+1) {            if (bd[i][j] == '.')                dpt[j] += dp[j];            else {                if (j - 1 < 0 + (i%2 != 0))                    dpt[j+1] += dp[j];                else if (j + 1 >= 2*(c-1)+1-(i%2 != 0))                    dpt[j-1] += dp[j];                else {                    dpt[j-1] += dp[j] * .5;                    dpt[j+1] += dp[j] * .5;                }            }        }        memcpy(dp, dpt, sizeof(dp));    }}int main() {    ifstream in(INPUT);    ofstream out(OUTPUT);    int n;    in >> n;    REP(i, n) {        int r, c, k, m;        in >> r >> c >> k >> m;        REP(ii, r) {            if (ii % 2) REP(jj, 2*(c-2)+1) {                bd[ii][jj] = (jj % 2) ? '.' : 'x';            }            else REP(jj, 2*(c-1)+1) {                bd[ii][jj] = (jj % 2) ? '.' : 'x';            }        }        REP(j, m) {            int ri, ci;            in >> ri >> ci;            bd[ri][2*ci] = '.';        }        REP(j, r) {            if (j % 2) {                char tmp;                tmp = '.';                REP(jj, 2*(c-2)+1)                    tmp[jj+1] = bd[j][jj];                tmp[2*(c-2)+2] = '.';                memcpy(bd[j], tmp, sizeof(bd[j]));            }        }        double prb = .0;        int ret = -1;        REP(p, c-1) {            memset(dp, 0, sizeof(dp));            dp[2*p+1] = 1.;            solve(r, c);            if (dp[2*k+1] > prb)                prb = dp[2*k+1], ret = p;        }        char rprb;        sprintf(rprb, "%.6lf", prb);        out << ret << " " << rprb << endl;    }    cout << "done." << endl;    return 0;}`

Studious Student:
`int main() {    ifstream in(INPUT);    ofstream out(OUTPUT);    int n, m;    in >> n;    REP(i, n) {        in >> m;        vector<string>ss;        string str, ret = "";        REP(j, m) {            in >> str;            ss.PB(str);        }        sort(ALL(ss));        do {            string ptr = "";            EACH(itr, ss)                ptr += *itr;            if (ret == "" || ret > ptr)                ret = ptr;        } while (next_permutation(ALL(ss)));        out << ret << endl;    }    cout << "done." << endl;    return 0;}`

I'm shooting for advancing to round2 !!

## 2011年1月7日金曜日

### 200 Accepted on POJ

I did it! I've got 200 ACs on POJ, Peking Online Judge, which is the biggest computer algorithm exercise platform!
The next target is, of course, 300 ACs.

Looking back on days after I got 100 ACs, what happened?
What I got? Or what I learned?

umm, I got a little familiar with the game tree, DFS, and the union find tree.
oh, last and not least, I learned a lot about the bit manipulations -- bit DP, the inclusion and exclusion principle --.

The problem left unsolved on POJ is getting more and more difficult.
I barely come up with an approach to the problems easily these day.
And the more problems I solve, the more I notice that I need lots of practices.

What I'm interested in now?
Well, hash algorithm, especially string manipulations against a large mount of text such as Rabin-Karp string search algorithm.
I understand how the hash function works and how it cuts the time to calculate the hash value. But I cannot apply it to several problems on POJ.

And also, I'm curious about the matching problem.
Both the matching problem in bipartite graph and the general matching problem.
But it seems it's a little difficult to me for now.
If you can solve this problem, could you tell me how to solve it??

Ahh, I get hungry. I have to go eat something.
See you.

## 2011年1月6日木曜日

### ゲーム問題のプログラミング

こんにちは。

ちなみに、彼女は北乃きい☆
メイプルのCMみたいに、「もう、やめてくださいっ！」って怒られる。。

やば、この妄想っぷり。。

ここで言うゲーム問題とは、「2人のプレイヤーが交互にプレーし、お互いが自身のターンで最善手を選んだときに、勝つのはどちらのプレイヤーか」という問題です。

• 必ずどちらかが勝てるような構造になっている
• 状態が循環することはない
という条件を満たしています。このような条件を満たす場合、オーソドックスな解法は「ゲーム木(game tree)」をDFSで探索するというものです。

A君、B君が以下のようなゲームをする。

もし、100を超えたら負け。
お互いが、各ターンで最善手を選択するとき、A君はこのゲームに勝つことができるかどうかを求めよ。
ただし、nは[1, 100)とする。

「お互いが、最善手を選択する」というのは、勝てる手があれば勝てる手を選び、勝てる手が1手も無い場合のみ負ける手を選ぶということです。
これだけきちんと理解できれば、比較的簡単に再帰で実装できます。

`bool solve(int n) {   if (n == 100) return false;   if (n > 100) return true;   if (!solve(n+1)) return true;   if (!solve(n+10)) return true;   return false;}`

この問題の場合は、
• 必ずどちらかが勝てるような構造になっている
• 状態が循環することはない（数字は増えるだけで、減ることはないため）
という条件があったため、ゲーム木による解法で解くことができました。しかし、勝ち負けが必ずしも決まらなかったり、循環したりする問題では、ゲーム木のDFSは使えません。
そのような場合は、DP-likeな解法で解くことができます。この解法は、比較的計算時間がかかりますが、queueを利用することで高速化することもできます。
このDP-likeな解法については、次回書こうかと思います。

（注意）SEO対策の実験のため、有名人の名前を無駄に入れてみました。冒頭の文章は決して私の趣味ではありません。たぶん。。おそらく。。。。

## 2011年1月5日水曜日

### Give or Take!?

Today I'll write about "Give" and "Take" in programming.

"Give" literally means that a module gives some information to other modules to calculate some value. While "take" means that a module takes some information from other modules.

Let's go over it more detail.
A simplest example would be recursion v.s. tail recursion.
Consider the problem below:

This problem can be solved with an easy DFS.
A "giving" solution to the problem would be as follows:

`class CrazyBot {public:   double _e, _w, _s, _n;   double ret;   char passed;   double getProbability(int n, int east, int west, int south, int north) {       _e = east/100.;       _w = west/100.;       _s = south/100.;       _n = north/100.;       ret = 0.;       memset(passed, 0, sizeof(passed));       passed = 1;       solve(n, 1., 50, 50);       return ret;   }   void solve(int n, double prb, int x, int y) {       if (!n) {           ret += prb;           return;       }       passed[x][y] = 1;       if (!passed[x-1][y]) solve(n-1, _w*prb, x-1, y);       if (!passed[x+1][y]) solve(n-1, _e*prb, x+1, y);       if (!passed[x][y-1]) solve(n-1, _n*prb, x, y-1);       if (!passed[x][y+1]) solve(n-1, _s*prb, x, y+1);       passed[x][y] = 0;   }};`

I think the solution above is like what they call "tail recursion." But I would rather call this kind of recursive function "giving recursion." You can see that the function call itself and give the probability to it!

Another solution would be "taking" solution.
`class CrazyBot {public:    double _e, _w, _s, _n;    char passed;    double getProbability(int n, int east, int west, int south, int north) {        _e = east/100.;        _w = west/100.;        _s = south/100.;        _n = north/100.;        memset(passed, 0, sizeof(passed));        passed = 1;        return solve2(n, 50, 50);    }    double solve2(int n, int x, int y) {        if (!n)            return 1.;        double prb = 0.;        passed[x][y] = 1;        if (!passed[x-1][y]) prb += _w*solve2(n-1, x-1, y);        if (!passed[x+1][y]) prb += _e*solve2(n-1, x+1, y);        if (!passed[x][y-1]) prb += _n*solve2(n-1, x, y-1);        if (!passed[x][y+1]) prb += _s*solve2(n-1, x, y+1);        passed[x][y] = 0;        return prb;    }};`
This is a general recursive function you are familiar with.
Taking some information from the invoked functions, and calculate the return value.

Which type of recursion do you like?
I think I like the former because it's easy to think how things going on.

Aside from recursive functions, there are giving DP and taking DP.
Let' say you want to count how many pattern there exist to move P, the left below point of a rectangle, to Q, the right upper point.
You would solve the problem by constructing a two-dimensional matrix and doing the DP.
In this case, there could be two different coding -- giving and taking--.
Something like this:

e.g.) Giving DP
dp[x][y] = dp[x-1][y] + dp[x][y-1];

e.g.) Taking DP
dp[x+1][y] += dp[x][y];
dp[x][y+1] += dp[x][y];

Also, when solving DP problems regarding string manipulations, you can choose "giving" or "taking."
I think there's no big difference in speed and memory consumption between these two coding style. It's matter of taste.
But it's good to be able to write both styles and tactically use them depending on situations.

## 2011年1月4日火曜日

### New Year's Resolutions

A happy new year!
How you guys doing?

Today I'll write down my new year's resolutions!
1. Be a "stable" blue coder
2. Be ranked in top 1 % on POJ
3. write Tech Tips(This blog) in English
4. Get a pay raise :)
Here I'll go over the things above one by one, more detail.
1. might be a little difficult, but not impossible if I have good preparations. "Stable" means that have an ability to solve all three problems on div2 in time.

2. This is quite easy task! I'm now ranked in top 1.25 % or so. So it's a matter of time!

3. This is for practicing English! After getting the score of 900+ on the TOEIC test, seems like I'm getting away from studying English. So I think I will brush up my English more and more!

4. This is difficult! I hope that my company will be generous!

Wow, I've got a lot on my plate.
Seems like it's gonna be pretty busy this year.

See you.

## 2011年1月3日月曜日

### C++のメモリ管理

newして確保した領域は、関数を抜けるときには解放されるものだと思っていたがどうやら違うみたい。
よく考えてみると、newはstackじゃなくて、heapの方だから、関数をreturnしても解放されないんだよなーー。。
なんて不便な。。。

では、サンプルコードを。

`void func() { int *x = new int ; return;}int main() { REP(i, 10)     func(); return 0;}`

`void func() {  int *x = new int ;  delete x;  return;}int main() {  REP(i, 10)      func();  return 0;}`

deleteするときに注意しなければいけないことがあります。
deleteされるのは、その変数が現在指しているアドレス領域だということです。よって、以下のコードを実行すると、エラーがおきます。
intはdeleteされますが、intはdeleteされないのです。

`void func() {   int *x = new int ;   x = new int ;   delete x;   return;}int main() {   REP(i, 10)       func();   return 0;}`