Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 283 C問題 Cash Register

AtCoder ABC283 ABC C問題 300 pts

問題

提出解答

問題の概要

$T=0$ で初期化された変数 $T$ に対して, 「以下の操作のうち1個を選び行う」ことを最低何回行うと $S$ にすることができるか?

$0$ 以上 $9$ 以下の整数 $x$ を選び, $T \gets 10T+x$
$T \gets 100T$

制約

$1 \leq S \leq 10^{10^5}$

解法

$S$ を文字列とみなす. すると, 問題は次のように言い換えることができる.

空文字で初期化された文字列 $T$ が与えられる. 「以下の操作のうち1個を選び行う」ことを最低何回行うと $S$ にすることができるか?

$0$ 以上 $9$ 以下の整数 $x$ を選び, $T$ の末尾に $x$ を表す数字を追加する.
$T$ の末尾に ${\tt 00}$ を追加する.

$S$ の中にある ${\tt 0}$ が連続する区間が $k$ 個あり, それぞれ, $m_1, \dots, m_k$ 個連続しているとする. $j$ 番目の区間について, 連続する $m_j$ 個の ${\tt 0}$ は次のようにして最短回数で表すことができる.

$\left \lfloor \dfrac{m_j}{2} \right \rfloor$ 回末尾に ${\tt 00}$ を追加する.
$m_j$ が奇数ならば, 末尾に ${\tt 0}$ を追加する.

それ以外の数字はその数字を1個ずつ入力するしか方法がない.

以上から, $S$ に含まれる ${\tt 0}$ 以外の数字の数を $M$ とすると, 答えは

$\displaystyle M+\sum_{j=1}^k \left \lceil \dfrac{m_j}{2} \right \rceil$

である.