Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-09-02KISSの原則 その2

KISSの原則 その2

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

の続き。考え方をシンプルにすることで楽に解くための考察。


突然ですが、以下のような問題について、どう解くべきでしょうか?


SRM481 Div1 250 ChickenOracle

Problem Statement

卵が先か、鶏が先か?どちらが先に存在したのか、神様に聞くことにした。

ところが神様はこれまでn人に対してその回答をしたので、答えを教えてくれない。

しかも、n人のうちlieCount人に対しては嘘の回答をしたとのこと。

そのn人に尋ねたところ、eggCount人は卵が先だと言い、n-eggCount人は鶏が先だと言う。

しかし、n人のうちliarCount人は嘘を付いているらしい。

以上の状況で、真実が導き出せるだろうか?

この問題を解く以下の関数を書くこと。

string theTruth(int n, int eggCount, int lieCount, int liarCount);

真実が導き出せて、卵が先なら"The egg"、鶏が先なら"The chicken"を返せ。

両方の解があり得るなら、"Ambiguous"、両方あり得ないなら、"The oracle is a lie"を返せ。

制約条件は以下の通り。

1<=n<=1000000

0<=eggCount, lieCount, liarCount<=n


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


場合分け解法

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

前回と同じですが、この問題を場合分けで解くと、非常に難しいコーナーケースが発生します。

私はお勧めしません。


探索による解法

もし嘘を付いている人が一人もいなかったらどうでしょうか?

chickenCount:=n-eggCountとおくと、

当然、eggCount==lieCountなら答えは"The chicken"、chickenCount==lieCountなら"The egg"、それ以外なら"The oracle is a lie"となります。

ただし、eggCount==chickenCount==lieCountの場合のみ"Ambiguous"となります。

これは自明だと思います。

ここで、eggCountのうちi人が嘘を付いているとすると、chickenCountのうちliarCount-i人が嘘を付いていることになります。

iを決めてやると、嘘を付いている人の数だけeggCountを増減させてやれば良いです。

eggCount:=eggCount-i+(liarCount-i)

ただし、0<=i<=eggCount、0<=liarCount-i<=chickenCount

これが分かれば、探索で解けますね!!


ということで、以下ソースコード例です。


class ChickenOracle {
public:
	string theTruth(int n, int eggCount, int lieCount, int liarCount) {
		int chickenCount=n-eggCount;

		bool egg=false, chicken=false;
		for(int i=0; i<=eggCount; i++) {
			if(liarCount-i<0 || liarCount-i>chickenCount) continue;

			int neweggCount=eggCount-i+(liarCount-i);
			int newchickenCount=n-neweggCount;

			if(neweggCount==lieCount) chicken=true;
			if(newchickenCount==lieCount) egg=true;
		}

		string res;
		if(egg&&chicken) res="Ambiguous";
		else if(egg&&!chicken) res="The egg";
		else if(!egg&&chicken) res="The chicken";
		else if(!egg&&!chicken) res="The oracle is a lie";

		return res;
	}
};

結局今回も言いたいことは、コンピュータ君の得意技である探索を利用しようということです。

意外と探索できなさそうでも探索で楽になることって多いし、僕は何をおいてもまず単純に探索できないか考えます。

単純化のための第一の方法は、とにかくまずは探索を考えてみることであると思います。

ただし、単に探索できそうでできないこともあるので、計算量の見極めは必要です!何が何でも探索ではないので!


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

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


続きがあるかも

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