C問題が解けるためには避けては通れない道っぽい....
2進数とか16進数とかすごい嫌いw
まずは理解できるまで下記を読みまくるのがいい気がする.
参考
lovedvoraklayout.hatenablog.com
ちなみに、ABC167のC問題の解説は非常にわかりやすいので必見。
Javaでのやり方
- まずbit単位でループさせる
for(int biti=0; biti<(1<<h); biti++) {
この部分は、下記のように書いてもいい. 行いたい回数分左にビットシフトさせるのは、2通りの組み合わせをいくつ行うのか、と同意になるため
要は、1<<hは2hと同意になります。
for(int biti=0; biti<Math.pow(2,h); biti++) {
対象部分を普通にループさせる
普通のループ文を書く.対象に対して動作させたいロジックを書く
if((biti&(1<<i)) == 1) // 処理
bitiはbit値（例えば4: 0100）とするので、i桁目をビットシフトしてフラグ(1)がたっているかどうか確認している。
iは基本的には10進数なので、普通にループさせているcntなどが当てはまる。
問題
C - H and V
赤色に塗った部分を1 = ビットが立っている、 何もしない部分を0 = ビットが立っていない
としてみる。それでビット探索で全ての組み合わせを模索する。
C - Many Formulas
+が入る位置は文字数-1となるので、その値までbit探索を行う。
tmp *= 10は、たとえば+が無い部分で1+2とかだった場合本来二桁目を10としないと桁数分の値を正しくとれない。
s.charAt(i) - '0';は指定された文字列から文字'0'(unicode=30)を差し引いてに数値に変換している。
例えば、1という数字の値を取得したければ、1はunicode31なので、31-30となり、1の値が取得できる。
import java.util.Scanner; public class Main1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); int n = s.length(); long ans = 0; for(int b=0; b<(1<<n-1); b++) { long tmp = 0; for(int i=0; i<n; i++) { tmp *= 10; tmp += s.charAt(i) - '0'; if((b >> i & 1) == 0) { ans += tmp; tmp = 0; } } ans += tmp; } System.out.println(ans); } }
C - Skill Up
買う/買わないの２つの選択肢のため、bit探索が使えるとイメージできれば成長かも。
Bit探索した後のロジックが複雑に見えるけどやってることはそんなに難しくない。
買う買わないの2つのパターンを与えられたn分の組み合わせを試すので2n通り試して、
ビットが立っている場合の価格をSumし、その場合のスキル習得値を足していく。
それらが全てx以上になっている場合、ansを更新する、という流れ。
int ans = Integer.MAX_VALUE; for(int i=0; i<(1<<n); i++) { int cost = 0; int[] skill = new int[m]; for(int j=0; j<n; j++) { if((i >> j & 1) == 1) { cost += price[j]; for(int k=0; k<m; k++) { skill[k] += c[j][k]; } } } boolean isQualified = true; for(int l=0; l<m; l++) { if(skill[l] < x) isQualified = false; } if(isQualified) ans = Math.min(ans, cost); } if(ans == Integer.MAX_VALUE) System.out.println("-1"); else System.out.println(ans);
