はじめに
AtCoder Beginner Contest 167
の
C問題(C-Skill Up)
の
解説動画を見てない。または見たが理解できたか心配という方向けの記事です。
私は動画の解説を見ましたが、整理するためにまとめてみました。
解説動画も非常にわかりやすい内容になっていますので、
そちらもぜひ参考にして下さい。
C問題は21:30〜42:00あたりです。解説動画はこちら。
1〜Nの数字の全ての組み合わせを試す方法の解説になります。
問題
問題文を要約すると、下記のようになるかと思います。
高橋くんが学びたいアルゴリズムがM個あって、
書店にはアルゴリズム の参考書がN個ある。
高橋くんには全ての参考書を買う予算があるが、
出来れば効率よく学び最小限どの出費で抑えたい。
どの順番で参考書を買って読むと費用が一番抑えられるか。
かかる費用の最小値を求めよ。
解き方
N冊ある参考書を購入する組み合わせ全てを試します
N冊ある参考書を購入する組み合わせは「1 << N」個あります。
<< はシフト演算です。 「1 << N」は１を左にN個シフト演算するという意味になります。
シフト演算は２進数で考えます。
＜２進数＞
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
例： 1 << 3
0001を左に３つシフトするという意味なので、
0001000となります。よって１０進数では「8」となります。
よって、N冊のNが「3」であれば、組み合わせは「８パターン」となります。
なぜそうなるか？
上の２進数の0〜7を見てください。
右から３桁に注目すると0〜7で全てのパターンが網羅されているのがわかると思います。
この各桁を各参考書を買うかどうかとして考えます。
例：参考書が３冊あった場合
000 ー＞１冊も買わないケース
001 ー＞１番目の参考書を買うが、２番目、３番目は買わないケース
010 ー＞2番目の参考書を買うが、1番目、３番目は買わないケース
011 ー＞1番目と２番目の参考書を買うが、3番目は買わないケース
100 ー＞3番目の参考書を買うが、1番目、2番目は買わないケース
101 ー＞1番目と3番目の参考書を買うが、2番目は買わないケース
110 ー＞2番目と3番目の参考書を買うが、1番目は買わないケース
111 ー＞全部買うケース
n=3の場合に８パターンループするソースコード
class Main {
public static void main(String[] args) {
int patternCount = 1 << 3;
System.out.printf("patternCount=%d\n", patternCount);
for (int i = 0; i < patternCount; i++) {
System.out.println(Integer.toBinaryString(i));
}
}
}
↑８パターンループするので、単に８回ループすればOKです。
0〜7を２進数で出力してみました。
patternCount=8
0
1
10
11
100
101
110
111
各パターンで買う本、買わない本をみていく
２進数で表現した場合の各桁が１かどうかで買う本、買わない本を見ていきます。
001であれば、１番目の参考書を買うが、２番目、３番目は買わないケース
110であれば、2番目と3番目の参考書を買うが、1番目は買わないケース
といった感じですよね。
つまり、
1番目の本を買う場合は、 右から数えて1番目の数字が1
2番目の本を買う場合は、 右から数えて2番目の数字が1
3番目の本を買う場合は、 右から数えて3番目の数字が1
ってことですね。
２進数で指定した桁の数字が1かどうかを調べるには「&」演算子を使います。
「&」演算子は、２進数の表現で各桁の数値が両方とも1だった場合にだけ１にします。
わかりやすく２進数で表現してみます。
1111 & 0001 -> 0001
1111 & 1001 -> 1001
1000 & 1001 -> 1000
このように左右の２進数の各桁を比較し両方とも1の場合だけその桁を1とする演算です。
これを利用し、
- 1番目の本を買ったかどうかを調べるには、 001 で & した結果が001かどうか調べる
- 2番目の本を買ったかどうかを調べるには、 010 で & した結果が010かどうか調べる
- 3番目の本を買ったかどうかを調べるには、 100 で & した結果が100かどうか調べる
となります。
class Main {
public static void main(String[] args) {
int n = 3;
System.out.printf("n=%d\n", n);
int patternCount = 1 << n;
System.out.printf("patternCount=%d\n", patternCount);
for (int i = 0; i < patternCount; i++) {
System.out.println(Integer.toBinaryString(i));
for (int j = 0; j < n; j++) {
if ( (i & 1<<j) == 1<<j) {
System.out.printf(" %d番目の参考書を買う\n", j + 1);
}
}
}
}
}
↑このように２進数の各桁が1かどうかを調べます。
出力結果は下記のようになります。
n=3
patternCount=8
0
1
1番目の参考書を買う
10
2番目の参考書を買う
11
1番目の参考書を買う
2番目の参考書を買う
100
3番目の参考書を買う
101
1番目の参考書を買う
3番目の参考書を買う
110
2番目の参考書を買う
3番目の参考書を買う
111
1番目の参考書を買う
2番目の参考書を買う
3番目の参考書を買う
購入費の最小値を探す
さて、これでこの問題を解く土台ができました。
全てのパターンを試して、購入費が一番小さくなるのを調べます。
下記のソースコードでC問題がACとなりました。
import java.util.*;
class Main {
final static int INF = 1001001001;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 入力データを変数に格納する
int n = sc.nextInt();
int m = sc.nextInt();
int x = sc.nextInt();
int[][] a = new int[12][12];
int[] c = new int[n];
for (int i = 0; i < n; i++) {
c[i] = sc.nextInt();
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
}
}
sc.close();
// 回答=コストの最小値なので最小値比較のために大きな数値で初期化しておく。
int ans = INF;
// 全ての組み合わせパターンをチェックする
for (int s = 0; s < 1<<n; s++) {
int cost = 0; // このs番目の組み合わせのコスト
int[] d = new int[m]; // このs番目の組み合わせでの各アルゴリズムの理解度
// ２進数で各ビットが1になっているかどうか調べる
for (int i = 0; i < n; i++) {
// 右からi番目のビットが1になっていれば、購入する参考書としてコストとアルゴリズムを加算する
if ( (s & 1<<i) == 1<<i) {
// コストを足す
cost += c[i];
// 各アルゴリズムの理解度に足す
for (int j = 0; j < m; j++) {
d[j] += a[i][j];
}
}
}
// 全てのアルゴリズムの理解度がxを超えているかチェックする
boolean ok = true;
for (int j = 0; j < m; j++) {
if (d[j] < x) ok = false; // １つでもx未満があれば。
}
// チェックOKであれば、そのコストが最小値を更新するかどうか。
if (ok) ans = Math.min(ans, cost);
}
// 全てのアルゴリズムの理解度がxを超えるパターンが１つもない場合はansがINFのままになってる
if (ans == INF) System.out.println(-1);
else System.out.println(ans);
}
}
おわりに
いかがでしたでしょうか？
1〜Nの数字の全ての組み合わせを試す
といった問題に出会ったときに、この解き方が使えるのではないかと思います。
おわり。