AtCoder ABC 128 A&B&C&D
近いうちにE&Fを解きに戻ってくる。
A - Apple Pie
private void solveA() {
out.println((nextInt() * 3 + nextInt()) / 2);
}
B - Guidebook
- 文字列の[][]で保持して、[][0]で文字順にソートして、[][0]が同じだったら[][1]を数値に変換して降順にソート
private void solveB() {
int n = nextInt();
String[][] s = new String[n][3];
for (int i = 0; i < n; i++) {
s[i][0] = next();
s[i][1] = next();
s[i][2] = Integer.toString(i + 1);
}
Arrays.sort(s,
(x, y) -> {
if (x[0].compareTo(y[0]) < 0) {
return -1;
} else if (x[0].compareTo(y[0]) > 0) {
return 1;
} else {
return -Integer.compare(Integer.parseInt(x[1]), Integer.parseInt(y[1]));
}
});
for (int i = 0; i < s.length; i++) {
out.println(s[i][2]);
}
}
C - Switches
-
段々書けるようになってきたbit使った全探索
-
スイッチは1-5、スイッチがONになっていないといけない個数 \ スイッチ番号
| 電球番号\スイッチ番号 | 1 | 2 | 3 | 4 | 5 | ||
|---|---|---|---|---|---|---|---|
| 1 | 0 | 〇 | 〇 | 〇 | |||
| 2 | 1 | 〇 | 〇 |
- 電球番号1は、使えるスイッチは1,2,5で、1,2,5の内偶数個（この例だと2つ）がONになっている必要がある
- 1,2,5全部がONになっているのはNGで、3,4のON/OFFは関係がない
- 電球番号2は、使えるスイッチは2,3で、2,3の内奇数個（この例だと1つ）がONになっている必要がある
- 2,3両方がONになっているのはNGで、1,4,5のON/OFFは関係がない
ということで、$2^{スイッチの数}$だけ選択肢があるということになる
具体的には以下のようなパターン($2^{スイッチの数}$個)を試す
出力例3を例にとると
| パターン\スイッチ | 1 | 2 | 3 | 4 | 5 | ||
|---|---|---|---|---|---|---|---|
| 1 | 〇 | スイッチ1をON 電球1も2もOFF |
|||||
| 2 | 〇 | 〇 | スイッチ1,2をON 電球1も2もON |
||||
| 3 | 〇 | 〇 | 〇 | スイッチ1,2,3をON 電球1がON。電球2はOFF |
|||
| xxx | 〇 | 〇 | スイッチ1,5をON 電球1がON。電球2はOFF |
private void solveC() {
int n = nextInt();
int m = nextInt();
int[] k = new int[m];
List<List<Integer>> s = new ArrayList<List<Integer>>();
for (int i = 0; i < k.length; i++) {
k[i] = nextInt();
List<Integer> temp = new ArrayList<Integer>();
for (int j = 0; j < k[i]; j++) {
temp.add(nextInt());
}
s.add(temp);
}
int[] p = IntStream.range(0, m).map(i -> nextInt()).toArray();
long res = 0;
for (int i = 0; i < 1 << n; i++) {
boolean isResult = true;
for (int j = 0; j < m; j++) {
//電球jのボタンリストを取得
List<Integer> sList = s.get(j);
//電球jがONになっていないといけないのは偶数か奇数か
int compareBase = p[j];
//電球jを点灯するのに必要なボタンのうち、何個ONになっているのか
int compare = 0;
for (Integer buttonNum : sList) {
/*
* 電球jのボタンリストの内、ONになっているボタンを探す
* buttonNum - 1 -> ボタン番号(配列に合わせて-1)
* (i & (1 << (buttonNum - 1)) -> ボタン番号の位置にフラグが立っているか？
*/
if ((i & (1 << (buttonNum - 1))) >= 1) {
compare++;
}
}
//ボタンがONになっていた個数の偶奇を判定し、電球jの必要条件を満たしているのか判定
if (compareBase != compare % 2) {
isResult = false;
break;
}
}
if (isResult) {
//このパターンは全部の電球がONになった
res++;
}
}
out.println(res);
}
D - equeue
- 以下の4操作を行う
- 1:左からとる
- 2:右からとる
- 3:手持ちを捨てて左につける
- 4:手持ちを捨てて右につける
- 3,4は操作の最後で一気に行えばよい（要らないものを最後に捨てるという発想）ので以下の操作を全たパターン行う
- 左から、$0-max(n,K)$回とる
- 右から、$0-min(n,(k-lからとった回))$回とる
- $(k-lからとった回-rからとった回)$分、手持ちから左または右につける
- 捨てる操作なので左でも右でもどちらでもよい。捨てた後とることをしないので
- また、0より小さいものは捨てる価値がある（捨てることによって手持ちの価値が上がる）が、0以上は捨てると手持ちの価値が減るので捨てる必要がない
private void solveD() {
int n = nextInt();
int k = nextInt();
long[] wk = new long[n];
for (int i = 0; i < n; i++) {
wk[i] = nextInt();
}
long res = 0;
//左からとれるだけ取る
for (int l = 0; l <= k; l++) {
//右からとれるだけ取る
for (int r = 0; r <= k; r++) {
//操作回数がkを超えるならbreak
if (l + r > k) {
break;
}
//現時点の手持ちの合計
long now = 0;
List<Long> s = new ArrayList<Long>();
int pickCount = 0;
//左側から取得した分だけ足す
for (int i = 0; i < Integer.min(l, n); i++) {
long tmp = wk[i];
now += tmp;
s.add(tmp);
pickCount++;
}
/*
* 右側から取得した分だけ足す
* 右側のmaxをいじっているのは、
* - 操作回数（K）がNより大きい場合があるため
* - 左側から取っていた場合と、右側からとっていった場合で2回ループしているが
* KがNより大きいと同じものをとってしまう場合がある
* そたのめ、本来のrのmax取得数とlで取得した数を比較している。
* e.g.K>=Nの場合、lのInteger.min(l, n)でnが返ってきている。
*/
for (int i = n - 1; i > Integer.max(n - 1 - r, Integer.min(l, n)); i--) {
long tmp = wk[i];
now += tmp;
s.add(tmp);
pickCount++;
}
//余計なものを捨てるために、要らない順に並べる
Collections.sort(s);
//余分な取得物を捨てることができる回数
int d = k - pickCount;
//この回数以上は捨てられないのでbreak
for (int i = 0; i < Integer.min(d, s.size()); i++) {
//
//取り出した宝石の価値が負の値でないなら捨てる必要がない
if (s.get(i) > 0) {
break;
}
//負の価値の宝石は捨てる
now -= s.get(i);
}
res = Long.max(res, now);
}
}
out.println(res);
}