AtCoder Beginner Contest 391
ABCDEの5完（94分3ペナ）でした。
1225perfでレートは989->1015（+26）となりました。
D問題は初提出が39分で、コードはこの時点でほぼ合っていたのですが、質問を時間の昇順にソートしているのを忘れて出力してしまい、気づくのに合計3ペナ、かつ20分後にACと35分のロスをしてしまいました。
残りの40分でE問題を解かないとレート冷えまである状況で、得意意識のある再帰の問題が出たので、なんとか終了5分前に通すことができました。
自分でも納得のいく5完で水perf、そして初の4桁レート突破でとても気分がいいです。
というわけで今回はA~Eをまとめます。
A - Lucky Direction
手打ちで反対側の方角を1つずつ書いても良いですが、打ち間違いが怖いので若干の工夫をして解きました。
まず、Nを0として反時計回りに番号を振ります。
以下のようなイメージです。
そうすると、反対側の方角とは4だけ差があることがわかります。
すなわち、ある方角のインデックス$d$に対して、反対方向のインデックス$rev_d$について$rev_d≡d+4\pmod{8}$が成り立ちます。
ACコードの実装は以下のとおりです。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const D = input[0];
const dir = ["N", "NW", "W", "SW", "S", "SE", "E", "NE"];
// map:= 方角を受け取った時に、その方角のindexを返すためのmap
const map = new Map();
for (let i = 0; i < 8; i++) map[dir[i]] = i;
// ちょうど4つindexをずらすと逆方向になる
let rev = (map[D] + 4) % 8;
console.log(dir[rev]);
}
Main(require("fs").readFileSync(0, "utf8"));
B - Seek Grid
$S$の内部で$M×M$の枠をずらしていって、$T$と完全一致する位置を探せばよいです。
以下、上が$N×N$の正方形$S$、下が$M×M$の正方形$T$として、探索のイメージを示します。
緑→水→青→紫→赤の順番に枠をずらして、ちょうど赤色のときに$T$と一致するため左上のマスである$(2, 2)$を出力します。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, M] = input[0].split(" ").map(Number);
const [S, T] = [[], []];
for (let i = 0; i < N; i++) S[i] = input[i + 1].split("");
for (let i = 0; i < M; i++) T[i] = input[N + i + 1].split("");
// [i, j]をTの左上隅として、Sと完全一致する位置を全探索
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
// TがSの範囲外になる場合はスキップ
if (i + M > N || j + M > N) continue
let ok = true;
// Sの[i, j]からM*Mの範囲がTと一致するか確認
for (let k = 0; k < M; k++) {
for (let l = 0; l < M; l++) {
// 一つでも一致しない場合はokをfalseにしてbreak
if (S[i + k][j + l] !== T[k][l]) {
ok = false;
break;
}
}
}
// 一致した場合は[i, j](1-indexed)を出力して終了
if (ok) return console.log(`${i + 1} ${j + 1}`);
}
}
}
Main(require("fs").readFileSync(0, "utf8"));
C - Pigeonhole Query
クエリ2では複数の鳩が存在する巣を全て列挙せよというわけではなく、個数の情報だけ出力すれば良いとのことなので、これをグローバルの可変変数$ans$で管理しておき、クエリ1の都度更新していくことを考えます。
$N,Q$ともに大きいですが、$ans$を保管しておけばクエリ2は$ans$を出力すればいいだけなので、クエリ1の処理を$O(1)$で行うことができればTLは問題なさそうです。
クエリ1は鳩の移動です。ここで、鳩と巣にそれぞれ$1〜N$まで番号を振ってやり、$N$個の要素を持つ配列$where$を用意して$where[i]$を「鳩$i$が今存在する巣の番号」と定義すれば、鳩$P$を巣$H$に移動するというのはwhere[P]=Hで書くことができます。
次に、複数の鳩が存在する巣を管理するために、$N$個の要素を持つ配列$cnt$を用意して$cnt[i]$を「巣$i$に存在する鳩の羽数」と定義します。初期状態は全ての巣に1匹ずつ鳩が住んでいるためどれも$1$となっています。
この配列$cnt$について、鳩が他所の巣に行く場合$1$を引き、鳩が自分の巣に来る場合$1$を足します。このとき、移動元の巣の$cnt$が2→1に変化する場合は「複数の鳩が存在する巣」が一つ減ることを意味するため$ans$から$1$を引きます。また、移動先の巣の$cnt$が1→2に変化する場合はその逆なので$ans$から$1$を足します。
query = [1, P, H]のイメージ
鳩：where[p] → H に移動
cnt[where[p]]が1減り、cnt[H]が1増える
cntの減少時に2→1になっていたらans--、
cntの増加時に1→2になっていたらans++。
以上で$ans$を高速に更新できるため、配列の作成とクエリ全てを処理を合わせて$O(N+Q)$でこの問題を解くことができました。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, Q] = input[0].split(" ").map(Number);
// where[i]:= 鳩iがどの巣にいるかを管理。最初はi番目の鳩がi番目の巣にいる
const where = Array(N).fill().map((_, i) => i);
// cnt[i]:= i番目の巣に何羽の鳩がいるかを管理。最初は全て1羽ずつ
const cnt = Array(N).fill(1);
// ans:= 複数（2羽以上）の鳩が存在する巣の数。最初は全ての巣に1羽ずつなので0
let ans = 0;
for (let i = 0; i < Q; i++) {
let [q, p, h] = input[i + 1].split(" ").map(Number);
p--;
h--;
if (q === 1) {
// from:= p番目の鳩がいる巣なので、where[p]。to:= h番目の巣
let [from, to] = [where[p], h];
// fromの巣は鳩の数を1羽減らし、toの巣は鳩の数を1羽増やす。p番目の鳩の位置はh番目の巣に変更
cnt[from]--;
cnt[to]++;
where[p] = h;
// fromの巣が2→1羽になる場合は複数の鳩がいる巣が1つ減る
if (cnt[from] == 1) ans--;
// toの巣が1→2羽になる場合は複数の鳩がいる巣が1つ増える
if (cnt[to] == 2) ans++;
} else console.log(ans);
}
}
Main(require("fs").readFileSync(0, "utf8"));
D - Gravity
愚直に毎秒ごとにシミュレーションして、一番下の行がブロックで満たされていたらその行のブロックを全て消去し、残っているブロック全ての$Y$座標を-1するといったコードを書いてしまうと全体計算量が$O(T(W+N))$となり全く間に合いません。
（なお、消去したブロックをsetに登録しておけば、任意の時刻$T$でどのブロックがすでに消去されているのか、あるいは残っているのかは高速に求めることができます）
計算量を削減するために、まず毎秒シミュレーションすることをやめましょう。クエリは$Q$個しかないため、$T_1, T_2,...,T_Q$についての最大$Q$回のループで終わらせる方法を考えます。
ここで、クエリの$[T, P]$を昇順にソートしておき、$T_1≦T_2≦…≦T_Q$を満たすようにします。そうすると、$T_i$で消去されているブロックは$T_{i+1}$でも消去されていることは自明なため、$T_i$から$T_{i+1}$の間に消去されるブロックはどのブロックか？ だけを考えればよいことになります。
では、次に$T_i$から$T_{i+1}$の間に消去されるブロックを高速で取得することができるような都合のいいデータ構造を構築することを考えましょう。ブロックの図をじっくり眺めて落ち着いて考えると、次の事実がわかります。
- 無限時間経過後に、$N$回の行消去が行われたとする。このとき、$k(≦N)$番目に消去が行われる第$k$層のブロックが消える時刻は全て、それらのブロックのうち最も$Y$座標の大きなブロック$p$がボトルネックとなり、$Y_p$秒後となる
上の具体例を見てください。緑で囲まれた部分が1番最初に消える第1層、青で囲まれた部分が2番目に消える第2層のブロックです。何も囲まれていない部分はどれだけ時間が経過しても一番下の行で$W$個並ぶことがないため消去されません。
ここで、第$i$層のボトルネックとなる、その層での$Y$座標の$max$値を$latest_i$と表現することにすると、第1層のブロック$[1,4,5]$は$latest_1=2$秒後に消え、第2層のブロック$[2,3,7]$は$latest_2=4$秒後に消えます。第$i$層のブロックが事前にわかっているとすると、$latest$配列の構築は$O(N)$で行うことができます。
また、第$i$層にどのブロックが含まれるかについては、各$x$座標に含まれるブロックについてそれぞれ$Y$座標の昇順でソートしておき、一番$Y$座標の小さいものからグリッド幅$W$個ずつ掬うことで$O(NlogN+N)$で計算することができます。
以上で全ての準備が整いました。
あとは、時刻$t$を$T_1≦T_2≦…≦T_Q$の順に進め、次に消去するべき層$cur$を$0$で初期化しておき、尺取り法の要領で$t>latest[cur]$であればその層に含まれるブロックを全消ししてcur++をするだけです！
最後に、クエリ順を時刻の昇順でソートしていることを思い出し、出力を元のクエリの順序に戻すことを忘れないでください。
以上で、$O(NlogN+Q)$となりこの問題を高速に解くことができました。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, W] = input[0].split(" ").map(Number);
const [X, Y] = [[], []];
for (let i = 0; i < N; i++) [X[i], Y[i]] = input[i + 1].split(" ").map(Number);
const Q = Number(input[N + 1]);
// col:= 各X座標について、存在するブロックのY座標と番号を管理
const col = Array(W).fill().map(() => []);
for (let i = 0; i < N; i++) {
[X[i], Y[i]] = [X[i] - 1, Y[i] - 1];
col[X[i]].push([Y[i], i]);
}
// Y座標の昇順にソートしておく
for (let i = 0; i < W; i++) col[i].sort((a, b) => a[0] - b[0]);
// latest[i]:= 無限時間経過した後、i番目に消去されるブロックのうち最遅のもののY座標
const latest = [];
// 1層目から順に、その層に存在するブロックのY座標の最大値をlatestに追加していく
let f = true;
while (f) {
let l = latest.length;
let max = -1;
for (let i = 0; i < W; i++) {
// もしi番目の層にブロックが存在しないような列があれば、継続フラグをfalseにして脱出
if (col[i][l] === undefined) f = false;
else max = Math.max(max, col[i][l][0]);
}
// 継続フラグがtrueの場合、latestに最大値を追加
if (f) latest.push(max);
}
// ev:= 各クエリの時間、消去するブロックの番号、クエリ番号を管理するイベント
const ev = [];
for (let i = 0; i < Q; i++) {
let [t, p] = input[N + i + 2].split(" ").map(Number);
ev.push([t, p, i]);
}
// 時間の昇順にソートしておく
ev.sort((a, b) => a[0] - b[0]);
// rem_ls:= 消去されるブロックの番号を管理するSet
let rem_ls = new Set();
// cur:= 何層目までのブロックが消去されたかを尺取り法の要領で管理する変数
let cur = 0;
// ans:= 各クエリに対する答えを管理する配列（イベントソートしているため、クエリ順に直す必要がある）
let ans = Array(Q).fill("No");
for (let i = 0; i < Q; i++) {
let [t, p, idx] = ev[i];
p--;
// tがlatest[cur]より大きい場合、cur層目までのブロックは全て消去されている
while (cur < latest.length && t > latest[cur]) {
for (let j = 0; j < W; j++) rem_ls.add(col[j][cur][1]);
cur++;
}
// p番目のブロックが消去されている場合はNo、残っている場合はYes
if (rem_ls.has(p)) ans[idx] = "No";
else ans[idx] = "Yes";
}
console.log(ans.join("\n"));
}
Main(require("fs").readFileSync(0, "utf8"));
E - Hierarchical Majority Vote
公式解説のエレガントな解法を見て驚きましたが、私の頭は凡人なので、最初に$A$を縮約することで得られる文字列全てと目標とする文字を求めてから、木DPのように再帰することでこの問題を解きました。
イメージとしては以下のとおりです。この図の場合$A$は010111010なので、操作の結果は0となります。これを1に変化させるためには次の手順で最小操作回数を探索します。
- 深さ2の文字列
010について、最小操作回数で過半数が1となることを目指す - 先頭の
0を1に変えるためのコストは$2$、真ん中はすでに1であるためコスト$0$、そして末尾の0を1に変えるためのコストは$1$である - 元から
1であった文字を含め、コストが小さい方から順に、深さ2の真ん中と末尾を$1$に変更する - 以上で深さ2の文字列が
011となり、結局深さ1の文字列をコスト$0+1=1$で1に変化させることができた
要するに、一つ下の階層を見て、1に変えるためのコストで小さい方から２つを選ぶという処理を葉→根の順に再帰的に行うことで最小操作回数を求めることができるというわけです。
計算量としては、$A$の遷移しうる配列を構築する分若干定数倍が重いかもしれませんが、$O(3^N)$なので十分高速です。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const N = Number(input[0]);
const A = input[1].split("").map(Number);
// structure(arr, i):= 次に操作をして得られる文字列を返す
const structure = (arr, i) => {
let n_arr = [];
for (let j = 0; j < 3 ** (N - i); j += 3) {
let [zeros, ones] = [0, 0];
for (let k = 0; k < 3; k++) {
if (arr[j + k] === 0) zeros++;
else if (arr[j + k] === 1) ones++;
}
if (zeros > 1) n_arr.push(0);
else if (ones > 1) n_arr.push(1);
}
return n_arr;
};
// tree:= 1回ずつ操作をして得られる文字列を順番に格納する
let tree = [A];
for (let i = 0; i < N; i++) tree.push(structure(tree[i], i));
// 小→大の順番の方が再帰がやりやすいので逆順にする
tree = tree.reverse();
// s:= AにN回操作を行った後に得られる文字、g:= 目標とする文字
const s = tree[0][0];
const g = s ^ 1;
// dfs(i,j):= 深さi、位置jの文字をgにするために必要な最小の操作回数を返す
const dfs = (i, j) => {
// 今見ている文字がgなら何も変える必要がないので0を返す。その上でもしiが最大深さならば1を返す
if (tree[i][j] === g) return 0;
if (i === N) return 1;
// 次の深さの対応する3つ文字をgにするために必要な最小の操作回数を取得し、昇順にソートする
let st = [dfs(i + 1, 3 * j), dfs(i + 1, 3 * j + 1), dfs(i + 1, 3 * j + 2)];
st.sort((a, b) => a - b);
// 過半数がgとなればよい。したがってgにするための最小操作回数の小さい方2つの合計がdfs(i,j)の答え
return st[0] + st[1];
};
console.log(dfs(0, 0));
}
Main(require("fs").readFileSync(0, "utf8"));
今年中の入水を目指しているのですが、今のところいいペースで進んでいるように見えます。
とはいえ、毎回コンテスト成績が1000~1200perfあたりをうろちょろしているので、もっと地力を上げて平均perfをupさせるか、水上位や青を本番で解いて一発を当てるかのどちらかができないと厳しくもあります。
最近は難問耐性をつけるために青をメインに解き始めました。
今後本番で高perfを出して、みなさんにいい報告ができるように頑張りたいです。
