Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-05-09Google Code Jam 2010 Qual Round

Google Code Jam 2010 Qual Round A Snapper Chain

| 14:36 | Google Code Jam 2010 Qual Round A Snapper Chain - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Qual Round A Snapper Chain - SRM diary(Sigmar) Google Code Jam 2010 Qual Round A Snapper Chain - SRM diary(Sigmar) のブックマークコメント

Problem Statement

Snap数が最大1億回なので何となくシミュレーションでも解けそうですが、問題数が1万あるので厳しいかも?と思いました。ちょっと考えたらシミュレーションする必要は全くありませんでした。

1回Snapすると1個目がON、2回Snapすると2個目がONし1個目がOFF、・・・(以下同様)。ということは、n個目までが全部ON時にSnapするとn+1個目がONとなりn個目までは全てOFFとなるため、漸化式にすると、n個目まで全てONになるSnap数*2+1がn+1個目まで全てONになるSnap数となる。漸化式を解くと、n個目まで全てがONになる最初の数は、2^n-1となる。連結がn個だと、2^nで最初の状態に戻るので、mod 2^nで2^n-1となるとき答えはON、それ以外のとき答えはOFFとなる。

以下、ソースです。Inputファイルの解析は省略します。


class GCJ {
public:
	string solve(int n, int k) {
		string result;
		
		if(k%(1<<n)==(1<<n)-1) result.assign("ON");
		else result.assign("OFF");

		return result;
	}
};

Google Code Jam 2010 Qual Round B Fair Warning

| 14:36 | Google Code Jam 2010 Qual Round B Fair Warning - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Qual Round B Fair Warning - SRM diary(Sigmar) Google Code Jam 2010 Qual Round B Fair Warning - SRM diary(Sigmar) のブックマークコメント

Problem Statement

64bitに入りきらない数が出てくるので、多倍長整数の扱いが必要です。私はJavaとか使えないので、今後Topcoderとかでも使うかもしれないと思いC++で多倍長四則演算の関数を作ってみましたが、例外処理などが多くて大変なので、疲れました。しかも途中Leading Zeroの処理ミスで1WAしてしまいました。とりあえず今回の問題で使うには十分なものができましたが、汎用的に使えるようにするにはかなり大変なので、少なくともCode Jamでは今後多倍長演算が必要な場合は既存のライブラリを使おうかなと思います。

肝心の問題そのものは、最大公約数を求めるだけの問題で、一旦Sortして隣同士の差をとってから、全ての最大公約数を求めてやれば良いです。解は、最大公約数から(最小の値 mod 最大公約数)を引くことで求まります。

提出版は自作ライブラリですが、以下は今後のためにNTLを使って書き直したソースです。ZZが多倍長整数の型です。(それにしても、NTLを使うとGCD関数なんかも用意されてるし、随分楽でした・・・あたりまえか・・)


#include <NTL/ZZ.h>
using namespace NTL;

class GCJ {
public:
	ZZ solve(vector <ZZ> vz) {
		ZZ result, z, gcdz;
		vector <ZZ> vzz;
		
		sort(vz.begin(), vz.end());
		for(int i=1; i<(int)vz.size(); i++) {
			z=vz[i]-vz[i-1];
			if(z!=0) vzz.push_back(z);
		}
		gcdz=vzz[0];
		for(int i=1; i<(int)vzz.size(); i++) {
			gcdz=GCD(gcdz, vzz[i]);
		}
		result=vz[0]%gcdz;
		if(result!=0) result=gcdz-result;

		return result;
	}
};

Google Code Jam 2010 Qual Round C Theme Park

| 14:36 | Google Code Jam 2010 Qual Round C Theme Park - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Qual Round C Theme Park - SRM diary(Sigmar) Google Code Jam 2010 Qual Round C Theme Park - SRM diary(Sigmar) のブックマークコメント

Problem Statement

高々1000グループしかいないので、1001回ジェットコースターを動かせば、必ずどこかでループします。ということで、1001回繰り返しシミュレーションして、先頭グループが同じものが2回来た時点でシミュレーションを終了します。あとはループの開始位置と終了位置に気をつけて、1ループの長さと稼ぎから全体の稼ぎを求めます。

配列のインデックスを書き間違えるという凡ミスで1WA、提出する結果ファイルを間違えるという更につまらないミスで1WAといけてないことをしてしましました。Topcoderだったら0点ですね。。今後気をつけようと思います。

以下、ソースです。


class GCJ {
public:
	ll solve(int R, int k, int N, vector <int> g) {
		ll result=0;
		int rotb, rote, cur=0, next;
		ll euro[1001], teuro, reuro=0;
		int calced[1001];
		
		memset(calced, -1, sizeof(calced));
		for(int i=0; i<=1000; i++) {
			if(calced[cur]>=0) {
				rotb=calced[cur]; rote=i; break;
			}
			next=cur;
			teuro=0;
			for(int j=0; j<N; j++) {
				if(teuro+g[next]<=k) {
					teuro+=g[next];
					next=(next+1)%N;
				} else break;
			}
			euro[i]=teuro;
			calced[cur]=i;
			cur=next;
		}
		for(int i=rotb; i<rote; i++) {
			reuro+=euro[i];
		}

		for(int i=0; i<min(rotb, R); i++) {
			result+=euro[i];
		}
		if(R<=rotb) return result;
		R-=rotb;
		result+=R/(rote-rotb)*reuro;
		R=R%(rote-rotb);
		for(int i=0; i<R; i++) {
			result+=euro[rotb+i];
		}

		return result;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100509