AtCoder ABC 018 A&B&C
A - 豆まき
- なぜか、一個ずつ判定したくなかったのでループで回した
- 初期indexと点数を保持しておく
- 点数でソート
- 点数の箇所を並び順番(index)に置換
- 初期indexでソート
- 置換した並び順を出力
private void solveA() {
int[][] wk = new int[3][2];
for (int i = 0; i < 3; i++) {
wk[i] = new int[] { i, nextInt() };
}
Arrays.sort(wk, (x, y) -> -Integer.compare(x[1], y[1]));
for (int i = 0; i < 3; i++) {
wk[i][1] = i + 1;
}
Arrays.sort(wk, (x, y) -> Integer.compare(x[0], y[0]));
for (int[] is : wk) {
out.println(is[1]);
}
}
B - 文字列の反転
private void solveB() {
char[] wk = next().toCharArray();
int n = nextInt();
for (int i = 0; i < n; i++) {
int s = nextInt() - 1;
int e = nextInt() - 1;
while (s < e) {
wk[s] += wk[e];
wk[e] = (char) (wk[s] - wk[e]);
wk[s] = (char) (wk[s] - wk[e]);
s++;
e--;
}
}
out.println(new String(wk));
}
C - 菱型カウント：マインスイーパー？
速度は遅いが、ACできた。（最初はループで実装してたけどTLEが解消できなさそうなので考察しなおした）
-
問題文だけだと？？？となったのでExcelで実際に値を入れてみたところ、以下が判明した
- 中心から$(k-1)$を足して菱形をつくる
- 菱形の中に×が含まれていてはいけない
- 上記条件を満たす菱形を何個作れるか？
- 全探索をするから遅いんであって、もう少し探索量を減らせればTLEかいしょうするかなということで、考察しなおした
- 原理はマインスイーパーの安全地帯の探し方
- 数値埋めるのに結局探索しなくてはいけないけど、いくらかは枝刈りできるでしょ？
入力例：
8 8 3
oooooooo
oooooooo
oooooooo
oooooooo
oxoooooo
oooooooo
oooooxoo
oooxoooo
- 表に直すとこう
| o | o | o | o | o | o | o | o |
| o | o | o | o | o | o | o | o |
| o | o | o | o | o | o | o | o |
| o | x | o | o | o | o | o | o |
| o | o | o | o | o | o | o | o |
| o | o | o | o | o | x | o | o |
| o | o | o | x | o | o | o | o |
- K=3なので、xが中心から3以内にいてはいけない
- また、壁を超えることもNG
- X=3/壁=2で値を入れる
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 2 | 3 | 0 | 0 | 0 | 0 | 0 | 2 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 2 | 0 | 0 | 0 | 0 | 3 | 0 | 2 |
| 2 | 2 | 2 | 3 | 2 | 2 | 2 | 2 |
- あとは周辺に値を入れて、残った0をカウントする
- 1,2,3の位置を中心にすると壁をはみ出すか×に引っかかる
- 0の位置は中心になれる
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 1 | 1 | 1 | 1 | 1 | 1 | 2 |
| 2 | 1 | 0 | 0 | 0 | 0 | 1 | 2 |
| 2 | 2 | 1 | 0 | 0 | 0 | 1 | 2 |
| 2 | 3 | 2 | 1 | 0 | 1 | 1 | 2 |
| 2 | 2 | 1 | 1 | 1 | 2 | 1 | 2 |
| 2 | 1 | 1 | 2 | 2 | 3 | 2 | 2 |
| 2 | 2 | 2 | 3 | 2 | 2 | 2 | 2 |
- TLE解消時の備考
- 周辺を再探索するときのcontinueをbreakにしたらTLE解消した（場所はコメントしてある）
- continueよりもきちんと探索を打ち切る方法を考慮しないといけないのを実感した。
private void solveC() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int[][] dist = new int[r][c];
for (int i = 0; i < r; i++) {
char[] wk = next().toCharArray();
for (int j = 0; j < c; j++) {
/*
* Xは地雷なのでmaxとそれ以外はいったん0
*/
if (wk[j] == 'x') {
dist[i][j] = k;
} else if (i == 0 || i == r - 1 || j == 0 || j == c - 1) {
/*
* 壁の横のものは埋め
*/
dist[i][j] = k - 1;
} else {
dist[i][j] = 0;
}
}
}
/*
* 各箇所の数値を更新し、安全地帯を確認する
*/
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
/*
* 自分が0なら周りには配れない
* 安全地帯
*/
if (dist[i][j] == 0) {
continue;
}
allocateNum(r, c, dist, i, j);
}
}
long res = 0;
/*
* 安全地帯の数を数える
*/
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (dist[i][j] == 0) {
res++;
}
}
}
out.println(res);
}
private static final int[] dx = new int[] { 0, 0, 1, -1 };
private static final int[] dy = new int[] { 1, -1, 0, 0 };
private void allocateNum(int r, int c, int[][] dist, int i, int j) {
/*
* 四方に自分の値を配る
* ただし、自分の値と距離から計算した値より大きい値がすでに入っている場合は無視
* 四方に配る場合、自分の値までの長さで配らなくてはいけないので2重ループ
*/
int base = dist[i][j];
for (int d4 = 0; d4 < 4; d4++) {
for (int dLen = 1; dLen <= base; dLen++) {
int wX = i + dx[d4] * dLen;
int wY = j + dy[d4] * dLen;
if (wX < 0 || r <= wX || wY < 0 || c <= wY || dist[wX][wY] >= base - dLen) {
/*
* continueをbreakに修正（この修正でTLE解消した）
* 中心に近いところから見ているので、行き先に大きい値があるならこれ以上は配賦の必要がない
*/
// continue;
break;
}
/*
* 距離が遠くなるとdLen分、配賦量が減る
*/
dist[wX][wY] = base - dLen;
//値を更新したので再度配布する
allocateNum(r, c, dist, wX, wY);
}
}
}
C - 菱型カウント：解説に記載の方法（累積和？）
4 5 2
xoooo
oooox
ooooo
oxxoo
UP側のカウント
| 0 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 | 0 |
| 2 | 3 | 3 | 3 | 1 |
| 3 | 0 | 0 | 4 | 2 |
DOWN側のカウント
| 0 | 3 | 3 | 4 | 1 |
| 3 | 2 | 2 | 3 | 0 |
| 2 | 1 | 1 | 2 | 2 |
| 1 | 0 | 0 | 1 | 1 |
private void solveC() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
char[][] wk = new char[r][c];
for (int i = 0; i < r; i++) {
wk[i] = next().toCharArray();
}
int[][] up = new int[r][c];
int[][] down = new int[r][c];
for (int i = 0; i < c; i++) {
int uCnt = 0;
int dCnt = 0;
for (int j = 0; j < r; j++) {
if (wk[j][i] == 'o') {
uCnt++;
} else {
uCnt = 0;
}
if (wk[r - 1 - j][i] == 'o') {
dCnt++;
} else {
dCnt = 0;
}
up[j][i] = uCnt;
down[r - 1 - j][i] = dCnt;
}
}
long res = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
/*
* 中心確定
* ただし、上下方向ともにk未満の場合は中心にはなれない
*/
if (up[i][j] < k || down[i][j] < k) {
continue;
}
boolean canCnt = true;
/*
* 左右に探索を広げる
*/
for (int l = 1; l < k; l++) {
/*
* cが+となる方向への探索
* up/downともに数値を満たすこと
*/
if (j + l >= c || up[i][j + l] < k - l || down[i][j + l] < k - l) {
canCnt = false;
break;
}
/*
* cが-となる方向への探索
* up/downともに数値を満たすこと
*/
if (j - l < 0 || up[i][j - l] < k - l || down[i][j - l] < k - l) {
canCnt = false;
break;
}
}
if (canCnt) {
res++;
}
}
}
out.println(res);
}
C - 菱型カウント：普通にループ（TLE）
- $(i,j)$を1個ずつ菱形になれるかを見ていく
- 当然TLEだが、部分点だけは何とかとれる。。。
private void solveC2() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
char[][] wk = new char[r][c];
for (int i = 0; i < wk.length; i++) {
wk[i] = next().toCharArray();
}
long res = 0;
/*
* X軸もY軸も(k-1)まで必要なので開始終了からその分を引く
*/
for (int i = k - 1; i < r - (k - 1); i++) {
for (int j = k - 1; j < c - (k - 1); j++) {
if (chkBlack(wk, k, i, j, r, c)) {
res++;
}
}
}
out.println(res);
}
private boolean chkBlack(char[][] wk, int k, int i, int j, int r, int c) {
/*
* 左右の振れ幅はk-1
*/
int wkK = k - 1;
/*
* X軸
* -(k-1) - 0 - (k-1)
*/
for (int i2 = -wkK; i2 <= wkK; i2++) {
/*
* Y軸
* -(k-1)
* -
* 0
* -
* (k-1)
*/
for (int j2 = -wkK; j2 <= wkK; j2++) {
int x = i + i2;
int y = j + j2;
/*
* 探索範囲を菱形に絞る
*/
if (Math.abs(i2) + Math.abs(j2) > wkK) {
continue;
}
/*
* はみ出たり黒があったらアウト
*/
if (x < 0 || r <= x || y < 0 || c <= y || wk[x][y] == 'x') {
return false;
}
}
}
return true;
}