#AtCoder ABC 080 B&C
AtCoder - 080
2015/05/23
問題名追記・C問題のDFSでの解法追記
2015/05/23
C問題のDFS解法について別解追記（フラグの管理をint[]からbitに置き換えたもの）
#A - Parking
- $T$ 時間駐車した場合 $T*A$ 円
- 駐車した時間$T$にかかわらず $B$ 円
- どちらが安いか？
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の方が速いんじゃないか？
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$通り
####マスク用のコード
//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}$通り )ループ
- マスク用配列生成ループ
- 一つのお店の営業時間をマスク
- お店の営業時間とマッチする時間帯をカウント
- 利益が最大となるものを取得
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版
/**
* 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 まで 〜
- 基本的な動きはDFS版と同じ。どこの時間帯でopenするかのチェック方法を変更
-
new int[10]なんていらなかったんや・・・
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);
}