けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

DISCO ディスカバリーチャンネル 2020 予選 D - Digit Sum Replace (青色, 500 点)

AtCoder AtCoder500点 不変量 整数値のconcatを考える問題 気付き系 ランレングス圧縮 操作 最大回数・最大個数を求める N進法 各桁の和 青色diff 倍数判定や九去法 最適化問題

すごく面白かった！

問題へのリンク

問題概要

ある数値が与えられる。ただしその数値は非常に桁数が大きいことがあるので、数値を 10 進法で表したときの文字列をランレングス圧縮した状態で与えられる。具体的には N 組の値 (d_{i}, c_{i}) が与えられて、 i = 0, 1, \dots, N-1 の順に、数値 d_{i} が c_{i} 個続くことを表す。

この数値に対して以下のような操作を行う:

  • 連続する 2 桁を選んで、その値を合計した値を、その場の 2 桁の数値と置き換える
    • 57435 の 74 の部分に操作を行うと、51135
    • 57435 の 43 の部分に操作を行うと、5775

数値が一桁になったら操作終了である。行える操作回数の最大回数を求めよ。

制約

  • 1 \le N \le 10^{5}
  • c_{i} の総和は 10^{15} 以下

考えたこと

いろいろ実験をしていると、どんな数値に対してどんな順序で操作を行っても、回数が等しくなる気がしてくる。

それを示すために、(何桁か、各桁の値の総和) に着目する。実は以下の 2 つの場合しかない。操作前の (何桁か、各桁の値の総和) を (d, s) として

  • (d, s) が (d-1, s) に変化する
  • (d, s) が (d, s-9) に変化する

前者は 57435 が 5775 になるような場合。後者は 57435 が 51135 になるような場合。

というわけなので、最終的に (1, (9以下)) となるまでの操作回数は

  • 桁数が 1 下がる変化： (c の総和 - 1) 回
  • 各桁の値の総和が 9 下がっていく変化： (d * c の総和 - 1) / 9 回

ということになる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    long long ketasuu = 0, sum = 0;
    for (int i = 0; i < N; ++i) {
        long long d, c;
        cin >> d >> c;
        ketasuu += c;
        sum += d * c;
    }
    cout << (sum - 1) / 9 + (ketasuu - 1) << endl;
}