kmjp's blog

競技プログラミング参加記です

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

色々反省点だらけ。
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_d

問題

最大10^15桁の正整数が与えられる。
この整数において、連続する2桁を、その和で置き換える(和が9以下なら1桁で置き換えるので、全体が1桁減る)とする。
最終的にこの値が1桁になるまで、最大何回処理できるか。

解法

消し方に関わらず消す回数は変わらない。
1回の処理で必ず以下どちらかだけが行われる。

  • 桁が減る
  • 桁の総和が9減る

よって、総桁数と桁の総和がわかればそこからはO(1)で求められる。

int M;
int D[202020];
ll C[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll A=0;
	ll sum=0;
	cin>>M;
	FOR(i,M) {
		cin>>D[i]>>C[i];
		sum+=D[i]*C[i];
		A+=C[i];
	}
	ll ret=A-1;
	if(sum>9) ret+=(sum+8)/9-1;
	cout<<ret<<endl;
}

解法

紙で試したとき、なぜか手順で回数が異なると勘違いして手間取った。