ARC229 A - AtCoder Reverse Contest

考え方

まず、文字列から操作回数を求めることを考える。

例えば、ARCRARCARC の場合、操作ごとに以下のようになり、$4$ 回である。

ARCRARCARC
CRARARCARC
CRARCRAARC
CRCRARAARC
CRCRARACRA

これは結局 ARCRARC ARC とわけて考えて、それらの回数を足したものになっている。
同じ A や同じ C を複数回使うには、R が $1$ 個飛ばしで存在する必要がある。
よって、R が $1$ 個飛ばしになっていないところは完全に分割してしまってよい。
また、これら $3$ 種以外の文字がある場合も、あきらかに切ってしまってよい。

では、ARCRARC 部分はどうするか。
R を省いた ACAC を見たときに、各 A を使える回数は、それより後ろにある C の個数である。
したがって、それを数えて $2+1=3$ 個と足し算で求められる。

ということで、短い長さで操作回数を稼ぐには、ざっくり以下のような方針を取ればよい。

• 奇数文字の文字列で、偶数文字目全てに R を配置する
• 残る奇数番目に、前半は A、後半は C を配置する
  • 個数の積が操作数なので、なるべく同じくらいの個数にするとよい（相加相乗平均の関係）

あとは、微調整の方法を考える。
まず、$C$ の個数を、$\sqrt{X}$ の切り上げくらいに決め打つ。
$A$ を置くことで、残りの $C$ の個数分だけ操作数を稼げる。
操作数が $X$ を超えないように貪欲に $A$ を置きながら、C が規定個数になるまで繰り返せばよい。

この説明で具体的なイメージがわきにくければ、以下の動作例を見ればわかりやすい。

最初の $C$ の個数を $i=\lfloor\sqrt{X}\rfloor+1$ とすれば $i\le25$ であり、A と C はそれぞれ高々 $i$ 個しか使わない。
間に入れる R を含めても文字列の長さは高々 $4i-1\le99$ なので、長さ制限も満たす。

計算量は $O(\sqrt{X})$ である。

具体例での動作

$X=7$ の場合を考える。

まず、$i=\lfloor\sqrt{7}\rfloor+1=3$ とする。
構築する文字列は空文字列から始める。

$i=3$ のとき、残りの操作数は $7$ なので、後ろに $3$ 個の C がある A を $2$ 個置ける。
AR を $2$ 回追加して残りを $1$ とし、その後 CR を追加する。

文字列: ARARCR
残り: 1

$i=2$ のとき、残りは $1$ なので A は追加せず、CR だけを追加する。

文字列: ARARCRCR
残り: 1

$i=1$ のとき、残りは $1$ なので AR を $1$ 回追加して残りを $0$ とし、その後 CR を追加する。

文字列: ARARCRCRARCR
残り: 0

最後の R は不要なので削除し、ARARCRCRARC となる。

R を省くと AACCAC である。
各 A より後ろにある C の個数は順に $3,3,1$ なので、操作回数は $3+3+1=7$ となる。
したがって、$f(S)=7$ を満たす文字列を構築できている。

注意点

解法によっては、$X=0$ の場合がコーナーケースになるので注意すること。

別解

特になし。