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 は入力を読み込んで解析するところまでで終わり.多分解けると思う.


Google Code Jam 2010 Round 1B A. File Fix-it

| 07:16

http://code.google.com/codejam/contest/dashboard?c=635101#s=p0&a=0

問題

既に存在する UNIX 形式のディレクトリパスの集合がある時に,与えられたディレクトリパスのディレクトリを作る際に,いくつのディレクトリを作らなければならないかを求める問題.

結果

small, large 共に correct.

アプローチ

本番では問題の細かい条件までちゃんと読む時間がなかったので,要点だけ押さえて,思い付くまま多分木を作ってディレクトリ構造とディレクトリの作成をシミュレートした.

large でも特に問題が大きくないので set を使ってすべてのディレクトリパスを保存しても問題なさそう.

問題の条件を読み直したら

1 1
/home/yuyarin/test
/home/yuyarin

みたいなケースも無い,つまり既存のディレクトリパスについてはその上位のディレクトリのパス(/home/yuyarin,/home)も,既存ディレクトリパスの集合に含まれているので,作るかどうかは既存ディレクトリパスの集合にパスの文字列が有るか無いかだけで判定できる.

作るべきディレクトリに対しては上位ディレクトリを求めていって,それが集合に無ければ追加してカウントを増やせばいい.

ソースコード

初めから書き直したので,提出時とアルゴリズムが違う

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

typedef vector<string> VS;

#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)
#define sz(a) int((a).size())

// using boost C++ library Version 1.41>=
// http://www.boost.org/
#include <boost/algorithm/string.hpp>

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int N, M;
		cin >> N >> M;
		VS ve(N);
		VS vc(M);
		set<string> sp;
		Rep(n,N)
		{
			cin >> ve[n];
			sp.insert(ve[n]);
		}
		int r = 0;
		Rep(m,M)
		{
			cin >> vc[m];
			VS vs;
			boost::algorithm::split(vs, vc[m], boost::is_any_of("/"));
			string s = "";
			For(i,1,sz(vs))
			{
				s = s + "/" + vs[i];
				if(sp.insert(s).second)
					r++;
			}
		}
		cout << "Case #" << t+1 << ": " << r << endl;
	}
	
	return 0;
}

Google Code Jam 2010 Round 1B C. Your Rank is Pure

| 04:38

http://code.google.com/codejam/contest/dashboard?c=635101#s=p2&a=0

問題

正数の集合 S の中においてある数 n が pure である条件がある.n が S の中で r 番目の数であるとき n のランクは r であると言う.n のランクが r1 であり,数 r1 のランクが r2 であり,,,としていき最後に 1 にたどり着けば n は pure であると言う.

与えられた n について, S = {x|x∈[2,n]} の部分集合 S' において n が pure であるような S' の作り方の個数を求める.

結果

small は correct だったけど提出するコードを間違えた.

large は答えを出したけど,提出がギリギリで駄目だったけど,admin に問い合せろとエラーが出た.

なので問い合わせ中.

→提出は + 0.674 秒遅かったらしい.そう計測された以上 reject とのこと.正しいソースコードの再アップロードと,エラーの理由はスルーされた.

large-practice では正解を出せていた.

アプローチ

数字 n がランク r として出現するときの場合の数を求める.

DP でも解けるけど DP にせずに再帰とキャッシュ(*1)を使った.

r〜n の間に m 個(m∈[0,r-2]) の数字が入る場合(*2)の数は Combination(n-r-1,m) で(*3),1〜r の間に数字が入る場合の数は数字 r がランク r-m-1 で現れる場合の数なのでこの関数の再帰で求められる.これらを掛け合せたものが,数字 n がランク r として出現するときの場合の数である(*4).

この関数を入力 n に対して,数字 n がランク r∈[1,n] として出現するときの場合の数の合計を計算してあげれば良い(*5).

Combination を求める部分で Integer Overflow を起こしそうな気配なので,gmpxx にお世話になった.

ソースコード

提出コードから掲載コードへの変更点

  • キャッシュ部分をマクロ化.
  • include 順序の整列,改行の追加削除等,表示を見やすくするもの
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <iostream>

// using The GNU Multiple Precision Arithmetic Library
// http://gmplib.org/
// compile with -lgmpxx -lgmp
#include <gmpxx.h>

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())

#define make_cache(...) map< __VA_ARGS__ > cache;\
map< __VA_ARGS__ >::iterator cache_it;
#define cache_hit(query_) (cache_it=cache.find(query_))!=cache.end()
#define check_cache(query_) if(cache_hit(query_)) return (*cache_it).second;
#define store_cache(key_,value_) cache.insert(mp(key_,value_))

make_cache(pair<int,int>,mpz_class)

mpz_class func(int n, int r)
{
	if(r==1) return 1;
	
	// *1
	check_cache(mp(n,r));
	
	int N = n-r-1;
	int M = r-2;
	mpz_class ans = 0;
	
	// *2
	for(int m=0; m<=M; m++)
	{
		if(N<m) continue;
		mpz_class p=1;
		// Combination(N,m) *3
		for(int j=0; j<=m-1; j++)
			p *= (N-j);
		for(int j=2; j<=m; j++)
			p /= j;
		// *4
		ans += p*func(r, M-m+1);
	}
	
	// *1
	store_cache(mp(n,r),ans);
	
	return ans;
}

int solve(int n)
{
	mpz_class ans = 0;
	// *5
	for(int i=1; i<n; i++)
		ans += func(n, i);
	ans %= 100003;
	return ans.get_si();
}

int main(int argc, char* argv[])
{
	uint T;
	cin >> T;
	
	for(uint t=0;t<T;t++)
	{
		uint n;
		cin >> n;
		cout << "Case #" << t+1 << ": " << solve(n) << endl;
	}
	
	return 0;
}

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>