AtCoder ABC 069 A&B&C
A問題
- 「道路に囲まれた=外周部は除外する」となる
private void solveA() {
int numN = nextInt();
int numM = nextInt();
out.println((numN - 1) * (numM - 1));
}
B問題
- 以下の文字を生成すればよい
- 文字列の最初の文字 + 数値=文字列長-2 + 文字列の最後の文字
- 文字列長-2 = 文字列長 - 1(文字列の最初の文字) - 1(文字列の最後の文字)
- 文字列の最初の文字 + 数値=文字列長-2 + 文字列の最後の文字
private void solveB() {
char[] wk = next().toCharArray();
out.println("" + wk[0] + (wk.length - 2) + wk[wk.length - 1]);
}
C問題
- $(a_i * a_{i+1})mod4=0$ということは、$a_i$または$a_{i+1}$のどちらかは4の倍数ということ
- 4の倍数に何をかけても4の倍数
- ただし例外として、2の倍数同士をかけた場合も4の倍数となる
- 4の倍数が数列の半分以上あれば $(a_i * a_{i+1})mod4=0$ が成り立つ
なので実装は、
1. 4の倍数の数をカウント
2. 4の倍数ではないものの中で、2の倍数の数をカウント
3. 2の倍数が偶数だったら、$数列長-(2の倍数の数)$ をする
4. 2の倍数が奇数だったら、$(数列長-(2の倍数の数-1)$ をする
5. 3または4の処理後の数列長の半分以上4の倍数があればtrue
1 | 2 | 2 | 1 | 4 | 4 | この数列も |
2 | 2 | 1 | 4 | 1 | 4 | となればよい |
1 | 4 | 1 | 4 | 2の倍数同士の乗算は4の倍数になるので、実質の数列はこうともとれる |
private void solveC() {
int numN = nextInt();
int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
int cnt4 = 0;
int cnt2 = 0;
/*
* 4の倍数か2の倍数かの判定
* 4の倍数は前後に何が来ても条件を満たす
* 2の倍数の場合は、2の倍数同士をかけると4の倍数となるので、
* 4の倍数ではない場合は組み合わせで条件を満たすものを探しておく
*/
for (int val : wk) {
if (val % 4 == 0) {
cnt4++;
} else if (val % 2 == 0) {
cnt2++;
}
}
/*
* 4の倍数が0
* そして、
* 2の倍数も0 または 2の倍数が偶数ではない(組み合わせで消し込めない)
* 場合は無理
*/
if (cnt4 == 0 && (cnt2 % 2 != 0 || cnt2 == 0)) {
out.println("No");
return;
}
/*
* 組み合わせを考慮しなくてはいけない数
* 2-2の組は2*2=4となるので外す
*
* 1 2 2 4 1 4 の組を
* 2 2 1 4 1 4 とするために
* 1 4 1 4 2の倍数の組み合わせを消込む
*
* 1 2 2 4 1 4 2 の場合、2の倍数の組み合わせを消込む(2が1個残る)
* 2 1 4 1 4 として、4の倍数になるのか?と考える
*/
int targetCnt = numN - (cnt2 % 2 == 0 ? cnt2 : cnt2 - 1);
if (targetCnt % 2 == 0) {
out.println(cnt4 >= targetCnt / 2 ? "Yes" : "No");
} else {
out.println(cnt4 >= (targetCnt - 1) / 2 - 1 ? "Yes" : "No");
}
}