AtCoder Beginner Contest 413
今回はonline judge toolsによるCLI提出が不可能な関係でunrated参加となりました。
ABCFの4完（66分3ペナ）でした。
AtCoder Rating Predictorは1219perfを示しています。
コンテスト後にD,E,Gを自力でACできたので、今回はA〜Gをまとめます。
A - Content Too Large
品物の大きさの合計$\text{sum}$を求め、$\text{sum} \le M$であればすべての品物を鞄に入れることができます。
$\text{sum}$は$N$回for文を回して求めても良いですし、JavaScriptのreduceメソッドを使って簡便に求めることもできます。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, M] = input[0].split(" ").map(Number);
const A = input[1].split(" ").map(Number);
const sum = A.reduce((acc, cur) => acc + cur, 0);
if (sum <= M) return console.log("Yes");
else return console.log("No");
}
Main(require("fs").readFileSync(0, "utf8"));
B - cat 2
$i \ne j$を満たす$i,j$について、$S_i+S_j$（ここでの$+$は文字列連結を表す）を全列挙し、重複を削除した上での要素数を出力すれば良いです。
重複削除は、ハッシュセットを用いるのが簡便な方法です。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const N = Number(input[0]);
const S = [];
for (let i = 0; i < N; i++) S[i] = input[i + 1];
const set = new Set();
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (i === j) continue;
let newS = S[i] + S[j];
set.add(newS);
}
}
console.log(set.size);
}
Main(require("fs").readFileSync(0, "utf8"));
C - Large Queue
まず、クエリ1を見ると、$x$を$c$個追加するとありますが、$x,c \le 10^9$であるため、一文字ずつ整数列$A$に数字を追加することは時間的に不可能です。
したがって、問題文の通り$A$を整数列とみなすのではなく、$A=[c_1, x_1],[c_2,x_2],\cdots ,[c_k,x_k]$のように、クエリ1で追加された部分をまとめて表現されているようなデータ構造とみなして処理できないかを考える必要があります。
例）544333222211111の場合
A = [1,5], [2,4], [3,3], [4,2], [5,1]
その前提で、クエリ2の処理方法を考えます。
先頭から$k$個削除するとありますが、上記のような配列構造の場合は次のようなアルゴリズムで高速に処理することができます。
- $k>0$を満たす間、以下の処理を繰り返す。なお、削除された整数の総和を$\text{sum}$とする
- （処理1）$k < c_1$の場合：$x_1$を$k$個削除してもまだ$c_1-k$個残っているため、$A_1←[c_1-k,x_1]$、$k←0$、$\text{sum}←sum+k \times x_1$を代入する
- （処理2）$k \ge c_1$の場合：$x_1$を$c_1$個すべて削除するため、$A$から先頭要素$A_1$を削除し、$k←k-c_1$、$\text{sum}←sum+c_1 \times x_1$を代入する
処理1はDequeや尺取り法を利用すれば$O(1)$です。
処理2はそもそも$A$にpushされた分しか削除できないためクエリ全体として$O(Q)$でキャップされます。
したがって、全体計算量は$O(Q)$となりこの問題を解くことができました。
なお、$\text{sum}$の計算の際$10^{18}$以上の値になる可能性があるため、オーバーフローを防ぐためNumber型ではなくBigInt型を使う必要があると言うことに注意しましょう。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const Q = Number(input[0]);
const que = [];
let pointer = 0;
const ans = [];
for (let i = 0; i < Q; i++) {
const [q, c, x] = input[i + 1].split(" ").map(Number);
if (q == 1) {
que.push([c, x]);
}else {
let k = BigInt(c);
let res = 0n;
while (k > 0n) {
let [cnt, val] = que[pointer].map(BigInt);
if (cnt >= k) {
que[pointer][0] -= Number(k);
res += k * val;
k = 0n;
} else {
k -= cnt;
res += cnt * val;
pointer++;
}
}
ans.push(res.toString());
}
}
console.log(ans.join("\n"));
}
Main(require("fs").readFileSync(0, "utf8"));
D - Make Geometric Sequence
$A_i>0$であれば、昇順ソートして任意の$i,j$について$A_{j+1}\times A_i=A_{i+1}\times A_j$（等比数列の定義）の関係が成り立っているかを確認するだけの簡単な作業になりますが、今回は負の数もありえます。したがって、公比$r$も負の数がありえるということです。
ただし、$N\ge 2, A_i\ne 0$のため$r\ne 0$であることは良心的といえるかもしれません。
基本方針としては、まず絶対値の昇順で並び替えて公比$|r|$の等比数列となるかどうかを確認します。次に、$A$がすべて正または負のとき公比が$r>0$であるような等比数列が存在することが確定します。一方で、正と負が混じっている時、絶対値の小さい順に正と負が交互に繰り返されるような場合にのみ公比が$r<0$であるような等比数列が存在することが確定します。
例１：Aがすべて正の時
A = 1,2,4,8,16 → 公比2の等比数列
例２：Aがすべて負の時
A = -1,-2,-4,-8,-16 → 公比2の等比数列
例３：Aは絶対値の小さい順に正と負が交互に繰り返されるようなとき
A = 1, -2, 4, -8, 16 → 公比-2の等比数列
ただし、一つだけ考慮しなければならない例外のケースも存在します。
それは、公比$r=-1$のケースです。基本方針の中で$r<0$の等比数列が存在するかどうかを判定する際に「絶対値の小さい順に正と負が交互に繰り返されるような場合」の確認をしましたが、$A$の要素の絶対値がすべて等しい時は、必ずしも都合よく並び替えられるとは限りません。
このような場合は、正と負の要素数の差が$1$以下であれば正と負が繰り返されるような並び順が必ず存在するという性質に着目します。
例２：Aの絶対値が等しい、かつ正と負の値が入り混じっているとき
A = 1, -1, -1, 1, 1
↓
絶対値の小さい順に並び替えても、1, -1, 1, -1, 1のように都合よく正と負が繰り返されるような並び順になるとは限らず、本来は公比r=-1であるような等比数列が存在するにも関わらず、存在しないと誤判定される可能性がある
代案として、正の要素数と負の要素数を比較する。
正の要素数は3、負の要素数は2なので、正の要素を初項として正負が繰り返されるような並び順が必ず存在する。
以上、きちんと場合分けをすることで特に大したアルゴリズムを必要とせずに解くことができます。
なお、割り算回避のために$A_{j+1}\times A_i=A_{i+1}\times A_j$をしますが、$A_i\le 10^9$であるため積が$10^{18}$近くになることがあるためBigInt型として比較する必要があります。
私は本番中に提出したコードのうちこの部分だけ修正したらACできたので、JavaScriptを利用する方はくれぐれもご注意ください。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const T = Number(input[0]);
const ans = [];
for (let t = 0; t < T; t++) {
const N = Number(input[2 * t + 1]);
const A = input[2 * t + 2].split(" ").map(Number);
const absA = A.map((x, i) => [Math.abs(x), i]).sort((a, b) => a[0] - b[0]);
if (absA.filter((x) => x[0] === absA[0][0]).length === N) {
let pl = A.filter((x) => x > 0).length;
let mi = A.filter((x) => x < 0).length;
if (pl === 0 || mi === 0) ans.push("Yes");
else if (Math.abs(pl - mi) <= 1) ans.push("Yes");
else ans.push("No");
continue;
}
// まず正負を無視した場合に等比数列かどうかを判定
let isAbsGeometric = true;
for (let i = 1; i < N - 1; i++) {
if (BigInt(absA[i][0]) * BigInt(absA[1][0]) !== BigInt(absA[0][0]) * BigInt(absA[i + 1][0])) {
isAbsGeometric = false;
}
}
if (!isAbsGeometric) ans.push("No");
else {
let pl = A.filter((x) => x > 0).length;
let mi = A.filter((x) => x < 0).length;
if (pl === 0 || mi === 0) ans.push("Yes");
else {
// 正負を考慮して等比数列かどうかを判定（常に正負の入れ替わりが起こることが条件）
let isGeometric = true;
for (let i = 0; i < N - 1; i++) {
if (A[absA[i][1]] * A[absA[i + 1][1]] > 0) isGeometric = false;
}
if (isGeometric) ans.push("Yes");
else ans.push("No");
}
}
}
console.log(ans.join("\n"));
}
Main(require("fs").readFileSync(0, "utf8"));
E - Reverse 2^i
問題文を読むだけでは何を言っているかわからないと思うので、図示してみましょう。
下手な図ですみませんが、これは$N=3$のときの反転可能な範囲を表しています。
この図から示唆されることとして、$2^3$レベルの反転について考えると、
前半の$2^2$個の中に$1$が含まれる場合は、前半の$2^2$個の中でうまく反転を繰り返せば$1$を先頭に持ってくることができそうです。一方、後半の$2^2$個の中に$1$が含まれる場合は、後半の$2^2$個の中でうまく反転を繰り返せば$1$を末尾に移動して、$2^3$レベルでの反転を行うことで$1$を先頭に持ってくることができそうです。
つまり、$b$の大きい順に、最小値が前半にある場合は反転しない、後半にある場合は反転するという判定を続けることによって、辞書順最小の整数列を得ることができます。
$b$の大きさによらず、最小値が前半にあるか後半にあるかを調べ、新しい文字列を構築する処理は共通するため、実装方法としては再帰関数を利用するのが簡便です。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const T = Number(input[0]);
const ans = [];
for (let t = 0; t < T; t++) {
const N = Number(input[2 * t + 1]);
const P = input[2 * t + 2].split(" ").map(Number);
const dfs = (curP) => {
if (curP.length === 1) {
return [curP];
}
let min = Infinity;
let where = new Map();
for (let i = 0; i < curP.length; i++) {
let p = curP[i] - 1;
where.set(p, i);
if (p < min) min = p;
}
let idx = where.get(min);
let l_arr = [];
let r_arr = [];
if (idx < curP.length / 2) {
l_arr = curP.slice(0, curP.length / 2);
r_arr = curP.slice(curP.length / 2);
} else {
l_arr = curP.slice(curP.length / 2).reverse();
r_arr = curP.slice(0, curP.length / 2).reverse();
}
return [dfs(l_arr).flat(), dfs(r_arr).flat()];
}
const res = dfs(P);
ans.push(res.flat().join(" "));
}
console.log(ans.join("\n"));
}
Main(require("fs").readFileSync(0, "utf8"));
F - No Passage
まず、ゲームの条件を整理しましょう。
要するに、高橋くんが一番行きたい場所を青木くんはブロックします。
つまり、高橋くんは二番目に行きたい場所には自由に行くことができるということです。
条件としてはこれだけなので、BFSや優先度付きキューのようなアルゴリズムを利用して、ゴール（移動回数=0）から移動回数の小さい順に移動元のマスを逆算します。
具体的な流れについては以下の例を考えるとわかりやすいかもしれません。
例）3行5列のグリッドにおいて、(1,3)と(2,4)にゴールが存在する場合
..G..
...G.
.....
Gに隣接するマスを一つずつ確認する
(1,2)：青木くんがゴールマスへの道をブロックするためゴールに行けない
(1,4)：青木くんはゴールマスへの道を片方一つしかブロックできないためいずれかのゴールに行ける
(2,3)：青木くんはゴールマスへの道を片方一つしかブロックできないためいずれかのゴールに行ける
(2,5)：青木くんがゴールマスへの道をブロックするためゴールに行けない
(3,4)：青木くんがゴールマスへの道をブロックするためゴールに行けない
以上により、(1,4)および(2,3)は移動回数=1でゴールに到達できることが確定する。
(1,4)と(2,3)を移動回数=1の新たなゴールとして上記を繰り返す。
本番では優先度付きキューを利用しましたが、公式解説の通り多点スタートBFSでも移動回数の小さい順にキューに入ることが保証されているので非効率な解法といえるかもしれません。
確かにJavaScriptではTLEしてしまうのですが、コンテストのルールに則りC++に翻訳すると1000ms程度でACできるため正解の一つといえます。
// JavaScriptの場合TLE（言語特性か、ライブラリが重いため）
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [H, W, K] = input[0].split(" ").map(Number);
const [R, C] = [[], []];
for (let i = 0; i < K; i++) {
[R[i], C[i]] = input[i + 1].split(" ").map(Number);
R[i]--;
C[i]--;
}
const pq = new PriorityQueue((a, b) => a[2] - b[2]);
const min = new Array(H).fill(0).map(() => new Array(W).fill(Infinity));
for (let i = 0; i < K; i++) {
min[R[i]][C[i]] = 0;
pq.add([R[i], C[i], 0]);
}
while (!pq.isEmpty()) {
const [r, c, d] = pq.remove();
if (d > min[r][c]) continue;
for (const [dr, dc] of [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
]) {
const nr = r + dr;
const nc = c + dc;
if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
let cnt = 0;
for (const [ddr, ddc] of [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
]) {
const nnr = nr + ddr;
const nnc = nc + ddc;
if (nnr < 0 || nnr >= H || nnc < 0 || nnc >= W) continue;
if (min[nnr][nnc] <= min[r][c]) cnt++;
}
if (cnt <= 1) continue;
else {
if (min[nr][nc] !== Infinity && min[nr][nc] <= d + 1) continue;
min[nr][nc] = d + 1;
pq.add([nr, nc, d + 1]);
}
}
}
let ans = 0;
for (let i = 0; i < H; i++) {
for (let j = 0; j < W; j++) {
if (min[i][j] === Infinity) continue;
ans += min[i][j];
}
}
console.log(ans);
}
// Priority Queueクラスは省略
# C++の場合1024msでAC
#include <bits/stdc++.h>
using namespace std;
int main() {
int H, W, K;
cin >> H >> W >> K;
vector<int> R(K), C(K);
for (int i = 0; i < K; i++) {
cin >> R[i] >> C[i];
R[i]--; C[i]--;
}
// Priority queue: {distance, row, col}
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
vector<vector<int>> min_dist(H, vector<int>(W, INT_MAX));
for (int i = 0; i < K; i++) {
min_dist[R[i]][C[i]] = 0;
pq.push(make_tuple(0, R[i], C[i]));
}
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while (!pq.empty()) {
int d = get<0>(pq.top());
int r = get<1>(pq.top());
int c = get<2>(pq.top());
pq.pop();
if (d > min_dist[r][c]) continue;
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
int cnt = 0;
for (int j = 0; j < 4; j++) {
int nnr = nr + dr[j];
int nnc = nc + dc[j];
if (nnr < 0 || nnr >= H || nnc < 0 || nnc >= W) continue;
if (min_dist[nnr][nnc] <= min_dist[r][c]) cnt++;
}
if (cnt <= 1) continue;
if (min_dist[nr][nc] != INT_MAX && min_dist[nr][nc] <= d + 1) continue;
min_dist[nr][nc] = d + 1;
pq.push(make_tuple(d + 1, nr, nc));
}
}
long long ans = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (min_dist[i][j] == INT_MAX) continue;
ans += min_dist[i][j];
}
}
cout << ans << endl;
return 0;
}
G - Big Banned Grid
$(1,1)$から$(H,W)$へ到達できないのは、障害物マスが以下のように連結している場合に限られます。
- パターン１：障害物が上端から下端までつながっている場合
- パターン２：障害物が左端から右端までつながっている場合
- パターン３：障害物が右端から下端までつながっている場合
- パターン４：障害物が左端から上端までつながっている場合
この４パターンの検出は、BFSやUnionFindで$O(K)$となりますが、障害物の連結は縦横斜めの8近傍で判定することになるため定数倍が大きくそこまで余裕があるわけではありません。
$(r,c)$を$r\times W + c$のように数値に置き換えて訪問管理をしないとTLが厳しいものと思われます。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [H, W, K] = input[0].split(" ").map(Number);
const [r, c] = [[], []];
const banned = new Set();
const map = new Map();
for (let i = 0; i < K; i++) {
[r[i], c[i]] = input[i + 1].split(" ").map(Number);
r[i]--;
c[i]--;
let val = r[i] * W + c[i];
banned.add(val);
map.set(val, i);
}
const dy = [0, 0, 1, 1, 1, -1, -1, -1];
const dx = [1, -1, 0, 1, -1, 0, 1, -1];
const seen = new Array(K).fill(false);
const bfs = (pos) => {
let posval = pos[0] * W + pos[1];
const visited = new Set([posval]);
const que = new Set([posval]);
seen[map.get(posval)] = true;
for (let cur of que) {
que.delete(cur);
cur = [Math.floor(cur / W), cur % W];
for (let j = 0; j < 8; j++) {
const ny = cur[0] + dy[j];
const nx = cur[1] + dx[j];
const nval = ny * W + nx;
if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
if (!banned.has(nval)) continue;
if (visited.has(nval)) continue;
visited.add(nval);
que.add(nval);
seen[map.get(nval)] = true;
}
}
return visited;
};
for (let i = 0; i < K; i++) {
if (seen[i]) continue;
const set = bfs([r[i], c[i]]);
let minY = H, minX = W, maxY = -1, maxX = -1;
for (const pos of set) {
const y = Math.floor(pos / W);
const x = pos % W;
minY = Math.min(minY, y);
minX = Math.min(minX, x);
maxY = Math.max(maxY, y);
maxX = Math.max(maxX, x);
}
if (maxY == H - 1 && minY == 0) return console.log("No");
if (maxX == W - 1 && minX == 0) return console.log("No");
if (maxX == W - 1 && maxY == H - 1) return console.log("No");
if (minX == 0 && minY == 0) return console.log("No");
}
console.log("Yes");
}
Main(require("fs").readFileSync(0, "utf8"));
まとめ
unratedでしたが、自身で初めて本番中に青perfを解くことができ、久しぶりの水perfでした。まだonline judge toolsが直っているわけではないため、次回もunrated参加になると思います。
最近は業務プログラミングへの利用を見据え、Rustへの乗り換えを検討しています。