DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 D - Digit Sum Replace (500)

D - Digit Sum Replace

概要

ある数Xの十進表記が与えられる。次の操作をXが1桁になるまで行う。

• 十進表記で任意の隣り合う2数をその和で置き換える

操作可能な回数の最大値を求めよ。ただし、入力は2つのM項の整数列c1, c2, ..., cM, d1, d2, ...dMを用いて表され、Xの先頭のc1桁の数字が全てd1、続くc2桁の数字が全てd2、...、最後のcM桁の数字が全てdMであるものとする。

制約

1 ≦ M ≦ 200000
0 ≦ di ≦ 9, d1 ≠ 0
2 ≦ c1 + ... + cM ≦ 10^15

方針

実はどのような順序で操作を行っても、終了までの操作回数は同じになる。これを確認する。

1回の操作の結果は次の2通り。
①Y48Z⇒Y12Zのように、桁数が変わらない
②Y13Z⇒Y4Zのように、桁数が変わる

①は桁数が変わらないかわりに、十進表記の各位の数字の総和が9減少する。
②は桁数が変わるが、十進表記の各位の数字の総和は変わらない。

最終的な結果としては「1桁かつ数字が1～9」であり、これを①・②の組み合わせで生成することになる。
①の回数は総和の減少にのみ寄与し、回数は「(もともとの十進表記の各位の数字の総和-1)を9で割った商」であり、
②の回数は桁数の減少にのみ寄与し、回数は「もともとの桁数-1」である。
よってこの2数の合計がもとめる解となる。

解答

Submission #8998585 - DISCO Presents Discovery Channel Code Contest 2020 Qual

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int m;
	cin >> m;
 
	ll digsum = 0;
	ll csum = 0;
	rep(i, m){
		ll d, c;
		cin >> d >> c;
 
		digsum += d * c;
		csum += c;
	}
 
	cout << (digsum-1) / 9 + csum - 1 << endl;
}