Google DevQuiz 回答アップ「一人ゲーム編」

Google Devquiz

回答をアップしていきますよ。
まずは一人ゲームから。

一人ゲームのルールは以下のとおりです。
■ルール

数がいくつか与えられます。なるべく少ない手数で数を全て取り除いてください。
あなたは 1 手で、

  • 全ての数を半分にする（端数は切り捨て）
  • 5 の倍数 (0 を含む) を全て取り除く

のどちらかの操作をすることができます。

例えば、以下の数字が与えられた場合：
10 21

回答は
2
となります。
このテストケースでは、まず全ての数を半分にします (10, 21 → 5, 10) 。次に、5 の倍数を全て取り除きます。これで 2 手で全ての数を取り除けます。

0 9 9
の場合は5となります。

このテストケースでは、全ての数を半分にする操作を 4 回行います。
0, 9, 9 → 0, 4, 4 → 0, 2, 2 → 0, 1, 1 → 0, 0, 0
その後、5 の倍数を全て取り除きます。これで 5 手で全ての数を取り除けます。

というわけで、一人ゲームの説明終わりです。
この数字が100個与えられるので、それの最適解を答えよ、という問題ですね。

自分の解法は幅優先探索による総当たり法です。
色々とパターンがあるかと思い、探ってみたのですが、1時間くらい悩んだところで、
総当たりで解いちゃえーって感じで。
言語はJavaを使いました。

package game;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 幅優先探索を使ってGoogle Devquizの一人ゲームを解く。
 * @author yosuke
 *
 */
public class GameByMySelf {
	private int DIV_OP = 0;
	private int MOD_OP = 1;
	private int testcaseNumber = 0;
	private int numofnum = 0;
	private int count = 0;
	
	/**
	 * 幅優先探索的に、全パターンを作りながら力づくで処理する方法。
	 * 
	 * @param integers 数列のリスト
	 * @return 最短で削除する数
	 */
	public void breadthFirstSearch(List<List<Integer>> list) {
		count++;
		List<List<Integer>> newList = new ArrayList<List<Integer>>();
		for (List<Integer> tempList : list) {
			for (int operation = 0 ; operation < 2; operation++) {
				//2で割る -> DIV_OP, mod5を使って削除する -> MOD_OP
				if (operation == DIV_OP) {
					//すべての配列の値を2で割り、値をnewList似格納する
					//すべての配列の値が0なら、2で割る意味が無いので評価しない。
					if (!isAllZero(tempList)) {
						newList.add(allDiv(tempList));
					}
				} else if (operation == MOD_OP) {
					//mod5を利用して、値を削除する。
					//mod5を利用してもひとつも削除できない場合は評価しない。
					if (containsMod5(tempList)) {
						newList.add(allMod(tempList));
					}
				}
			}
			//空配列を見つけたら、終了。
			for (List<Integer> intList : newList) {
				if (intList.isEmpty()) {
					return;
				}
			}
		}
		breadthFirstSearch(newList);
	}
	
	private void clearCount() {
		count = 0;
	}
	
	public int getCount() {
		return count;
	}
	
	/**
	 * すべての値が0ならtrue, 一つでも0じゃなければfalse
	 * @param integers
	 * @return
	 */
	private boolean isAllZero(List<Integer> integers) {
		for (Integer num : integers) {
			if (num != 0) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 * ひとつでもmod5で削除できればtrue,削除できない場合はfalse
	 * @param integers
	 * @return
	 */
	private boolean containsMod5(List<Integer> integers) {
		for (Integer num : integers) {
			if (num % 5 == 0) {
				return true;
			}
		}
		return false;
	}
	
	/**
	 * すべて2で割る
	 * @param integers
	 * @return
	 */
	private List<Integer> allDiv(List<Integer> integers) {
		List<Integer> result = new ArrayList<Integer>();
		for (Integer num : integers) {
			result.add(num/2);
		} 
		return result;
	}
	
	/**
	 * すべて5で割って余り0のものを削除する
	 * @param integers
	 * @return
	 */
	private List<Integer> allMod(List<Integer> integers) {
		List<Integer> result = new ArrayList<Integer>();
		for (int i=0; i<integers.size(); i++) {
			if (integers.get(i) % 5 != 0) {
				result.add(integers.get(i));
			}
		}
		return result;
	}
	
	/**
	 * inputFileをリードして、処理を実行し、回数をoutputFileに書きこむ。
	 * @param inputFile
	 * @param outputFile
	 * @throws IOException
	 */
	private void loadFile(File inputFile, File outputFile) throws IOException {
		BufferedReader br = null;
		BufferedWriter bw = null;
		try {
			br = new BufferedReader(new FileReader(inputFile));
			bw = new BufferedWriter(new FileWriter(outputFile));
			String line;
			int lineNum = 0;
			while((line = br.readLine()) != null) {
				if (lineNum == 0) {
					testcaseNumber = Integer.parseInt(line);
				} else if (lineNum%2 == 1) {
					numofnum = Integer.parseInt(line);
				} else {
					StringTokenizer st = new StringTokenizer(line);
					List<List<Integer>> list = new ArrayList<List<Integer>>();
					List<Integer> intList = new ArrayList<Integer>();
					while (st.hasMoreTokens()) {
						intList.add(Integer.parseInt(st.nextToken()));
					}
					assert intList.size() == numofnum;
					list.add(intList);
					breadthFirstSearch(list);
					bw.write(getCount() + "\n");
					clearCount();
				}
				lineNum++;
			}
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			if (br != null) {
				br.close();
			}
			if (bw != null) {
				bw.close();
			}
		}
	}
	
	public static void main(String[] args) {
		GameByMySelf main = new GameByMySelf();
		try {
			main.loadFile(new File(args[0]), new File(args[1]));
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

工夫という程でもないですが、一応幅が広がり過ぎないように意味が無いパターン
(2で割っても数が減らない、mod5をしても削除できない場合)は枝を伸ばさないように
しています。

詳細はGitHubに上がっています。
gdd11jp/gamebymyself at master · yosuke-furukawa/gdd11jp · GitHub