2月, 2020 | 個人用メモ帳

2020年2月29日2020年2月29日

C++ の動作確認をしてみた（１５１）

C++の練習を兼ねて, AtCoder Beginner Contest 031 の問題D (D – 語呂合わせ) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので, 良かったと思う.
2. 個人的には, 非常に, 面白い問題と感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 031解説をご覧下さい.

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

// コメント修正して, 再提出.
#include <bits/stdc++.h>
using namespace std;
#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 a first
#define b second
#define pb push_back

// 桁数情報のリストを更新する.
// @param s:    (更新前)桁数情報のリスト.
// @return ret: (更新後)桁数情報のリスト.
set<string> updateDigits(set<string> s){
    set<string> ret;
    for(auto &p : s) repx(i, 1, 4) ret.insert(p + to_string(i));
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int K, N;
    vector<pair<string, string>> v;
    scanf("%d %d", &K, &N);
    rep(i, N){
        char c1[33], c2[33];
        scanf("%s %s", c1, c2);
        string s1(c1), s2(c2);
        v.pb({s1, s2});
    }
    // for(auto &p : v) printf("%s %s\n", p.a.c_str(), p.b.c_str());
    
    // 2. s1, ..., sK の 取り得る桁数情報を作成.
    set<string> s;
    repx(i, 1, 4) s.insert(to_string(i));
    rep(i, K - 1){
        set<string> ls = updateDigits(s);
        swap(s, ls);
    }
    // for(auto &p : s) printf("%s\n", p.c_str());
    // printf("size=%d\n", s.size());
    
    // 3. s1, ..., sK の 取り得る桁数情報から, 推論.
    string ans[K];
    bool ok;
    for(auto &d : s){
        ok = true;
        // 3-1. 推論開始.
        rep(i, N){
            // 一つ取り出す.
            string a = v[i].a, b = v[i].b;
            
            // 桁数が矛盾してないかチェック.
            int dl = 0;
            rep(j, a.size()) dl += d[a[j] - '1'] - '0';
            if(b.size() < dl){
                ok = false;
                break;
            }
            
            // s1, ..., sK を 順次確定させる.
            int bsi = 0; // 文字列 b の 部分文字列 についての 開始インデックス.
            rep(j, a.size()){
                ans[a[j] - '1'] = b.substr(bsi, d[a[j] - '1'] - '0');
                bsi += d[a[j] - '1'] - '0';
            }
        }
        
        // 3-2. 推論チェック.
        rep(i, N){
            // 一つ取り出す.
            string a = v[i].a, b = v[i].b;
            
            // 推論文字列を作成.
            string ps = "";
            rep(j, a.size()) ps += ans[a[j] - '1'];
            
            // 与えられた文字列情報 と 推論文字列 を 比較.
            if(ps != b){
                ok = false;
                break;
            }
        }
        if(ok) break;
    }
    
    // 4. 出力.
    rep(i, K) printf("%s\n", ans[i].c_str());
    return 0;
    
}

// コメント修正して, 再提出.

#include <bits/stdc++.h>

using namespace std;

#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 a first

#define b second

#define pb push_back

// 桁数情報のリストを更新する.

// @param s: (更新前)桁数情報のリスト.

// @return ret: (更新後)桁数情報のリスト.

set<string> updateDigits(set<string> s){

set<string> ret;

for(auto &p : s) repx(i, 1, 4) ret.insert(p + to_string(i));

return ret;

}

