Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/05/23

Google Code Jam 2010 Round 1

| 23:25

通過出来ませんでした.

総評

全体的に凡ミスが多いというか,注意力が欠けていることを思い知らされた感じです.きちんとできていれば通っていたなぁというのが悔しいですね(みんなそうだと思いますが).

コマンドの操作をミスする,ファイルの操作を間違える,変数名を間違える,boost のヘッダが全部無くなっている,入力ファイルをダウンロードしてからデバッグコードを取り除いてコンパイルする...アルゴリズムやコーディングと本質的に関係のない部分でのロスが大きすぎました.

急がば回れってことで次回までは落ち着いて注意深く解く訓練をしたいと思います.

Round 1A

23 pt. Rank: 1346

Problemsmalllarge
A. Rotate1:14:05, 2 wrong tries1:14:40
B. Make it Smooth------
C. Number Game------

A は方向を示す配列にバグが有ったので修正したのはいいけど,small の input が毎度変わっていることに気がつかずに無駄に時間を食った...

	int dx[] = {1,0,1,-1};
	int dy[] = {0,1,-1,1};

B は与えられた文字列に対してレーベンシュタイン距離が最小となるような smooth な文字列を求める問題ということまでは分かったけど,アプローチが全く分からず.要復習.

C は sample が通らずに撃沈.rng さんのコードをチラ見したがまだ理解出来ていない.

Round 1B

40 pt. Rank: 1625

Problemsmalllarge
A. File Fix-it2:26:582:27:32
B. Picking Up Chicks------
C. Your Rank is Pure1:35:28Time expired

C から着手した.

C は少し時間がかかったけど良く解けたと思う.large の submission が +0.674 遅かったらしく reject された.これは large をかけて「やっぱり」終わらなさそうなので急遽 cache を実装したことが原因.「やっぱり」と思うことは初めからそうしたほうが良かったのに,急いでしまって実装しなかった.頭の悪い判断ミス.解く順番を変えたことでファイルの保存先を間違えたせいで small では提出するファイルを間違えた.その時に map の変数名に map を使ってコンパイルエラーを出したのがロスになってさらに悔やまれる.

A は簡単なので何も考えずに実装してパス.ディレクトリ構造の多分木ライブラリを見つけておきたい.boost を使ったけど何故か /usr/include にインストルされてーた boost (しかも1.35から1.41まで全部)がごっそり消えていたので急遽インストール.焦る.

B は未着手.問題も見ていない.

C large が通っていれば通過したので非常に悔やまれる.

Round 1C

9 pt. Rank: 2815

Problemsmalllarge
A. Rope Intranet15:231 wrong try
B. Load Testing4 wrong tries---
C. Making Chess Boards------

18:05 頃まで寝てしまったので頭がボケていた.

A は簡単なのですぐに実装したのはいいけど,large で間違っていた.見直してみると

int solve(int N, VI A, VI B)
{
	int cnt = 0;
	For(i,0,N) For(j,i+1,N)
	{
		if(A[i+1]>A[i] && B[i+1]<B[i]) cnt++;
		if(A[i+1]<A[i] && B[i+1]>B[i]) cnt++;
	}
	return cnt;
}

i, j の全組み合わせループなのに j はどこにいった...しかも For(i,0,N) じゃなくて For(i,0,N-1) だ.

B は問題の意味が未だにわかっていないが,なんとなく解き方を推測してコードを書いてみたけど全部失敗.答え合わせをしたところ,最初に書いたコードで 2 とするべきところを何故か C としていた(サンプルが C=2 の場合が多かったせいだろうか).あと -1 するのを忘れていたり.凡ミス.

C は入力を読み込んで解析するところまでで終わり.多分解けると思う.

AndiAndi2011/07/22 15:08Thanks alot - your answer solved all my problems after several days srtuglging

ymztwdpymztwdp2011/07/26 00:50iMKSlH , [url=http://vxqonjgohmzr.com/]vxqonjgohmzr[/url], [link=http://bdghiksyjeoz.com/]bdghiksyjeoz[/link], http://fqpjpgeffbmu.com/

EgwoloEgwolo2013/02/16 23:19Thanks for contributing. It's helepd me understand the issues.

zzokgazzokga2013/02/19 14:25gNeh7s <a href="http://jdxldqxslfbx.com/">jdxldqxslfbx</a>

ealpalshhtealpalshht2013/02/19 14:25ftpxVI <a href="http://cpdedlynamuf.com/">cpdedlynamuf</a>