SRM509 Div1 Easy - LuckyRemainder

問題

　整数から数字を1つ以上取り除き残った数字を順番はそのままに右へ詰めてできる整数らの和を9で割った余りを求めよ。

解法

　上の桁から順番に9で割った余りがそれぞれ何回出てくるかを記録していく。これをとする()。桁目の数字がだったとき、これを使うことによりが現在のだけ増える。また桁目の数字を一つだけ使うことによりも1増える。この二つの操作を桁を順番に下りながらやっていき、最後に各要素の和を取っていけばよいのでで求まる。

反省

　ちょうどこの前やったARC020のCなどの印象が強く、桁をずらしながら足して余りを求めていくという発想しか出てこなかった。もっと簡単にできるらしい。

　多少でも複雑になってしまうと桁目の数字を一つだけ使うことを忘れたりそこで9の余りを取るのを忘れたりでWAを出してしまう(しまった)ので、できるだけ簡単な解法まで落としてからコードを書き始めるということが重要なんだろうが、まぁ実際はいけそうな解法を思いついたらすぐ書き出してしまうのが人の性である。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class LuckyRemainder {
public:
    int getLuckyRemainder(string X) {
        vector<ll> num(9, 0);
        for (char c : X) {
            ll n = c - '0';
            auto before = num;
            for (ll i = 0; i < 9; i++) {
                num[(i * 10 + n) % 9] += before[i];
            }
            num[n % 9]++;
        }

        ll sum = 0;
        for (ll i = 0; i < 9; i++) {
            sum += num[i] * i;
        }
        return sum % 9;
    }
};