int main(){

// 1. 入力情報.

int K, N;

vector<pair<string, string>> v;

scanf("%d %d", &K, &N);

rep(i, N){

char c1[33], c2[33];

scanf("%s %s", c1, c2);

string s1(c1), s2(c2);

v.pb({s1, s2});

}

// for(auto &p : v) printf("%s %s\n", p.a.c_str(), p.b.c_str());

// 2. s1, ..., sK の取り得る桁数情報を作成.

set<string> s;

repx(i, 1, 4) s.insert(to_string(i));

rep(i, K - 1){

set<string> ls = updateDigits(s);

swap(s, ls);

}

// for(auto &p : s) printf("%s\n", p.c_str());

// printf("size=%d\n", s.size());

// 3. s1, ..., sK の取り得る桁数情報から, 推論.

string ans[K];

bool ok;

for(auto &d : s){

ok = true;

// 3-1. 推論開始.

rep(i, N){

// 一つ取り出す.

string a = v[i].a, b = v[i].b;

// 桁数が矛盾してないかチェック.

int dl = 0;

rep(j, a.size()) dl += d[a[j] - '1'] - '0';

if(b.size() < dl){

ok = false;

break;

}

// s1, ..., sK を順次確定させる.

int bsi = 0; // 文字列 b の部分文字列についての開始インデックス.

rep(j, a.size()){

ans[a[j] - '1'] = b.substr(bsi, d[a[j] - '1'] - '0');

bsi += d[a[j] - '1'] - '0';

}

// 3-2. 推論チェック.

rep(i, N){

// 一つ取り出す.

string a = v[i].a, b = v[i].b;

// 推論文字列を作成.

string ps = "";

rep(j, a.size()) ps += ans[a[j] - '1'];

// 与えられた文字列情報と推論文字列を比較.

if(ps != b){

ok = false;

break;

}

if(ok) break;

}

// 4. 出力.

rep(i, K) printf("%s\n", ans[i].c_str());

return 0;

}

[入力例]
6 4
356 migoro
461 yoroi
2 ni
12 ini

[出力例]
i
ni
mi
yo
go
ro
※AtCoderテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.
i
ni
m
y
ig
oro

[入力例]
3 4
21 aaa
12 aaa
123 aaaaaa
13 aaaa

[出力例]
a
aa
aaa
※AtCoderテストケースより

[入力例]
2 3
12211 abcaaaaabcabc
2121 aaabcaaabc
222221 aaaaaaaaaaabc

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

[入力例]
2 1
12 abcab

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

[入力例]
9 20
135 okyesme
2469 idnoyouzoo
3571 yesmeheok
4572 nomeheid
56832 meyousheyesid
67143 youheoknoyes
79264 hezooidyouno
823756 sheidyeshemeyou
34527 yesnomeidhe
428 noidshe
531 meyesok
752 hemeid
842 shenoid
953 zoomeyes
184 oksheno
895 shezoome
9462 zoonoyouid
6573 youmeheyes
72843 heidshenoyes
63954 youyeszoomeno

[出力例]
ok
id
yes
no
me
you
he
she
zoo

[入力例]

6 4

356 migoro

461 yoroi

2 ni

12 ini

[出力例]

※AtCoderテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.

oro

[入力例]

3 4

21 aaa

12 aaa

123 aaaaaa

13 aaaa

[出力例]

aaa

※AtCoderテストケースより

[入力例]

2 3

12211 abcaaaaabcabc

2121 aaabcaaabc

222221 aaaaaaaaaaabc

[出力例]

abc

※AtCoderテストケースより

[入力例]

2 1

12 abcab

[出力例]

cab

※AtCoderテストケースより

[入力例]

9 20

135 okyesme

2469 idnoyouzoo

3571 yesmeheok

4572 nomeheid

56832 meyousheyesid

67143 youheoknoyes

79264 hezooidyouno

823756 sheidyeshemeyou

34527 yesnomeidhe

428 noidshe

531 meyesok

752 hemeid

842 shenoid

953 zoomeyes

184 oksheno

895 shezoome

9462 zoonoyouid

6573 youmeheyes

72843 heidshenoyes

63954 youyeszoomeno

[出力例]

yes

you

she

zoo

■参照サイト
AtCoder Beginner Contest 031

2020年2月24日2020年2月29日

C++ の動作確認をしてみた（１５０）

C++の練習を兼ねて, AtCoder Beginner Contest 156 の問題F (F – Modularness) を解いてみた.

■感想.
1. 方針が全く見えなかったので, 解説を参照して, 実装した.
2. 何とか実装したものの, 結構苦労した気がする(※本質が理解出来てない気もする).
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 156解説をご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc156/tasks/abc156_f
#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 d[5050], dMod[5050];

int main(){
    
    // 1. 入力情報.
    int k, q;
    scanf("%d %d", &k, &q);
    rep(i, k) scanf("%lld", &d[i]);
    
    // 2. クエリに回答(解説通り).
    rep(i, q){
        LL n, x, m, s = 0, t = 0;
        scanf("%lld %lld %lld", &n, &x, &m);
        
        // 2-1. d の 要素 を m で 割った余りで置き換える.
        rep(j, k) dMod[j] = d[j] % m;
        
        // 2-2. (a[i] mod m) == (a[i + 1] mod m) となる場合.
        rep(j, k){
            // if(dMod[j] % k == 0){ // 誤答となるっぽい.
            if(dMod[j] == 0){
                LL q = (n - 1) / k;
                LL r = (n - 1 - j) - q * k;
                s += (q + (r > 0));
            }
        }
        
        // 2-3. (a[i] mod m) > (a[i + 1] mod m) となる場合.
        // a[n - 1] を m で 割った商 から a[0] を m で 割った商 を 引く.
        // ex.
        // k = 5, n = 12
        // i = 0 1 2 3 4 5 6 7 8 9 10 11 (= n - 1)
        // a[0]  = x
        // a[1]  = x + 1 * d[0]
        // a[2]  = x + 1 * d[0] + 1 * d[1]
        // a[3]  = x + 1 * d[0] + 1 * d[1] + 1 * d[2]
        // a[4]  = x + 1 * d[0] + 1 * d[1] + 1 * d[2] + 1 * d[3]
        // a[5]  = x + 1 * d[0] + 1 * d[1] + 1 * d[2] + 1 * d[3] + 1 * d[4]
        // a[6]  = x + 2 * d[0] + 1 * d[1] + 1 * d[2] + 1 * d[3] + 1 * d[4]
        // a[7]  = x + 2 * d[0] + 2 * d[1] + 1 * d[2] + 1 * d[3] + 1 * d[4]
        // a[8]  = x + 2 * d[0] + 2 * d[1] + 2 * d[2] + 1 * d[3] + 1 * d[4]
        // a[9]  = x + 2 * d[0] + 2 * d[1] + 2 * d[2] + 2 * d[3] + 1 * d[4]
        // a[10] = x + 2 * d[0] + 2 * d[1] + 2 * d[2] + 2 * d[3] + 2 * d[4]
        // a[11] = x + 3 * d[0] + 2 * d[1] + 2 * d[2] + 2 * d[3] + 2 * d[4]
        t = x;
        rep(j, k){
            LL q = (n - 1) / k;
            LL r = (n - 1 - j) - q * k;
            LL u = (q + (r > 0)) * dMod[j];
            t += u;
        }
        // printf("s=%lld t=%lld n=%lld\n", s, t, n);
        t /= m;       // (a[n - 1] / m) を 計算.
        t -= (x / m); // (a[0] / m) を マイナス.
        
        // 2-4. (n - 1) から, 前項までの結果をマイナス.
        LL ans = (n - 1) - (s + t);
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc156/tasks/abc156_f

#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 d[5050], dMod[5050];

int main(){

// 1. 入力情報.

int k, q;

scanf("%d %d", &k, &q);

rep(i, k) scanf("%lld", &d[i]);

// 2. クエリに回答(解説通り).

rep(i, q){

LL n, x, m, s = 0, t = 0;

scanf("%lld %lld %lld", &n, &x, &m);

// 2-1. d の要素を m で割った余りで置き換える.

rep(j, k) dMod[j] = d[j] % m;

// 2-2. (a[i] mod m) == (a[i + 1] mod m) となる場合.

rep(j, k){

// if(dMod[j] % k == 0){ // 誤答となるっぽい.

if(dMod[j] == 0){

LL q = (n - 1) / k;

LL r = (n - 1 - j) - q * k;

s += (q + (r > 0));

}

// 2-3. (a[i] mod m) > (a[i + 1] mod m) となる場合.

// a[n - 1] を m で割った商から a[0] を m で割った商を引く.

// ex.

// k = 5, n = 12

// i = 0 1 2 3 4 5 6 7 8 9 10 11 (= n - 1)

// a[0] = x

// a[1] = x + 1 * d[0]

// a[2] = x + 1 * d[0] + 1 * d[1]

// a[3] = x + 1 * d[0] + 1 * d[1] + 1 * d[2]

// a[4] = x + 1 * d[0] + 1 * d[1] + 1 * d[2] + 1 * d[3]

// a[5] = x + 1 * d[0] + 1 * d[1] + 1 * d[2] + 1 * d[3] + 1 * d[4]

// a[6] = x + 2 * d[0] + 1 * d[1] + 1 * d[2] + 1 * d[3] + 1 * d[4]

// a[7] = x + 2 * d[0] + 2 * d[1] + 1 * d[2] + 1 * d[3] + 1 * d[4]

// a[8] = x + 2 * d[0] + 2 * d[1] + 2 * d[2] + 1 * d[3] + 1 * d[4]

// a[9] = x + 2 * d[0] + 2 * d[1] + 2 * d[2] + 2 * d[3] + 1 * d[4]

// a[10] = x + 2 * d[0] + 2 * d[1] + 2 * d[2] + 2 * d[3] + 2 * d[4]

// a[11] = x + 3 * d[0] + 2 * d[1] + 2 * d[2] + 2 * d[3] + 2 * d[4]

t = x;

rep(j, k){

LL q = (n - 1) / k;

LL r = (n - 1 - j) - q * k;

LL u = (q + (r > 0)) * dMod[j];

t += u;

}

// printf("s=%lld t=%lld n=%lld\n", s, t, n);

t /= m; // (a[n - 1] / m) を計算.

t -= (x / m); // (a[0] / m) をマイナス.

// 2-4. (n - 1) から, 前項までの結果をマイナス.

LL ans = (n - 1) - (s + t);

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

}

return 0;

}

[入力例]
3 1
3 1 4
5 3 2

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

[入力例]
7 3
27 18 28 18 28 46 1000000000
1000000000 1 7
1000000000 2 10
1000000000 3 12

[出力例]
224489796
214285714
559523809
※AtCoderテストケースより

[入力例]
10 5
120 20 56 903 15 95 94 285 3997 3816151
46008408 19 1182
936523469 6 958
555662761 22 703
776784387 12 1198
353200718 4 152
828319977 25 1207
181860716 17 1118
291738659 26 192
762764016 29 1018
939777463 28 501

[出力例]
35522228
722433031
426508714
613906058
176600359

[入力例]

3 1

3 1 4

5 3 2

[出力例]

※AtCoderテストケースより

[入力例]

7 3

27 18 28 18 28 46 1000000000

1000000000 1 7

1000000000 2 10

1000000000 3 12

[出力例]

224489796

214285714

559523809

※AtCoderテストケースより

[入力例]

10 5

120 20 56 903 15 95 94 285 3997 3816151

46008408 19 1182

936523469 6 958

555662761 22 703

776784387 12 1198

353200718 4 152

828319977 25 1207

181860716 17 1118

291738659 26 192

762764016 29 1018

939777463 28 501

[出力例]

35522228

722433031

426508714

613906058

176600359

■参照サイト
AtCoder Beginner Contest 156

2020年2月23日2020年2月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 156 の問題E (E – Roaming) を解いてみた.

■感想.
1. 方針が全く見えなかったので, 解説を参照して, 実装した.
2. 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 156解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/abc156/editorial.pdf
#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--)
const LL MOD = 1e9 + 7;
const int LIMIT = 2020202;
LL FAC[LIMIT];
LL INV[LIMIT];

// 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;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL n, k;
    scanf("%lld %lld", &n, &k);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    
    // 2. 解説通り.
    // nCm * (n - 1)C(n - m - 1) の 総和を計算.
    LL ans = 0;
    int upper = (int)min(k, n) + 1;
    rep(m, upper){
        LL t = combination(n, m);
        t %= MOD;
        t *= combination(n - 1, n - m - 1);
        t %= MOD;
        ans += t;
        ans %= MOD;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

#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--)

const LL MOD = 1e9 + 7;

const int LIMIT = 2020202;

LL FAC[LIMIT];

LL INV[LIMIT];

// 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;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

LL n, k;

scanf("%lld %lld", &n, &k);

FAC[0] = 1;

repx(i, 1, LIMIT) FAC[i] = i * FAC[i - 1] % MOD;

rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2) % MOD;

// 2. 解説通り.

// nCm * (n - 1)C(n - m - 1) の総和を計算.

LL ans = 0;

int upper = (int)min(k, n) + 1;

rep(m, upper){

LL t = combination(n, m);

t %= MOD;

t *= combination(n - 1, n - m - 1);

t %= MOD;

ans += t;

ans %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
3 2

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

[入力例]
200000 1000000000

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

[入力例]
15 6

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

[入力例]

3 2

[出力例]

※AtCoderテストケースより

[入力例]

200000 1000000000

[出力例]

607923868

※AtCoderテストケースより

[入力例]

15 6

[出力例]

22583772

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 156

2020年2月22日2020年2月29日

C++ の動作確認をしてみた（１４８）

C++の練習を兼ねて, AtCoder Beginner Contest 156 の問題D (D – Bouquet) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので良かったと思う.
2. 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 156解説をご覧下さい.

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

#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--)
const LL MOD = 1e9 + 7;
const int LIMIT = 2020202;
LL INV[LIMIT];

// 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;
}

int main(){
    
    // 1. 入力情報.
    LL n, a, b;
    scanf("%lld %lld %lld", &n, &a, &b);
    rep(i, LIMIT) INV[i] = mPow(i, MOD - 2) % MOD;
    
    // 2. 花束の種類数(全パターン, 2 の n乗通り) を 計算.
    LL ans = mPow(2, n);
    
    // 3. n種類の花から, x本選ぶ選び方(nCx通り) を 計算.
    // ex.
    // 11C5 は, (11 * 10 * 9 * 8 * 7) / (5 * 4 * 3 * 2 * 1) 
    // = (7 / 1) * (8 / 2) * (9 / 3) * (10 / 4) * (11 / 5)
    // のように計算したい.
    
    // 3-1. 0本選ぶとき.
    LL c0 = 1;
    
    // 3-2. a本選ぶとき.
    LL ca = 1;
    rep(i, a){
        ca *= (MOD + n - i);
        ca %= MOD;
        ca *= INV[i + 1];
        ca %= MOD;
    }
    
    // 3-3. b本選ぶとき.
    LL cb = 1;
    rep(i, b){
        cb *= (MOD + n - i);
        cb %= MOD;
        cb *= INV[i + 1];
        cb %= MOD;
    }
    
    // 4. 0 または a または b に 一致しない花束の種類数を計算.
    ans = (ans + MOD - c0) % MOD;
    ans = (ans + MOD - ca) % MOD;
    ans = (ans + MOD - cb) % MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#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--)

const LL MOD = 1e9 + 7;

const int LIMIT = 2020202;

LL INV[LIMIT];

// 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;

}

int main(){

// 1. 入力情報.

LL n, a, b;

scanf("%lld %lld %lld", &n, &a, &b);

rep(i, LIMIT) INV[i] = mPow(i, MOD - 2) % MOD;

// 2. 花束の種類数(全パターン, 2 の n乗通り) を計算.

LL ans = mPow(2, n);

// 3. n種類の花から, x本選ぶ選び方(nCx通り) を計算.

// ex.

// 11C5 は, (11 * 10 * 9 * 8 * 7) / (5 * 4 * 3 * 2 * 1)

// = (7 / 1) * (8 / 2) * (9 / 3) * (10 / 4) * (11 / 5)

// のように計算したい.

// 3-1. 0本選ぶとき.

LL c0 = 1;

// 3-2. a本選ぶとき.

LL ca = 1;

rep(i, a){

ca *= (MOD + n - i);

ca %= MOD;

ca *= INV[i + 1];

ca %= MOD;

}

// 3-3. b本選ぶとき.

LL cb = 1;

rep(i, b){

cb *= (MOD + n - i);

cb %= MOD;

cb *= INV[i + 1];

cb %= MOD;

}

// 4. 0 または a または b に一致しない花束の種類数を計算.

ans = (ans + MOD - c0) % MOD;

ans = (ans + MOD - ca) % MOD;

ans = (ans + MOD - cb) % MOD;

// 5. 出力.

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

return 0;

}

[入力例]
4 1 3

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

[入力例]
1000000000 141421 173205

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

[入力例]
2718281 82845 90452

[出力例]
443740209

[入力例]
31415926 53589 79323

[出力例]
174245672

[入力例]
123456789 101112 131415

[出力例]
557850348

[入力例]

4 1 3

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 141421 173205

[出力例]

34076506

※AtCoderテストケースより

[入力例]

2718281 82845 90452

[出力例]

443740209

[入力例]

31415926 53589 79323

[出力例]

174245672

[入力例]

123456789 101112 131415

[出力例]

557850348

■参照サイト
AtCoder Beginner Contest 156

2020年2月13日2020年2月29日

C++ の動作確認をしてみた（１４７）

C++の練習を兼ねて, AtCoder Beginner Contest 154 の問題E (E – Almost Everywhere Zero) を解いてみた(二回目).

■感想.
1. 前回いまいちな解き方していたので, 解説で, 桁DPを使うことを指摘されていたので, 解き直してみた.
2. 色々苦労したものの, 苦手な DP の訓練のため, 良い経験になったと思う.
※ dp0, dp1 で, どのような値が保存されるかのイメージが, 見えるまでに, 時間かかってしまった(汗).
3. 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 154解説をご覧下さい.

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

// ロジック, コメントを, 一部修正して, 再提出.
// 桁DP使った実装.
// 解き直し.
// https://img.atcoder.jp/abc154/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#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--)
int dp0[111][4]; // 上からi桁目まで決めて, 0でない桁がj個あり, Nより小さいことが確定.
int dp1[111][4]; // 上からi桁目まで決めて, 0でない桁がj個あり, Nより小さいことが未確定.

int main(){
    
    // 1. 入力情報.
    int K;
    char N[111];
    scanf("%s %d", N, &K);
    int d = strlen(N);
    
    // 2. 解説通り.
    // 2-1. dp1更新.
    // ex.
    // 3500125
    // 3
    // => 以下のように設定したい.
    // dp1[0][1] = 1 // 1桁目が, '3'.
    // dp1[1][2] = 1 // 2桁目が, '5'.
    // dp1[2][2] = 1 // 3桁目が, '0'.
    // dp1[3][2] = 1 // 4桁目が, '0'.
    // dp1[4][3] = 1 // 5桁目が, '1'.
    // dp1[5][3] = 0 // 6桁目が, '2'. (※但し, dp1[5][4] = 1 を イメージしている)
    // dp1[6][3] = 0 // 7桁目が, '5'. (※但し, dp1[6][5] = 1 を イメージしている)
    int c = 1;
    dp1[0][c] = 1; // 1桁目を更新.
    repx(i, 1, d){
        if(N[i] > '0') c++;
        if(c > K)      break; // この条件が無いと, 上手く動作しないように見える.
        dp1[i][c] = 1;
    }
    // rep(i, d){
    //     rep(j, 4) printf("%d ", dp1[i][j]);
    //     puts("");
    // }
    
    // 2-2. dp0更新.
    // ex.
    // [入力例]
    // 3500125
    // 3
    // => 以下のように更新していく.
    // [1桁目]
    // dp0[0][0] = 1 // 1桁目が, '0'.        (0XXXXXX のみ)
    // dp0[0][1] = 2 // 1桁目が, '1' ～ '2'. (1XXXXXX, 2XXXXXX のみ)
    // dp0[0][2] = 0 // 1桁目までで, '0' でない数字が, 2個出ることはありえない.
    // dp0[0][3] = 0 // 1桁目までで, '0' でない数字が, 3個出ることはありえない.
    // 
    // [2桁目]
    // dp0[1][0] = 1                             // 2桁目も, '0'. (00XXXXX のみ)
    // dp0[1][1] 
    // = dp0[0][0] * 9                           // 2桁目が, '0' 以外. (01XXXXX, 05XXXXX など)
    // + dp0[0][1] * 1                           // 2桁目が, '0'.      (10XXXXX, 20XXXXX のみ)
    // + dp1[0][0] * (N[1] > '1') * (N[1] - '1') // 2桁目が, '0' 以外. (今回は無し)
    // + dp1[0][1] * (N[1] > '0')                // 2桁目が, '0'.      (30XXXXX の形)
    // = 1 * 9 + 2 * 1 + 0 * 1 * 4 + 1 * 1 = 12通り.
    // dp0[1][2] 
    // = dp0[0][1] * 9                           // 2桁目が, '0' 以外.   (21XXXXX, 15XXXXX など)
    // + dp0[0][2] * 1                           // 2桁目が, '0'.        (今回は無し)
    // + dp1[0][1] * (N[1] > '1') * (N[1] - '1') // 2桁目が, '1' ～ '4'. (31XXXXX, 34XXXXX など)
    // + dp1[0][2] * (N[1] > '0')                // 2桁目が, '0'.        (今回は無し)
    // = 2 * 9 + 0 * 1 + 1 * 1 * 4 + 0 * 1 = 22通り.
    // dp0[1][3] = 0 // 2桁目までで, '0' でない数字が, 3個出ることはありえない.
    // ※ 上記の結果から, 例えば, 以下の入力例は, dp0[1][2] + dp1[1][2] = 22 + 1 = 23通り と 計算できたりする.
    // [入力例]
    // 35
    // 2
    // 
    // [3桁目]
    // dp0[2][0] = 1                             // 3桁目も, '0'. (000XXXX のみ)
    // dp0[2][1] 
    // = dp0[1][0] * 9                           // 3桁目が, '0' 以外. (002XXXX, 005XXXX など)
    // + dp0[1][1] * 1                           // 3桁目が, '0'.      (100XXXX, 020XXXX など)
    // + dp1[1][0] * (N[2] > '1') * (N[2] - '1') // 3桁目が, '0' 以外. (今回は無し)
    // + dp1[1][1] * (N[2] > '0')                // 3桁目が, '0'.      (今回は無し)
    // = 1 * 9 + 12 * 1 + 0 * 0 * (-1) + 0 * 0 = 21通り.
    // dp0[2][2] 
    // = dp0[1][1] * 9                           // 3桁目が, '0' 以外. (209XXXX, 057XXXX など)
    // + dp0[1][2] * 1                           // 3桁目が, '0'.      (120XXXX, 280XXXX など)
    // + dp1[1][1] * (N[2] > '1') * (N[2] - '1') // 3桁目が, '0' 以外. (今回は無し)
    // + dp1[1][2] * (N[2] > '0')                // 3桁目が, '0'.      (今回は無し)
    // = 12 * 9 + 22 * 1 + 0 * 0 * (-1) + 1 * 0 = 130通り.
    // dp0[2][3] 
    // = dp0[1][2] * 9                           // 3桁目が, '0' 以外. (219XXXX, 176XXXX など)
    // + dp0[1][3] * 1                           // 3桁目が, '0'.      (今回は無し)
    // + dp1[1][2] * (N[2] > '1') * (N[2] - '1') // 3桁目が, '0' 以外. (今回は無し)
    // + dp1[1][3] * (N[2] > '0')                // 3桁目が, '0'.      (今回は無し)
    // = 22 * 9 + 0 * 1 + 1 * 0 * (-1) + 0 * 0 = 198通り.
    // ※ 上記の結果から, 例えば, 以下の入力例は, dp0[2][3] + dp1[2][3] = 198 + 0 = 198通り と 計算できたりする.
    // [入力例]
    // 350
    // 3
    // 
    // ～(略)～
    // 
    // [7桁目]
    // dp0[6][0] = 1                             // 7桁目も, '0'. (0000000 のみ)
    // dp0[6][1] 
    // = dp0[5][0] * 9                           // 7桁目が, '0' 以外. (0000001, 0000009 など)
    // + dp0[5][1] * 1                           // 7桁目が, '0'.      (1000000, 0000700 など)
    // + dp1[5][0] * (N[6] > '1') * (N[6] - '1') // 7桁目が, '0' 以外. (今回は無し)
    // + dp1[5][1] * (N[6] > '0')                // 7桁目が, '0'.      (今回は無し)
    // = 1 * 9 + 48 * 1 + 0 * 1 * 4 + 0 * 1 = 57通り.
    // dp0[6][2] 
    // = dp0[5][1] * 9                           // 7桁目が, '0' 以外. (0090001, 2000009 など)
    // + dp0[5][2] * 1                           // 7桁目が, '0'.      (1050000, 0007700 など)
    // + dp1[5][1] * (N[6] > '1') * (N[6] - '1') // 7桁目が, '0' 以外. (今回は無し)
    // + dp1[5][2] * (N[6] > '0')                // 7桁目が, '0'.      (今回は無し)
    // = 48 * 9 + 941 * 1 + 0 * 1 * 4 + 0 * 1 = 1373通り.
    // dp0[6][3] = 0 
    // = dp0[5][2] * 9                           // 7桁目が, '0' 以外. (1007001, 2080009 など)
    // + dp0[5][3] * 1                           // 7桁目が, '0'.      (1060010, 2050900 など)
    // + dp1[5][2] * (N[6] > '1') * (N[6] - '1') // 7桁目が, '0' 以外. (今回は無し)
    // + dp1[5][3] * (N[6] > '0')                // 7桁目が, '0'.      (今回は無し)
    // = 941 * 9 + 9550 * 1 + 0 * 1 * 4 + 0 * 1 = 18019通り.
    // => 以上から, dp0[6][3] + dp1[6][3] = 18019 + 0 = 18019通り と 計算できた.
    // 
    // 1桁目を更新.
    dp0[0][0] = 1;
    dp0[0][1] = N[0] - '1';
    
    // 2桁目以降を更新.
    repx(i, 1, d) dp0[i][0] = 1;
    repx(i, 1, d){
        repx(j, 1, 4){
            // (i - 1)桁目までで, '0' でない桁が, (j - 1)個出現する形で, 確定している場合,
            // i桁目は, '1' ～ '9'(9通り) を取り得る(※).
            // ※もし, i桁目が, '0' の場合, i桁目までで, '0' でない桁が, j個とならないので矛盾.
            dp0[i][j] = dp0[i - 1][j - 1] * 9;
            
            // (i - 1)桁目までで, '0' でない桁が, j個出現する形で, 確定している場合,
            // i桁目は, '0'(1通り) のみ取り得る(※).
            // ※もし, i桁目が, '1' ～ '9' の場合, i桁目までで, '0' でない桁が, (j + 1)個となり矛盾.
            dp0[i][j] += dp0[i - 1][j] * 1;
            
            // i桁目が, '1' ～ '(N[i] - '1')' で 確定(※)するためには, (i - 1)桁目までで, 
            // '0' でない桁が, (j - 1)個出現している必要がある.
            // ※もし, i桁目が, 'N[i]' の場合, N より小さいか確定していないので, 矛盾.
            // => N = 12 K = 2 として, 1桁目 を 1 を 確定させると, 最大 11, ... , 19 がカウントされ, 9個 となるが,
            // 実際は, 2通りなので, 誤った結果となる.
            dp0[i][j] += dp1[i - 1][j - 1] * (N[i] > '1') * (N[i] - '1');
            
            // i桁目が, '0' (1通り) で 確定するためには, i桁目が, '0' より 大きい必要がある.
            // -> この1通りは, N[i] > '0' の 値で, 表現可能である.
            dp0[i][j] += dp1[i - 1][j] * (N[i] > '0');
        }
    }
    // rep(i, d){
    //     rep(j, 4) printf("%d ", dp0[i][j]);
    //     puts("");
    // }
    
    // 3. 出力.
    printf("%d\n", dp0[d - 1][K] + dp1[d - 1][K]);
    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

// ロジック, コメントを, 一部修正して, 再提出.

// 桁DP使った実装.

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

#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--)

int dp0[111][4]; // 上からi桁目まで決めて, 0でない桁がj個あり, Nより小さいことが確定.

int dp1[111][4]; // 上からi桁目まで決めて, 0でない桁がj個あり, Nより小さいことが未確定.

int main(){

// 1. 入力情報.

int K;

char N[111];

scanf("%s %d", N, &K);

int d = strlen(N);

// 2. 解説通り.

// 2-1. dp1更新.

// ex.

// 3500125

// 3

// => 以下のように設定したい.

// dp1[0][1] = 1 // 1桁目が, '3'.

// dp1[1][2] = 1 // 2桁目が, '5'.

// dp1[2][2] = 1 // 3桁目が, '0'.

// dp1[3][2] = 1 // 4桁目が, '0'.

// dp1[4][3] = 1 // 5桁目が, '1'.

// dp1[5][3] = 0 // 6桁目が, '2'. (※但し, dp1[5][4] = 1 をイメージしている)

// dp1[6][3] = 0 // 7桁目が, '5'. (※但し, dp1[6][5] = 1 をイメージしている)

int c = 1;

dp1[0][c] = 1; // 1桁目を更新.

repx(i, 1, d){

if(N[i] > '0') c++;

if(c > K) break; // この条件が無いと, 上手く動作しないように見える.

dp1[i][c] = 1;

}

// rep(i, d){

// rep(j, 4) printf("%d ", dp1[i][j]);

// puts("");

// }

// 2-2. dp0更新.

// ex.

// [入力例]

// 3500125

// 3

// => 以下のように更新していく.

// [1桁目]

// dp0[0][0] = 1 // 1桁目が, '0'. (0XXXXXX のみ)

// dp0[0][1] = 2 // 1桁目が, '1' ～ '2'. (1XXXXXX, 2XXXXXX のみ)

// dp0[0][2] = 0 // 1桁目までで, '0' でない数字が, 2個出ることはありえない.

// dp0[0][3] = 0 // 1桁目までで, '0' でない数字が, 3個出ることはありえない.

// [2桁目]

// dp0[1][0] = 1 // 2桁目も, '0'. (00XXXXX のみ)

// dp0[1][1]

// = dp0[0][0] * 9 // 2桁目が, '0' 以外. (01XXXXX, 05XXXXX など)

// + dp0[0][1] * 1 // 2桁目が, '0'. (10XXXXX, 20XXXXX のみ)

// + dp1[0][0] * (N[1] > '1') * (N[1] - '1') // 2桁目が, '0' 以外. (今回は無し)

// + dp1[0][1] * (N[1] > '0') // 2桁目が, '0'. (30XXXXX の形)

// = 1 * 9 + 2 * 1 + 0 * 1 * 4 + 1 * 1 = 12通り.

// dp0[1][2]

// = dp0[0][1] * 9 // 2桁目が, '0' 以外. (21XXXXX, 15XXXXX など)

// + dp0[0][2] * 1 // 2桁目が, '0'. (今回は無し)

// + dp1[0][1] * (N[1] > '1') * (N[1] - '1') // 2桁目が, '1' ～ '4'. (31XXXXX, 34XXXXX など)

// + dp1[0][2] * (N[1] > '0') // 2桁目が, '0'. (今回は無し)

// = 2 * 9 + 0 * 1 + 1 * 1 * 4 + 0 * 1 = 22通り.

// dp0[1][3] = 0 // 2桁目までで, '0' でない数字が, 3個出ることはありえない.

// ※ 上記の結果から, 例えば, 以下の入力例は, dp0[1][2] + dp1[1][2] = 22 + 1 = 23通りと計算できたりする.

// [入力例]

// 35

// 2

// [3桁目]

// dp0[2][0] = 1 // 3桁目も, '0'. (000XXXX のみ)

// dp0[2][1]

// = dp0[1][0] * 9 // 3桁目が, '0' 以外. (002XXXX, 005XXXX など)

// + dp0[1][1] * 1 // 3桁目が, '0'. (100XXXX, 020XXXX など)

// + dp1[1][0] * (N[2] > '1') * (N[2] - '1') // 3桁目が, '0' 以外. (今回は無し)

// + dp1[1][1] * (N[2] > '0') // 3桁目が, '0'. (今回は無し)

// = 1 * 9 + 12 * 1 + 0 * 0 * (-1) + 0 * 0 = 21通り.

// dp0[2][2]

// = dp0[1][1] * 9 // 3桁目が, '0' 以外. (209XXXX, 057XXXX など)

// + dp0[1][2] * 1 // 3桁目が, '0'. (120XXXX, 280XXXX など)

// + dp1[1][1] * (N[2] > '1') * (N[2] - '1') // 3桁目が, '0' 以外. (今回は無し)

// + dp1[1][2] * (N[2] > '0') // 3桁目が, '0'. (今回は無し)

// = 12 * 9 + 22 * 1 + 0 * 0 * (-1) + 1 * 0 = 130通り.

// dp0[2][3]

// = dp0[1][2] * 9 // 3桁目が, '0' 以外. (219XXXX, 176XXXX など)

// + dp0[1][3] * 1 // 3桁目が, '0'. (今回は無し)

// + dp1[1][2] * (N[2] > '1') * (N[2] - '1') // 3桁目が, '0' 以外. (今回は無し)

// + dp1[1][3] * (N[2] > '0') // 3桁目が, '0'. (今回は無し)

// = 22 * 9 + 0 * 1 + 1 * 0 * (-1) + 0 * 0 = 198通り.

// ※ 上記の結果から, 例えば, 以下の入力例は, dp0[2][3] + dp1[2][3] = 198 + 0 = 198通りと計算できたりする.

// [入力例]

// 350

// 3

// ～(略)～

// [7桁目]

// dp0[6][0] = 1 // 7桁目も, '0'. (0000000 のみ)

// dp0[6][1]

// = dp0[5][0] * 9 // 7桁目が, '0' 以外. (0000001, 0000009 など)

// + dp0[5][1] * 1 // 7桁目が, '0'. (1000000, 0000700 など)

// + dp1[5][0] * (N[6] > '1') * (N[6] - '1') // 7桁目が, '0' 以外. (今回は無し)

// + dp1[5][1] * (N[6] > '0') // 7桁目が, '0'. (今回は無し)

// = 1 * 9 + 48 * 1 + 0 * 1 * 4 + 0 * 1 = 57通り.

// dp0[6][2]

// = dp0[5][1] * 9 // 7桁目が, '0' 以外. (0090001, 2000009 など)

// + dp0[5][2] * 1 // 7桁目が, '0'. (1050000, 0007700 など)

// + dp1[5][1] * (N[6] > '1') * (N[6] - '1') // 7桁目が, '0' 以外. (今回は無し)

// + dp1[5][2] * (N[6] > '0') // 7桁目が, '0'. (今回は無し)

// = 48 * 9 + 941 * 1 + 0 * 1 * 4 + 0 * 1 = 1373通り.

// dp0[6][3] = 0

// = dp0[5][2] * 9 // 7桁目が, '0' 以外. (1007001, 2080009 など)

// + dp0[5][3] * 1 // 7桁目が, '0'. (1060010, 2050900 など)

// + dp1[5][2] * (N[6] > '1') * (N[6] - '1') // 7桁目が, '0' 以外. (今回は無し)

// + dp1[5][3] * (N[6] > '0') // 7桁目が, '0'. (今回は無し)

// = 941 * 9 + 9550 * 1 + 0 * 1 * 4 + 0 * 1 = 18019通り.

// => 以上から, dp0[6][3] + dp1[6][3] = 18019 + 0 = 18019通りと計算できた.

// 1桁目を更新.

dp0[0][0] = 1;

dp0[0][1] = N[0] - '1';

// 2桁目以降を更新.

repx(i, 1, d) dp0[i][0] = 1;

repx(i, 1, d){

repx(j, 1, 4){

// (i - 1)桁目までで, '0' でない桁が, (j - 1)個出現する形で, 確定している場合,

// i桁目は, '1' ～ '9'(9通り) を取り得る(※).

// ※もし, i桁目が, '0' の場合, i桁目までで, '0' でない桁が, j個とならないので矛盾.

dp0[i][j] = dp0[i - 1][j - 1] * 9;

// (i - 1)桁目までで, '0' でない桁が, j個出現する形で, 確定している場合,

// i桁目は, '0'(1通り) のみ取り得る(※).

// ※もし, i桁目が, '1' ～ '9' の場合, i桁目までで, '0' でない桁が, (j + 1)個となり矛盾.

dp0[i][j] += dp0[i - 1][j] * 1;

// i桁目が, '1' ～ '(N[i] - '1')' で確定(※)するためには, (i - 1)桁目までで,

// '0' でない桁が, (j - 1)個出現している必要がある.

// ※もし, i桁目が, 'N[i]' の場合, N より小さいか確定していないので, 矛盾.

// => N = 12 K = 2 として, 1桁目を 1 を確定させると, 最大 11, ... , 19 がカウントされ, 9個となるが,

// 実際は, 2通りなので, 誤った結果となる.

dp0[i][j] += dp1[i - 1][j - 1] * (N[i] > '1') * (N[i] - '1');

// i桁目が, '0' (1通り) で確定するためには, i桁目が, '0' より大きい必要がある.

// -> この1通りは, N[i] > '0' の値で, 表現可能である.

dp0[i][j] += dp1[i - 1][j] * (N[i] > '0');

}

// rep(i, d){

// rep(j, 4) printf("%d ", dp0[i][j]);

// puts("");

// }

// 3. 出力.

printf("%d\n", dp0[d - 1][K] + dp1[d - 1][K]);

return 0;

}

[入力例]
100
1

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

[入力例]
25
2

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

[入力例]
314159
2

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

[入力例]
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

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

[入力例]
1
2

[出力例]
0

[入力例]
100
3

[出力例]
0

[入力例]
1111
3

[出力例]
820

[入力例]
3500125
3

[出力例]
18019

[入力例]
123454321
3

[出力例]
42645

[入力例]
12345678987654321
1

[出力例]
145

[入力例]
12345678987654321
2

[出力例]
9857

[入力例]
12345678987654321
3

[出力例]
417009

[入力例]
100200300400500600700800900
3

[出力例]
1916283

[入力例]
3971059109076882976283276868823325568475235692362086997028948054557023320411225092214081379099432804
2

[出力例]
395604

[入力例]
3316624790355399849114932736670686683927088545589353597058682146116484642609043846708843399128290650
3

[出力例]
115516414

100

101

102

103

104

105

106

107

108

[入力例]

100

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

314159

[出力例]

937

※AtCoderテストケースより

[入力例]

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

[出力例]

117879300

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

100

[出力例]

[入力例]

1111

[出力例]

820

[入力例]

3500125

[出力例]

18019

[入力例]

123454321

[出力例]

42645

[入力例]

12345678987654321

[出力例]

145

[入力例]

12345678987654321

[出力例]

9857

[入力例]

12345678987654321

[出力例]

417009

[入力例]

100200300400500600700800900

[出力例]

1916283

[入力例]

3971059109076882976283276868823325568475235692362086997028948054557023320411225092214081379099432804

[出力例]

395604

[入力例]

3316624790355399849114932736670686683927088545589353597058682146116484642609043846708843399128290650

[出力例]

115516414

■参照サイト
AtCoder Beginner Contest 154

2020年2月11日2020年2月29日

C++ の動作確認をしてみた（１４６）

C++の練習を兼ねて, AtCoder Beginner Contest 154 の問題F (F – Many Many Paths) を解いてみた.

■感想.
1. 高速に計算する方法が見えなかったので, 解説を確認して実装した.
2. 組み合わせの性質を, 新しく仕入れることが出来たので, 個人的には, 大満足だった.
3. 引き続き, たくさんの過去問を振り返っていきたいと思う.

本家のサイトABC 154解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/abc154/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(LL i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
const LL MOD = 1e9 + 7;
const int LIMIT = 2020202;
LL FAC[LIMIT];
LL INV[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL inverse(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;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

// (0, 0) ～ (r, c) の範囲で, 組み合わせ(nCk) の 総和 を 計算.
// @param r: (目的地の)行番号.
// @param c: (目的地の)列番号.
// @return : 計算結果(mod版).
LL S(LL r, LL c){
    // TLE版.
    // ex.
    // 12345 123 54321 543
    // -> 614939681 の 出力で, 481[ms] かかった.
    // LL ret = 0;
    // rep(i, r + 1) rep(j, c + 1) ret += combination(i + j, i), ret %= MOD;
    
    // 高速版(解説通り).
    LL ret = combination(r + 1 + c + 1, c + 1);
    ret += MOD;
    ret--;
    ret %= MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL r1, c1, r2, c2;
    scanf("%lld %lld %lld %lld", &r1, &c1, &r2, &c2);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = inverse(FAC[i], MOD - 2) % MOD;
    
    // 2. チェック.
    assert(S(0, 0) == combination(1 + 1, 1) - 1);
    assert(S(0, 1) == combination(1 + 2, 2) - 1);
    assert(S(1, 0) == combination(2 + 1, 1) - 1);
    assert(S(1, 1) == combination(2 + 2, 2) - 1);
    assert(S(5, 8) == combination(6 + 9, 9) - 1);
    assert(S(12, 15) == combination(13 + 16, 16) - 1);
    
    // 3. 経路数の総和を計算(解説通り).
    // S(r, c) = ΣΣf(i, j) (0 <= i <= r, 0 <= j <= c) と置くと,
    // S(r2, c2) - S(r2, c1 - 1) - S(r1 - 1, c2) + S(r1 - 1, c1 - 1) で 計算可能とのこと.
    // また, S(r, c) = f(r + 1, c + 1) - 1 となることを使うらしい.
    LL ans = 0;
    ans += S(r2, c2);
    ans += MOD;
    ans -= S(r2, c1 - 1);
    ans %= MOD;
    ans += MOD;
    ans -= S(r1 - 1, c2);
    ans %= MOD;
    ans += S(r1 - 1, c1 - 1);
    ans %= MOD;
    
    // 4. 出力 ～ 後処理.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

const LL MOD = 1e9 + 7;

const int LIMIT = 2020202;

LL FAC[LIMIT];

LL INV[LIMIT];

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

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

// @param b: 指数.

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

LL inverse(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;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

// (0, 0) ～ (r, c) の範囲で, 組み合わせ(nCk) の総和を計算.

// @param r: (目的地の)行番号.

// @param c: (目的地の)列番号.

// @return : 計算結果(mod版).

LL S(LL r, LL c){

// TLE版.

// ex.

// 12345 123 54321 543

// -> 614939681 の出力で, 481[ms] かかった.

// LL ret = 0;

// rep(i, r + 1) rep(j, c + 1) ret += combination(i + j, i), ret %= MOD;

// 高速版(解説通り).

LL ret = combination(r + 1 + c + 1, c + 1);

ret += MOD;

ret--;

ret %= MOD;

return ret;

}

int main(){

// 1. 入力情報.

LL r1, c1, r2, c2;

scanf("%lld %lld %lld %lld", &r1, &c1, &r2, &c2);

FAC[0] = 1;

repx(i, 1, LIMIT) FAC[i] = i * FAC[i - 1] % MOD;

rep(i, LIMIT) INV[i] = inverse(FAC[i], MOD - 2) % MOD;

// 2. チェック.

assert(S(0, 0) == combination(1 + 1, 1) - 1);

assert(S(0, 1) == combination(1 + 2, 2) - 1);

assert(S(1, 0) == combination(2 + 1, 1) - 1);

assert(S(1, 1) == combination(2 + 2, 2) - 1);

assert(S(5, 8) == combination(6 + 9, 9) - 1);

assert(S(12, 15) == combination(13 + 16, 16) - 1);

// 3. 経路数の総和を計算(解説通り).

// S(r, c) = ΣΣf(i, j) (0 <= i <= r, 0 <= j <= c) と置くと,

// S(r2, c2) - S(r2, c1 - 1) - S(r1 - 1, c2) + S(r1 - 1, c1 - 1) で計算可能とのこと.

// また, S(r, c) = f(r + 1, c + 1) - 1 となることを使うらしい.

LL ans = 0;

ans += S(r2, c2);

ans += MOD;

ans -= S(r2, c1 - 1);

ans %= MOD;

ans += MOD;

ans -= S(r1 - 1, c2);

ans %= MOD;

ans += S(r1 - 1, c1 - 1);

ans %= MOD;

// 4. 出力～後処理.

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

return 0;

}

[入力例]
1 1 2 2

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

[入力例]
314 159 2653 589

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

[入力例]
2 3 5 7

[出力例]
2884

[入力例]
577 2156 64901 532860

[出力例]
939635786

[入力例]
120 2056 90315 959428

[出力例]
689057583

[入力例]
111111 222222 333333 444444

[出力例]
548411328

[入力例]
1 1 1000000 1000000

[出力例]
625314154

[入力例]

1 1 2 2

[出力例]

※AtCoderテストケースより

[入力例]

314 159 2653 589

[出力例]

602215194

※AtCoderテストケースより

[入力例]

2 3 5 7

[出力例]

2884

[入力例]

577 2156 64901 532860

[出力例]

939635786

[入力例]

120 2056 90315 959428

[出力例]

689057583

[入力例]

111111 222222 333333 444444

[出力例]

548411328

[入力例]

1 1 1000000 1000000

[出力例]

625314154

■参照サイト
AtCoder Beginner Contest 154

2020年2月11日2020年2月29日

C++ の動作確認をしてみた（１４５）

C++の練習を兼ねて, AtCoder Beginner Contest 154 の問題E (E – Almost Everywhere Zero) を解いてみた.

■感想.
1. 解説を見る前にAC版となったものの, 実装に大変苦労した(問題の本質が見えて無い気がする).
2. 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 154解説をご覧下さい.

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

// コメントなど修正して, 再提出.
#include <bits/stdc++.h>
using namespace std;
#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--)
int C[111][111]; // nCr の 事前計算.
int p9[5] = {1, 9, 81, 729, 6561};

// 0でない数字が, ちょうどK個あるようなものの個数を計算.
// @param N: 与えられた整数.
// @param c: 現在見ている桁.
// @param k: 0でない数字が使える残りの桁数.
// @return : 計算結果.
int recursive(string N, int c, int k){
    int ret = 0, d = N.size();
    // ex.
    // 10
    //  2
    // -> 0 が 正解だが, 1 と 出力された.
    // -> 以下の桁数チェックのロジックを追加.
    // -> hand_02 で WA版 となったので, 最初にチェックさせるように修正.
    if(d - c < k) return 0;
    
    // hand_03 ～ hand_05 で, WA版.
    // ex.
    // 1
    // 1
    // -> 1 が 正解だが, 3 と 出力されたため, ロジック修正.
    // if(c >= d) return 1;
    if(c >= d - 1) return N[d - 1] - '0';
    if(k == 0) return 1;
    
    if(N[c] > '0'){
        // c桁目が, 0 だった場合, (c + 1)桁目 ～ d桁目 の中で, 1 ～ 9 を k回選択できる.
        ret += C[d - 1 - c][k] * p9[k];
        
        // c桁目が, 1 ～ (N[c] - 1) だった場合, (c + 1)桁目 ～ d桁目 の中で, 1 ～ 9 を (k - 1)回選択できる.
        ret += (N[c] - '1') * C[d - 1 - c][k - 1] * p9[k - 1];
        
        // c桁目が, N[c] だった場合, (c + 1)桁目 ～ d桁目 の中で, 1 ～ 9 を (k - 1)回選択できる.
        ret += recursive(N, c + 1, k - 1);
    }else{
        // c桁目が, 0 だった場合, (c + 1)桁目 ～ d桁目 の中で, 1 ～ 9 を k回選択できる.
        ret += recursive(N, c + 1, k);
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int K;
    char c[111];
    scanf("%s %d", c, &K);
    string N(c);
    int d = N.size();
    
    // 2. nCr の 事前計算.
    C[0][0] = 1;
    rep(n, 111) C[n][0] = C[n][n] = 1;
    rep(n, 110) repx(k, 1, 111) C[n + 1][k] = C[n][k - 1] + C[n][k];
    
    // 3. 0でない数字が, ちょうどK個あるようなものの個数を計算.
    // ex.
    // 1111
    // 3
    // 
    // 1011 ～ 1099: 81通り
    // 1101 ～ 1109: 9通り
    // 1110 ～ 1110: 1通り
    // 0111 ～ 0999: 729通り
    // => 合計 820通り
    int ans = recursive(N, 0, K);
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// コメントなど修正して, 再提出.

#include <bits/stdc++.h>

using namespace std;

#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--)

int C[111][111]; // nCr の事前計算.

int p9[5] = {1, 9, 81, 729, 6561};

// 0でない数字が, ちょうどK個あるようなものの個数を計算.

// @param N: 与えられた整数.

// @param c: 現在見ている桁.

// @param k: 0でない数字が使える残りの桁数.

// @return : 計算結果.

int recursive(string N, int c, int k){

int ret = 0, d = N.size();

// ex.

// 10

// 2

// -> 0 が正解だが, 1 と出力された.

// -> 以下の桁数チェックのロジックを追加.

// -> hand_02 で WA版となったので, 最初にチェックさせるように修正.

if(d - c < k) return 0;

// hand_03 ～ hand_05 で, WA版.

// ex.

// 1

// -> 1 が正解だが, 3 と出力されたため, ロジック修正.

// if(c >= d) return 1;

if(c >= d - 1) return N[d - 1] - '0';

if(k == 0) return 1;

if(N[c] > '0'){

// c桁目が, 0 だった場合, (c + 1)桁目～ d桁目の中で, 1 ～ 9 を k回選択できる.

ret += C[d - 1 - c][k] * p9[k];

// c桁目が, 1 ～ (N[c] - 1) だった場合, (c + 1)桁目～ d桁目の中で, 1 ～ 9 を (k - 1)回選択できる.

ret += (N[c] - '1') * C[d - 1 - c][k - 1] * p9[k - 1];

// c桁目が, N[c] だった場合, (c + 1)桁目～ d桁目の中で, 1 ～ 9 を (k - 1)回選択できる.

ret += recursive(N, c + 1, k - 1);

}else{

// c桁目が, 0 だった場合, (c + 1)桁目～ d桁目の中で, 1 ～ 9 を k回選択できる.

ret += recursive(N, c + 1, k);

}

return ret;

}

int main(){

// 1. 入力情報.

int K;

char c[111];

scanf("%s %d", c, &K);

string N(c);

int d = N.size();

// 2. nCr の事前計算.

C[0][0] = 1;

rep(n, 111) C[n][0] = C[n][n] = 1;

rep(n, 110) repx(k, 1, 111) C[n + 1][k] = C[n][k - 1] + C[n][k];

// 3. 0でない数字が, ちょうどK個あるようなものの個数を計算.

// ex.

// 1111

// 3

// 1011 ～ 1099: 81通り

// 1101 ～ 1109: 9通り

// 1110 ～ 1110: 1通り

// 0111 ～ 0999: 729通り

// => 合計 820通り

int ans = recursive(N, 0, K);

// 4. 出力.

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

return 0;

}

[入力例]
100
1

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

[入力例]
25
2

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

[入力例]
314159
2

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

[入力例]
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

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

[入力例]
1
2

[出力例]
0

[入力例]
1111
3

[出力例]
820

[入力例]
123454321
3

[出力例]
42645

[入力例]
12345678987654321
3

[出力例]
417009

[入力例]
100200300400500600700800900
3

[出力例]
1916283

[入力例]
3971059109076882976283276868823325568475235692362086997028948054557023320411225092214081379099432804
3

[出力例]
115521712

[入力例]
100
3

[出力例]
0

[入力例]

100

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

314159

[出力例]

937

※AtCoderテストケースより

[入力例]

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

[出力例]

117879300

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

1111

[出力例]

820

[入力例]

123454321

[出力例]

42645

[入力例]

12345678987654321

[出力例]

417009

[入力例]

100200300400500600700800900

[出力例]

1916283

[入力例]

3971059109076882976283276868823325568475235692362086997028948054557023320411225092214081379099432804

[出力例]

115521712

[入力例]

100

[出力例]

■参照サイト
AtCoder Beginner Contest 154

2020年2月10日2020年2月29日

C++ の動作確認をしてみた（１４４）

C++の練習を兼ねて, AtCoder Beginner Contest 154 の問題D (D – Dice in Line) を解いてみた.

■感想.
1. 累積和を使う方法に気付けたので, 良かったと思う.
2. 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 154解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
#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--)
double e[202020], ecum[202020];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N){
        double p;
        scanf("%lf", &p);
        e[i] = (p + 1.0) / 2.0; // i番目のサイコロの期待値.
    }
    
    // 2. 累積和.
    rep(i, N) ecum[i + 1] = ecum[i] + e[i];
    
    // 3. 出る目の合計の期待値の最大値は？
    double ans = 0.0;
    rep(i, N - K + 1) ans = max(ans, ecum[i + K] - ecum[i]);
    
    // 4. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

#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--)

double e[202020], ecum[202020];

int main(){

// 1. 入力情報.

int N, K;

scanf("%d %d", &N, &K);

rep(i, N){

double p;

scanf("%lf", &p);

e[i] = (p + 1.0) / 2.0; // i番目のサイコロの期待値.

}

// 2. 累積和.

rep(i, N) ecum[i + 1] = ecum[i] + e[i];

// 3. 出る目の合計の期待値の最大値は？

double ans = 0.0;

rep(i, N - K + 1) ans = max(ans, ecum[i + K] - ecum[i]);

// 4. 出力.

printf("%.12lf\n", ans);

return 0;

}

[入力例]
5 3
1 2 2 4 5

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

[入力例]
4 1
6 6 6 6

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

[入力例]
10 4
17 13 13 12 15 20 10 13 17 11

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

[入力例]
20 5
5 6 11 11 3 18 8 18 7 13 6 18 2 14 17 15 3 19 12 18

[出力例]
36.500000000000

[入力例]

5 3

1 2 2 4 5

[出力例]

7.000000000000

※AtCoderテストケースより

[入力例]

4 1

6 6 6 6

[出力例]

3.500000000000

※AtCoderテストケースより

[入力例]

10 4

17 13 13 12 15 20 10 13 17 11

[出力例]

32.000000000000

※AtCoderテストケースより

[入力例]

20 5

5 6 11 11 3 18 8 18 7 13 6 18 2 14 17 15 3 19 12 18

[出力例]

36.500000000000

■参照サイト
AtCoder Beginner Contest 154

C++の練習を兼ねて, AtCoder Beginner Contest 031 の 問題D (D – 語呂合わせ) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 156 の 問題F (F – Modularness) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 156 の 問題E (E – Roaming) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 156 の 問題D (D – Bouquet) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 154 の 問題E (E – Almost Everywhere Zero) を解いてみた(二回目).

C++の練習を兼ねて, AtCoder Beginner Contest 154 の 問題F (F – Many Many Paths) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 154 の 問題E (E – Almost Everywhere Zero) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 154 の 問題D (D – Dice in Line) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 031 の問題D (D – 語呂合わせ) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 156 の問題F (F – Modularness) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 156 の問題E (E – Roaming) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 156 の問題D (D – Bouquet) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 154 の問題E (E – Almost Everywhere Zero) を解いてみた(二回目).

C++の練習を兼ねて, AtCoder Beginner Contest 154 の問題F (F – Many Many Paths) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 154 の問題E (E – Almost Everywhere Zero) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 154 の問題D (D – Dice in Line) を解いてみた.