C++ の動作確認をしてみた（８０３）

C++の練習を兼ねて, AtCoder Grand Contest 023 の問題C (Painting Machines) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 但し, このような内容を解答で説明されているだろう, と推測した内容(重複カウントの除外など)をもとに, 実装している.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Grand Contest 023 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/agc023/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 pb push_back
const LL MOD = 1e9 + 7;
const int LIMIT = 1010101;
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;
}

// 組み合わせ(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. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = i * FAC[i - 1] % MOD;
        INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    }
    
    // 3. 例外(N = 2).
    if(N == 2){
        puts("1");
        return 0;
    }
    
    // 4. 例外(N = 3).
    if(N == 3){
        puts("4");
        return 0;
    }
    
    // 5. N > 3.
    LL ans = 0, bef = 0;
    repx(k, 2, N){
        // 今回分更新.
        LL cur = combination(k - 1, N - 1 - k);
        cur %= MOD;
        cur *= FAC[k];
        cur %= MOD;
        cur *= FAC[N - 1 - k];
        cur %= MOD;
        
        // スコア化.
        // -> スコア化には, マシンの稼働回数を反映させる必要があるので, k を 設定.
        LL e = (LL)k;
        
        // 重複カウント削除.
        // -> k 回マシンを稼働したときの場合の数は, (k - 1) 回マシンを稼働した場合の数を, 
        // 重複カウントしているため, 除外する必要がある.
        e *= (cur + MOD - bef);
        e %= MOD;
        
        // 集計.
        ans += e;
        ans %= MOD;
        
        // 前回分更新.
        bef = cur;
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://img.atcoder.jp/agc023/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 pb push_back

const LL MOD = 1e9 + 7;

const int LIMIT = 1010101;

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;

}

// 組み合わせ(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. 入力情報.

int N;

scanf("%d", &N);

// 2. 事前準備.

FAC[0] = INV[0] = 1;

repx(i, 1, LIMIT){

FAC[i] = i * FAC[i - 1] % MOD;

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

}

// 3. 例外(N = 2).

if(N == 2){

puts("1");

return 0;

}

// 4. 例外(N = 3).

if(N == 3){

puts("4");

return 0;

}

// 5. N > 3.

LL ans = 0, bef = 0;

repx(k, 2, N){

// 今回分更新.

LL cur = combination(k - 1, N - 1 - k);

cur %= MOD;

cur *= FAC[k];

cur %= MOD;

cur *= FAC[N - 1 - k];

cur %= MOD;

// スコア化.

// -> スコア化には, マシンの稼働回数を反映させる必要があるので, k を設定.

LL e = (LL)k;

// 重複カウント削除.

// -> k 回マシンを稼働したときの場合の数は, (k - 1) 回マシンを稼働した場合の数を,

// 重複カウントしているため, 除外する必要がある.

e *= (cur + MOD - bef);

e %= MOD;

// 集計.

ans += e;

ans %= MOD;

// 前回分更新.

bef = cur;

}

// 6. 出力.

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

return 0;

}

[入力例]
4

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

[入力例]
2

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

[入力例]
5

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

[入力例]
100000

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

[入力例]
3

[出力例]
4

[入力例]
6

[出力例]
516

[入力例]
7

[出力例]
3696

[入力例]
10

[出力例]
2786400

[入力例]
11

[出力例]
31000320

[入力例]
2022

[出力例]
810002666

[入力例]
1000000

[出力例]
128397156

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100000

[出力例]

341429644

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

516

[入力例]

[出力例]

3696

[入力例]

[出力例]

2786400

[入力例]

[出力例]

31000320

[入力例]

2022

[出力例]

810002666

[入力例]

1000000

[出力例]

128397156

■参照サイト
AtCoder Grand Contest 023

C++の練習を兼ねて, AtCoder Grand Contest 023 の 問題C (Painting Machines) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 023 の問題C (Painting Machines) を解いてみた.

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