AtCoder Beginner Contest 382
ABCDの4完（41分0ペナ）でした。
1154perfでレートは888->918（+30）となりました（2枚目の瓦！）。
E問題は本当に惜しいところまでできていて、1回の試行で1枚もレアカードを引けない場合の自己ループさえ考慮できていればACでした。F問題もコンテスト後に解いたら20分くらいで解けました。6完青perfあったかも…と考えると悔しいです(T T)
この記事では、A~Fをまとめます。
A - Daily Cookie
求めるべきは、「初日に空き箱であった箱の個数」$+$「中身を食べられて空き箱になった箱の個数（$D$個）」です。前者は文字列$S$の.の個数を全探索により数え上げることで求められます。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, D] = input[0].split(" ").map(Number);
const S = input[1];
let ans = 0;
// すでに空き箱である箱の個数を調べる
for (let i = 0; i < N; i++) if (S[i] == ".") ans++;
// 元から空き箱だった箱と中身を食べられて空き箱になった箱の個数の合計が答え
console.log(ans + D);
}
Main(require("fs").readFileSync(0, "utf8"));
B - Daily Cookie 2
文字列$S$を後ろから順に見ていき、クッキーがあれば食べてその位置を空き箱にする、という処理を繰り返します。なお、String型はイミュータブル（中身を変更できない）ので、一度配列に変換する必要があります。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
let [N, D] = input[0].split(" ").map(Number);
const S = input[1].split("");
// 後ろから順に確認する
for (let i = N - 1; i >= 0; i--) {
// クッキーがあればそれを食べ、空き箱にする
if (S[i] == "@") {
D--;
S[i] = ".";
// 合計でD個食べたらループを終了する
if (D == 0) break;
}
}
console.log(S.join(""));
}
Main(require("fs").readFileSync(0, "utf8"));
C - Kaiten Sushi
色々解き方はあると思いますが、二分探索で解く方法を紹介します。
「例示は理解の試金石」ということで、まずは美食家$A=[3,8,2]$, 流れる寿司$B=[5,2,1]$という例を考えてみましょう。最初に流れてくる$B_1=5$ですが、$A_1=3<B_1$のため一人目の美食家に食べられてしまいます。ここで重要な事実として、二人目以降の美食家は美食度$3$以上の寿司は永遠に食べられません。 二人目以降は美食度$2$以下の寿司しか回ってこないのです。しかも、この例の場合二人目は$A_2=8$の美食家なので美食度2以下の寿司が回ってきても食べようとはしません。つまり、二人目の人は永遠に寿司を食べることができない ということになります。ということは、二人目については答えになりようがありませんので考えなくて良いことになります。
これを一般化すると、「配列$A$のうち、単調減少となる部分列だけを考慮すれば十分」ということがいえます。また、単調性が保証される配列に対しては二分探索が適用できます。上記の例であれば、配列$A$のうち単調減少の部分列$L=[3,2]$だけを考えてあげれば、$B_1=5$は$3$よりも左、$B_2=2$は$3$と$2$の間、$B_3=1$は$2$よりも右、というのが二分探索によりクエリ1回あたり$O(logN)$で求められます。
以上が方針の概要ですが、実際には配列$L$にインデックスの情報も持たせ、「その値は元の配列$A$の何番目に当たるのか？」を参照できるようにします。このようにすれば全体計算量が$O(NlogN)$となり十分高速にこの問題を解くことができました。
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 B = input[2].split(" ").map(Number);
// Aの単調減少となる部分列を抜き出す（例：L = [7,5,4,2]）
const L = [];
for (let i = 0; i < N; i++) {
if (L.length == 0) L.push([A[i], i]);
else if (A[i] < L[L.length - 1][0]) L.push([A[i], i]);
}
let ans = [];
for (let i = 0; i < M; i++) {
const idx = lower_bound(L, B[i]);
// idxがL.lengthのときは-1,それ以外は元の配列Aにおけるインデックスを出力
if (idx == L.length) ans.push(-1);
else ans.push(L[idx][1] + 1);
}
console.log(ans.join("\n"));
}
// 基準値key以下(右側に位置する)であればOK
const isOK = (arr, mid, key) => arr[mid][0] <= key;
const lower_bound = (arr, key) => {
let ng = -1;
let ok = arr.length;
while (ok - ng > 1) {
let mid = Math.floor((ok + ng) / 2);
if (isOK(arr, mid, key)) ok = mid;
else ng = mid;
}
return ok;
};
Main(require("fs").readFileSync(0, "utf8"));
D - Keep Distance
「制約$N$が非常に小さい」ことと、「辞書順に出力」というワードから即座にdfs全探索を考えました。そもそも辞書順に出力させるということはどう頑張っても線形時間かかってしまうため、全探索を前提にどうすれば計算量を最小限に抑えることを考えるのが良いです。
これは例を考えれば比較的単純です。例えば、$N=3, M=23$の制約で配列を組むことを考えます。このとき、初項が$3$であればギリギリ$[3,13,23]$という配列が作成できますが、初項が$4$となった時点でドボンです。どう頑張っても、各要素がそれぞれ$[4,14,24]$以上となり、第三項が$23$より大きくなってしまいます。
一般に、構築途中の配列$s$の最後尾$z$に対し未確定の要素が$x$個あると仮定して、$z + 10x > M$が成り立つ場合、絶対に長さ$N$の配列を構築することはできません。そのため、配列を構築する際のループの最初に必ずこれを評価し、「今後絶対に長さ$N$の配列を作ることができない」とわかった分岐については探索を打ち切ることにします。これを枝刈りといいます。
以上を踏まえて、単純なforループで枝刈り全探索をして配列を構築すれば、答えは自然と辞書順になります。答えを出力用の配列arrに格納し、最後にarrの長さと要素を1行ずつ出力することで、この問題を解くことができました。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, M] = input[0].split(" ").map(Number);
let arr = [];
const dfs = (n, s) => {
// 終了条件は、構築した配列sの長さがNとなったとき
if (n == N) {
arr.push(s.join(" "));
return;
// 構築の途中で、条件を満たす配列を作れないことが確定した場合は探索を打ち切る
} else if (s[s.length - 1] + 10 * (N - s.length) > M) return;
// 現在構築している配列sの最後尾に10以上の数値を足したものを新しく追加して再帰
// Mを超えてはいけないことに注意
for (let i = 10; i + s[s.length - 1] <= M; i++) {
s.push(s[s.length - 1] + i);
dfs(n + 1, s);
s.pop();
}
};
// 最初の1つだけ配列に入れた状態でdfs
// 再帰に入ってすぐに無駄なループは打ち切られるため、1からMまで調べて問題ない
for (let i = 1; i <= M; i++) dfs(1, [i]);
console.log(arr.length);
console.log(arr.join("\n"));
}
Main(require("fs").readFileSync(0, "utf8"));
E - Expansion Packs
E問題は、レアカードが引けない場合の自己ループdp[i] /= 1 - p[N][0];（ACコード参照）のたった1行に気づくことができず、あえなく敗れてしまいました。
考え方ですが、まず最初に$dp[X]$を「レアカードを$X$枚以上引くまでにパックを引かなければならない回数の期待値」として、それをどうにか高速に求めることができないかを考えます。
ここから思いっきり数学要素もりもりになりますが、できるだけパッションでわかるように説明するので怖がらないでください。
まず、$p_i$を「1回パックを引いた時にレアカードを$i$枚引く確率」とします。すると、実は$dp[X]=1 + \sum_{i=0}^{N} (p_i × dp[X-i])$（式＊） と書くことができます。$\sum$記号が出てきて一見おどろおどろしいのですが、要するに、$dp[X]$を「1回の試行」と「1回の試行で$i$枚のレアカードが引けた場合に、余った分の$X-i$枚以上レアカードを引くまでの回数の期待値」に分解しているだけです。こうすれば、$dp$テーブルを値が小さい順に構築すれば高速に答えを求められそうだという目処がつきます。なお、これは非常に典型的な考え方で、他にも色々な問題で使えることがあるので覚えておいた方がよいです。
次に、確率$p_i$をどのように求めるべきかを考えましょう。これは少しひらめきが必要かもしれませんが、$p_{i,j}$を「1パック引いたときに$i$枚目までみて、レアカードが$j$枚引ける確率」とすれば、$p_{i+1,j+1}$は「$p_{i,j+1}$でレアカードを引けない確率」と「$p_{i,j}$でレアカードを引けた確率」の和で求められるため、二次元dpの要領で確率テーブル$p_{i,j}$を構築すればよいです。このようにして、知りたい情報である$p_{N,j}=p_i$（1パック全体でレアカードが$i$枚引ける確率）の情報が手に入りました。
ここまでくれば、式＊$dp[X]=1 + \sum_{i=0}^{N} (p_i × dp[X-i])$に当てはめ、$dp$テーブルを小さい順に埋めていくだけです。ただ、最後に一つだけ落とし穴があり、パックに1枚もレアカードがないことがあり得る場合、$dp[X]=1 + p_0×dp[X]+ \sum_{i=1}^{N} (p_i × dp[X-i])$で右辺にも$dp[X]$が来てしまいます。そのため、右辺の$dp[X]$を左辺に移行して、以下の形で計算する必要があります。$$dp[X]=\frac{1+ \sum_{i=1}^{N} (p_i \times dp[X-i])}{1-p_0}$$
以上で全体計算量$O(NX+N^2)$となり、本問題の制約下で十分高速に解くことができました。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, X] = input[0].split(" ").map(Number);
const P = input[1].split(" ").map(Number);
// p[i][j] := 1パック引いたときにi枚目までみて、レアカードがj枚引ける確率
// 1パック引いた時に1,2,...,N枚のレアカードがそれぞれどれくらいの確率で引けるかが知りたい
const p = Array(N + 1)
.fill(0)
.map(() => Array(N + 1).fill(0));
p[0][0] = 1;
for (let i = 0; i < N; i++) {
for (let j = 0; j <= i; j++) {
// レアカードが引けない場合の遷移
p[i + 1][j] += p[i][j] * (1 - P[i] / 100);
// レアカードが引けた場合の遷移
p[i + 1][j + 1] += p[i][j] * (P[i] / 100);
}
}
// dp[i] := i枚以上のレアカードが引けるまでにパックを開ける回数の期待値
const dp = Array(X + 1).fill(0);
for (let i = 1; i <= X; i++) {
// dp[X] = 1 + Σ(p[N][i] * dp[X-i])・・・＊
// すなわち、dp[X]は1回分パックを引いた上で残りのレアカードを引くまでにかかる回数と等しい
// また、この計算式が成り立つとき、dp[1]~dp[X-1]がわかっていればO(1)で計算可能 → dpが最適
dp[i] = 1;
for (let j = 1; j <= N; j++) {
// i-j≦0のときレアカードはX枚以上引けているので終了
if (i - j > 0) dp[i] += p[N][j] * dp[i - j];
}
// レアカードが引けないこともある。上記の式＊の右辺のdp[X]を左に移項するだけでよい
dp[i] /= 1 - p[N][0];
}
console.log(dp[X]);
}
Main(require("fs").readFileSync(0, "utf8"));
F - Falling Bars
この問題は、バーの上下の位置関係を維持しながら、上から落とされるバーの最終位置を求めるものです。バーは一部でも下のバーと接触すれば分裂せずにその高さで停止します。つまり、区間$[l,r]$にバーを置く際、その区間内の現在の最大高さ+1の位置に配置されることとなります。ある区間における最大の高さの取得と、バーの積み上げは区間max遅延セグ木で処理することができます。
遅延セグ木はライブラリを用意しておくと良いです。そうすれば、こうした問題はライブラリペターっ、で簡単に解くことができます。
本番ではE問題に時間を取られてこの問題に着手できず、惜しいチャンスを逃してしまいました…
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [H, W, N] = input[0].split(" ").map(Number);
const [R, C, L] = [[], [], []];
const bar = [];
for (let i = 0; i < N; i++) {
[R[i], C[i], L[i]] = input[i + 1].split(" ").map(Number);
bar.push([R[i], C[i], L[i], i]);
}
// 下のバーから順番に答えを求めていくため、Rの降順でソート
bar.sort((a, b) => b[0] - a[0]);
// 区間max遅延セグ木
const seg = new LazySegTree(W, {
op: (x, y) => Math.max(x, y),
e: () => 0,
map: (f, x) => Math.max(f, x),
cmp: (f, g) => Math.max(f, g),
id: () => 0,
});
let ans = new Array(N).fill(0);
for (let i = 0; i < N; i++) {
let [r, c, l, idx] = bar[i];
// バーを置く区間[c - 1, c - 2 + l]の中で一番高いところの高さを取得する
let max = seg.prod(c - 1, c - 2 + l);
// その一つ上の、区間[c - 1, c - 2 + l]にバーを置く
seg.applyRange(c - 1, c - 2 + l, max + 1);
// maxは下から見て何番目かのため、上から見て何番目か、に直す
ans[idx] = H - max;
}
console.log(ans.join("\n"));
}
// 以下、LazeSegTreeクラス。本記事では省略とする。
パフォーマンスは平凡でしたが、青diffのEと水diff上位のFをあと一歩で解けそうなところまできていたため、今までで一番成長を感じられたABCでした。今後は難しい問題に解き慣れることで、水diff以上でも60分以内を目安に解けるよう精進していきたいです。