Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-06-06Google Code Jam 2010 Round 2

BのS/LとCのSを解いて31点2h10mで645位でした。

Round3には進めず・・・あと30分早く解ければ次に進めましたが、遅すぎてダメダメでした。

  • 問題A→実装がきつそう
  • 問題B→Smallの点が高く難しそう
  • 問題C→Smallはただのシミュレーションぽい

ということで問題Cから取り掛かりました。

Google Code Jam 2010 Round 2 C Bacteria

| 00:16 | Google Code Jam 2010 Round 2 C Bacteria - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 C Bacteria - SRM diary(Sigmar) Google Code Jam 2010 Round 2 C Bacteria - SRM diary(Sigmar) のブックマークコメント

バクテリアの増殖と死滅の過程をシミュレーションします。

上と左の両方にバクテリアがいないと増殖しないので、初期状態の右端バクテリアより右側及び下端バクテリアより下側にバクテリアが増殖することはありません。

ということで、Smallでは100*100の範囲内でバクテリアの増殖・死滅をシミュレーションすればよいです。

15分くらいでしこしこと書きましたが、あまりにもミスが多く、デバッグでさらに15分くらい消耗・・・

ダメすぎたので、間違えたところを書き留めておくことにします。

  • 増殖の条件が、左か上のどちらかにバクテリアがいるだけで増えるようになっていた
  • gridの次の状態をgrid2として記録していたが、繰り返し時にgrid2をgridにコピーし忘れていた
  • 最初のバクテリアの個体数を計算する際に、重複しているところを2重に数えていた(問題文に注意としてわざわざ書いてあるのに・・・)

3個目のミスについては、シミュレーションの終了条件を個体数管理によって実現しようとしましたが、そもそもシミュレーションの過程で必ずグリッド全体をスキャンするので、個体数管理は必要なかった・・・

当たり前の確認をきちんとしていないからこうなるんですかね。。

  • if文はよく内容を確認する
  • 問題文の注意点は実行前に再確認する
  • 不必要に複雑なことをしようとしていないか確認する

提出したソースは以下のとおりです。

typedef long long ll;

class GCJ {
public:
	ll solve(int R, vector <int> X1, vector <int> X2, vector <int> Y1, vector <int> Y2) {
		ll res=0, cnt=0;
		vector <vector <int> > grid(102, vector <int>(102, 0)), grid2;

		for(int i=0; i<R; i++) {
			for(int p=X1[i]; p<=X2[i]; p++) {
				for(int q=Y1[i]; q<=Y2[i]; q++) {
					if(grid[q][p]==0) {
						grid[q][p]=1;
						cnt++;
					}
				}
			}
		}

		while(cnt>0) {
			grid2=grid;
			for(int i=1; i<=100; i++) {
				for(int j=1; j<=100; j++) {
					if(grid[i][j]==1) {
						if(grid[i-1][j]==0 && grid[i][j-1]==0) {
							grid2[i][j]=0;
							cnt--;
						}
					} else {
						if(grid[i-1][j]==1 && grid[i][j-1]==1) {
							grid2[i][j]=1;
							cnt++;
						}
					}
				}
			}
			res++;
			grid=grid2;
		}

		return res;
	}
};

Google Code Jam 2010 Round 2 B World Cup 2010

| 00:16 | Google Code Jam 2010 Round 2 B World Cup 2010 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 B World Cup 2010 - SRM diary(Sigmar) Google Code Jam 2010 Round 2 B World Cup 2010 - SRM diary(Sigmar) のブックマークコメント

みなさんの提出状況を見ると、BのS/Lの提出率が高かったため、Cの終了後Bに取り掛かりました。

この問題については、以下のような仮定をした上で進めます。

  • 各々のチームが勝ち進むかどうか分からないので、すべてのチームが決勝まで進むと仮定する必要があります。
  • 見逃していい数というのは分かりにくいので、決勝までのうち、見なければいけない試合数に変換します。

Smallについては、Greedyな戦略で解けそうでした。

