AtCoder Beginner Contest 372
A~Dの4完（61分）でした。
974perfでレートは758->782（+24）です。
Eも解けそうでしたがkが10以下という制約をすっかり見落としており、
UnionFind＋マージテク＋SortedSetをがちゃがちゃやって最終的にTLEで沼りました。
コンテスト後に正しい解法でupsolveしたので、それを含めてA~E問題をまとめます。
A - delete .
入力$S$を受け取り文字列.を削除するか、あるいは$S$を1文字目から見ていき.以外だけ追加していけばよいです。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const s = input[0].split("");
for(let i = 0; i < s.length; i++) if(s[i] === ".") s[i] = "";
console.log(s.join(""));
}
Main(require("fs").readFileSync(0, "utf8"));
B - 3^A
$3^A≦M$を満たす$A$のうち最も大きなものを選び、$M$を$M-3^A$に置き換えるという操作を繰り返す貪欲法により、最小回数で$M=0$にできます。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
let M = Number(input[0]);
let ans = [];
for (let i = 20; i >= 0; i--) {
if (M >= 3 ** i) {
M -= 3 ** i;
ans.push(i);
i++;
}
}
console.log(ans.length);
console.log(ans.join(" "));
}
Main(require("fs").readFileSync(0, "utf8"));
C - Count ABC Again
各クエリ$[X[i],C[i]]$の変更によりABCの個数が変わる可能性のある部分は$X[i]$の周辺のみ、すなわち「$S_{X-2}S_{X-1}S_{X}$」、「$S_{X-1}S_{X-1}S_{X+1}$」、「$S_{X}S_{X+1}S_{X+2}$」の3パターンだけです。
よって、最初の数え上げだけ愚直にやり、クエリごとに答えに寄与する周辺部分を更新するようにすれば全体計算量は$O(N+Q)$となり、これは十分高速です。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, Q] = input[0].split(" ").map(Number);
const S = input[1].split("");
let X = [],
C = [];
for (let i = 0; i < Q; i++) [X[i], C[i]] = input[i + 2].split(" ");
X = X.map((x) => Number(x) - 1);
let f = new Array(N - 2).fill(false);
for (let i = 0; i < N - 2; i++) {
if (S[i] === "A" && S[i + 1] === "B" && S[i + 2] === "C") f[i] = true;
}
let s = 0;
for (let i = 0; i < N - 2; i++) if (f[i]) s++;
for (let i = 0; i < Q; i++) {
let x = X[i];
let c = C[i];
S[x] = c;
if (x > 1) {
if (f[x - 2] && !(S[x - 2] === "A" && S[x - 1] === "B" && S[x] === "C")) {
s--;
f[x - 2] = false;
} else if (!f[x - 2] && S[x - 2] === "A" && S[x - 1] === "B" && S[x] === "C") {
s++;
f[x - 2] = true;
}
}
if (x > 0 && x < N - 1) {
if (f[x - 1] && !(S[x - 1] === "A" && S[x] === "B" && S[x + 1] === "C")) {
s--;
f[x - 1] = false;
} else if (!f[x - 1] && S[x - 1] === "A" && S[x] === "B" && S[x + 1] === "C") {
s++;
f[x - 1] = true;
}
}
if (x < N - 2) {
if (f[x] && !(S[x] === "A" && S[x + 1] === "B" && S[x + 2] === "C")) {
s--;
f[x] = false;
} else if (!f[x] && S[x] === "A" && S[x + 1] === "B" && S[x + 2] === "C") {
s++;
f[x] = true;
}
}
console.log(s);
}
}
Main(require("fs").readFileSync(0, "utf8"));
余談ですが、セグ木を使えばほんの少しだけ実装が簡素になります。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, Q] = input[0].split(" ").map(Number);
const S = input[1].split("");
let X = [],
C = [];
for (let i = 0; i < Q; i++) [X[i], C[i]] = input[i + 2].split(" ");
X = X.map((x) => Number(x) - 1);
const seg = new SegTree(N - 2, (a, b) => a + b, 0);
for (let i = 0; i < N - 2; i++) {
if (S[i] === "A" && S[i + 1] === "B" && S[i + 2] === "C") seg.update(i, 1);
}
for (let i = 0; i < Q; i++) {
let [x, c] = [X[i], C[i]];
S[x] = c;
if (x > 1) {
if (S[x - 2] === "A" && S[x - 1] === "B" && S[x] === "C") seg.update(x - 2, 1);
else seg.update(x - 2, 0);
}
if (x > 0 && x < N - 1) {
if (S[x - 1] === "A" && S[x] === "B" && S[x + 1] === "C") seg.update(x - 1, 1);
else seg.update(x - 1, 0);
}
if (x < N - 2) {
if (S[x] === "A" && S[x + 1] === "B" && S[x + 2] === "C") seg.update(x, 1);
else seg.update(x, 0);
}
console.log(seg.query(0, N - 3));
}
}
class SegTree {
constructor(m, op, e) {
this.n = Math.pow(2, Math.ceil(Math.log2(m))); // 葉の数を確定
this.op = op; // 演算子
this.e = e; // 単位元
this.node = new Array(2 * this.n).fill(e); // 0-indexedで葉を初期化
}
update(a, x) {
a += this.n;
this.node[a] = x;
while (a > 0) {
a >>= 1;
this.node[a] = this.op(this.node[2 * a], this.node[2 * a + 1]); // 親ノードに子ノードの演算結果を反映
}
}
get(a) {
a += this.n;
return this.node[a];
}
query(a, b) {
// 閉区間[a, b]の演算結果を取得
let res = this.e;
a += this.n;
b += this.n + 1;
while (a < b) {
res = a % 2 === 1 ? this.op(res, this.node[a++]) : res;
res = b % 2 === 1 ? this.op(res, this.node[--b]) : res;
a >>= 1;
b >>= 1;
}
return res;
}
show() {
console.log(this.node.slice(this.n, 2 * this.n));
}
}
Main(require("fs").readFileSync(0, "utf8"));
D - Buildings
想定解はスタックでしたが、セグ木（RMQ）＋ハッシュマップ＋主客転倒で解きました。
この問題はとっかかりが掴みにくいと思いますので、まずイメージのために例を出します。まず、$\text{H}=[2,1,5,3,4]$として、自分より左側にあり自分より高いビルのうち最初に見えるビルはどれか？を考えます。これを、配列$\text{maxRight}$とします。もし自分よりも左側に自分より高いビルがなければ、$\text{maxRight}[i]=-1$とおきます。
| $i$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| $\text{H}[i]$ | 2 | 1 | 5 | 3 | 4 |
| $\text{maxRight}[i]$ | -1 | 0 | -1 | 2 | 2 |
問題文には「$i$ごとに、$i$と$j$の間に$j$より高いビルが存在しないような$j$の個数を出力せよ（意訳）」とありますが、視点を変えて「$j$を固定して$i$を$j$からどんどん左にずらしていく。$i$と$j$の間に$j$より高いビルが存在しないような$i$の左端はどこか」を考えます。
上記の例だと、$i=4$のとき$\text{maxRight}[i]$は$2$のため、
- $i<2$ならば$i,j$の間に$j$よりも高いビルは存在する（ビル$2$のこと）
- $i≧2$ならば$i,j$の間に$j$よりも高いビルは存在しない
したがって、一般的には$i$が$\text{maxRight}[i]$よりも左側にあるとき、$i,j$の間に$j$よりも高いビルが必ず存在するため$i$の答えに寄与しません。反対に$i$が$\text{maxRight}[i]$と同じかそれより右側にあるとき、$i,j$の間に$j$よりも高いビルは存在しないため$i$の答えに寄与します。
この性質を利用すれば、$i=0$の答えは自分を含まない$\text{maxRight}[i]≦0$となる総和を取って求め、$i$を右にずらしていって、自分が$\text{maxRight}[i]$であるような個数分だけ加算するのと、$i$を右にずらしたときに$i$と$i+1$のペアは必ず減算する必要がある点を考慮して$O(N)$ですべての$i$についての個数を求めることができます。なお、「自分が$\text{maxRight}[i]$であるような個数」はハッシュマップ等であらかじめ準備しておく必要があります。この考えをもとに、出力すべき配列$\text{ans}[i]$を更新するとこのようになります。
| $i$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| $\text{H}[i]$ | 2 | 1 | 5 | 3 | 4 |
| $\text{maxRight}[i]$ | -1 | 0 | -1 | 2 | 2 |
| $\text{ans}[i]$ | 2 | 1 | 2 | 1 | 0 |
ここまでくれば、あとは$\text{maxRight}[i]$をどのように準備すればよいかさえわかれば、この問題はACできたも同然です。
Range Maximum Queryのセグ木で「値$i$で最も右側にあるものはどこか？」を管理します。先ほどの例の$\text{H}=[2,1,5,3,4]$であれば、$\text{seg}=[1,0,3,4,2]$となります（値$i$が$\text{seg}[i]$番目に最も右側で出現するということ。例えば、値$3$は$\text{H}[3]$にあり、値$5$は$\text{H}[2]$にある）。
これを用意することで、値$x$より大きい値の右端を$O(logN)$で取得できます。より具体的には、seg.query(x+1,N)で閉区間$[x+1,N]$の最大値を高速に取得します。
ただし、「自分より左側」という条件があるため、右側から順に見ていき、すでに見たインデックスは$-1$などにしてクエリを邪魔しないようにする必要があります。
以上より、$O(NlogN)$で$\text{maxRight}[i]$を構築することができ、全体として$O(NlogN+Q)$でこの問題を解くことができました。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const N = Number(input[0]);
const H = input[1].split(" ").map(Number);
const seg = new SegTree(N + 1, (a, b) => Math.max(a, b), -1);
for (let i = 0; i < N; i++) seg.update(H[i], i);
let maxRight = new Array(N).fill(-1);
for (let i = N - 1; i >= 0; i--) {
maxRight[i] = seg.query(H[i] + 1, N);
seg.update(H[i], -1);
}
const map = new Map();
for (let i = 0; i < N; i++) map.set(maxRight[i], (map.get(maxRight[i]) || 0) + 1);
let ans = [];
let cur = 0;
for (let i = 1; i < N; i++) if (maxRight[i] <= 0) cur++;
ans.push(cur);
for (let i = 1; i < N; i++) {
cur--;
cur += map.get(i) || 0;
ans.push(cur);
}
console.log(ans.join(" "));
}
class SegTree {
constructor(m, op, e) {
this.n = Math.pow(2, Math.ceil(Math.log2(m))); // 葉の数を確定
this.op = op; // 演算子
this.e = e; // 単位元
this.node = new Array(2 * this.n).fill(e); // 0-indexedで葉を初期化
}
update(a, x) {
a += this.n;
this.node[a] = x;
while (a > 0) {
a >>= 1;
this.node[a] = this.op(this.node[2 * a], this.node[2 * a + 1]); // 親ノードに子ノードの演算結果を反映
}
}
get(a) {
a += this.n;
return this.node[a];
}
query(a, b) {
// 閉区間[a, b]の演算結果を取得
let res = this.e;
a += this.n;
b += this.n + 1;
while (a < b) {
res = a % 2 === 1 ? this.op(res, this.node[a++]) : res;
res = b % 2 === 1 ? this.op(res, this.node[--b]) : res;
a >>= 1;
b >>= 1;
}
return res;
}
show() {
console.log(this.node.slice(this.n, 2 * this.n));
}
}
Main(require("fs").readFileSync(0, "utf8"));
E - K-th Largest Connected Components
コンテスト後にupsolveしたコードを貼っておきます。
考え方はDよりもシンプルで、UnionFindでクエリ1のときノード$u,v$を連結し、上位10番目以内の辺を愚直に親に書き込みます。クエリ2のとき、$k$が与えられるので上から$k$番目の辺を出力するだけで良いです。
$k≦10$を完全に見落としており、SortedSetやマージテク（連結した頂点の個数が少ない方を大きい方にマージする）を利用して任意の$k$で求めようとしており、タイムアップになりました。これが解けていたらほぼ水パフォ出ていたと思いますし、点数傾斜でABCE4完勢よりも順位が下で結構悔しいです。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, Q] = input[0].split(" ").map(Number);
const query = [];
for (let i = 0; i < Q; i++) query.push(input[i + 1].split(" ").map(Number));
const max = new Array(N + 1).fill(0).map(() => []);
for (let i = 1; i <= N; i++) max[i].push(i);
const uf = new UnionFind();
for (let i = 0; i < Q; i++) {
if (query[i][0] === 1) {
let [q, u, v] = query[i];
if (!uf.connected(u, v)) {
let node = [...max[uf.find(u)], ...max[uf.find(v)]];
node.sort((a, b) => b - a);
uf.union(u, v);
max[uf.find(u)] = node.slice(0, 10);
}
} else {
let [q, v, k] = query[i];
if (max[uf.find(v)].length < k) console.log(-1);
else console.log(max[uf.find(v)][k - 1]);
}
}
}
//経路圧縮済み、動的拡張可能なUnionFind
class UnionFind {
constructor() {
this.parent = [];
this.rank = [];
this.size = [];
}
find(x) {
if (this.parent[x] === undefined) {
this.parent[x] = x;
this.rank[x] = 0;
this.size[x] = 1;
}
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
this.size[rootX] += this.size[rootY];
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
this.size[rootY] += this.size[rootX];
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
this.size[rootX] += this.size[rootY];
}
}
}
// unionの前にすでにconnected=trueの場合、その素集合は閉路を持つ
connected(x, y) {
return this.find(x) === this.find(y);
}
getSize(x) {
return this.size[this.find(x)];
}
}
Main(require("fs").readFileSync(0, "utf8"));
気を取り直して、次週も入緑チャレがんばります！