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

C++の練習を兼ねて, AtCoder Regular Contest 075 の問題F (Mirrored) を解いてみた.

■感想.
1. 方針が見えなかったので, 解説を参照して実装したところ, ようやく, AC版となった.
2. プログラム上に, コメントしている内容であるが, 解説内容から, いくつかの性質を仮定していると推測し, 実装している.
3. 個人的には, いろいろ苦労したものの, 非常に面白い問題に感じた.
4. 久しぶりに, 再帰処理の実装を行うことが出来たので良かったと思う.
5. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc075/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--)
LL p10[20];

int main(){
    
    // 1. 入力情報.
    LL D;
    scanf("%lld", &D);
    
    // 2. 10 の 冪乗.
    p10[0] = 1;
    rep(i, 19) p10[i + 1] = p10[i] * 10LL;
    // rep(i, 19) printf("%lld\n", p10[i]);
    
    // 3. D の 桁数.
    string strLD = to_string(D);
    int LD = strLD.size();
    
    // 4. L に対応する f(L, d) = D を 計算.
    // d[i] = n[i] - n[L - 1 - i] について, 以下のように解釈を追加する.
    // d[i] の 値 について, n[L - 1] が 0 でないことに注意して, 
    // ① i = 0 の 場合(※ 9 - d[i] 通り).
    // 0 … (1, 1), (2, 2), ..., (9, 9) の 9通り.
    // 1 … (2, 1), (3, 2), ..., (9, 8) の 8通り.
    // ...
    // 8 … (9, 1) の 1通り.
    // 9 … 0通り.
    // 
    // ② i > 0 の 場合(※ 10 - d[i] 通り).
    // 0 … (0, 0), (2, 2), ..., (9, 9) の 10通り.
    // 1 … (1, 0), (2, 1), ..., (9, 8) の 9通り.
    // ...
    // 8 … (9, 1), (8, 0) の 2通り.
    // 9 … (9, 0) の 1通り.
    // d[i] < 0 の 場合も, 絶対値を取って, d[i] > 0 の パターンに帰着.
    function<LL(LL, int, int, int, LL)> f = [&](LL dif, int L, int i, int u, LL ret) {
        // 4-1. 終了条件.
        if(u < i){
            // i の 2倍 が L 未満 の 場合, 10倍する必要があるように見える性質を仮定.
            LL d = (i * 2 < L) ? 10LL : 1LL;
            if(dif == 0) return ret * d;
            else         return 0LL;
        }
        
        // 4-2. 10 の 冪乗.
        LL tP10 = p10[L - 1 - i] - p10[i];
        
        // 4-3. d[i] の 値 を 検討.
        LL q = abs(dif) / tP10;
        // printf("1. L=%d i=%d u=%d tP10=%lld q=%lld dif=%lld\n", L, i, u, tP10, q, dif);
        
        // 4-4. D から 離れすぎている場合.
        if(q > 9){
            // printf("2. Too far away: i=%d u=%d tP10=%lld q=%lld dif=%lld\n", i, u, tP10, q, dif);
            return 0LL;
        }
        
        // 4-5. dif の 正負 で 分岐.
        int sign = (dif >= 0) ? 1 : -1;  // dif が 0 以上 か 0未満か.
        LL dx = (LL)(10 - q - (i == 0)); // i が 0 と等しい か 否か.
        LL dif1 = dif - tP10 * q * sign;
        LL dif2 = dif - tP10 * (q + 1) * sign;
        // printf("3. dif >= 0 i=%d dif=%lld dif1=%lld dif2=%lld\n", i, dif, dif1, dif2);
        if(q < 9) return f(dif1, L, i + 1, u, ret * dx) + f(dif2, L, i + 1, u, ret * (dx - 1LL));
        else      return f(dif1, L, i + 1, u, ret * dx);
        return 0LL;
    };
    LL ans = 0LL;
    repx(L, LD, LD * 2 + 1){
        // 上限.
        int uppper = (L / 2) - 1;
        
        // dif = D - Σ((10 の (L - 1 - j)乗 - 10 の j乗) * d[j]) の 計算.
        // ※ 解説上, N - *** と記載されているが, N を D に 読み替えている.
        ans += f(D, L, 0, uppper, 1LL);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/arc075/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--)

LL p10[20];

int main(){

// 1. 入力情報.

LL D;

scanf("%lld", &D);

// 2. 10 の冪乗.

p10[0] = 1;

rep(i, 19) p10[i + 1] = p10[i] * 10LL;

// rep(i, 19) printf("%lld\n", p10[i]);

// 3. D の桁数.

string strLD = to_string(D);

int LD = strLD.size();

// 4. L に対応する f(L, d) = D を計算.

// d[i] = n[i] - n[L - 1 - i] について, 以下のように解釈を追加する.

// d[i] の値について, n[L - 1] が 0 でないことに注意して,

// ① i = 0 の場合(※ 9 - d[i] 通り).

// 0 … (1, 1), (2, 2), ..., (9, 9) の 9通り.

// 1 … (2, 1), (3, 2), ..., (9, 8) の 8通り.

// ...

// 8 … (9, 1) の 1通り.

// 9 … 0通り.

// ② i > 0 の場合(※ 10 - d[i] 通り).

// 0 … (0, 0), (2, 2), ..., (9, 9) の 10通り.

// 1 … (1, 0), (2, 1), ..., (9, 8) の 9通り.

// ...

// 8 … (9, 1), (8, 0) の 2通り.

// 9 … (9, 0) の 1通り.

// d[i] < 0 の場合も, 絶対値を取って, d[i] > 0 のパターンに帰着.

function<LL(LL, int, int, int, LL)> f = [&](LL dif, int L, int i, int u, LL ret) {

// 4-1. 終了条件.

if(u < i){

// i の 2倍が L 未満の場合, 10倍する必要があるように見える性質を仮定.

LL d = (i * 2 < L) ? 10LL : 1LL;

if(dif == 0) return ret * d;

else return 0LL;

}

// 4-2. 10 の冪乗.

LL tP10 = p10[L - 1 - i] - p10[i];

// 4-3. d[i] の値を検討.

LL q = abs(dif) / tP10;

// printf("1. L=%d i=%d u=%d tP10=%lld q=%lld dif=%lld\n", L, i, u, tP10, q, dif);

// 4-4. D から離れすぎている場合.

if(q > 9){

// printf("2. Too far away: i=%d u=%d tP10=%lld q=%lld dif=%lld\n", i, u, tP10, q, dif);

return 0LL;

}

// 4-5. dif の正負で分岐.

int sign = (dif >= 0) ? 1 : -1; // dif が 0 以上か 0未満か.

LL dx = (LL)(10 - q - (i == 0)); // i が 0 と等しいか否か.

LL dif1 = dif - tP10 * q * sign;

LL dif2 = dif - tP10 * (q + 1) * sign;

// printf("3. dif >= 0 i=%d dif=%lld dif1=%lld dif2=%lld\n", i, dif, dif1, dif2);

if(q < 9) return f(dif1, L, i + 1, u, ret * dx) + f(dif2, L, i + 1, u, ret * (dx - 1LL));

else return f(dif1, L, i + 1, u, ret * dx);

return 0LL;

};

LL ans = 0LL;

repx(L, LD, LD * 2 + 1){

// 上限.

int uppper = (L / 2) - 1;

// dif = D - Σ((10 の (L - 1 - j)乗 - 10 の j乗) * d[j]) の計算.

// ※ 解説上, N - *** と記載されているが, N を D に読み替えている.

ans += f(D, L, 0, uppper, 1LL);

}

// 5. 出力.

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

return 0;

}

[入力例]
63

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

[入力例]
75

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

[入力例]
864197532

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

[入力例]
530865

[出力例]
252

[入力例]
38427606

[出力例]
1260

[入力例]
314159265

[出力例]
0

[入力例]
401999796

[出力例]
40000

[入力例]
573999525

[出力例]
7200

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

864197532

[出力例]

1920

※AtCoderのテストケースより

[入力例]

530865

[出力例]

252

[入力例]

38427606

[出力例]

1260

[入力例]

314159265

[出力例]

[入力例]

401999796

[出力例]

40000

[入力例]

573999525

[出力例]

7200

■参照サイト
AtCoder Regular Contest 075

C++の練習を兼ねて, AtCoder Regular Contest 075 の 問題F (Mirrored) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 075 の問題F (Mirrored) を解いてみた.

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