チーム0から順に、決勝から順に見なければいけない試合数分チケットを購入します。

チーム0の必要分を購入したら、チーム1でまた決勝から必要分購入していきます。(もちろん、既に購入してある分は除きます)

これだけで最小費用でチケットを購入できると思います。(試してませんが)


すぐに書けそうでしたが、Largeの提出率が高いので、こちらもやり方を考えてみました。

LargeはDPになりそうです。

チーム0から始めて、必要な試合数分(P-M[i])だけチケットを購入します。

C(n,k)をnからk個選ぶ組み合わせ数とすると、C(P,(P-M[i]))通りの購入方法があります。

次に、チーム1では、チーム0で購入したチケットに加えて、さらに必要なチケットだけを購入します。(これも、チーム0での購入状況に従って何通りか購入方法ができます)

というのをdfsでチーム2^P-1まで続けていき、コストが最小になるものを解とします。


現在のチケットの購入状況のうち、次のチームに対して意味のあるチケットかどうかを判断して状態を更新していくところが少しややこしく、実装に不安がありましたが、恐らくLargeを解かねば通過は難しいと考え、SmallはスルーしてLargeに挑むことにしました。

実際に書いてみると、思ったよりも状態の更新は難しくなく、むしろ計算量を減らす部分で苦労しました。

n個のうちk個を選ぶ組み合わせについて、

  • for文で1<<n通り回して、</li>
  • ビット数がkになる場合以外continue

という方針で書いたのですが・・・

  • 前回の購入時に既にk個を超えたチケットを購入している

という場合に、うまく動きませんでした。(これも、最初正しい答えが出ず原因解明に苦労しました)

とりあえず、

  • ビット数k未満のときcontinue

と変更してみましたが、特定の入力ケースにおいて計算量が爆発的に増え、TLEしてしまいました。

よく考えると既にk個以上のチケットが購入されている場合、これ以上チケットを買う必要はないので、

  • 前回の購入時に既にk個以上チケットを購入している場合、これ以上チケットを購入しないという例外処理をする

で問題なく動きました。

このあたりでビット演算でかなりごちゃごちゃして混乱してしまい、時間を浪費してしまい、結局1時間半近くかかってしまいました。

なんとか、うまくビットDPを混乱せずに書けるようになりたいですが・・・

練習するしかないでしょうか。


あとで、解説や他の人の解答を見ると、決勝のチケットからdfsで購入/非購入を試していけば良かったようです。

このほうがコードも簡単だし、計算量も少なくなりそうです。

一度解けそうな方法が見つかると、他の方法を探そうという意志がかなり弱くなってしまうため、解法が妙に複雑そうな場合は気をつけて別解を考えてみるようにしたいです・・・

以下、提出したソースです。solve関数が本体です。

typedef long long ll;

int popcount(unsigned int x) {
	int result=0;
	for(int i=0; i<sizeof(x)*8; i++) if(x&(1U<<i)) result++;
	return result;
}

class GCJ {
public:
	ll memo[1050][1050];
	int P;
	vector <int> M;
	vector <vector <int> > price;

	ll rec(int d, int pb) {
		ll res=2000000000000, tmp;
		int buy[11];
		int nb, pcnt, ppcnt;

		if(d==(1<<P)) return 0;
		if(memo[d][pb]>=0) return memo[d][pb];

		ppcnt=popcount(pb);
		for(int i=0; i<(1<<P); i++) {
			if(ppcnt>=P-M[d]) {
				if(i>pb) break;
				else i=pb;
			}
			pcnt=popcount(i);
			if((ppcnt<=P-M[d] && pcnt!=P-M[d]) || (ppcnt>P-M[d] && pcnt!=ppcnt)) continue;
			if(popcount(pb|i)!=pcnt) continue;
			memset(buy, 0, sizeof(buy));
			tmp=0;
			for(int j=0; j<P; j++) {
				if(i&(1<<j)) {
					buy[j]=1;
					if(!(pb&(1<<j))) tmp+=price[j][d/(1<<(j+1))];
				}
			}
			nb=0;
			for(int j=0; j<P; j++) {
				if(buy[j]) {
					if((d+1)%(1<<(j+1))>0) nb|=(1<<j);
				}
			}
			tmp+=rec(d+1, nb);
			res=min(res, tmp);
		}

		memo[d][pb]=res;
		return res;
	}

