C++ の動作確認をしてみた（３２６）

C++の練習を兼ねて, AtCoder Regular Contest 090 の問題F (Number of Digits) を解いてみた.

■感想.
1. F問題は, 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. 但し, 正しく数え上げできるまでに, 実装に, 非常に苦労した(※).
※ おそらく, このような内容だろうと推測して, 解説を, 若干読み替えている箇所を含む.
3. AC版となったものの, TLEをギリギリ回避している実装(1985[ms])なので, 高速化について, 将来的な課題として残っている.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Regular Contest 090 解説をご覧下さい.

■C++版プログラム(問題F／AC版).

// 解き直し.
// https://img.atcoder.jp/arc090/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define pb push_back
const LL MOD = 1e9 + 7;
const LL pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000};

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t % MOD;
}


// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数(※1以上).
set<LL> div(LL X){
    set<LL> ret;
    for(LL d = 1; d * d <= X; d++){
        if(!(X % d)){
            ret.insert(d);
            if(d * d != X) ret.insert(X / d);
        }
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL S;
    scanf("%lld", &S);
    
    // 2. S の 約数.
    set<LL> s = div(S);
    // for(auto &p : s) printf("%lld ", p);
    // puts("");
    
    // 3. 場合分け.
    // 3-1. f[l] = f[r].
    // ex.
    // S = 50 の 場合.
    //  1桁:         0個
    //  2桁:        66個
    //  5桁:     89991個
    // 10桁: 999999940個 (MOD版)
    // 25桁: 440999999個 (MOD版)
    // 50桁: 487370014個 (MOD版)
    // -> 928460003(MOD版) と 推測される.
    LL ans = 0;
    for(auto &d : s){
        if(d < 11){
            LL nd = pow10[d] - pow10[d - 1];
            ans += max(0LL, nd - (S / d) + 1LL) % MOD;
        }else{
            LL nd = (mPow(10LL, d) + MOD - mPow(10LL, d - 1)) % MOD;
            ans += (nd + MOD - (S / d) + 1LL) % MOD;
        }
        ans %= MOD;
    }
    
    // 3-2. f[r] <= 9 かつ f[r] >= f[l] + 1.
    // l は, 1 ～ 99999999 を取り得るはず(※解説の範囲を拡大する方向に変更).
    function<bool(int, int, LL, LL)> f = [&](int od, int cd, LL sum, LL S){
        // 終了条件.
        if(sum >= S) return false;
        
        // r を確定させるための 残差分を 計算.
        LL ds = S - sum;
        LL dr = pow10[cd] - pow10[cd - 1];
        
        // 残差分を更新.
        if(ds > dr * (LL)cd) sum += dr * (LL)cd;
        else                 return (ds % cd == 0);
        
        // r を 再帰的に, 探索.
        // ※ return を 指定しないと, 正しく動作しないので要注意.
        return f(od, cd + 1, sum, S);
    };
    // ex.
    // S = 50 の 場合.
    // 1桁:  8個, 2桁: 21個
    // 1桁:  6個, 2桁: 22個
    // 1桁:  4個, 2桁: 23個
    // 1桁:  2個, 2桁: 24個
    // 2桁: 22個, 3桁:  2個
    // 2桁: 19個, 3桁:  4個
    // 2桁: 16個, 3桁:  6個
    // 2桁: 13個, 3桁:  8個
    // 2桁: 10個, 3桁: 10個
    // 2桁:  7個, 3桁: 12個
    // 2桁:  4個, 3桁: 14個
    // 2桁:  1個, 3桁: 16個
    // 3桁: 14個, 4桁:  2個
    // 3桁: 10個, 4桁:  5個
    // 3桁:  6個, 4桁:  8個
    // 3桁:  2個, 4桁: 11個
    // 4桁: 10個, 5桁:  2個
    // 4桁:  5個, 5桁:  6個
    // 5桁:  4個, 6桁:  5個
    // 6桁:  6個, 7桁:  2個
    // 7桁:  6個, 8桁:  1個
    // 8桁:  4個, 9桁:  2個 <- 上限を, 10000000 とした場合, 探索から漏れるパターン(※探索方法を要検討)
    // の 22通りが考えられる.
    // 但し, repx の 上限 に 100000000 を 指定すると, 7458[ms] かかるので, TLE版 となってしまう.
    // repx(l, 1, 100000000){
    // -> while文 に 書き換え.
    int l = 0;
    // S = 100 の 場合に, 9桁: 10個, 10桁: 1個 が, 探索から漏れてしまうため, 
    // 探索上限を, 100000000 -> 1000000000 に 変更.
    // while(++l < 100000000){
    // -> 06.txt などのテストケースで, TLE版となるため, 却下.
    // while(++l < 1000000000){
    while(++l < 100000000){
        // l の 桁数.
        string sl = to_string(l);
        int dl = sl.size();
        
        // l の 桁数 と 同じものの総和.
        LL lSum = pow10[dl] - (LL)l;
        lSum *= dl;
        
        // l を Skip.
        if(lSum > S){
            l = pow10[dl] - S / dl;
            if(S % dl == 0) l++;
            lSum = pow10[dl] - (LL)l;
            lSum *= dl;
        }
        
        // r の 存在チェック.
        if(f(dl, dl + 1, lSum, S)) ans++;
    }
    
    // 3-3. f[r] >= 10 かつ f[r] = f[l] + 1.
    // ex.
    // S = 50 の 場合.
    // f[l] = 12, f[r] = 13
    // f[l] = 16, f[r] = 17
    // の 2通りが考えられる.
    // -> 実際, 50 = 12 + 12 + 13 + 13, 16 + 17 + 17 となるからである.
    // int u = (int)(S / 10);
    // if(S % 10 != 0) u++;
    // -> TLE回避のため, 評価する数字を, 10 => 9 に 変更.
    int u = (int)(S / 9);
    if(S % 9 != 0) u++;
    repx(i, 1, u) if(!s.count((LL)i)) ans++, ans %= MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

// 解き直し.

// https://img.atcoder.jp/arc090/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define all(x) x.begin(), x.end()

#define pb push_back

const LL MOD = 1e9 + 7;

const LL pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000};

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

// 与えられた正の整数のすべての約数を抽出.

// @param X: 約数を抽出したい正の整数.

// @return ret: すべての約数(※1以上).

set<LL> div(LL X){

set<LL> ret;

for(LL d = 1; d * d <= X; d++){

if(!(X % d)){

ret.insert(d);

if(d * d != X) ret.insert(X / d);

}

return ret;

}

int main(){

// 1. 入力情報.

LL S;

scanf("%lld", &S);

// 2. S の約数.

set<LL> s = div(S);

// for(auto &p : s) printf("%lld ", p);

// puts("");

// 3. 場合分け.

// 3-1. f[l] = f[r].

// ex.

// S = 50 の場合.

// 1桁: 0個

// 2桁: 66個

// 5桁: 89991個

// 10桁: 999999940個 (MOD版)

// 25桁: 440999999個 (MOD版)

// 50桁: 487370014個 (MOD版)

// -> 928460003(MOD版) と推測される.

LL ans = 0;

for(auto &d : s){

if(d < 11){

LL nd = pow10[d] - pow10[d - 1];

ans += max(0LL, nd - (S / d) + 1LL) % MOD;

}else{

LL nd = (mPow(10LL, d) + MOD - mPow(10LL, d - 1)) % MOD;

ans += (nd + MOD - (S / d) + 1LL) % MOD;

}

ans %= MOD;

}

// 3-2. f[r] <= 9 かつ f[r] >= f[l] + 1.

// l は, 1 ～ 99999999 を取り得るはず(※解説の範囲を拡大する方向に変更).

function<bool(int, int, LL, LL)> f = [&](int od, int cd, LL sum, LL S){

// 終了条件.

if(sum >= S) return false;

// r を確定させるための残差分を計算.

LL ds = S - sum;

LL dr = pow10[cd] - pow10[cd - 1];

// 残差分を更新.

if(ds > dr * (LL)cd) sum += dr * (LL)cd;

else return (ds % cd == 0);

// r を再帰的に, 探索.

// ※ return を指定しないと, 正しく動作しないので要注意.

return f(od, cd + 1, sum, S);

};

// ex.

// S = 50 の場合.

// 1桁: 8個, 2桁: 21個

// 1桁: 6個, 2桁: 22個

// 1桁: 4個, 2桁: 23個

// 1桁: 2個, 2桁: 24個

// 2桁: 22個, 3桁: 2個

// 2桁: 19個, 3桁: 4個

// 2桁: 16個, 3桁: 6個

// 2桁: 13個, 3桁: 8個

// 2桁: 10個, 3桁: 10個

// 2桁: 7個, 3桁: 12個

// 2桁: 4個, 3桁: 14個

// 2桁: 1個, 3桁: 16個

// 3桁: 14個, 4桁: 2個

// 3桁: 10個, 4桁: 5個

// 3桁: 6個, 4桁: 8個

// 3桁: 2個, 4桁: 11個

// 4桁: 10個, 5桁: 2個

// 4桁: 5個, 5桁: 6個

// 5桁: 4個, 6桁: 5個

// 6桁: 6個, 7桁: 2個

// 7桁: 6個, 8桁: 1個

// 8桁: 4個, 9桁: 2個 <- 上限を, 10000000 とした場合, 探索から漏れるパターン(※探索方法を要検討)

// の 22通りが考えられる.

// 但し, repx の上限に 100000000 を指定すると, 7458[ms] かかるので, TLE版となってしまう.

// repx(l, 1, 100000000){

// -> while文に書き換え.

int l = 0;

// S = 100 の場合に, 9桁: 10個, 10桁: 1個が, 探索から漏れてしまうため,

// 探索上限を, 100000000 -> 1000000000 に変更.

// while(++l < 100000000){

// -> 06.txt などのテストケースで, TLE版となるため, 却下.

// while(++l < 1000000000){

while(++l < 100000000){

// l の桁数.

string sl = to_string(l);

int dl = sl.size();

// l の桁数と同じものの総和.

LL lSum = pow10[dl] - (LL)l;

lSum *= dl;

// l を Skip.

if(lSum > S){

l = pow10[dl] - S / dl;

if(S % dl == 0) l++;

lSum = pow10[dl] - (LL)l;

lSum *= dl;

}

// r の存在チェック.

if(f(dl, dl + 1, lSum, S)) ans++;

}

// 3-3. f[r] >= 10 かつ f[r] = f[l] + 1.

// ex.

// S = 50 の場合.

// f[l] = 12, f[r] = 13

// f[l] = 16, f[r] = 17

// の 2通りが考えられる.

// -> 実際, 50 = 12 + 12 + 13 + 13, 16 + 17 + 17 となるからである.

// int u = (int)(S / 10);

// if(S % 10 != 0) u++;

// -> TLE回避のため, 評価する数字を, 10 => 9 に変更.

int u = (int)(S / 9);

if(S % 9 != 0) u++;

repx(i, 1, u) if(!s.count((LL)i)) ans++, ans %= MOD;

// 5. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
1

[出力例]
9
※AtCoderテストケースより

[入力例]
2

[出力例]
98
※AtCoderテストケースより

[入力例]
123

[出力例]
460191684
※AtCoderテストケースより

[入力例]
36018

[出力例]
966522825
※AtCoderテストケースより

[入力例]
1000

[出力例]
184984484
※AtCoderテストケースより

[入力例]
50

[出力例]
928460027

[入力例]
100

[出力例]
132532820

[入力例]
1234

[出力例]
127428960

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

123

[出力例]

460191684

※AtCoderテストケースより

[入力例]

36018

[出力例]

966522825

※AtCoderテストケースより

[入力例]

1000

[出力例]

184984484

※AtCoderテストケースより

[入力例]

[出力例]

928460027

[入力例]

100

[出力例]

132532820

[入力例]

1234

[出力例]

127428960

■参照サイト
AtCoder Regular Contest 090

C++の練習を兼ねて, AtCoder Regular Contest 090 の 問題F (Number of Digits) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Regular Contest 090 の問題F (Number of Digits) を解いてみた.

コメントを残すコメントをキャンセル