プログラミングコンテストの問題解いてみた

野球選手が素振をするように。

マラソン選手がランニングをするように。

ボディービルダーが筋トレをするように。

そう、われわれプログラマーは定期的にプログラミングコンテストの問題を解いて、常に能力の向上に勤しむべきだ。

山崎屋

今日はちょっと古い記事ですが、プログラミングコンテスト界隈で有名な AtCoder 社の代表でもある wikipedia:高橋直大さんの記事に紹介されていた問題を解いたので、その考え方を紹介したいと思います。

記事中には答えが書かれておらず、ググっても正解が見つからないので、間違えているかもしれません。ご注意ください。

ちなみに私の実力は AtCoder だったら初心者レベルです。

問題

次のような問題が紹介されています。

人間が1人、モンスターがM匹、ウサギがB匹います。ここから、モンスターか人間がいなくなるまで無作為に2匹（もしくは1人と1匹）を選び出し、以下の行動を繰り返します。

モンスターとモンスターが選ばれると、両方のモンスターが死にます

モンスターとモンスター以外が選ばれると、モンスター以外が殺されてしまいます

ウサギとウサギが選ばれると、何も起こりません

ウサギと人間が選ばれると、人間の生存確率が最も高くなるように、ウサギを殺す、またはそのままにする、のどちらかの選択をします

モンスターの数Mとウサギの数Bが与えられたときに、最後に人間が生き残る確率を答えなさい。ただし、M、Bともに1000以下の整数とする。

http://www.itmedia.co.jp/enterprise/articles/0910/10/news003.html

うん。どうやって解けばいいのか検討もつきませんねｗ。

高橋直大さんによると 2 ステップだそうですｗ。

まず考えたこと

とりあえずなにか取っ掛かりでもつかめればと思って次のようなことを考えました。

人間、モンスター、モンスターが残っている場合、生き残る確率は 3 分の 1
人間とウサギが選ばれた場合、「そのままにする」とメリットになるシチュエーションが思い浮かばない
モンスターが奇数のときって確実に死ぬ

ここまでで分かっている生き残る確率を以下の表にまとめました。
縦の見出しがモンスターの数。横の見出しがウサギの数です。

	0	1	2	3	4	5	6
0	1	1	1	1	1	1	1
1	0	0	0	0	0	0	0
2	1/3	?	?	?	?	?	?
3	0	0	0	0	0	0	0
4	?	?	?	?	?	?	?
5	0	0	0	0	0	0	0
6	?	?	?	?	?	?	?

( 0 が生き残る確率 0 %、1 が 100 %)

さて次は・・・

はやくもここで行き詰った・・・

シュミレーションプログラムを作った

実際に問題に記載のとおりの処理をするプログラムを作りました。

実際には標準入力で受け取るモンスターとウサギの数ですが、シンプルにするため、変数にハードコーディングしてしまいます。

package org.yyama;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.IntStream;

class Main {
	enum CREATURE {
		HUMAN, // 人間
		RABBIT, // ウサギ
		MONSTER, // モンスター
	}

	public static void main(String[] args) throws Exception {
		Main tMain = new Main();
		tMain.proc();
	}

	final int M = 2; // モンスターの数 （ これをいろいろ変えて試す ）
	final int B = 1; // ウサギの数 （ これをいろいろ変えて試す ）

	float numSurvive = 0; // 生き残った回数
	float numDead = 0; // 死んだ回数

	final int NUM_TRAIAL = 10000; // 試す回数

	private void proc() {
		for (int i = 0; i < NUM_TRAIAL; i++) {
			if (isSurvive()) {
				numSurvive++;
			} else {
				numDead++;
			}
		}
		System.out.println("試した回数:" + (numSurvive + numDead));
		System.out.println("生き残った回数:" + numSurvive);
		System.out.println("生き残った確率:" + (numSurvive / (numSurvive + numDead)));
	}

	private boolean isSurvive() {
		// 準備 ( リストに保存 )
		List<CREATURE> list = new ArrayList<>();
		list.add(CREATURE.HUMAN);
		IntStream.range(0, M).forEach(i -> list.add(CREATURE.MONSTER));
		IntStream.range(0, B).forEach(i -> list.add(CREATURE.RABBIT));
		Random r = new Random();

		// 人間かモンスターがいなくなるまで繰り返し
		while (list.contains(CREATURE.HUMAN) && list.contains(CREATURE.MONSTER)) {
			// 無作為に2個抽出
			int pos1 = r.nextInt(list.size());
			int pos2 = -1;
			while (pos2 < 0 || pos1 == pos2) {
				pos2 = r.nextInt(list.size());
			}
			if (list.get(pos1) == CREATURE.MONSTER && list.get(pos2) == CREATURE.MONSTER) {
				// モンスターとモンスター
				// 両方とも死ぬ
				list.remove(Math.max(pos1, pos2));
				list.remove(Math.min(pos1, pos2));
			} else if (list.get(pos1) == CREATURE.MONSTER) {
				// 片方モンスター
				// もう片方が死ぬ
				list.remove(pos2);
			} else if (list.get(pos2) == CREATURE.MONSTER) {
				// 片方モンスター
				// もう片方が死ぬ
				list.remove(pos1);
			} else if (list.get(pos1) == CREATURE.HUMAN) {
				// 人間とウサギ
				// ウサギが死ぬ（死なないパターンも試す必要あり）
				list.remove(pos2);
			} else if (list.get(pos2) == CREATURE.HUMAN) {
				// 人間とウサギ
				// ウサギが死ぬ（死なないパターンも試す必要あり）
				list.remove(pos1);
			} else {
				// ウサギとウサギ
				// 何もしない
			}
		}
		if (list.contains(CREATURE.HUMAN)) {
			return true;
		} else {
			return false;
		}

	}
}