	ll solve(int _P, vector <int> _M, vector <vector <int> > _price) {
		ll res=0;
		
		P=_P; M=_M; price=_price;
		memset(memo, -1, sizeof(memo));
		res=rec(0, 0);
		return res;
	}
};

Google Code Jam 2010 Round 2 A Elegant Diamond

| 00:16 | Google Code Jam 2010 Round 2 A Elegant Diamond - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 A Elegant Diamond - SRM diary(Sigmar) Google Code Jam 2010 Round 2 A Elegant Diamond - SRM diary(Sigmar) のブックマークコメント

残り30分となってしまいましたが、この時点で550位くらいで、おそらくもう一問解かないと通過できないだろうという状態でした。

問題Aについては実装が難しそうでしたが、既に問題の内容は把握済みでしたので、これをやるしかないと思い、進めました。


やり方として、せっかく綺麗なダイアの形で与えられた入力をわざわざvector <int>に直してしまい、非常に処理が煩雑になってしまいました。。。

stringのまま読み込めば良かった・・・不必要にメモリ効率を良くしようとする悪いくせが出てしまいました。

30分では全く間に合わず、残念ながら私のGoogle Code Jam 2010はここで終わってしまいました。

他にも色々アルゴリズム的に判定処理を間違えたりしていたので、どちらにしてもダメでした。

今の私の実力ではこれでベストを尽くしたという感じです。

これ以上進むためには、妙なミスを減らすこと、コーディングを早くすること、そのためにさらに訓練を積み重ねることがまず必要なようです。

以下、コンテスト終了後に書いたコードです。solve関数が本体です。stringでの読み込みに直してあります。

check関数の中で同じチェックを2度するなど冗長な部分がありますが、このほうが早く書けると思うのでそのままにしてあります。


class GCJ {
public:
	int k;
	vector <string> dia;

	bool check(int r, int c, int s) {
		int top, rig, bot, lef;
		for(int i=1; i<s; i++) {
			for(int l=0; l<=i; l++) {
				top=r-i+l; rig=c+l; bot=r+i-l; lef=c-l;
				if(abs(top-(k-1))+abs(rig-(k-1))<k && abs(top-(k-1))+abs(lef-(k-1))<k && dia[top][rig]!=dia[top][lef]) return false;
				if(abs(top-(k-1))+abs(rig-(k-1))<k && abs(bot-(k-1))+abs(rig-(k-1))<k && dia[top][rig]!=dia[bot][rig]) return false;
				if(abs(bot-(k-1))+abs(lef-(k-1))<k && abs(bot-(k-1))+abs(rig-(k-1))<k && dia[bot][lef]!=dia[bot][rig]) return false;
				if(abs(bot-(k-1))+abs(lef-(k-1))<k && abs(top-(k-1))+abs(lef-(k-1))<k && dia[bot][lef]!=dia[top][lef]) return false;
			}
		}
		return true;
	}

	int solve(int _k, vector <string> _dia) {
		int r, c;
		int dri[4]={-1,0,1,0}, dci[4]={0,1,0,-1}, dr[4]={1,1,-1,-1}, dc[4]={1,-1,-1,1};

		k=_k; dia=_dia;
		r=k-1; c=k-1;
		if(check(r, c, k)) return 0;
		for(int i=1; i<2*k; i++) {
			for(int j=0; j<4; j++) {
				r=k-1+dri[j]*i; c=k-1+dci[j]*i;
				for(int l=0; l<i; l++) {
					if(check(r, c, k+i)) return (k+i)*(k+i)-k*k;
					r+=dr[j]; c+=dc[j];
				}
			}
		}

		return 0;
	}
};

