Long Beautiful Integer - #609 div2 c

#greedy

i番目とi + k番目は同じ数
同じグループにする
グループ内では数字を合わせる

手前の数が入ってるグループほど値を大きくしたくない

例
6 2
123456

グループに分けると,
グループ1
1, 3, 5
グループ2
2, 4, 6

ここで, 先頭に近いほど値を変えたくない
より大きくなるから
グループごとに, 先頭に合わせる $\ \ \ \ (1)$

すると,
121212
になる

値を変えるなら, 先頭から遠いグループから
グループ2の値を1大きくする $\ \ \ \ (2)$
すると,
131313 > 123456
になる

まず, グループを作るときに各グループ内で先頭の数に合わせた
(2)のように, グループ全体の値を変えるとき, (1)で変えなかった先頭の数が大きくなる
その大きくなった先頭の数を i 番目とする
i + 1 番目以降の変化はどうでもいい
i 番目が大きくなったから

そして, i - 1 番目より前は値が変わっていない

よって, k 個のグループを後ろから見て, 変えられるのを探す
9 なら変えられない
9 ならそれより前のグループの値を変えることになる
9 だったグループの数を 0 にするのをお忘れなく

ちょっと説明
(1)の操作で元の数 a より値が大きくなった場合, (2)はいらない
それを flg で判定
初めて $a_{i} = a_{i + k}$ でなくなったとき, $a_{i} < a_{i + k}$ だったなら
$a_{i + k}$ は小さくなり, (2)が必要

6 3
123456

6
124124

6 4
123456

6
123512

6 1
318772

6
333333

7 3
7283464

7
7287287

4 3
2137

4
2142

7 3
1117653

7
1121121

3 2
192

3
202

3 2
112

3
121