AtCoder ABC 124 A&B&C&D
2019/05/22
問題名を追記
A - Buttons
- 大きい方をカウントする
- 大きい方は-1される
- 上記を2回
private void solveA() {
int numA = nextInt();
int numB = nextInt();
int cnt = 0;
for (int i = 0; i < 2; i++) {
if (numA > numB) {
cnt += numA;
numA--;
} else {
cnt += numB;
numB--;
}
}
out.println(cnt);
}
- よりも、、、以下のソースの方がわかりやすい。
- パターンは3パターンしかないので列挙すれだけ
ans = max(ans, A + A - 1);
ans = max(ans, A + B);
ans = max(ans, B + B - 1);
B - Great Ocean View
海を見ることが出来るのは赤い位置のみ
- 今見ている山が、今までに出現した一番高い山より高いなら海が見える
private void solveB() {
int numN = nextInt();
int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
int cnt = 1;
int baseHeight = wk[0];
for (int i = 1; i < wk.length; i++) {
if (baseHeight <= wk[i]) {
cnt++;
}
baseHeight = Math.max(baseHeight, wk[i]);
}
out.println(cnt);
}
C - Coloring Colorfully
並び替えるパターンは2つしかない
- 黒白黒白黒白黒白
- 白黒白黒白黒白黒
どちらのパターンが並び替えるときに一番手数が少ないかを比較する
private void solveC() {
String[] wk = next().split("");
int bC = 0;//奇数を白から黒くする
int wC = 0;//奇数を黒から白くする
int bC2 = 0;//偶数を白から黒くする
int wC2 = 0;//偶数を黒から白くする
for (int i = 0; i < wk.length; i++) {
if (i % 2 != 0) {
if (wk[i].equals("0")) {
//奇数を白くするときの回数
wC++;
} else {
//奇数を黒くするときの回数
bC++;
}
} else {
if (wk[i].equals("0")) {
//偶数を白くするときの回数
wC2++;
} else {
//偶数を黒くするときの回数
bC2++;
}
}
}
int val1 = bC + wC2;
int val2 = bC2 + wC;
out.println(Math.min(val1, val2));
}
D問題:複数の解法を記載
-
解説のyoutubeを見るのが一番わかりやすい
-
解説を基にした内容をコードにインラインで記述
-
どの解法も以下の作業を前提にしている
- 1(2個)-0(1個)-1(1個)-0(..個)-1(..個) という1が何個続いて、0が何個続いて...という形に変換するところは共通
- 上記の様な配列を生成し、その後どうやってカウントするのか？で分かれる
D - Handstand:全探索
/*
* 実行時間が長い版
*/
private void solveD3() {
int numN = nextInt();
int numK = nextInt();
String[] wk = next().split("");
List<Integer> oneZeroList = new ArrayList<Integer>();
//今見ている数
int now = 1;
//いくつこの数が続いているのか
int cnt = 0;
/*
* 1-0-1-0-1
*/
for (int i = 0; i < wk.length; i++) {
/*
* iが0か1かを判定している
* wk[i].charAt(0) == (char) ('0' + now)
*/
if (wk[i].charAt(0) == (char) ('0' + now)) {
cnt++;
} else {
oneZeroList.add(cnt);
cnt = 1;
/*
* 0と1を切り替えるテクニック
* now ^=1でのおｋ
*/
now = 1 - now;
}
}
/*
* 0のまま、または、1のまま終わった場合の処理
*/
if (cnt != 0) {
oneZeroList.add(cnt);
}
/*
* 1-0-1-0-1-0-1の配列が欲しい
* 1-0-1-0-1-0 で終わっていたら1を足す
*/
if (oneZeroList.size() % 2 == 0) {
oneZeroList.add(0);
}
//ここより上は全処理共通------------------------------------------------
int countRange = 2 * numK + 1;
int res = 0;
/*
* 1-0-1-0-1....と詰まっているのを数え上げていく
* なので、奇数番しか使わない
*
* テストケース1の
* 14 2
* 11101010110011
* を例に取ると、1,0の配列は以下になる。
* 3 1 1 1 1 1 2 2 2
* 1 0 1 0 1 0 1 0 1
* 上記の様な1-0リストを以下の様にループしてカウントする
* 3+1+1+1+1
* 1+1+1+1+2
* 1+1+2+2+2
*/
for (int i = 0; i < oneZeroList.size(); i += 2) {
int temp = 0;
int left = i;
int right = Math.min(i + countRange, oneZeroList.size());
/*
* 選択位置から、countRange内の個数を数える
*/
for (int j = left; j < right; j++) {
temp += oneZeroList.get(j);
}
res = Math.max(res, temp);
}
out.println(res);
}
D - Handstand:累積和
/*
* 実行時間が短い版
* 累積和
*/
private void solveD() {
int numN = nextInt();
int numK = nextInt();
String[] wk = next().split("");
List<Integer> oneZeroList = new ArrayList<Integer>();
int now = 1;
int cnt = 0;
for (int i = 0; i < wk.length; i++) {
if (wk[i].charAt(0) == (char) ('0' + now)) {
cnt++;
} else {
oneZeroList.add(cnt);
cnt = 1;
now = 1 - now;
}
}
if (cnt != 0) {
oneZeroList.add(cnt);
}
if (oneZeroList.size() % 2 == 0) {
oneZeroList.add(0);
}
int countRange = 2 * numK + 1;
//ここより上は全処理共通------------------------------------------------
//累積和用の配列
int[] resList = new int[oneZeroList.size() + 1];
/*
* 累積和用配列に詰めていく
* テストケース1の
* 14 2
* 11101010110011
* を例に取ると、1,0の配列は以下になる。
* 3 1 1 1 1 1 2 2 2
* 1 0 1 0 1 0 1 0 1
* 上記の様な1-0リストだとしたら
* 累積和用配列には以下の様に詰められる
* resListのindex 0 1 2 3 4 5 6 7 8 9
* resListのvalue 0 3 4 5 6 7 8 10 12 14
* 0->1に変換可能な回数は2回
* なので、5この幅を取りたい
*/
for (int j = 0; j < oneZeroList.size(); j++) {
resList[j + 1] = resList[j] + oneZeroList.get(j);
}
int res = 0;
for (int i = 0; i < oneZeroList.size(); i += 2) {
//次のleft,rightを計算する[left,right)
int left = i;
int right = Math.min(i + countRange, oneZeroList.size());
int temp = resList[right] - resList[left];
res = Math.max(res, temp);
}
out.println(res);
}
D - Handstand:しゃくとり法
- よくわかってない
/*
* 実行時間が短い版
* 尺取り法
*/
private void solveD2() {
int numN = nextInt();
int numK = nextInt();
String[] wk = next().split("");
List<Integer> oneZeroList = new ArrayList<Integer>();
int now = 1;
int cnt = 0;
for (int i = 0; i < wk.length; i++) {
if (wk[i].charAt(0) == (char) ('0' + now)) {
cnt++;
} else {
oneZeroList.add(cnt);
cnt = 1;
now = 1 - now;
}
}
if (cnt != 0) {
oneZeroList.add(cnt);
}
if (oneZeroList.size() % 2 == 0) {
oneZeroList.add(0);
}
//ここより上は全処理共通------------------------------------------------
int countRange = 2 * numK + 1;
int res = 0;
/*
* forループの外側にleft/rightを持つ
*/
int left = 0;
int right = 0;
/*
* [left, right) のsum
* ->半開区間
* left以上、right未満
* () より大きい、より小さい -> 両端を含まない
* [] 以上、以下 -> 両端を含む
*/
int temp = 0;
/*
* 1-0-1-0-1....と詰まっているのを数え上げていく
* なので、奇数番しか使わない
*/
for (int i = 0; i < oneZeroList.size(); i += 2) {
/*
* 次のleft,rightを計算する
*/
int nextLeft = i;
int nextRight = Math.min(i + countRange, oneZeroList.size());
//左端を移動する
while (nextLeft > left) {
temp -= oneZeroList.get(left);
left++;
}
//右端を移動する
while (nextRight > right) {
temp += oneZeroList.get(right);
right++;
}
res = Math.max(res, temp);
}
out.println(res);
}