Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-08-27KISSの原則

KISSの原則

| 14:34 | KISSの原則 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - KISSの原則 - SRM diary(Sigmar) KISSの原則 - SRM diary(Sigmar) のブックマークコメント

KISSの原則といって、プログラムは単純であることが望ましいと言われるが、基本的に大賛成である。

確かに、コンテストにおいても工夫することでよりシンプルな考え方で解けるものや、考え方によってコーディングがシンプルになる問題がある。

特に、場合分けが多くコーナーケースでWAしそうな場合や、コーディングが大量・複雑になるような場合には、何かしら単純化を図ったほうがいいことが多いと思う。

しかしこれがなかなか難しくて、単純化する方法に容易には気づかないことが多い。

苦労して解いたあとに他人のコードを見て、こんな簡単にできたんだ、みたいに思うこともしばしばある。

ということで、過去に解いた問題を振り返りながら、どうすれば問題を単純化できるのか、色々考えてみたい。


とりあえずは分かりやすい例として、以下考え方によって解くのが楽になる問題の一例です。


Codeforces 78 Div1 A.Help Victoria the Wise

Problem Statement

6面のサイコロがある。1面につき1つgemを取り付けることができる。gemが6つ渡されるので、取り付け方が何通りあるか答えよ。

ただし、gemはまったく同一のものが複数渡される可能性があり、回転して同一になるつけ方は同じ取り付け方とみなす。

gemの種類は最大6種類。

gemの種類は6文字の文字列で与えられる。同じ文字は同一のgem。

例:入力=BOOOOB、解=2

制約:1問2秒以内


数学的に解けそうですが、これはプログラミングコンテストの問題であるというところが1つのポイントです。


以下、僕の考える解答例です。


場合分け解法

ある意味数学的に解くという方法。コンピュータの力(高速で正確な計算)を使わない。

プログラミングコンテストに慣れていない場合、この方法で解くことをまず考えるのではないでしょうか。

つまり、gemの種類と数についてあり得るパターンを全て列挙し、それらについて注意深く検討し、場合分けで解答をするという方法です。

この方法でももちろん解けますが、あり得るパターンの列挙及び各パターンの組み合わせ数を検討することは非常に難しいと思います。

おそらく検討には相当時間を要するだろうし、コーナーケースでWAを出す可能性が非常に高くなるでしょう。


探索による解法

サイコロの各面に0~5のindexをつけて、各indexに対応するgemを1文字で表すことで、6文字の文字列でgemのつけ方を表現します。

そして、gemの全ての取り付け方を探索するため、その文字列の全ての並べ方を列挙します。

さらに、各並べ方を回転させた場合に、これまでにその並べ方が登場していないか調べ、登場していない場合のみ解に加算します。

回転は文字列の要素の入れ替えで表現できるので、それほど難しいものではないです。

こちらの解答のほうが早く書けると思います。また、回転の方法さえ正しく書ければ、間違った解答を返すことはほぼないと思います。

もちろん、プログラムの実行時間はこちらのほうがはるかに遅いです。しかし、制約の2秒を超えることはありません。また、その代わりとして、コーディング時間の短縮化と正確性の向上が図れるのです。


以下のソースコードは僕が実際に本番で提出したものです。

変数名があまり実態を表してませんがご容赦ください。


int main() {
	//デバッグ用にfin,foutを定義しているがcin,coutをそのまま使用してOK
	istream &fin=cin;
	ostream &fout=cout;
	
	//回転その1。どの面を最初の要素に持ってくるかという考え方で回転する。
	int perm[6][6]={{0,1,2,3,4,5},{1,0,4,5,2,3},{2,0,1,5,3,4},{3,0,2,5,4,1},{4,0,3,5,1,2},{5,4,3,2,1,0}};
	//回転その2。最初の要素が表す面とその対面を軸として回転する。
	int rot[4][6]={{0,1,2,3,4,5},{0,2,3,4,1,5},{0,3,4,1,2,5},{0,4,1,2,3,5}};

	string s;
	fin >> s;

	sort(s.begin(), s.end());
	set <string> all;
	int res=0;
	do {
		bool ok=true;
		for(int i=0; i<6; i++) {
			string t=s;
			for(int j=0; j<6; j++) t[j]=s[perm[i][j]];
			for(int j=0; j<4; j++) {
				string t2=t;
				for(int k=0; k<6; k++) t2[k]=t[rot[j][k]];
				if(all.count(t2)) {
					ok=false;
					break;
				}
			}
			if(!ok) break;
		}
		if(ok) {
			res++;
			all.insert(s);
		}
	} while(next_permutation(s.begin(), s.end()));

	fout << res << endl;
	
}

自分で書いておいて何ですが、このコードは、改良の余地があると思います。

回転の種類を合計10種も書いていますが、実際は2種で十分だと思います。2種にすると、コーディング時間はもっと短くなりそう。


今回のポイントは、以下の点です。

  • なるべく場合分けしない。探索で解決できるなら探索する。

  コンピュータが得意な探索を使えば、難しく考える必要がなくなる場合があります。

  • 対称性のある図形の問題は、回転/反転等の操作を利用する。

  回転/反転等の操作を施すと、同じコードを使いまわせます。


以上ですがまた続きを書くかも

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110827