Search on the blog

2011年1月30日日曜日

Facebook Hacker Cup Round 1C

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

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

1. Polynomial Factoring
最初見たとき、「Gauss-Jordan??」と思って、2.に行く。
2.を解いて、じっくり考えると、簡単な割り算に帰着できることに気付く。
以外とすんなり実装が終了し、F, Gが定数のとき, Fの次数 < Gの次数のときの例外ケースをテストしてちょっと直す。submit。

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.とも通ってました!
次はRound2という名のSemi-final。T-shirt取れるようベストを尽くします!

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個以下に分割するパターンの総数を求めよ。

一般に、m=nのとき、このパターン数をnの分割数と呼ぶらしい。

悩んで、悩んで2つ日目に分かった。(解説が天才的すぎて凡人の僕にはちょっと理解できません。。)
以下、凡人でも分かりそうな解説。
まず、dp[i][j]を整数jをi個以下に分割するパターン数とする。
jをi個以下に分割するパターンは、jをi-1個以下に分割するパターンとjをi個に分割するパターンの和である。ここで、前者の「jをi-1個に分割するパターン」はdp[i-1][j]と書ける。

次に後者。「jをi個に分割するパターン」は、予めi個を1個ずつi個の集合に割り当てて、残ったj-i個をこの集合に割り当てるパターンを考えればいいと分かる。
ちょっと、ややこしいので例題を。
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[0].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[0].size();
int m = mtx.val[0].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;
}
};
以下のように使います。3*3行列の足算と掛算をやってみましょう。


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 64
int 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本戦が始まった。
結果は、3問中1問解けただけ。。でも1000位以内に入ってるので、Round 2行けるのでは!?

とりあえず、問題解説。

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

2問目。
不等式制約のついた関数最大化問題。
凸関数なら、二分法でいけると思ったが、よく考えると目的関数は局所的にはギザギザな形になる。
とりあえず、解いてみるがサンプルと合わない。てか、サンプルより良い解が出るのですが・・。サンプル間違ってるんじゃ疑惑。そして何故か現在2問目はサイトから消滅している・・・。
⇒疑惑が確信へと変わる。

【追記】
目的関数ギザギザってのは誤解があるようですねー。
不等式制約から片方の変数の最大値を割り出して、1変数の二次関数にすれば目的関数がギザギザするけど、オリジナル問題の目的関数はギザギザじゃないですね。。単なる単調増加の平面です。
適当な初期点から出発して、逐次、偏微分値が大きい方に進んで行くってのを制約式を満たすまで繰り返せば最大値に辿り着くんじゃないのか、これ。。

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)
今日は、HackerCupやCodeJam対策で学んだ便利なスキルについて。

標準入出力を指定したファイルに結びつける方法です。java風に言うと、標準入出力ストリームにファイルストリームを代入するみたいな感じです。

これを使うと、ファイル出力に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[256], dpt[256];
char bd[256][256];

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[256];
tmp[0] = '.';
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[16];
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.
Thanks for reading.

2011年1月6日木曜日

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

こんにちは。

合コンに行ったら、AKB48の前田敦子、篠田麻里子、板野友美、大島優子が現れて、楽しんでいたら、彼女に見つかってしまって怒られる。。
ちなみに、彼女は北乃きい☆
メイプルのCMみたいに、「もう、やめてくださいっ!」って怒られる。。


正月休みが長すぎて、変な想像をして時間を潰しています(笑)
やば、この妄想っぷり。。

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

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

取りあえず、例題を見てみましょう。今回は、私のオリジナル問題です。

A君、B君が以下のようなゲームをする。
最初、数字nが与えられて、A君は、n+1またはn+10を選ぶ。
次にB君は、A君が選んだ数字に対して、1または10を足す。さらに、A、B、A、・・・と続く。
先に、100に達した方が、勝ち。
もし、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[100][100];

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[50][50] = 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[100][100];

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[50][50] = 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++のメモリ管理

最近、C++のnew、deleteについてなんとなく気になっていることがあったので、試しにプログラミングを作ってみた。
newして確保した領域は、関数を抜けるときには解放されるものだと思っていたがどうやら違うみたい。
よく考えてみると、newはstackじゃなくて、heapの方だから、関数をreturnしても解放されないんだよなーー。。
なんて不便な。。。

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


void func() {
int *x = new int [100000000];

return;
}

int main() {

REP(i, 10)
func();

return 0;
}

上のコードを実行するとエラーになります。windowsで利用できるアプリケーションのメモリ最大値は2GBなので、メモリリークを起こします。以下のようにきちんとdeleteするとエラーは起きません。


void func() {
int *x = new int [100000000];

delete x;
return;
}

int main() {

REP(i, 10)
func();

return 0;
}

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



void func() {
int *x = new int [100000000];

x = new int [10];
delete x;
return;
}

int main() {

REP(i, 10)
func();

return 0;
}