AtCoder Beginner Contest 387
ABDの3完（70分4ペナ）でした。
898perfでレートは969->962（-7）となりました。
明けましておめでとうございます。私は新年早々微冷えして良いお年を過ごせていませんが、みなさまは良いお年をお過ごしでしょうか？
いや〜、C問題は地獄でしたね。気合いで愚直に数え上げるか、桁DPでエレガントに解くか迷い、結局どちらの方針でもコンテスト時間内に正しいコードを書けませんでしたorz
コンテスト後に、初心者でも理解できるような桁DPの解法で無事にACすることができましたので、本記事ではそちらを紹介します。
今回はA~Dをまとめます。
A - Happy New Year 2025
さすがAtCoder、新年一発目はみんなが解ける簡単な問題を出してくれましたね。
$A$、$B$どちらも小さいのでオーバーフローを気にする必要はありません。
問題文の通りに、$A$と$B$を足して$2$乗したものを出力しましょう。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [A, B] = input[0].split(" ").map(Number);
console.log((A + B) ** 2);
}
Main(require("fs").readFileSync(0, "utf8"));
B - 9x9 Sum
盤面は$81$マスしかないため、全部のマスを一つずつ確認しても十分高速に間に合います。
$i$行$j$列目には$i×j$が書かれているので、その数字が$X$かどうかを確認し、$X$以外の数字の総和を出力すればこの問題を解くことができます。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const X = Number(input[0]);
let ans = 0;
for (let i = 1; i <= 9; i++) {
for (let j = 1; j <= 9; j++) {
if (X !== i * j) ans += i * j;
}
}
console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));
C - Snake Numbers
本番中、公式解説のように桁DPを使って一発でヘビ数を求めようとしましたが、正確に遷移を書くのが難しくACすることができませんでした。
なお、「ヘビ数」とは先頭の桁（最も大きい位）の数字がそれ以外のどの桁の数字よりも真に大きくなるような$10$以上の正整数をいいます。以下の解法では、便宜的に$1〜9$までの$1$桁の数値もヘビ数とみなして説明を試みます。
筆者が難しいと思ったのは、「$N$以下の正整数において、最上位桁が異なる場合がありえる」ところの処理です。
例えば、$N=587$としたら、$5xx$の形のヘビ数だけでなく、$4xx$や$3xx$、$0xx$の形のヘビ数も数え上げる必要があります。
この部分が、桁DPの難易度を一段階底上げしているように感じました。
※ここで言う$0xx$は、2桁の数として解釈され、例えば$09x$のように1桁目が0で2桁目が新たな最上位桁となるケースを指します。
逆に言えば、「$N$以下で、桁数と最上位桁の数が$N$と同じのヘビ数の総数」ならば、最上位桁が固定されるためヘビ数を数えやすくなり、比較的簡単に解くことができそうです。これは、後述する2変数の桁DPにより$O(logN)$で解くことができます。
「$N$以下で、桁数と最上位桁の数が$N$と同じのヘビ数の総数」を解く方法が確立できれば、あとは$N$の桁数以下で、最上位桁ごとに同じ方法を適用すれば済みます。例えば$N=587$としたら、$1,2,...,9,1x,2x,...,9x,1xx,2xx,3xx,4xx$を同じ方法で数え上げるのです。この全探索は各桁ごとに1~9までの数字を置く通り数ですから、高々$18桁×9通り=162回$で済み、オーダー記法だと$O(logN)$となります。
方針
1. $N$以下で、桁数と最上位桁の数が$N$と同じのヘビ数の総数を求める
2. $N$を超えない範囲で、全ての桁数と最上位桁の組み合わせに対して1.をやる！
全体としては$O(log^2N)$で今回の制約において十分高速にこの問題を解くことができました。
あれ、メンタルモデルとしてはすごく簡単に見えてきませんか？
まあ、この解法で一番ややこしいのは「任意に与えられた$N$以下で、桁数と最上位桁の数が$N$と同じのヘビ数の総数」を数え上げる桁DPのパートですよね。
桁DPパート
桁DPを使って、「$N$以下で、桁数と最上位桁の数が$N$と同じのヘビ数の総数」を求める方法を考えましょう。まず、 $dp$テーブルを次のように定義します。
$$dp[i][j]:= iは左から何桁目か、jは未満フラグでj=1のときN未満であることが確定しており、j=0のとき確定していない$$
次に、$dp$テーブルの遷移を考えます。今見ている桁について、前の桁の寄与がどれだけかを考えてみましょう。
$i$桁目までで$N$未満であることが確定している（$j=1$）場合のヘビ数の総和$dp[i][0]$は、次のように表すことができます。ここで、$lead:=Nの最上位桁の数$、$ni:=Nのi桁目の数$です。
$$dp[i][1] = dp[i-1][1] \cdot \text{lead} + dp[i-1][0] \cdot \min(ni, \text{lead})$$
第一項は前の桁の時点で$N$未満であることが確定しているため、$0$から$lead-1$までの$lead$通り追加で選ぶことができるということを表します。
第二項は前の桁の時点では$N$未満かどうかは確定していないため、$0$から$lead-1$または$ni-1$の小さい方まで選ぶことになります。
ここで、二つの疑問があると思います。まず、なぜ$\text{min}$を取らなければならないかというと、$ni$まで選ぶことにすると$N$より大きくなってしまうからです。例えば、$N=4321$で$current=43xx$として、次に3を選ぶと$433x$となり$N$より大きくなってしまいますよね。
N = 4321
current = 433x →xに何を入れてもNより大きくなってしまうのでNG
次の疑問として、$ni$ではなく$ni-1$なのはなぜかと思われるかもしれません。これは、次に$ni-1$を選ぶと$N$未満であることが確定するが、$ni$を選ぶと確定しなくなるからです。再度$N=4321$で$current=43xx$まで決まっているという例を考えると、次に$1$を選ぶと$431x$となり、$x$に何を入れても$N$以下であることが確定します。一方で、$2$を選んでしまうと$432x$となり、次の桁でも$x$が$N$を超えないかどうかを気にする必要が出てきます。
したがって、$0〜ni-1$は未満フラグの立っていない$dp[i][1]$の方に遷移させ、$ni$だけ未満フラグの立っている$dp[i][0]$の方に遷移させます。
N = 4321
current = 431x
→xに何を入れてもNより大きくなることはないので、純粋にlead=4より小さいかどうかだけ気にすれば良い
current = 432x
→x = {0,1,2,3}の何を入れてもヘビ数の条件を満たすが、x>1のときNより大きくなってしまう
そこで、$dp$テーブルの$j=0$の場合、すなわち$dp[i][0]$の遷移は次のように表すことができます。
$$dp[i][0] = 1 \quad \text{if } n_i < \text{lead} \text{ and } dp[i-1][0] > 0$$
$0 \quad \text{otherwise}$
$ni< lead$の条件は、$ni$をそのまま採用してもヘビ数かどうかを表します。
例えば$N=4351$として、$current=43xx$のとき、次に$5$を選んで$435x$としようとしても、最上位桁の$4$を超えてしまうためヘビ数ではなくなってしまいます。したがって、$ni≧lead$のとき条件を満たしません。
$dp[i-1][0]>0$の条件は、前の桁で$N$以下かどうかがギリギリのヘビ数のパターンがあるかどうかを表します。$N=42515$のとき、三桁目までで最大のヘビ数は$423xx$のパターンなので、四桁目を見る時には全てのパターンがヘビ数であることが確定しているため、$N$以下かどうかをいちいち確認する必要がないというわけです。
以上の$dp$テーブルを用いて、最上位桁の次の桁から順に一桁ずつ処理していきます。全ての桁を処理し終えた後、最終桁の$dp[i][0]$と$dp[i][1]$を合計することで、条件を満たすヘビ数の総数を得ることができます。
ここまで頑張って読んでいただいてありがとうございました。
もしうまく伝わっていなかったらすみません。
JavaScriptとPythonの正解例を載せておきますので、参考にしていただけると嬉しいです。
// JavaScript版コード
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [L, R] = input[0].split(" ").map(BigInt);
// b_getLength(a): aの桁数を返す
// b_getNumber(a, i): aのi桁目の数値を返す
// b_min(...arr): arrの最小値を返す
const b_getLength = (a) => a.toString().length;
const b_getNumber = (a, i) => BigInt(a.toString()[i]);
const b_min = (...arr) => arr.reduce((a, b) => (a < b ? a : b), arr[0]);
// count(n): nと同じ桁数で、最上位の数字が同じであるn以下のヘビ数の総数を返す
const count = (n) => {
// len:= nの桁数 lead:= nの最上位桁の数値
const len = b_getLength(n);
const lead = b_getNumber(n, 0);
// dp[i][j]:= i桁目までヘビ数がいくつあるか。jは未満フラグ。
// j=1のときn未満が確定しており、j=0のときn以上となる可能性があることを示す。
const dp = Array(len).fill(0).map(() => Array(2).fill(0n));
dp[0][0] = 1n;
for (let i = 1; i < len; i++) {
const ni = b_getNumber(n, i);
// 前の桁で未満フラグが立っている時、次の桁で選択できる数はlead通りある
// 未満フラグが立っていない時、niを超えることはできないので通り数はniかleadのどちらか小さい方
dp[i][1] += dp[i - 1][1] * lead + dp[i - 1][0] * b_min(ni, lead);
// 前の桁で未満フラグが立っていない、かつniがleadよりも小さい時に限り、次の桁でもn以上か考慮が必要
if (dp[i - 1][0]) dp[i][0] = ni < lead ? 1n : 0n;
}
return dp[len - 1][0] + dp[len - 1][1];
};
// countAll(n): n以下のヘビ数の総数を返す
const countAll = (n) => {
const len = b_getLength(n);
const lead = b_getNumber(n, 0);
let ans = 0n;
// 11~99,111~999,...の順に桁数(i)と最上位の数字(j)ごとにヘビ数を数える
for (let i = 1; i <= len; i++) {
for (let j = 1; j < 10; j++) {
// len桁目がleadよりも大きい時、nより大きい部分を探索しているので終了
if (i == len && j > lead) return ans;
// len桁目がleadと等しい時、n以下のヘビ数を数える
else if (i == len && j == lead) ans += count(n);
// 上に当てはまらない時、jで始まるi桁のヘビ数全てを数える（j999...が最大）
else ans += count(`${j}${"9".repeat(i - 1)}`);
}
}
return ans;
};
// Rまでのヘビ数からL-1までのヘビ数を引けば良い
let ans = countAll(R) - countAll(L - 1n);
console.log(ans.toString());
}
Main(require("fs").readFileSync(0, "utf8"));
# Python版コード
L, R = map(int, input().split())
def count(n):
n = str(n)
lead = int(n[0])
dp = [[0] * 2 for _ in range(len(n))]
dp[0][0] = 1
for i in range(1, len(n)):
ni = int(n[i])
dp[i][1] += dp[i - 1][1] * lead + dp[i - 1][0] * min(ni, lead)
dp[i][0] = 1 if ni < lead and dp[i - 1][0] else 0
return dp[-1][0] + dp[-1][1]
def countAll(n):
n = str(n)
ans = 0
for i in range(1, len(n) + 1):
for j in range(1, 10):
if i == len(n) and j > int(n[0]):
return ans
elif i == len(n) and j == int(n[0]):
ans += count(n)
else:
num = str(j) + "9" * (i - 1)
ans += count(num)
return ans
ans = countAll(R) - countAll(L - 1)
print(ans)
D - Snaky Walk
公式解説と同じ考え方です。
というかこれはほぼBFSでのシミュレーション一択ではないでしょうか。
DFSでACできたという声もちらほら見かけますが、意地悪なテストケースがあったり、定数倍が悪いプログラムを書いてしまったり、遅い言語を使ったりしていると多分落ちると思います。基本的にグリッドでの最短経路の問題では、DFSの計算量は$O(3^{HW})$となる（この問題では当てはまりませんが）ので基本的にBFSを考えるとよいです。
各マスの最短距離の配列$\text{dist}$を次のように定義します。
$$\text{dist}[i][j][f]:=次の移動がf=0の時に横向き、f=1の時に縦向きとなるような(i,j)までの最短距離$$
さらに、BFSのキューには$[y, x, f]$を格納することにします。$y:=行情報、x:=列情報、f:=次の移動方向$です。
このように定義することで、$\text{dist}$とうまく対応づけることができます。
あとは、スタート地点において最初の一歩を横移動にするか、縦移動にするかで両方試して、ゴールまでの距離が短い方を出力すればこの問題を$O(HW)$で解くことができます。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [H, W] = input[0].split(" ").map(Number);
const S = [];
for (let i = 0; i < H; i++) S.push(input[i + 1].split(""));
// スタート地点とゴール地点の座標をメモ
let [sy, sx] = [0, 0];
let [gy, gx] = [H - 1, W - 1];
for (let i = 0; i < H; i++) {
for (let j = 0; j < W; j++) {
if (S[i][j] === "S") [sy, sx] = [i, j];
if (S[i][j] === "G") [gy, gx] = [i, j];
}
}
// 0,2番目に横移動、1,3番目に縦移動を定義すると2の剰余で移動方向を場合分けできる
const dy = [0, 1, 0, -1];
const dx = [1, 0, -1, 0];
// dist[i][j][f]:= (i,j)において、f=0の時は横向き、f=1の時は縦向きに移動する場合の最短距離
let dist = Array(H).fill(-1).map(() => Array(W).fill(-1).map(() => Array(2).fill(-1)));
const bfs = (pos) => {
const que = new Set([pos]);
dist[pos[0]][pos[1]][pos[2]] = 0;
for (let i of que) {
que.delete(i);
for (let j = 0; j < 4; j++) {
const [y, x, f] = i;
const ny = y + dy[j];
const nx = x + dx[j];
// 1とのxorを取ることで0,1をフリップして移動方向の変更を表現できる
const nf = f ^ 1;
if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
if (S[ny][nx] === "#") continue;
// j mod 2 = 0のとき横方向の移動、1のとき縦方向の移動を表す。fと一致しないなら終了
if (j % 2 !== f) continue;
if (dist[ny][nx][nf] !== -1) continue;
dist[ny][nx][nf] = dist[y][x][f] + 1;
que.add([ny, nx, nf]);
}
}
};
// 最初に横方向に移動する場合と、縦方向に移動する場合の両方でBFS
bfs([sy, sx, 0]);
bfs([sy, sx, 1]);
let ans = Number.MAX_SAFE_INTEGER;
if (dist[gy][gx][0] !== -1) ans = Math.min(ans, dist[gy][gx][0]);
if (dist[gy][gx][1] !== -1) ans = Math.min(ans, dist[gy][gx][1]);
console.log(ans === Number.MAX_SAFE_INTEGER ? -1 : ans);
}
Main(require("fs").readFileSync(0, "utf8"));
JavaScriptではFIFOのキューを単純に実装しようとすると$O(N)$のshift()を使う羽目になるのですが、実はSet()のfor…of構文を使うと$O(1)$のFIFOを実現できます。これはネットで検索すると海外の記事で見つけました。リンクを共有するので興味ある方はぜひ確認してみてください。