Google Code Jam 2010 Round 2 D Grazing Google Goats

| 00:17 | Google Code Jam 2010 Round 2 D Grazing Google Goats - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 D Grazing Google Goats - SRM diary(Sigmar) Google Code Jam 2010 Round 2 D Grazing Google Goats - SRM diary(Sigmar) のブックマークコメント

コンテスト中は読むこともできませんでしたが、後で読んでみるとSmallは2円の重なる面積を求めるだけのようなので、簡単そうでした。

ということで解いてみましたが、意外と扇形の面積の求め方で場合分けなどが必要になってきて、時間がかかってしまいました。(40分くらい)

もっと簡単に書けるみたいなので、幾何に関する勉強が必要です。

以下、ソースです。solve関数が本体です。


typedef complex <double> pt;

double triangle_area_u(pt a, pt b, pt c) {
	return fabs(imag(conj(b-a)*(c-a))*0.5);
}

vector <pt> cross_c_c(pt c, double r, pt d, double s) {
	vector <pt> res;
	double di=abs(c-d);

	if (di<=r+s && di>=abs(r-s) && !(c==d)) {
		double l=((r*r-s*s)/di+di)/2.0;
		double n=sqrt(r*r-l*l);
		pt e=c+(d-c)*l/di;
		pt p=(d-c)*n/di*pt(0,-1);
		res.push_back(e+p);
		res.push_back(e-p);
	}
	return res;
}

vector <double> cross_l_l(pt a, pt u, pt b, pt v) {
	vector <double> res;
	double det=imag(conj(u)*v);

	if (abs(det)>1e-7) {
		res.push_back(-imag(conj(v)*(b-a))/det);
		res.push_back(-imag(conj(u)*(b-a))/det);
	}
	return res;
}

class GCJ {
public:
	vector <double> solve(int N, int M, vector <int> Px, vector <int> Py, vector <int> Qx, vector <int> Qy) {
		vector <double> res;
		vector <pt> c;
		pt a, b, q;
		double da, db, dab, area, areaa, areab;
		
		a.real(Px[0]); a.imag(Py[0]);
		b.real(Px[1]); b.imag(Py[1]);
		for(int i=0; i<M; i++) {
			q.real(Qx[i]); q.imag(Qy[i]);
			da=abs(q-a); db=abs(q-b); dab=abs(a-b);
			//a円とb円の交点を求める
			c=cross_c_c(a, da, b, db);
			//扇形の面積を求める(1/2 θr^2)
			areaa=abs(arg((c[0]-a)/(c[1]-a))*da*da/2);
			areab=abs(arg((c[0]-b)/(c[1]-b))*db*db/2);
			//扇形から三角形の面積を引く
			areaa-=triangle_area_u(a, c[0], c[1]);
			areab-=triangle_area_u(b, c[0], c[1]);
			//c[0]c[1]直線とab直線の交点を求める
			//ab方向に負ならa円の面積から引く
			if(cross_l_l(a, b-a, c[0], c[1]-c[0])[0]<0) {
				areaa=M_PI*da*da-areaa;
			}
			//bも同様
			if(cross_l_l(b, a-b, c[0], c[1]-c[0])[0]<0) {
				areab=M_PI*db*db-areab;
			}
			area=areaa+areab;
			res.push_back(area);
		}

		return res;
	}
};

コーディング時の注意点1

| 00:17 | コーディング時の注意点1 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - コーディング時の注意点1 - SRM diary(Sigmar) コーディング時の注意点1 - SRM diary(Sigmar) のブックマークコメント

Google Code Jam 2010 Round2の反省点

  • コーディング前
    • 問題文が長い場合、注意点を書き出す
    • 解法が妙に複雑な場合はより簡単な別解がないか考えてみる
    • 計算量に問題ない限り、可読性、書きやすさを重視したデータ構造を利用する
  • コーディング中
    • if文はよく内容を確認する
    • 不必要に複雑なことをしようとしていないか確認する
  • コーディング後
    • 問題文の注意点は実行前に再確認する
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100606