ABC - 080- A&B&C

#AtCoder ABC 080 B&C
[AtCoder - 080](https://atcoder.jp/contests/abc080)

**2015/05/23**
　問題名追記・C問題のDFSでの解法追記
**2015/05/23**
　C問題のDFS解法について別解追記（フラグの管理をint[]からbitに置き換えたもの）

#A - Parking

 - $T$ 時間駐車した場合 $T*A$ 円
 - 駐車した時間$T$にかかわらず $B$ 円
 - どちらが安いか？

```java
	private void solveA() {
		Scanner scanner = null;
		int numN = 0;
		int numA = 0;
		int numB = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();
			numA = scanner.nextInt();
			numB = scanner.nextInt();

			System.out.println(Math.min(numA * numN, numB));

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

```

#B - Harshad Number

 - $X$の各桁の和を求める
 - $mod 各桁の和 = 0 $ かどうか判定

各桁の和をついつい再帰で求めている。whileの方が速いんじゃないか？

```java

	private void solveB() {
		Scanner scanner = null;
		int numN = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();

			int res = addAllDigit(numN);

			if (numN % res == 0) {
				System.out.println("Yes");
			} else {
				System.out.println("No");

			}

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private int addAllDigit(int num) {
		if (num < 10) {
			return num;
		}
		return addAllDigit(num / 10) + num % 10;
	}
```

#C - Shopping Street

###bitマスク利用版

 - $F_1 ・・・ F_n$ まで店がある
 - お店の営業時間は午前午後で10通り
 - 自分のお店の営業時間を $2^{10}$ 通りの中から選択して営業利益が最大になるものを探す

必要なものとして、

 - 自分の店の $2^{10}$ 通りの営業時間をどう表現するのか？

がある。

forで1023回回して都度bit配列を生成すれば、マスク用の配列を生成できる。
- 0000000000=どの時間帯でも営業していないはNGなので$1024-0$通り

####マスク用のコード

```java
		//0000000000から、1111111111までの配列を作成。2の剰余を入れていけば2進数に変換できる。
		for (int i = 1; i < 1024; i++) {
			int[] myShop = new int[10];
			int wkBit = i;
			for (int j = 0; j < 10; j++) {
				myShop[j] = wkBit % 2;
				wkBit /= 2;
			}
		}
```

####C問題解答の本体コード

 - 自分のお店の取りうる営業時間分( $ 2^{10}$通り )ループ
    - マスク用配列生成ループ
    - 一つのお店の営業時間をマスク
        - お店の営業時間とマッチする時間帯をカウント
    - 利益が最大となるものを取得


```java
	private void solveC() {
		Scanner scanner = null;
		int numN = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();

			int[][] shop = new int[numN][10];
			int[][] rieki = new int[numN][11];

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 10; k++) {
					shop[j][k] = scanner.nextInt();
				}
			}

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 11; k++) {
					rieki[j][k] = scanner.nextInt();
				}
			}
			int res = Integer.MIN_VALUE;
			//0000000000=0、1111111111=1023
			for (int i = 1; i < 1024; i++) {
				int wkRes = 0;
				int[] myShop = new int[10];
				int wkBit = i;
				//0000000000から、1111111111までの配列を作成。2の剰余を入れていけば2進数に変換できる。
				for (int j = 0; j < 10; j++) {
					myShop[j] = wkBit % 2;
					wkBit /= 2;
				}
				for (int j = 0; j < shop.length; j++) {
					int cnt = 0;
					for (int k = 0; k < myShop.length; k++) {
						if (myShop[k] == shop[j][k] && myShop[k] == 1) {
							cnt++;
						}
					}
					wkRes += rieki[j][cnt];
				}
				res = Math.max(res, wkRes);
			}

			System.out.println(res);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}
```

###DFS版

```java

	/**
	 * DFS
	 */
	private void solveC3() {

		try (Scanner scanner = new Scanner(System.in)) {

			int numN = scanner.nextInt();

			int[][] shop = new int[numN][10];
			int[][] rieki = new int[numN][11];

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 10; k++) {
					shop[j][k] = scanner.nextInt();
				}
			}

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 11; k++) {
					rieki[j][k] = scanner.nextInt();
				}
			}
			/*
			 * DFSで調べる
			 * new int[10] => joisinoお姉ちゃんがopenする時間帯のmemo
			 */
			int res = recursiveC(shop, rieki, new int[10], 0, numN);

			System.out.println(res);

		}
	}

	private int recursiveC(int[][] shop, int[][] rieki, int[] joisinoShop, int currentI, int shopNum) {

		/*
		 * お店のopen時間は10種類
		 * currentI>=10になったので、joisinoShopを埋め終わりOpenする時間帯を決定した。
		 * 利益計算
		 */
		if (currentI >= 10) {
			int res = 0;
			for (int j = 0; j < shop.length; j++) {
				int cnt = 0;
				boolean isOpen = false;
				for (int k = 0; k < 10; k++) {
					if (shop[j][k] == 1 && joisinoShop[k] == 1) {
						cnt++;
					}
					//どこかの時間帯でopenしているのであればopenフラグON
					if (joisinoShop[k] == 1 && !isOpen) {
						isOpen = true;
					}
				}
				/*
				 * 何処もopenしないのはNG
				 * 利益を最低にする
				 */
				if (!isOpen) {
					return Integer.MIN_VALUE;
				}
				res += rieki[j][cnt];
			}
			return res;
		}
		//currentIの時間帯にopenしなかった場合のコスト
		int val1 = recursiveC(shop, rieki, joisinoShop, currentI + 1, shopNum);
		//currentIの時間帯のopenした場合のコスト
		joisinoShop[currentI] = 1;
		int val2 = recursiveC(shop, rieki, joisinoShop, currentI + 1, shopNum);
		//次の探索用にopenフラグを落とす
		joisinoShop[currentI] = 0;
		return Integer.max(val1, val2);

	}
```

###DFS+フラグ管理をbitで行う

参考：
[ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜](https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361)

 - 基本的な動きはDFS版と同じ。どこの時間帯でopenするかのチェック方法を変更
 - ```new int[10]``` なんていらなかったんや・・・

```java
	private void solveC3() {

		try (Scanner scanner = new Scanner(System.in)) {

			int numN = scanner.nextInt();

			int[][] shop = new int[numN][10];
			int[][] rieki = new int[numN][11];

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 10; k++) {
					shop[j][k] = scanner.nextInt();
				}
			}

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 11; k++) {
					rieki[j][k] = scanner.nextInt();
				}
			}
			/*
			 * DFSで調べる
			 * joisinoShop => joisinoお姉ちゃんがopenする時間帯をmemoするmemo用
			 */
			int res = recursiveCNotUseArray(shop, rieki, 0, 0, numN);

			System.out.println(res);

		}
	}

	private int recursiveCNotUseArray(int[][] shop, int[][] rieki, int joisinoShop, int currentI, int shopNum) {

		/*
		 * お店のopen時間は10種類
		 * currentI>=10になったので、joisinoShopを埋め終わりOpenする時間帯を決定した。
		 * 利益計算
		 */
		if (currentI >= 10) {
			/*
			 * 何処もopenしないのはNG
			 * 利益を最低にする
			 */
			if (joisinoShop == 0) {
				return Integer.MIN_VALUE;
			}
			//どこかの時間帯でopenしているのであれば計算
			int res = 0;
			for (int j = 0; j < shop.length; j++) {
				int cnt = 0;
				for (int k = 0; k < 10; k++) {
					if (shop[j][k] == 1 && (joisinoShop & (1 << k)) > 0) {
						cnt++;
					}
				}
				res += rieki[j][cnt];
			}
			return res;
		}
		//currentIの時間帯にopenしなかった場合のコスト
		int val1 = recursiveCNotUseArray(shop, rieki, joisinoShop, currentI + 1, shopNum);
		//currentIの時間帯にopenした場合のコスト
		joisinoShop = joisinoShop | (1 << currentI);
		int val2 = recursiveCNotUseArray(shop, rieki, joisinoShop, currentI + 1, shopNum);
		//次の探索用にopenフラグを落とす
		joisinoShop = joisinoShop ^ (1 << currentI);
		return Integer.max(val1, val2);

	}
```