ABC 242

Table of Contents

A - T-shirt

問題

を出力

提出コード

B - Minimize Ordering

問題

文字を昇順に並べ替えたものが答え

提出コード

C - 1111gal password

問題

$dp[i][x]$: $i$ 桁の整数で, $i$ 桁目が $x$ である問題の条件を満たす整数の場合の数とする. また初期状態として $\forall x, dp[1][x] = 1$ とする.

$i$ 桁の整数で $i$ 桁目が $x$ となるような整数の場合の数は $i-1$ 桁目の数と $x$ の差の絶対値が1以下となるような $i-1$ 桁の整数の数の合計であるから

dp[i][x] += dp[i-1][x]
if (x-1 >= 1) dp[i][x] += dp[i-1][x-1]
if (x+1 <= 9) dp[i][x] += dp[i-1][x+1]

となる.

提出コード

D - ABC Transform

問題

簡単のため 0-index で考える. よって文字列の一番左は 0 文字目と数える. また A, B, C をそれぞれ 0, 1, 2 に置き換えて考える.

文字列を置き換える操作をするたびに文字列長は2倍になる. $10^{18} < 2^60$ より, 60 回以上の操作によってできる文字列の $k$ 番目 ($k <= 10^{18}$) は初期状態の文字列の 0 文字目を起源とする文字だとわかる.

ここで $t$ が 60 以下のときと 60 より大きいときに分けて考える.

$S^{(t)}$ の $k$ 番目の文字はもとの文字列の $\displaystyle \lfloor \frac{k}{2^t} \rfloor$ 番目の文字を起源とする. この文字を $x$ とすると $x$ に $t$ 回操作してできる文字列の $(k \mod 2^t)$ 番目の 文字は何かという問題に言い換えることができる.

$x$ を起源とし, $t$ 回操作した後にできる文字列の $k$ 番目の文字を $c = f(x, t, k)$ とする. $c$ は $x$ に1度操作をしてできた文字列の $\lfloor k / 2^{t-1} \rfloor$ 番目の文字を 起源とし, この文字列に $t-1$ 回操作してできた文字列の $k \mod 2^{t-1}$ 番目の文字と 言い換えられるから $f(x, t, k) = f((x+\lfloor k/2^{t-1} \rfloor + 1 \mod 3), t-1, k \mod 2^{t-1})$ となる.

例:

0 から始まり 3 回操作してできる文字列について考える. 各回の操作によって次のような数列ができる.

t = 0: 0
t = 1: 1 2
t = 2: 2 0 0 1
t = 3: 0 1 2 0 1 2 2 0

ここで $t = 3$ での 6 番目の数, すなわち $t = 3, k = 6$ のときは $t = 0$ の $\lfloor k / 2^t \rfloor = \lfloor 6 / 2^3 \rfloor = 0$ 番目の文字を起源とする. またこの数は $t = 1$ の $\lfloor k / 2^{t-1} \rfloor = \lfloor 6 / 2^2 \rfloor = 1$ 番目の文字を起源ともする. 逆に考えると操作0回目基準で見ると $f(x, t, k)$, 操作を1回終えた時点を基準にして見ると $f(x^\prime, t-1, k \mod 2^{t-1})$ ($x^\prime = x+\lfloor k/2^{t-1} \rfloor + 1 \mod 3$) となる.

はじめに書いたように $t \geq 60$ のときの $k$ 番目の文字は初期状態の 0 番目の文字を起源とする. ここで 0 番目の文字だけに注目して操作を繰り返すと

… -> 0 -> 1 -> 2 -> 0 -> 1 -> 2 -> … と周期的になっている. これより $t-60$ 回目終了時の 0 文字目の文字を求め $f(x, 60, k)$ を求めればよい. ここで $x$ は $t-60$ 回操作をしたあとの 0 番目の文字.

提出コード