AtCoder Beginner Contest 406
ABCDの4完（23分0ペナ）でした。
1267perfでレートは1116->1132（+16）となりました。
今回はA〜Dの解説と、upsolveしたE,Fの感想を記載します。
A - Not Acceptable
$C$時$D$分の提出が、$A$時$B$分の締切前である必要があるということなので、
- $C<A$のとき
Yes - $C=A$のとき、$D<B$であれば
Yes、そうでなければNo - $C>A$のとき
No
という整理となります。
これを丁寧に場合分けして出力すればこの問題に正解できます。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [A, B, C, D] = input[0].split(" ").map(Number);
if (A > C || (A === C && B > D)) console.log("Yes");
else console.log("No");
}
Main(require("fs").readFileSync(0, "utf8"));
B - Product Calculator
愚直に都度計算して、$(K+1)$桁になっている場合は$1$に変更するという処理を繰り返せば良いです。
計算結果は$10^{18}$以上になる可能性があるため、BigInt型を利用しましょう。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, K] = input[0].split(" ").map(Number);
let max = 10n ** BigInt(K);
const A = input[1].split(" ").map(BigInt);
let cur = 1n;
for (let i = 0; i < N; i++) {
cur *= A[i];
if (cur >= max) cur = 1n;
}
console.log(cur.toString());
}
Main(require("fs").readFileSync(0, "utf8"));
C - ~
数式で書かれた複雑な条件が多くとっつきにくいですが、平易な言葉で表すと、
- 数列の長さが4以上
- 左から右へ順に見ると、最初は単調に増加してどこかで山に到達する
- その後単調に減少して、どこかで谷に到達する
- それからは単調に増加し続ける
ここで、$P$が$1〜N$の並び替えであって同じ数字が二度現れないため、常に$P_i≠P_{i+1}$なのもポイントです。
図で表すと以下のようになります。
つまり「~」のように「山」→「谷」のような形であればよいです。
したがって、上図のように「山」→「谷」となる範囲を一つ見つけて、
- 山から左にはどこまで（単調減少で）伸ばせるのか
ここで、「~」の左端となりうる点の個数を$l$とする - 谷から右にはどこまで（単調増加で）伸ばせるのか
ここで、「~」の右端となりうる点の個数を$r$とする
をそれぞれ数え上げることで、その「山」「谷」をペアに持つチルダ型数列の組み合わせを$l×r$で計算することができます。
なお、「山」と「谷」がそれぞれ一つ以上ある配列をなすためには必ず長さが4以上である必要があるため、一つ目の条件「数列の長さが4以上」は実質あまり気にする必要がありません。
これは、配列を左から右に順に見ていって、最後に見た山の位置$\text{lastMt}$をうまく管理することで$O(N)$で数え上げることができます。
実装の流れとしては、以下のとおりです。
- $\text{lastMt}$を$-1$に初期化する
- 左から右へ順に見ていって、山か谷を見つける
- 山を見つけたら、$\text{lastMt}$をその位置に更新する
- 谷を見つけたら、$\text{lastMt}$が$-1$なら何もせずにスキップする。そうでなければ、前回の山から単調減少が続く限り左に進み$l$を数え、今見ている谷から単調増加が続く限り右に進み$r$を数え、$l×r$を計算して$\text{lastMt}$を$-1$に初期化する
- 2.に戻る
なお、一見4.で二重ループが発生していて$O(N^2)$のように見えますが、
- $l$を数えるために（右から左へ）単調減少となる範囲を各要素についてそれぞれ1回
- $r$を数えるために（左から右へ）単調増加となる範囲を各要素についてそれぞれ1回
しか見ませんので、高々$2N$回の計算量となり全体計算量が$O(N)$に抑えられます。
以上でこの問題を高速に解くことができました。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const N = Number(input[0]);
const P = input[1].split(" ").map(Number);
// lastMt: 前回見た山の位置。一度~を計算したら-1に初期化する
let lastMt = -1;
let ans = 0;
for (let i = 1; i < N - 1; i++) {
// 山を見つけたらlastMtを更新
if (P[i - 1] < P[i] && P[i] > P[i + 1]) lastMt = i;
// 谷を見つけたら~の組み合わせを計算。
if (P[i - 1] > P[i] && P[i] < P[i + 1]) {
// もしlastMtが-1なら、山が見つかっていないor前回の山が計算済みのためスキップ
if (lastMt == -1) continue;
// 山から左の要素の数をl、谷から右の要素の数をrとして愚直に数える
let [l, r] = [0, 0];
for (let j = lastMt - 1; j >= 0; j--) {
if (P[j] < P[j + 1]) l++;
else break;
}
for (let j = i + 1; j < N; j++) {
if (P[j - 1] < P[j]) r++;
else break;
}
ans += l * r;
lastMt = -1;
}
}
console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));
D - Garbage Removal
各行、各列それぞれでゴミがある座標をハッシュセット管理して、クエリに従って必要に応じてそれぞれでゴミを除去します。なお、除去の直前に残っているゴミの個数はSet.sizeプロパティが$O(1)$でアクセスできることを利用して高速に求めます。
具体例を示します。
例）3x2のマス目の場合
初期状態
ox
xo
oo
o:ゴミが落ちている
x:ゴミが落ちていない
行のゴミの管理配列row
row[1]: 1
row[2]: 2
row[3]: 1, 2
列のゴミの管理配列col
col[1]: 1, 3
col[2]: 2, 3
↓
クエリ1: 1行目のゴミの個数を出力して、1行目のゴミを全て処理する
処理
1. row[1]のsizeを取得して出力する
2. row[1]に含まれる座標それぞれについて、col配列側の1を削除する
3. row[1]の座標を全て消去する
行のゴミの管理配列row
row[1]: - (null)
row[2]: 2
row[3]: 1, 2
列のゴミの管理配列col
col[1]: 3
col[2]: 2, 3
↓
…（同様の処理が続く）
Setを利用しているため、各行、各列のゴミのある座標は高速にすることができ、処理2,3の計算量は全体としてゴミの個数と一致して$O(N)$となります。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [H, W, N] = input[0].split(" ").map(Number);
const [X, Y] = [[], []];
for (let i = 0; i < N; i++) {
const [x, y] = input[i + 1].split(" ").map(Number);
X.push(x - 1);
Y.push(y - 1);
}
const row = new Array(H).fill(0).map(() => new Set());
const col = new Array(W).fill(0).map(() => new Set());
for (let i = 0; i < N; i++) {
row[X[i]].add(Y[i]);
col[Y[i]].add(X[i]);
}
const Q = Number(input[N + 1]);
const ans = new Array(Q).fill(0);
for (let i = 0; i < Q; i++) {
let [q, u] = input[i + N + 2].split(" ").map(Number);
u--;
if (q === 1) {
ans[i] = row[u].size;
for (const v of row[u]) col[v].delete(u);
row[u].clear();
} else {
ans[i] = col[u].size;
for (const v of col[u]) row[v].delete(u);
col[u].clear();
}
}
console.log(ans.join("\n"));
}
Main(require("fs").readFileSync(0, "utf8"));
E - Popcount Sum 3
コンテスト後にビット桁dpでACしました。
より具体的には、各ビット桁ごとに次のビット桁dpで「そのビット桁が1であるような、popcountが$K$であるN以下の個数はいくつか」を求めさえすれば、$$\sum(そのビット桁だけが立っている値の大きさ)×(\text{popcount}がKとなるN以下の個数)$$でこの問題の答えが求められます。
あとは丁寧に遷移を書けばよいです。
桁dpの解説は他の記事に譲ります。（解説記事）
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const T = Number(input[0]);
const testCases = [];
for (let i = 0; i < T; i++) testCases[i] = input[i + 1].split(" ").map(BigInt);
const mod = 998244353n;
const ans = new Array(T).fill(0n);
for (let i = 0; i < T; i++) {
const [N, K] = testCases[i];
let num_k = Number(K);
let maxBit = N.toString(2).length;
let cur = 0n;
for (let j = 0; j < maxBit; j++) {
const thisBit = 1n << BigInt(j);
const dp = new Array(maxBit + 1).fill(0).map(() => new Array(2).fill(0).map(() => new Array(num_k + 1).fill(0n)));
dp[0][1][0] = 1n;
for (let k = 0; k < maxBit; k++) {
for (let l = 0; l < 2; l++) {
for (let m = 0; m < num_k; m++) {
if (dp[k][l][m] === 0n) continue;
let nexBit = (N >> BigInt(maxBit - 1 - k)) & 1n;
if (nexBit === 1n) {
dp[k + 1][l][m + 1] += dp[k][l][m];
dp[k + 1][l][m + 1] %= mod;
if (maxBit - 1 - k !== j) {
dp[k + 1][0][m] += dp[k][l][m];
dp[k + 1][0][m] %= mod;
}
} else {
if (l === 0) {
dp[k + 1][0][m + 1] += dp[k][l][m];
dp[k + 1][0][m + 1] %= mod;
}
if (maxBit - 1 - k !== j) {
dp[k + 1][l][m] += dp[k][l][m];
dp[k + 1][l][m] %= mod;
}
}
}
}
}
let sum = 0n;
sum += dp[maxBit - j][0][num_k] + dp[maxBit - j][1][num_k];
sum %= mod;
for (let k = maxBit - j + 1; k < maxBit + 1; k++) {
for (let l = 0; l < 2; l++) {
sum += dp[k][l][num_k];
sum %= mod;
}
}
cur += sum * thisBit;
cur %= mod;
}
ans[i] = cur;
}
console.log(ans.join("\n"));
}
Main(require("fs").readFileSync(0, "utf8"));
余談ですが、私は桁dpそのものは適切に書けていましたが、popcountが$K+1$のものを含めて計算してしまっていました。
本番ではたくさん時間が残っていたにもかかわらずそれに気づくことができなかったので少し歯痒いです。
F - Compare Tree Weights
木上のオイラーツアーというアルゴリズムを初めて知りました。
名前が仰々しいですが、dfsして行きがけ順と帰りがけ順を記録しておくことで、FenwickTreeやセグメント木での区間クエリによって木上の部分木クエリ、パスクエリができるというものらしいです。
こちらの解説記事で履修しました。参考までにACコードを貼っておきます。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const N = Number(input[0]);
const [U, V] = [[], []];
for (let i = 0; i < N - 1; i++) [U[i], V[i]] = input[i + 1].split(" ").map(Number);
const Q = Number(input[N]);
const G = new Array(N + 1).fill(0).map(() => []);
for (let i = 0; i < N - 1; i++) {
G[U[i]].push(V[i]);
G[V[i]].push(U[i]);
}
const In = new Array(N + 1).fill(-1);
const Out = new Array(N + 1).fill(-1);
const dist = new Array(N + 1).fill(0);
let order = 0;
const dfs = (v) => {
In[v] = order;
order++;
for (const u of G[v]) {
if (In[u] !== -1) continue;
dist[u] = dist[v] + 1;
dfs(u);
}
Out[v] = order;
order++;
};
dfs(1);
const ans = [];
const seg = new SegTree(2 * N, (x, y) => x + y, 0);
for (let i = 0; i < N; i++) seg.set(In[i + 1], 1);
let weightsSum = N;
for (let i = 0; i < Q; i++) {
const [q, x, w] = input[N + 1 + i].split(" ").map(Number);
if (q == 1) {
seg.set(In[x], seg.get(In[x]) + w);
weightsSum += w;
}else {
let y = x - 1;
let [u, v] = [U[y], V[y]];
if (dist[u] > dist[v]) [u, v] = [v, u];
let sum = seg.prod(In[v], Out[v] + 1);
let other = weightsSum - sum;
ans.push(Math.abs(other - sum));
}
}
console.log(ans.join("\n"));
}
// 以下、SegmentTreeクラスのため省略
まとめ
これで3連続水パフォーマンスとなりレートの伸びが順調なのですが、今回は難易度が低めの問題を早く解けただけなので、あまり手応えがありません。
AtCoder Rating Estimatorによると、次回での入水に向けて必要なパフォーマンスは1680以上ということです。
青パフォで入水できたらかっこいいのですが、そのために必要な精進が最近はできていない気がするのであまり期待していません笑
ただ、いい結果を出せるように頑張りたいと思います。