EducationalCF53 E - Segment Sum
かなり残念な落とし方をした
4完でもhighest更新したからこれも通ってれば・・😠
問題
L以上r以下の整数のうち、各桁の数字の種類がk以下であるものの和を求めよ
1 <= L <= r < 10^18
1 <= k <= 10
解法
とりあえず求めるものは (r以下の条件を満たす数字の和) - (L-1以下の〜) としてok
1桁ずつ考える
まず1の位に注目し、
Σ (条件を満たし、かつ1の位がxになるような数字の個数) * x (1 <= x <= 9)
を求める
これはありふれた桁dpを、1の位の遷移だけxに絞るようにちょっと書き換えるだけで求められる
10の位以上も同様に求め、それらを足し合わせることで答えが得られる
桁dpのテーブルは
dp[i][j][L][b]: 上からi桁目まで決まり、nより小さいことが確定し(j=1)、leading-zeroは終了し(L=1)、使った数字の組み合わせがbであるような数字の個数
とすればいい
leading-zeroに気を付けないと、例えばnが3桁のとき、11って数字が0と1の2種類の数字を使った数字として扱われてしまう(011)
実装
時間制限が1sで割とギリギリだから無駄な処理はなるべく削った
気を付けたことは
・0〜2^10のpopcountを事前に求めておく(cnt)
・10の0〜18乗も事前に求めておく(ten)
・dp[〜]が空のときはcontinueする
本番では最後のcontinueをしてなくてTLEした
これ書き足しただけで10倍くらい速くなった
これ書かないと無駄な処理が結構増えるのはわかってたけど、そこまで速度に差が出るとは知らなかった & 別にcontinueしなくても答えは変わらないから、別に書かなくてもいいものだと自分の中で思ってた
もう一生continueを省略することはないと思う
関係ないけどコドフォはコードに長めの日本語のコメントが含まれるとJudgement Failedってエラーが出るらしい
ジャッジが詰まってる系だと思ってイラついて連投してたら注意された
#define int long long int l, r, k, cnt[1<<10], ten[33]; int dig(const string &s, int x, int y) { int n = s.size(), dp[22][2][2][1<<10] = {}; dp[0][0][0][0] = 1; rep(i,n) rep(j,2) rep(l,2) rep(b,1<<10) if (dp[i][j][l][b]) { if (i==x) { if (cnt[b|(1<<y)]>k) continue; if (j==0 && s[i]-'0'<y) continue; (dp[i+1][j|(s[i]-'0'>y)][1][b|(1<<y)] += dp[i][j][l][b]) %= mod; } else { rep(t,(j ? 10 : (s[i]-'0')+1)) { int bit = (l==0 && t==0 ? b : b|(1<<t)); if (cnt[bit]>k) continue; (dp[i+1][j|(s[i]-'0'>t)][l|(t!=0)][bit] += dp[i][j][l][b]) %= mod; } } } int res = 0; rep(i,2) rep(l,2) rep(j,1<<10) (res += dp[n][i][l][j]) %= mod; return res; } int ans(int n) { string s = to_string(n); int res = 0, m = s.size(); rep(i,m) reps(j,1,10) { if (i==0 && s[i]-'0'<j) continue; (res += dig(s,i,j) * ten[m-i-1] %mod * j) %= mod; } return res; } signed main() { rep(i,1<<10) cnt[i] = __builtin_popcount(i); ten[0] = 1; reps(i,1,33) ten[i] = ten[i-1]*10 %mod; cin >> l >> r >> k; cout << (ans(r) - ans(l-1) + mod) %mod << endl; }