いろいろ試して、次のことがわかりました。

人間 1 人、モンスター 2 引きの場合の想定（1/3で生き残れる）は正しかった
ウサギの数は人間が生き残る確率に関係ない。（本当は証明したい）
人間とウサギが選ばれた場合、ウサギを殺しても殺さなくても人間が生き残る確率に関係ない。（本当はCry）

ということで、ウサギの数は考えなくていいことになりました。
先ほどの表から、ウサギの列を 0 固定にしてシンプルにします。

	0
0	1
1	0
2	1/3
3	0
4	?
5	0
6	?

( 0 が生き残る確率 0 %、1 が 100 %)

モンスター 4 匹と人間 1 人の場合を考える

モンスター 3 匹のときは確実に生き残れないので、次にモンスター 4 匹の場合を考えます。

全員で 5 体の生物がいて、2 体を無作為に選ぶとき、以下 10 の組み合わせがあります。

人間、モンスター１
人間、モンスター2
人間、モンスター3
人間、モンスター4
モンスター1、モンスター2
モンスター1、モンスター3
モンスター1、モンスター4
モンスター2、モンスター3
モンスター2、モンスター4
モンスター3、モンスター4

1 ～ 4 の場合は死にます。つまり、10 分の 4 は生き残れません。

残りの 6 ケースの場合を考えます。

いずれも、モンスターが 2 匹減るので、モンスター 2 匹と人間 1 人が残ります。

これはすでに 3 分の 1 で生き残れることが分かっています。

なので、10 分の 6 掛ける 3 分の 1 が生き残れる可能性ですね。計算すると 5 分の 1 です。

先ほどのシュミレーション用のプログラムで検証すると合っているようでした。

表を更新しました。

	0
0	1
1	0
2	1/3
3	0
4	1/5
5	0
6	?

( 0 が生き残る確率 0 %、1 が 100 %)

モンスター 6 匹と人間 1 人の場合を考える

7 体の中から 2 体を抽出する場合の組み合わせの数は 21 。

その内、人間とモンスターが選ばれてしまうの場合の数は 6。

残りの 15 ケースはモンスターが 2 体減るので生き残る可能性は 5 分の 1（モンスターが4匹の場合の生き残れる確率と同じ）。

よって、モンスターが 6 匹の場合に、人間が生き残れる確率は 21 分の 15 掛ける 5 分の 1 で 7 分の 1。

シュミレーションプログラムでもその通りになりました。

表を更新します。

	0
0	1
1	0
2	1/3
3	0
4	1/5
5	0
6	1/7

( 0 が生き残る確率 0 %、1 が 100 %)

分かったかも

（モンスターの数 + 1）分の 1 が人間が生き残れる確率じゃないですかね？
（ただしモンスターの数は偶数）

100 匹のモンスターで考えて見ます。

先ほど導いた式に当てはめると

（ 100 + 1 ）分の 1、計算機で計算すると 0.00990099・・・となります。

シュミレーションプログラムでもそのあたりの数値になります。

これで大丈夫そうです。

正解（と思われる）プログラム

というわけで正解と思われるコードはこちらです。

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt(); // モンスターの数

		float f = M % 2 == 0 ? 1f / (M + 1) : 0;
		System.out.println(f);
	}
}

本質的なコードは本当に以下の2行ですｗ

		float f = M % 2 == 0 ? 1f / (M + 1) : 0;
		System.out.println(f);

最後に

AtCoder のコンテストにもチャレンジしたいです。

まだ、正解にたどり着くまでの時間がかかりすぎるので、もっとたくさんの問題を解く必要があります。

さっそく AIZU ONLINE JUDGE: Programming Challenge で練習してきます！

それでは。

これ持ってます。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ
発売日: 2012/01/28
メディア: 単行本（ソフトカバー）
購入: 25人クリック: 473回
この商品を含むブログ (36件) を見る

直大さんの本はこちら。

最強最速アルゴリズマー養成講座プログラミングコンテストTopCoder攻略ガイド

作者: 高橋直大
出版社/メーカー: SBクリエイティブ
発売日: 2012/09/27
メディア: 単行本
購入: 9人クリック: 319回
この商品を含むブログ (8件) を見る

	0	1	2	3	4	5	6
0	1	1	1	1	1	1	1
1	0	0	0	0	0	0	0
2	1/3	?	?	?	?	?	?
3	0	0	0	0	0	0	0
4	?	?	?	?	?	?	?
5	0	0	0	0	0	0	0
6	?	?	?	?	?	?	?

	0	1	2	3	4	5	6
0	1	1	1	1	1	1	1
1	0	0	0	0	0	0	0
2	1/3	?	?	?	?	?	?
3	0	0	0	0	0	0	0
4	?	?	?	?	?	?	?
5	0	0	0	0	0	0	0
6	?	?	?	?	?	?	?

	0	1	2	3	4	5	6
0	1	1	1	1	1	1	1
1	0	0	0	0	0	0	0
2	1/3	?	?	?	?	?	?
3	0	0	0	0	0	0	0
4	?	?	?	?	?	?	?
5	0	0	0	0	0	0	0
6	?	?	?	?	?	?	?