AtCoder Beginner Contest 192のきろく - Flkanjin’s 競プロ録

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)に参加しましたが、レートが冷えてしまいました... 悲しいね。

A - Star (100点)
B - uNrEaDaBlE sTrInG (200点)
C - Kaprekar Number (300点)
D - Base n (400点)
- 自分が通した解法
- 解説の解法
E - Train (500点)
F - Potion (600点)
結果、感想

A - Star (100点)

$X$ より大きい、 $100$ の倍数で、 $X$ に最も近い数は $100\displaystyle\left\lfloor \frac{X}{100} + 1 \right\rfloor$ であり、求める答えは $$100 \left\lfloor \frac{X}{100} + 1 \right\rfloor - X = 100 - \left(X - 100 \left\lfloor \frac{X}{100} \right\rfloor\right) = 100 - (X \bmod 100)$$ となります。
最後の等号は $$ \left( \frac{X}{100} - \left\lfloor \frac{X}{100} \right\rfloor \right) = \left(\frac{X}{100}\text{ の小数部分}\right) $$であることから導かれます。

B - uNrEaDaBlE sTrInG (200点)

問題名自体が読みにくい文字列(unreadable string)になっていますね。
問題文にあるようなことを素直に実装します。大体の言語でインデックスが0オリジン*1であることに注意しましょう。

C - Kaprekar Number (300点)

C++ではstd::to_string(int)で文字列にし、std::sort(iterator, iterator)でソート、std::stoi(std::string)で整数型にする、ということができます。

D - Base n (400点)

素直に探索しようとしてはまってしまいました。
$X$ が1文字の時に注意です。得られる値は1種類しかないのでこの時の答えは $0$ か $1$ です。 $X \leq M$ のとき $1$ で、そうでないとき $0$ です。

自分が通した解法

場合分けが多いきれいじゃない解法です...
素直に $n$ について $d + 1$ から値を全探索しようとしました。 $n$ 進数の時の $X$ の値を求めて $M$ より大きくなったら終わります。

$X$ が3文字以下の時は $M$ の値や1文字目によってはこの方針では間に合わないです。

$X$ が2文字の時は $X = ab$ (文字列として)とすると、 $ax + b \leq M$ となる $x$ の範囲を求めますが、一次式なので $O(M)$ ぐらいまでの可能性があります。この不等式を解いて $x \leq \displaystyle\frac{M-b}{a}$ となるので、答えは $\displaystyle\max\left\{\frac{M-b}{a} - d,\,0\right\}$ です。

$X$ が3文字の時は $X = abc$ (文字列として)とすると、 $ax^2 + bx + c \leq M$ となる $x$ の範囲を求めますが、二次式なので $O(\sqrt{M})$ ぐらいまでの可能性があります。この不等式は $C = c - M$ として、 $\displaystyle\frac{-b - \sqrt{b^2 - 4aC}}{2a} \leq x \leq \frac{-b + \sqrt{b^2 - 4aC}}{2a}$ となります。勿論、判別式が非正のときは解がなく*2、答えは $0$ です。そうでないとき答えは $\displaystyle\max\left\{\left\lfloor\frac{-b + \sqrt{b^2 - 4aC}}{2a}\right\rfloor - d,\,0\right\}$ となりますが、平方根が出てきて、誤差が怖いのでこの附近をすこし探索します。

解説の解法

$n$ 進数での $X$ の値は単調増加であるので、二分探索によって $n$ の範囲を求めることができます。オーバーフローにしないようにすれば、初期上限は $M + 1$ にすることができます。
オーバーフローしないようにするには

bool ng = false;
long long v = 0;
for(int i(0), i_len(X.size()); i < i_len; ++i){
    if(M / n < v){
        ng = true;
        break;
    }
    v *= mid;
    if(v + X[i] - '0' > M){
        ng = true;
        break;
    }
    v += X[i] - '0';
}

のようにすればいいです。他にも $M$ を $n$ 進数に直すのも手です*3。

E - Train (500点)

Dijkstra法を改造します。各辺に行き先 $\mathrm{to}_e$ と所要時間 $T_e$ だけでなく、 $K_e$ の情報を持たせ、Dijkstra法の更新の所がもともと $d_v + \mathrm{cost}_e$ のところを、 $K_e\displaystyle\left\lceil \frac{d_v}{K_e}\right\rceil + \mathrm{cost}_e$ とすると今回の問題が求まります。

F - Potion (600点)

DPであるとは思いましたが、各 $\bmod i$ のときの最大値を記憶する必要があるのですが、なぜかこの時に $\mathrm{lcm}(1,\,2,\,\dots,\,N)$ だけ必要だと思い込んでしまい、 $\mathrm{lcm}(1,\,\dots,\,100) = 69\,720\,375\,229\,712\,477\,164\,533\,808\,935\,312\,303\,556\,800$ で無理だなってなってしまい、コンテスト中には通せませんでした。実際は各 $\bmod i$ のときのを記憶すればいいので、そこに関してはそれぞれ計算させてやればいいので、普通に間に合います。

合成する素材数を $l$ 個と決めたときの $A_i$ のうち $l$ 個を選んだ時の和で $\bmod l$ が $X \bmod l$ と等しいものの最大値を $m$ とした時、 $\displaystyle\frac{X - m}{l}$ の最小値が答えとなります。
ここで

${\mathrm{dp}}_{i,j,k} = (\text{$i$ 番目までを $j$ 個選んだ時の和で$\bmod l = k$ であるものの最大値})$

とすると ${\mathrm{dp}}_{0,1,k} = 0$ であり、

${\mathrm{dp}}_{i,1,k}=\left\{ \begin{array}{ll} \max\{{\mathrm{dp}}_{i-1,1,k},\,A_i\} & (k = A_i \bmod l)\\ {\mathrm{dp}}_{i-1,1,k} & (\text{otherwise}) \end{array} \right.$

で、
${\mathrm{dp}}_{i-1,j-1,k} \neq 0$ のとき $b = {\mathrm{dp}}_{i-1,j-1,k} + A_i$ として

${\mathrm{dp}}_{i,j,b \bmod l} = \max\{{\mathrm{dp}}_{i-1,j,b \bmod l},\,b\}$

となります。 $j$ を大きい方から更新していくと実は $i$ の部分は使いまわせ、次元を1つ減らすことができます。計算量は $O(N^4)$ で $100^4 = 10^8$ なので若干危うく見えますが、 $i,\,j,\,k \leq l \leq N \leq 100$ であることから $\displaystyle\sum_{l = 1}^{N} \,l^3 = \frac{1}{4}N^2(N+1)^2$ より定数倍が $\displaystyle\frac{1}{4}$ ほどなので余裕があることが分かります。

結果、感想

f:id:Flkanjin:20210221010831p:plain
D問題で5ペナ喰らった事と、F問題が描けなかったのが悔しいです。ちゃんと精進しないと...

*1:因みにこれは和製英語らしく、英語では0-basedというそうです

*2:0の時は $x$ が0以下になるので不適です

*3:10以上の数字が必要な桁は数字より大きな文字にすればいいです