AtCoder ABC 023 A&B&C
A問題
private void solveA() {
int x = nextInt();
int res = 0;
while (x != 0) {
res += x % 10;
x /= 10;
}
out.println(res);
}
B問題
-
'a'と'c'と'b'の組み合わせの順番を考慮していないので実は嘘解法だということにきづいている。。。修正は近いうちに。 -
サンプルをみると
- スタートは
'b'から始まり、常に+2文字されているので必ず奇数になる- 偶数の場合はfalse
- 真ん中は
'b'で、その左右は以下のどれかになる'a' xxx 'c''c' xxx 'a''b' xxx 'b'
- 真ん中の
'b'を基準に左右を見ていけばよい
- スタートは
private void solveB() {
int numN = nextInt();
String s = next();
if ((numN & 1) == 0) {
out.println(-1);
return;
}
int max = numN / 2;
int res = 0;
for (int i = 0; i < max; i++) {
char down = s.charAt((numN - 1) - (max + 1) - i);
char up = s.charAt((max + 1) + i);
if ((down == 'a' && up == 'c') || (down == 'c' && up == 'a') || (down == 'b' && up == 'b')) {
res = i + 1;
} else {
out.println(-1);
return;
}
}
out.println(res);
}
C問題
AtCoder Beginner Contest 023 解説 P.12~
-
基本は解説を読めば
-
[微調整\何処に飴を置いたのか調査]についての補足だけ書いておく
合計がKと等しい場合
| col no\row no | 1 | 2 | 3 | ||
|---|---|---|---|---|---|
| colのカウント\rowのカウント | 2 | 1 | 2 | ||
| 1 | 1 | 〇 | |||
| 2 | 2 | 〇 | 〇 | ||
| 3 | 2 | 〇 | 〇 |
- k=3の場合
- $(col no,row no)=(2,2)$の位置だと問題なくあめは3個とれる
- $(colのカウント,rowのカウント)=(2,1)$ なので合計も3個
- $(col no,row no)=(3,2)$の位置だと飴は2個しか取れない
- $(colのカウント,rowのカウント)=(2,1)$ なので計算上は3個とれているはず。。。
- $(col no,row no)=(2,2)$の位置だと問題なくあめは3個とれる
飴を置いた場所が、$colのカウント+rowのカウント=K$の場合は、数えてはいけないところを数えている。
合計がK+1と等しい場合
| col no\row no | 1 | 2 | 3 | ||
|---|---|---|---|---|---|
| colのカウント\rowのカウント | 2 | 1 | 2 | ||
| 1 | 1 | 〇 | |||
| 2 | 2 | 〇 | 〇 | ||
| 3 | 2 | 〇 | 〇 |
-
k=3の場合
- $(col no,row no)=(3,3)$の位置だと問題なくあめは3個とれる
- ただし、$(colのカウント,rowのカウント)=(2,2)$ なので合計は4個
- $(col no,row no)=(3,3)$の位置だと問題なくあめは3個とれる
-
飴を置いた場所が、$colのカウント+rowのカウント=K+1$の場合は、飴を重複して数えている
- +1なのは、置いた飴を2回数えているから
private void solveC() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int n = nextInt();
int[] rI = new int[n];
int[] cI = new int[n];
int[] rP = new int[r + 1];
int[] cP = new int[c + 1];
for (int i = 0; i < n; i++) {
int tmpR = nextInt() - 1;
int tmpC = nextInt() - 1;
rI[i] = tmpR;
cI[i] = tmpC;
//rの各行毎の飴の個数
rP[tmpR]++;
//cの各列毎の飴の個数
cP[tmpC]++;
}
/*
* 各row毎の飴の個数について集計
* row毎にこの個数なら
* [1, 2, 2, 0]
* 以下のようにカウントする
* 0=1
* 1=1
* 2=2
* 3=0
* rPCountのサイズがN+1なのは、これ以上の飴の個数は存在しないから
*/
int[] rPCount = new int[n + 1];
for (int i = 0; i < r; i++) {
rPCount[rP[i]]++;
}
//各columnについてもrowと同様に処理
int[] cPCount = new int[n + 1];
for (int i = 0; i < c; i++) {
cPCount[cP[i]]++;
}
long res = 0;
/*
* ざっぱに組み合わせを計算
* 入力例１なら、
* rowの飴の個数が0の時は、colの飴の個数は3個ないといけない
* そのため、[rの飴が0の行数]×[cの飴が3の行数]を計算
* 同様に、rowの飴の個数が1の時は、colの飴の個数は2個必要なので、
* [rの飴が1の行数]×[cの飴が2の行数]を計算
* これでざっぱな組み合わせを出す
*/
for (int i = 0; i <= k; i++) {
res += rPCount[i] * cPCount[k - i];
}
/*
* 微調整
* 何処に飴を置いたのか調査
*/
for (int i = 0; i < n; i++) {
long sum = rP[rI[i]] + cP[cI[i]];
if (sum == k) {
/*
* 合計がKと等しいということは、ざっぱな組み合わせ計算の時に数えてはいけない対象を数えている
* そのため、この位置はカウントから除外する
*/
res--;
} else if (sum == k + 1) {
/*
* 合計がK+1ということは、ざっぱな組み合わせ計算の時に数える対象外となっている
* そのため、この位置はカウントする
*/
res++;
}
}
out.println(res);
}
C問題:TLE
- メモリは減った？ようだけど速度が足らん。。。
private void solveC3() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int n = nextInt();
// int[][] masu = new int[r][c];
Map<Integer, Set<Integer>> wk = new HashMap<Integer, Set<Integer>>();
int[] rP = new int[r];
int[] cP = new int[c];
for (int i = 0; i < n; i++) {
int tmpR = nextInt() - 1;
int tmpC = nextInt() - 1;
// masu[tmpR][tmpC] = 1;
Set<Integer> tmpSet = new HashSet<Integer>();
tmpSet.add(tmpC);
wk.merge(tmpR, tmpSet, (oldV, newV) -> {
oldV.addAll(newV);
return oldV;
});
rP[tmpR]++;
cP[tmpC]++;
}
long res = 0;
Set<Integer> defSet = new HashSet<Integer>();
for (int i = 0; i < rP.length; i++) {
for (int j = 0; j < cP.length; j++) {
int val = wk.getOrDefault(i, defSet).contains(j) ? 1 : 0;
// int val = wk.getOrDefault(i, new HashSet<Integer>()).contains(j) ? 1 : 0;
if (rP[i] + cP[j] - val == k) {
res++;
}
}
}
out.println(res);
}
C問題:MLE
- 配列が大きすぎてメモリが足らん。。。
/**
* MLE
*/
private void solveC2() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int n = nextInt();
int[][] masu = new int[r][c];
int[] rP = new int[r];
int[] cP = new int[c];
for (int i = 0; i < n; i++) {
int tmpR = nextInt();
int tmpC = nextInt();
masu[tmpR - 1][tmpC - 1] = 1;
rP[tmpR - 1]++;
cP[tmpC - 1]++;
}
long res = 0;
for (int i = 0; i < rP.length; i++) {
for (int j = 0; j < cP.length; j++) {
if (rP[i] + cP[j] - masu[i][j] == k) {
res++;
}
}
}
out.println(res);
}