C++ | 個人用メモ帳

2019年6月16日2019年6月16日

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

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

■感想.
1. 解答方針がよく分からなかったので, 解説から類推する形で解き直しした.
2. 二分探索を実装する部分で, 終了条件をどうすればよいか分からず, 手こずった.
=> これを解決するために, ゴリゴリ書く羽目になったものの, 以下の二点を対応したところ, AC版とすることが出来た.
① 風船の情報を, 構造体に保管して, 再利用できるようにした
② 確認対象としている高度で, 風船を割る方法が存在するかをチェックする関数の追加を行った

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

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

// 解き直し.
// ABC023 解説.
// https://www.slideshare.net/chokudai/abc023
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MAX = 1e18 + 1;

struct balloon {
    LL h;     // 風船の高度.
    LL s;     // 風船の速度.
    double t; // 制限時間.
    bool operator < (const balloon &B) const { return t < B.t; }
};

// 確認対象としている高度で, 風船を割る方法が存在するかをチェック.
// @param v: 風船に関する情報.
// @param opt: 確認対象の高度.
// @return : 風船を割る方法の存在確認.
//    true : 風船を割る方法が存在する, false : 風船を割る方法が存在しない.
bool isExist(vector<balloon> v, LL opt){
    
    bool ret = true;
    for(int i = 0; i < v.size(); i++){
        double bHeight = v[i].h + v[i].s * i + 0.0;
        // i秒後 の 風船の高さが, 確認対象の高度 を 超えていたら, 風船を割る方法が存在しないと判定.
        if(opt < bHeight){
            // cout << "i=" << i << " v[i].h=" << v[i].h << " v[i].s=" << v[i].h << " bHeight=" << bHeight << endl;
            ret = false;
            break;
        }
    }
    
    return ret;

}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    LL H[N], S[N];
    vector<balloon> v;
    for(int i = 0; i < N; i++){
        balloon b;
        cin >> b.h >> b.s;
        v.push_back(b);
    }
    
    // 2. 解説通り.
    // 高さを固定して, 制限時間で, sort.
    // -> 二分探索で, opt を 探す
    LL hi = MAX;
    LL lo  = 1;
    LL opt = MAX;
    int counter = 0;
    // 無限ループ防止のため, カウンター入れる.
    while(counter < 100){
        
        // 2-1. 制限時間を保存.
        for(int i = 0; i < N; i++){
            double t = (opt - v[i].h) / v[i].s;
            v[i].t = t;
        }
        
        // 2-2. sort.
        sort(v.begin(), v.end());
        
        // 2-3. hi, lo, opt 更新.
        // if(counter > 98) cout << " hi=" << hi << " lo=" << lo << " opt=" << opt << endl;
        bool b = isExist(v, opt);
        if(b) hi = (lo + hi) / 2LL;
        else  lo = (lo + hi) / 2LL + 1;
        opt = (hi + lo) / 2;
        
        // 2-4. カウンター を インクリメント.
        counter++;
        
        // 2-5. 終了.
        if(hi - lo <= 0) break;
        
    }
    
    // 3. 出力.
    cout << opt << endl;
    return 0;
   
}

// 解き直し.

// ABC023 解説.

// https://www.slideshare.net/chokudai/abc023

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MAX = 1e18 + 1;

struct balloon {

LL h; // 風船の高度.

LL s; // 風船の速度.

double t; // 制限時間.

bool operator < (const balloon &B) const { return t < B.t; }

};

// 確認対象としている高度で, 風船を割る方法が存在するかをチェック.

// @param v: 風船に関する情報.

// @param opt: 確認対象の高度.

// @return : 風船を割る方法の存在確認.

// true : 風船を割る方法が存在する, false : 風船を割る方法が存在しない.

bool isExist(vector<balloon> v, LL opt){

bool ret = true;

for(int i = 0; i < v.size(); i++){

double bHeight = v[i].h + v[i].s * i + 0.0;

// i秒後の風船の高さが, 確認対象の高度を超えていたら, 風船を割る方法が存在しないと判定.

if(opt < bHeight){

// cout << "i=" << i << " v[i].h=" << v[i].h << " v[i].s=" << v[i].h << " bHeight=" << bHeight << endl;

ret = false;

break;

}

return ret;

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

LL H[N], S[N];

vector<balloon> v;

for(int i = 0; i < N; i++){

balloon b;

cin >> b.h >> b.s;

v.push_back(b);

}

// 2. 解説通り.

// 高さを固定して, 制限時間で, sort.

// -> 二分探索で, opt を探す

LL hi = MAX;

LL lo = 1;

LL opt = MAX;

int counter = 0;

// 無限ループ防止のため, カウンター入れる.

while(counter < 100){

// 2-1. 制限時間を保存.

for(int i = 0; i < N; i++){

double t = (opt - v[i].h) / v[i].s;

v[i].t = t;

}

// 2-2. sort.

sort(v.begin(), v.end());

// 2-3. hi, lo, opt 更新.

// if(counter > 98) cout << " hi=" << hi << " lo=" << lo << " opt=" << opt << endl;

bool b = isExist(v, opt);

if(b) hi = (lo + hi) / 2LL;

else lo = (lo + hi) / 2LL + 1;

opt = (hi + lo) / 2;

// 2-4. カウンターをインクリメント.

counter++;

// 2-5. 終了.

if(hi - lo <= 0) break;

}

// 3. 出力.

cout << opt << endl;

return 0;

}

[入力例]
4
5 6
12 4
14 7
21 2

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

[入力例]
6
100 1
100 1
100 1
100 1
100 1
1 30

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

[入力例]
10
10 5
12 8
8 15
4 12
30 7
45 6
18 12
22 13
17 8
25 5

[出力例]
68
具体的には, 
競技開始から 0秒後 に 風船6 を割る, 風船6 の ペナルティは 45 +  6 × 0 = 45
競技開始から 1秒後 に 風船8 を割る, 風船8 の ペナルティは 22 + 13 × 1 = 35
競技開始から 2秒後 に 風船5 を割る, 風船5 の ペナルティは 30 +  7 × 2 = 44
競技開始から 3秒後 に 風船7 を割る, 風船7 の ペナルティは 18 + 12 × 3 = 54
競技開始から 4秒後 に 風船3 を割る, 風船3 の ペナルティは  8 + 15 × 4 = 68
競技開始から 5秒後 に 風船4 を割る, 風船4 の ペナルティは  4 + 12 × 5 = 64
競技開始から 6秒後 に 風船9 を割る, 風船9 の ペナルティは 17 +  8 × 6 = 65
競技開始から 7秒後 に 風船2 を割る, 風船2 の ペナルティは 12 +  8 × 7 = 68
競技開始から 8秒後 に 風船10を割る, 風船10の ペナルティは 25 +  5 × 8 = 65
競技開始から 9秒後 に 風船1 を割る, 風船1 の ペナルティは 10 +  5 × 9 = 55

[入力例]

5 6

12 4

14 7

21 2

[出力例]

※AtCoderテストケースより

[入力例]

100 1

1 30

[出力例]

105

※AtCoderテストケースより

[入力例]

10 5

12 8

8 15

4 12

30 7

45 6

18 12

22 13

17 8

25 5

[出力例]

具体的には,

競技開始から 0秒後に風船6 を割る, 風船6 のペナルティは 45 + 6 × 0 = 45

競技開始から 1秒後に風船8 を割る, 風船8 のペナルティは 22 + 13 × 1 = 35

競技開始から 2秒後に風船5 を割る, 風船5 のペナルティは 30 + 7 × 2 = 44

競技開始から 3秒後に風船7 を割る, 風船7 のペナルティは 18 + 12 × 3 = 54

競技開始から 4秒後に風船3 を割る, 風船3 のペナルティは 8 + 15 × 4 = 68

競技開始から 5秒後に風船4 を割る, 風船4 のペナルティは 4 + 12 × 5 = 64

競技開始から 6秒後に風船9 を割る, 風船9 のペナルティは 17 + 8 × 6 = 65

競技開始から 7秒後に風船2 を割る, 風船2 のペナルティは 12 + 8 × 7 = 68

競技開始から 8秒後に風船10を割る, 風船10のペナルティは 25 + 5 × 8 = 65

競技開始から 9秒後に風船1 を割る, 風船1 のペナルティは 10 + 5 × 9 = 55

■参照サイト
AtCoder Beginner Contest 023

2019年6月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 006 の問題D (D – トランプ挿入ソート) を解いてみた.

■感想.
1. 解答方針がよく分からなかったので, 解説を丸写しする感覚で解き直しした.
2. 新しい知識として, LIS(Longest increase subsequence) のアルゴリズムを体感できたので, 非常に勉強になったと思う.

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

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

// 解き直し.
// AtCoder Beginner Contest 006 解説.
// https://www.slideshare.net/chokudai/abc006
#include <bits/stdc++.h>
using namespace std;
const int MAX = 3e4 + 1;

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<int> c(N);
    vector<int> dp;
    for(int i = 0; i < N; i++) cin >> c[i];
    
    // 2. 解説通り.
    // -> LIS で 解く必要があるとのこと.
    dp.push_back(c[0]);
    for(int i = 1; i < N; i++){
        // 2-1. dpテーブル末尾 の 要素(last) より大きな値(c[i])であれば, dpテーブル に 追加.
        int last = dp.back();
        if(last < c[i]) dp.push_back(c[i]);
        // 2-2. dpテーブル末尾 の 要素(last) より小さな値(c[i])であれば, 
        // dpテーブル上 の 更新場所 を 探索後, dpテーブル を 更新.
        if(last > c[i]){
            auto it = lower_bound(dp.begin(), dp.end(), c[i]);
            int dist = it - dp.begin();
            dp[dist] = c[i];
            // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
            // cout << endl;
        }
    }
    // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
    // cout << endl;
    
    // 3. カードを昇順に並べるのに必要な回数を計算し, 出力.
    int ans = N - dp.size();
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

// AtCoder Beginner Contest 006 解説.

// https://www.slideshare.net/chokudai/abc006

#include <bits/stdc++.h>

using namespace std;

const int MAX = 3e4 + 1;

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<int> c(N);

vector<int> dp;

for(int i = 0; i < N; i++) cin >> c[i];

// 2. 解説通り.

// -> LIS で解く必要があるとのこと.

dp.push_back(c[0]);

for(int i = 1; i < N; i++){

// 2-1. dpテーブル末尾の要素(last) より大きな値(c[i])であれば, dpテーブルに追加.

int last = dp.back();

if(last < c[i]) dp.push_back(c[i]);

// 2-2. dpテーブル末尾の要素(last) より小さな値(c[i])であれば,

// dpテーブル上の更新場所を探索後, dpテーブルを更新.

if(last > c[i]){

auto it = lower_bound(dp.begin(), dp.end(), c[i]);

int dist = it - dp.begin();

dp[dist] = c[i];

// for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";

// cout << endl;

}

// for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";

// cout << endl;

// 3. カードを昇順に並べるのに必要な回数を計算し, 出力.

int ans = N - dp.size();

cout << ans << endl;

return 0;

}

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

[出力例(debug版)]
1 2 5 
1 2 4 
1 2 4 6 
2
※AtCoderテストケースより

[入力例]
8
1
2
5
3
8
6
4
7

[出力例(debug版)]
1 2 3 
1 2 3 6 
1 2 3 4 
1 2 3 4 7 
3

[入力例]
12
1
9
2
12
3
7
4
11
5
6
10
8

[出力例(debug版)]
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5 
1 2 3 4 5 6 8 
1 2 3 4 5 6 8 
5

実際, 
1 9  2 12 3  7  4 11  5  6 10  8 
↓
↓(1回目)
↓
1 2 12  3 7  4 11  5  6 10  8  9
↓
↓(2回目)
↓
1 2  3  7 4 11  5  6 10  8  9 12
↓
↓(3回目)
↓
1 2  3  7 4  5  6 10  8  9 11 12
↓
↓(4回目)
↓
1 2  3  7 4  5  6  8  9 10 11 12
↓
↓(5回目)
↓
1 2  3  4 5  6  7  8  9 10 11 12
の 5回 と分かる.

[入力例]

[出力例(debug版)]

1 2 5

1 2 4

1 2 4 6

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

1 2 3

1 2 3 6

1 2 3 4

1 2 3 4 7

[入力例]

[出力例(debug版)]

1 2

1 2 3

1 2 3 4

1 2 3 4 5

1 2 3 4 5 6 8

実際,

1 9 2 12 3 7 4 11 5 6 10 8

↓

↓(1回目)

↓

1 2 12 3 7 4 11 5 6 10 8 9

↓

↓(2回目)

↓

1 2 3 7 4 11 5 6 10 8 9 12

↓

↓(3回目)

↓

1 2 3 7 4 5 6 10 8 9 11 12

↓

↓(4回目)

↓

1 2 3 7 4 5 6 8 9 10 11 12

↓

↓(5回目)

↓

1 2 3 4 5 6 7 8 9 10 11 12

の 5回と分かる.

■参照サイト
AtCoder Beginner Contest 006

2019年6月16日

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

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

■感想.
1. 数え上げについて, 解答方針が全く見えなかったので, 解説を丸写しする感覚で解き直しした.
2. 数え上げに必要なライブラリが, 正常に動作していることの確認も出来たので良かったと思う.

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

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

// ABC 110解説
// https://img.atcoder.jp/abc110/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
const LL MAX = 123456;
LL F[MAX];
LL IF[MAX];

// Efficient program to print all prime factors of a given number
// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
// 与えられた正整数についての素因数分解を計算.
// @param X: 素因数分解を行う整数.
// @return ret: 素因数分解 の 結果 を 返却.
map<LL, LL> div(LL X) {
    
    // 1. X を 2で割り切れなくなるまで割っていく.
    map<LL, LL> ret;
    while(X % 2 == 0) ret[2]++, X >>= 1;
    
    // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    for(LL i = 3; i <= sqrt(X); i += 2){
        while(X % i == 0){
            ret[i]++;
            X /= i;
        }
    }
    
    // 3. X が 2 より 大きな素数であれば, 追加.
    if(X > 2) ret[X]++;
    
    // 4. 出力.
    return ret;
}

// Fermat's little theorem を 適用するため, ap-2乗 などを計算できるようにする.
// @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;
}

// 配列 IF に, 逆元を保存.
// @param: 特に無し.
// @return: 配列IF の update.
void initialize(){
    F[0] = 1, IF[0] = 1;
    for(LL i = 1; i < MAX; i++){
        F[i] = (F[i - 1] * i) % MOD;
        //逆元を、フェルマーの小定理を利用して求める
        IF[i] = inverse(F[i], MOD - 2) % MOD;
    }
}

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

int main() {

    // 1. 入力情報取得.
    LL N, M;
    cin >> N >> M;
    initialize();
    
    // 2. 素因数分解.
    map<LL, LL> m = div(M);
    // for(auto &p : m) cout << "p.first=" << p.first << " p.second=" << p.second << endl;
    
    // 3. 場合の数をカウント.
    // -> 解説通り.
    LL ans = 1;
    for(auto &p : m) ans *= combination(p.second + N - 1, p.second), ans %= MOD;
    
    // 4. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;

}

// ABC 110解説

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 1e9 + 7;

const LL MAX = 123456;

LL F[MAX];

LL IF[MAX];

// Efficient program to print all prime factors of a given number

// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

// 与えられた正整数についての素因数分解を計算.

// @param X: 素因数分解を行う整数.

// @return ret: 素因数分解の結果を返却.

map<LL, LL> div(LL X) {

// 1. X を 2で割り切れなくなるまで割っていく.

map<LL, LL> ret;

while(X % 2 == 0) ret[2]++, X >>= 1;

// 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.

for(LL i = 3; i <= sqrt(X); i += 2){

while(X % i == 0){

ret[i]++;

X /= i;

}

// 3. X が 2 より大きな素数であれば, 追加.

if(X > 2) ret[X]++;

// 4. 出力.

return ret;

}

// Fermat's little theorem を適用するため, ap-2乗などを計算できるようにする.

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

}

// 配列 IF に, 逆元を保存.

// @param: 特に無し.

// @return: 配列IF の update.

void initialize(){

F[0] = 1, IF[0] = 1;

for(LL i = 1; i < MAX; i++){

F[i] = (F[i - 1] * i) % MOD;

//逆元を、フェルマーの小定理を利用して求める

IF[i] = inverse(F[i], MOD - 2) % MOD;

}

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

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

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

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

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

LL combination(LL n, LL k){

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

LL ret = F[n] * IF[k] % MOD * IF[n - k] % MOD;

return ret;

}

int main() {

// 1. 入力情報取得.

LL N, M;

cin >> N >> M;

initialize();

// 2. 素因数分解.

map<LL, LL> m = div(M);

// for(auto &p : m) cout << "p.first=" << p.first << " p.second=" << p.second << endl;

// 3. 場合の数をカウント.

// -> 解説通り.

LL ans = 1;

for(auto &p : m) ans *= combination(p.second + N - 1, p.second), ans %= MOD;

// 4. 出力～後処理.

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 110

2019年6月15日2019年6月15日

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

C++の練習を兼ねて, AtCoder Regular Contest 059 の問題F (F – バイナリハック / Unhappy Hacking) を解いてみた.

■感想.
1. DPが良くわかってないので, 解説(数え上げテクニック集)を参照して実装してみた.

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

// 数え上げテクニック集
// https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
LL dp[5001][5001];

int main() {
    
    // 1. 入力情報取得.
    LL N;
    string S;
    cin >> N >> S;
    
    // 2. 数え上げ.
    // 数え上げテクニック集 に従って, dp[n][x] で 数え上げ.
    // n: 操作回数, x: 現在の文字列長.
    // ex.
    // n = 1: dp[1][0] = 1, dp[1][1] = 2
    //   => 合計 3通り.
    // n = 2: dp[2][0] = dp[1][0] * 1 + dp[1][1] * 1 = 3, dp[2][1] = dp[1][0] * 2 = 2, 
    //        dp[2][2] = dp[1][1] * 2 = 4
    //   => 合計 9通り.
    // n = 3: dp[3][0] = dp[2][0] * 1 + dp[2][1] * 1 = 5, dp[3][1] = dp[2][0] * 2 + dp[2][2] * 1 = 10, 
    //        dp[3][2] = dp[2][1] * 2 = 4, dp[3][3] = dp[2][2] * 2 = 8
    //   => 合計 27通り.
    int l = S.size();
    dp[1][0] = 1, dp[1][1] = 2;
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= N; j++){
            // 2-1. (j - 1)文字 から j文字 に 遷移(文字 '0' or '1' を 右端 に 追加)する場合.
            if(j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1] * 2, dp[i][j] %= MOD;

            // 2-2. (j + 1)文字 から j文字 に 遷移(バックスペースキー で 右端 の 文字 を 削除)する場合.
            if(j + 1 < i)  dp[i][j] += dp[i - 1][j + 1] * 1, dp[i][j] %= MOD;

            // 2-3. 0文字 から 0文字 に 遷移する場合.
            if(j == 0)     dp[i][j] += dp[i - 1][j] * 1,     dp[i][j] %= MOD;
            // cout << "i=" << i << " j=" << j << " dp=" << dp[i][j] << " ";
        }
    }
    
    // 3. 出力 ～ 後処理.
    // 数え上げテクニック集 に従って, 同じ文字数の文字列を作る場合の数が, すべて等しいとの内容を反映.
    // -> 2 で, S.size()回割れば良い筈 => 500000004 を 乗ずる形に修正.
    LL ans = dp[N][l];
    for(int j = 1; j <= l; j++) ans *= 500000004, ans %= MOD;
    cout << ans << endl;
    return 0;
    
}

// 数え上げテクニック集

// https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 1e9 + 7;

LL dp[5001][5001];

int main() {

// 1. 入力情報取得.

LL N;

string S;

cin >> N >> S;

// 2. 数え上げ.

// 数え上げテクニック集に従って, dp[n][x] で数え上げ.

// n: 操作回数, x: 現在の文字列長.

// ex.

// n = 1: dp[1][0] = 1, dp[1][1] = 2

// => 合計 3通り.

// n = 2: dp[2][0] = dp[1][0] * 1 + dp[1][1] * 1 = 3, dp[2][1] = dp[1][0] * 2 = 2,

// dp[2][2] = dp[1][1] * 2 = 4

// => 合計 9通り.

// n = 3: dp[3][0] = dp[2][0] * 1 + dp[2][1] * 1 = 5, dp[3][1] = dp[2][0] * 2 + dp[2][2] * 1 = 10,

// dp[3][2] = dp[2][1] * 2 = 4, dp[3][3] = dp[2][2] * 2 = 8

// => 合計 27通り.

int l = S.size();

dp[1][0] = 1, dp[1][1] = 2;

for(int i = 1; i <= N; i++){

for(int j = 0; j <= N; j++){

// 2-1. (j - 1)文字から j文字に遷移(文字 '0' or '1' を右端に追加)する場合.

if(j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1] * 2, dp[i][j] %= MOD;

// 2-2. (j + 1)文字から j文字に遷移(バックスペースキーで右端の文字を削除)する場合.

if(j + 1 < i) dp[i][j] += dp[i - 1][j + 1] * 1, dp[i][j] %= MOD;

// 2-3. 0文字から 0文字に遷移する場合.

if(j == 0) dp[i][j] += dp[i - 1][j] * 1, dp[i][j] %= MOD;

// cout << "i=" << i << " j=" << j << " dp=" << dp[i][j] << " ";

}

// 3. 出力～後処理.

// 数え上げテクニック集に従って, 同じ文字数の文字列を作る場合の数が, すべて等しいとの内容を反映.

// -> 2 で, S.size()回割れば良い筈 => 500000004 を乗ずる形に修正.

LL ans = dp[N][l];

for(int j = 1; j <= l; j++) ans *= 500000004, ans %= MOD;

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Regular Contest 059
数え上げテクニック集

2019年6月15日2019年6月15日

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

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, yukicoder の No.697 池の数はいくつかに似ていることが分かった.
2. 上記の類題を適用するため, 埋め立て後の陸地の個数をカウントする方法で, 本問の解答方針とした.

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

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
constexpr int MAX = 100;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int H, W;
char board[MAX];
int memo[MAX];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// 迷路を幅優先探索する.
// ※bfsの動作確認用.
// @param c: 探索地点の迷路の座標.
// @param d: 池の番号.
// @return: 特に無し.
void bfs(int c, int d){
    
    // 1. 終了条件設定.
    if(board[c] == 'x') return;
    
    // 2. 空のキュー.
    queue<int> q;
    
    // 3. 訪問済みフラグ設定.
    memo[c] = d;
    
    // 4. 探索地点 c をキュー q に追加.
    q.push(c);
    while(!q.empty()){
        // 5. キューから取り出す.
        int v = q.front();
        q.pop();
        // 6. 取り出した要素を処理.
        // x: 列方向, y: 行方向 で考える.
        int nx, ny, n;
        int cx = v % W , cy = v / W;
        FOR(i, 0, 4){
            nx = cx + dx[i];
            ny = cy + dy[i];
            n = nx + ny * W;
            // cout << "cx=" << cx << " nx=" << nx  << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;
            // 7. 訪問不可能なマス であれば, 処理をスキップ.
            if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
            if(memo[n] == d)                                    continue;
            // 8. 訪問可能 かつ 未訪問 のマス であれば, 訪問済みを設定.
            if(board[n] == 'o' && memo[n] == 0) memo[n] = d, q.push(n);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    W = 10, H = 10;
    FOR(i, 0, H){
        string s;
        cin >> s;
        FOR(j, 0, W) board[i * W + j] = s[j];
    }
    
    // 2. 海を1マスだけ陸地にして, 1つの島に出来るかを確認.
   int counter = 0;
   bool ans = false;
    FOR(i, 0, H * W){
        if(board[i] == 'x'){
            // 2-1. 海を1マスだけ陸地にしてみる.
            board[i] = 'o';
            
            // 2-2. 陸地の分割.
            // cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl;
            FOR(j, 0, H * W) if(board[j] == 'o' && memo[j] == 0) counter++, bfs(j, counter);
            // FOR(k, 0, H){
            //     FOR(l, 0, W){
            //         cout << memo[k * W + l] << " ";
            //     }
            //     cout << endl;
            // }
            // cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl;
            // ex.
            // [入力例]
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // ooooxooooo
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // 
            // [探索状況(抜粋)]
            // ----- i=44 counter=0 -----
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 1 1 1 1 1 1 1 1 1 1 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // ----- i=44 counter=1 -----
            // -> YES 正しく判定されているように見える.
            
            // 2-3. 1つの島に出来た場合は, 後続処理をスキップ.
            if(counter == 1){
                ans = true;
                break;
            }
            
            // 2-4. 元に戻す.
            counter = 0;
            board[i] = 'x';
            FOR(j, 0, H * W) memo[j] = 0;
        }
    }
    
    // 3. 出力 ～ 後処理.
    if(ans) cout << "YES" << endl;
    else    cout << "NO"  << endl;
    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

#include <bits/stdc++.h>

using namespace std;

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

constexpr int MAX = 100;

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int H, W;

char board[MAX];

int memo[MAX];

// 幅優先探索.

// https://ja.wikipedia.org/wiki/幅優先探索

// 迷路を幅優先探索する.

// ※bfsの動作確認用.

// @param c: 探索地点の迷路の座標.

// @param d: 池の番号.

// @return: 特に無し.

void bfs(int c, int d){

// 1. 終了条件設定.

if(board[c] == 'x') return;

// 2. 空のキュー.

queue<int> q;

// 3. 訪問済みフラグ設定.

memo[c] = d;

// 4. 探索地点 c をキュー q に追加.

q.push(c);

while(!q.empty()){

// 5. キューから取り出す.

int v = q.front();

q.pop();

// 6. 取り出した要素を処理.

// x: 列方向, y: 行方向で考える.

int nx, ny, n;

int cx = v % W , cy = v / W;

FOR(i, 0, 4){

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * W;

// cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;

// 7. 訪問不可能なマスであれば, 処理をスキップ.

if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue;

if(memo[n] == d) continue;

// 8. 訪問可能かつ未訪問のマスであれば, 訪問済みを設定.

if(board[n] == 'o' && memo[n] == 0) memo[n] = d, q.push(n);

}

return;

}

int main() {

// 1. 入力情報取得.

W = 10, H = 10;

FOR(i, 0, H){

string s;

cin >> s;

FOR(j, 0, W) board[i * W + j] = s[j];

}

// 2. 海を1マスだけ陸地にして, 1つの島に出来るかを確認.

int counter = 0;

bool ans = false;

FOR(i, 0, H * W){

if(board[i] == 'x'){

// 2-1. 海を1マスだけ陸地にしてみる.

board[i] = 'o';

// 2-2. 陸地の分割.

// cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl;

FOR(j, 0, H * W) if(board[j] == 'o' && memo[j] == 0) counter++, bfs(j, counter);

// FOR(k, 0, H){

// FOR(l, 0, W){

// cout << memo[k * W + l] << " ";

// }

// cout << endl;

// }

// cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl;

// ex.

// [入力例]

// xxxxoxxxxx

// ooooxooooo

// xxxxoxxxxx

// [探索状況(抜粋)]

// ----- i=44 counter=0 -----

// 0 0 0 0 1 0 0 0 0 0

// 1 1 1 1 1 1 1 1 1 1

// 0 0 0 0 1 0 0 0 0 0

// ----- i=44 counter=1 -----

// -> YES 正しく判定されているように見える.

// 2-3. 1つの島に出来た場合は, 後続処理をスキップ.

if(counter == 1){

ans = true;

break;

}

// 2-4. 元に戻す.

counter = 0;

board[i] = 'x';

FOR(j, 0, H * W) memo[j] = 0;

}

// 3. 出力～後処理.

if(ans) cout << "YES" << endl;

else cout << "NO" << endl;

return 0;

}

■参照サイト
AtCoder Regular Contest 031
No.697 池の数はいくつか

2019年6月11日

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

C++の練習を兼ねて, Typical DP Contest の問題A (A – コンテスト) を解いてみた.

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, yukicoder の No.4 おもりと天秤に似ていることが分かった.
2. DPを使う方法を模索したが, 使い方が, 分からなかったので, 要復習と認識している.

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

// yukicoder の 問題 を 参照.
// No.4 おもりと天秤
// https://yukicoder.me/problems/no/4
#include <bits/stdc++.h>
using namespace std;

// 獲得可能な得点を更新する.
// @param m: 得点のリスト.
// @param s: 得点.
// @return ret: 更新した得点のリスト.
map<int, int> updateScore(map<int, int> m, int s){
    map<int, int> ret;
    ret[s]++;
    for(auto &p : m) ret[p.first]++, ret[p.first + s]++;
    // for(auto &p : ret) cout << "updateScore(ret): " << p.first << " ";
    // cout << endl;
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    int p[N + 1];
    p[0] = 0;
    for(int i = 1; i < N + 1; ++i) cin >> p[i];
    
    // 2. sort.
    sort(p, p + N + 1);

    // 3. ありうる得点を保存.
    map<int, int> m;
    m[p[0]]++;
    for(int i = 1; i < N + 1; i++){
        map<int, int> lm = updateScore(m, p[i]);
        swap(m, lm);
    }
    // for(auto &p : m) cout << p.first << " ";

    // 4. 出力.
    int ans = 0;
    for(auto &p : m) if(p.second > 0) ans++;
    cout << ans << endl;
    return 0;
    
}

// yukicoder の問題を参照.

// No.4 おもりと天秤

// https://yukicoder.me/problems/no/4

#include <bits/stdc++.h>

using namespace std;

// 獲得可能な得点を更新する.

// @param m: 得点のリスト.

// @param s: 得点.

// @return ret: 更新した得点のリスト.

map<int, int> updateScore(map<int, int> m, int s){

map<int, int> ret;

ret[s]++;

for(auto &p : m) ret[p.first]++, ret[p.first + s]++;

// for(auto &p : ret) cout << "updateScore(ret): " << p.first << " ";

// cout << endl;

return ret;

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

int p[N + 1];

p[0] = 0;

for(int i = 1; i < N + 1; ++i) cin >> p[i];

// 2. sort.

sort(p, p + N + 1);

// 3. ありうる得点を保存.

map<int, int> m;

m[p[0]]++;

for(int i = 1; i < N + 1; i++){

map<int, int> lm = updateScore(m, p[i]);

swap(m, lm);

}

// for(auto &p : m) cout << p.first << " ";

// 4. 出力.

int ans = 0;

for(auto &p : m) if(p.second > 0) ans++;

cout << ans << endl;

return 0;

}

■参照サイト
Typical DP Contest
No.4 おもりと天秤

2019年6月3日

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

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題P (P – Independent Set) を解いてみた.

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, AtCoder Beginner Contest 036(D – 塗り絵) に似ていることが分かった.
2. 差分は, N = 1 を含める(本問)か, 含めないかのようだった.

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

// 下記を, 一部修正.
// 解き直し.
// ABC #036 解説.
// http://abc036.contest.atcoder.jp/data/abc/036/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;
const int LIMIT = 100000;
const LL MOD = 1e9 + 7;

struct edge {
    int to;    // 次の頂点.
    int cost;  // コスト.
};

struct vertex {
    int id;        // 頂点番号.
    int distance;  // 指定された頂点(根)からの距離.
};

int depth[LIMIT];
vector<edge> tree[LIMIT];

// AtCoder Beginner Contest 070 (問題D Transit Tree Path) を参照.
// https://img.atcoder.jp/abc070/editorial.pdf
// 深さ優先探索(depth-first search).
// @param c: 探索地点となる頂点.
// @param b: 探索地点から見て, 前回探索済の頂点.
// @param d: 探索開始地点からの距離.
// @return : 特に無し.
void dfs(int c, int b, int d) {
    depth[c] = d;
    for (auto &e : tree[c]) {
        if (e.to == b) continue;
        dfs(e.to, c, d + e.cost);
    }
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    map<int, int> m; // 開始頂点取得用.
    FOR(i, 0, N - 1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        tree[a].push_back({b, 1});
        tree[b].push_back({a, 1});
        m[a]++;
        m[b]++;
    }
    
    // 2. N = 1 の 場合は, 終了(※本問用で追加).
    if(N == 1){
        cout << 2 << endl;
        return 0;
    }
    
    // 3. 探索開始の頂点(根)を取得し, 各頂点までの最短距離を保存.
    int root = -1;
    for(auto &p : m) {
        if(p.second == 1) {
            root = p.first;
            break;
        }
    }
    dfs(root, -1, 0);
    // cout << "root=" << root << endl;
    // FOR(i, 0, N) for(auto &p : tree[i]) cout << "i=" << i << " to=" << p.to << endl;
    // FOR(i, 0, N) cout << depth[i] << " ";
    
    // 4. 解説通り(色の塗り方の数をカウント).
    // -> tree DP を 使って解くとのこと.
    // 探索開始の頂点(根) から遠い順に, f, g の 値を計算していく.
    
    // 4-1. 頂点と距離のセットで保管.
    vector<vertex> vertexes;
    FOR(i, 0, N) {
        vertex v;
        v.id = i;
        v.distance = depth[i];
        vertexes.push_back(v);
    }
    
    // 4-2. 距離で, 降順sort.
    sort(vertexes.begin(), vertexes.end(), [](const vertex& x, const vertex& y) {return x.distance > y.distance;});
    
    // 4-3. f, g を 帰納的に計算.
    LL f[N] = {};
    LL g[N] = {};
    for(auto &x : vertexes) {
        // 頂点 x を 親とする部分木で, x と 隣り合っている頂点(xの子)を探索.
        int p = x.id;  // 親の頂点番号.
        LL lf = 1LL;
        LL lg = 1LL;
        // 隣接している, かつ, 探索開始の頂点(根) からより遠い場合は, xの子 と識別.
        for(auto &v : tree[p]) {
            int c = v.to;  // 子の候補となる頂点番号.
            if(depth[p] < depth[c]) {
                lg *= f[c];
                lf *= g[c];
                lg %= MOD;
                lf %= MOD;
            }
        }
        // f, g を 更新.
        lf += lg;
        lf %= MOD;
        f[p] = lf;
        g[p] = lg;
    }
    // FOR(i, 0, N) cout << f[i] << " ";
    // cout << endl;
    // FOR(i, 0, N) cout << g[i] << " ";
    
    // 5. 出力 ～ 後処理.
    LL ans = f[root];
    cout << ans << endl;
    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

// 下記を, 一部修正.

// 解き直し.

// ABC #036 解説.

// http://abc036.contest.atcoder.jp/data/abc/036/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

const int LIMIT = 100000;

const LL MOD = 1e9 + 7;

struct edge {

int to; // 次の頂点.

int cost; // コスト.

};

struct vertex {

int id; // 頂点番号.

int distance; // 指定された頂点(根)からの距離.

};

int depth[LIMIT];

vector<edge> tree[LIMIT];

// AtCoder Beginner Contest 070 (問題D Transit Tree Path) を参照.

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

// 深さ優先探索(depth-first search).

// @param c: 探索地点となる頂点.

// @param b: 探索地点から見て, 前回探索済の頂点.

// @param d: 探索開始地点からの距離.

// @return : 特に無し.

void dfs(int c, int b, int d) {

depth[c] = d;

for (auto &e : tree[c]) {

if (e.to == b) continue;

dfs(e.to, c, d + e.cost);

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

map<int, int> m; // 開始頂点取得用.

FOR(i, 0, N - 1) {

int a, b;

cin >> a >> b;

a--, b--;

tree[a].push_back({b, 1});

tree[b].push_back({a, 1});

m[a]++;

m[b]++;

}

// 2. N = 1 の場合は, 終了(※本問用で追加).

if(N == 1){

cout << 2 << endl;

return 0;

}

// 3. 探索開始の頂点(根)を取得し, 各頂点までの最短距離を保存.

int root = -1;

for(auto &p : m) {

if(p.second == 1) {

root = p.first;

break;

}

dfs(root, -1, 0);

// cout << "root=" << root << endl;

// FOR(i, 0, N) for(auto &p : tree[i]) cout << "i=" << i << " to=" << p.to << endl;

// FOR(i, 0, N) cout << depth[i] << " ";

// 4. 解説通り(色の塗り方の数をカウント).

// -> tree DP を使って解くとのこと.

// 探索開始の頂点(根) から遠い順に, f, g の値を計算していく.

// 4-1. 頂点と距離のセットで保管.

vector<vertex> vertexes;

FOR(i, 0, N) {

vertex v;

v.id = i;

v.distance = depth[i];

vertexes.push_back(v);

}

// 4-2. 距離で, 降順sort.

sort(vertexes.begin(), vertexes.end(), [](const vertex& x, const vertex& y) {return x.distance > y.distance;});

// 4-3. f, g を帰納的に計算.

LL f[N] = {};

LL g[N] = {};

for(auto &x : vertexes) {

// 頂点 x を親とする部分木で, x と隣り合っている頂点(xの子)を探索.

int p = x.id; // 親の頂点番号.

LL lf = 1LL;

LL lg = 1LL;

// 隣接している, かつ, 探索開始の頂点(根) からより遠い場合は, xの子と識別.

for(auto &v : tree[p]) {

int c = v.to; // 子の候補となる頂点番号.

if(depth[p] < depth[c]) {

lg *= f[c];

lf *= g[c];

lg %= MOD;

lf %= MOD;

}

// f, g を更新.

lf += lg;

lf %= MOD;

f[p] = lf;

g[p] = lg;

}

// FOR(i, 0, N) cout << f[i] << " ";

// cout << endl;

// FOR(i, 0, N) cout << g[i] << " ";

// 5. 出力～後処理.

LL ans = f[root];

cout << ans << endl;

return 0;

}

■参照サイト
Educational DP Contest / DP まとめコンテスト
 AtCoder Beginner Contest 036 (D – 塗り絵)

2019年5月26日2019年5月26日

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

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題M (M – Candies) を解いてみた.

■感想.
1. 解答に時間かかったものの正答出来たので, アップロードしてみた.
2. 飴を N人にK個配る場合と, (N – 1)人に, K個以下配る場合の関係を抽出出来たので, 解答に到達することが出来たと思う.
3. 引き算を行う場合のMOD計算で躓いたので, 今後の実装で, 注意しようと思う.

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;

// N人 に K個 の 飴 を配る場合の総数を保管.
LL dp[101][100001];
// 各子供(1, 2, ..., N) が受け取る飴の個数上限.
LL A[101];

int main() {
    
    // 1. 入力情報取得.
    LL N, K;
    cin >> N >> K;
    for(LL i = 1; i <= N; i++) cin >> A[i];
    
    // 2. 飴 の 配り方を確認.
    // dp[N][K] = 
    // dp[N - 1][K - 0]    (N人目 に 0個配る場合) +
    // dp[N - 1][K - 1]    (N人目 に 1個配る場合) +
    // dp[N - 1][K - 2]    (N人目 に 2個配る場合) +
    // ...
    // dp[N - 1][K - A[N]] (N人目 に A[N]個配る場合)
    // のような関係が成り立つことに注意.
    // ※但し, 第二成分 K - XX が, 0以上となる必要がある.

    // 2-1. 1人目の情報.
    for(LL j = 0; j <= A[1]; j++) dp[1][j] = 1;

    // 2-2. 2人目以降の情報.
    for(LL i = 2; i <= N; i++){
        dp[i][0] = dp[i - 1][0];
        for(LL j = 1; j <= K; j++){
            dp[i][j] = dp[i][j - 1];
            dp[i][j] += dp[i - 1][j], dp[i][j] %= MOD;
            // 1_04, 1_05, 1_07, 1_10 で, WA となったので, MOD計算 を修正.
            // if(j > A[i]) dp[i][j] -= dp[i - 1][j - 1 - A[i]], dp[i][j] %= MOD;
            if(j > A[i]) dp[i][j] += MOD, dp[i][j] -= dp[i - 1][j - 1 - A[i]], dp[i][j] %= MOD;
        }
    }
    
    // for(LL i = 0; i <= N; i++){
    //     for(LL j = 0; j <= K; j++) cout << dp[i][j] << " ";
    //     cout << endl;
    // }
    
    // 3. 出力.
    cout << dp[N][K] << endl;
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 1e9 + 7;

// N人に K個の飴を配る場合の総数を保管.

LL dp[101][100001];

// 各子供(1, 2, ..., N) が受け取る飴の個数上限.

LL A[101];

int main() {

// 1. 入力情報取得.

LL N, K;

cin >> N >> K;

for(LL i = 1; i <= N; i++) cin >> A[i];

// 2. 飴の配り方を確認.

// dp[N][K] =

// dp[N - 1][K - 0] (N人目に 0個配る場合) +

// dp[N - 1][K - 1] (N人目に 1個配る場合) +

// dp[N - 1][K - 2] (N人目に 2個配る場合) +

// ...

// dp[N - 1][K - A[N]] (N人目に A[N]個配る場合)

// のような関係が成り立つことに注意.

// ※但し, 第二成分 K - XX が, 0以上となる必要がある.

// 2-1. 1人目の情報.

for(LL j = 0; j <= A[1]; j++) dp[1][j] = 1;

// 2-2. 2人目以降の情報.

for(LL i = 2; i <= N; i++){

dp[i][0] = dp[i - 1][0];

for(LL j = 1; j <= K; j++){

dp[i][j] = dp[i][j - 1];

dp[i][j] += dp[i - 1][j], dp[i][j] %= MOD;

// 1_04, 1_05, 1_07, 1_10 で, WA となったので, MOD計算を修正.

// if(j > A[i]) dp[i][j] -= dp[i - 1][j - 1 - A[i]], dp[i][j] %= MOD;

if(j > A[i]) dp[i][j] += MOD, dp[i][j] -= dp[i - 1][j - 1 - A[i]], dp[i][j] %= MOD;

}

// for(LL i = 0; i <= N; i++){

// for(LL j = 0; j <= K; j++) cout << dp[i][j] << " ";

// cout << endl;

// }

// 3. 出力.

cout << dp[N][K] << endl;

return 0;

}

[入力例]
3 4
1 2 3

[出力例(debug版)]
0 0 0 0 0 
1 1 0 0 0 
1 2 2 1 0 
1 3 5 6 5 
5
※AtCoderのテストケースより

[入力例]
1 10
9

[出力例(debug版)]
0 0 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 1 0 
0
※AtCoderのテストケースより

[入力例]
2 0
0 0

[出力例(debug版)]
0 
1 
1 
1
※AtCoderのテストケースより

[入力例]
4 100000
100000 100000 100000 100000

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

[入力例]
2 7
3 4

[出力例(debug版)]
0 0 0 0 0 0 0 0 
1 1 1 1 0 0 0 0 
1 2 3 4 4 3 2 1 
1

[入力例]
2 6
3 4

[出力例(debug版)]
0 0 0 0 0 0 0 
1 1 1 1 0 0 0 
1 2 3 4 4 3 2 
2

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

[出力例(debug版)]
0 0 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 
1 2 2 1 0 0 0 0 
1 3 5 6 5 3 1 0 
1 4 9 15 20 22 20 15 
1 5 14 29 49 71 90 101 
101

[入力例]
5 7
2 3 4 5 6

[出力例(debug版)]
0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 
1 2 3 3 2 1 0 0 
1 3 6 9 11 11 9 6 
1 4 10 19 30 41 49 52 
1 5 15 34 64 105 154 205 
205

[入力例]

3 4

1 2 3

[出力例(debug版)]

0 0 0 0 0

1 1 0 0 0

1 2 2 1 0

1 3 5 6 5

※AtCoderのテストケースより

[入力例]

1 10

[出力例(debug版)]

0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1 1 1 0

※AtCoderのテストケースより

[入力例]

2 0

0 0

[出力例(debug版)]

※AtCoderのテストケースより

[入力例]

4 100000

100000 100000 100000 100000

[出力例]

665683269

※AtCoderのテストケースより

[入力例]

2 7

3 4

[出力例(debug版)]

0 0 0 0 0 0 0 0

1 1 1 1 0 0 0 0

1 2 3 4 4 3 2 1

[入力例]

2 6

3 4

[出力例(debug版)]

0 0 0 0 0 0 0

1 1 1 1 0 0 0

1 2 3 4 4 3 2

[入力例]

5 7

1 2 3 4 5

[出力例(debug版)]

0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

1 2 2 1 0 0 0 0

1 3 5 6 5 3 1 0

1 4 9 15 20 22 20 15

1 5 14 29 49 71 90 101

101

[入力例]

5 7

2 3 4 5 6

[出力例(debug版)]

0 0 0 0 0 0 0 0

1 1 1 0 0 0 0 0

1 2 3 3 2 1 0 0

1 3 6 9 11 11 9 6

1 4 10 19 30 41 49 52

1 5 15 34 64 105 154 205

205

■参照サイト
Educational DP Contest / DP まとめコンテスト

2019年5月14日

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

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題I (I – Coins) を解いてみた.

■感想.
1. 解答に時間かかったものの本問も正答出来たので, アップロードしてみた.

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    double P[N + 1] = {};
    for(int i = 1; i <= N; i++) cin >> P[i];
    
    // 2. 表の個数が裏の個数を上回る確率を計算.
    // dp[i][j]: i枚目のコインまで確認して, 表の個数(j)となる確率を保存.
    double dp[N + 1][N + 1] = {};
    
    // 2-1. 1回目は, P[1], 1.0 - P[1] を設定.
    dp[1][1] = P[1];
    dp[1][0] = 1.0 - P[1];
    
    // 2-2. 2回目以降は, 前回の状態をもとに設定.
    // ex.
    // 2枚目まで確認して, 表が2枚 … 1枚目まで確認して, 表が1枚.
    // dp[2][2] = P[2] * dp[1][1];
    // 2枚目まで確認して, 表が1枚 … 1枚目まで確認して, 表が1枚 or 表が0枚.
    // dp[2][1] = (1 - P[2]) * dp[1][1] + P[2] * dp[1][0];
    // 2枚目まで確認して, 表が0枚 … 1枚目まで確認して, 表が0枚.
    // dp[2][0] = (1 - P[2]) * dp[1][0];
    // 
    for(int i = 2; i <= N; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0)         dp[i][0] = (1 - P[i]) * dp[i - 1][0];
            if(i == j)         dp[i][i] = P[i] * dp[i - 1][i - 1];
            if(j > 0 && j < i) dp[i][j] = P[i] * dp[i - 1][j - 1] + (1 - P[i]) * dp[i - 1][j];
        }
    }
    // for(int i = 0; i <= N; i++){
    //     for(int j = 0; j <= i; j++){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    
    // 3. 後処理.
    double ans = 0.0;
    for(int j = (N + 1) / 2; j <= N; j++) ans += dp[N][j];
    cout << fixed;
    cout << setprecision(10) << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

double P[N + 1] = {};

for(int i = 1; i <= N; i++) cin >> P[i];

// 2. 表の個数が裏の個数を上回る確率を計算.

// dp[i][j]: i枚目のコインまで確認して, 表の個数(j)となる確率を保存.

double dp[N + 1][N + 1] = {};

// 2-1. 1回目は, P[1], 1.0 - P[1] を設定.

dp[1][1] = P[1];

dp[1][0] = 1.0 - P[1];

// 2-2. 2回目以降は, 前回の状態をもとに設定.

// ex.

// 2枚目まで確認して, 表が2枚 … 1枚目まで確認して, 表が1枚.

// dp[2][2] = P[2] * dp[1][1];

// 2枚目まで確認して, 表が1枚 … 1枚目まで確認して, 表が1枚 or 表が0枚.

// dp[2][1] = (1 - P[2]) * dp[1][1] + P[2] * dp[1][0];

// 2枚目まで確認して, 表が0枚 … 1枚目まで確認して, 表が0枚.

// dp[2][0] = (1 - P[2]) * dp[1][0];

for(int i = 2; i <= N; i++){

for(int j = 0; j <= i; j++){

if(j == 0) dp[i][0] = (1 - P[i]) * dp[i - 1][0];

if(i == j) dp[i][i] = P[i] * dp[i - 1][i - 1];

if(j > 0 && j < i) dp[i][j] = P[i] * dp[i - 1][j - 1] + (1 - P[i]) * dp[i - 1][j];

}

// for(int i = 0; i <= N; i++){

// for(int j = 0; j <= i; j++){

// cout << dp[i][j] << " ";

// }

// cout << endl;

// }

// 3. 後処理.

double ans = 0.0;

for(int j = (N + 1) / 2; j <= N; j++) ans += dp[N][j];

cout << fixed;

cout << setprecision(10) << ans << endl;

return 0;

}

[入力例]
3
0.30 0.60 0.80

[出力例(debug版)]
0 
0.7 0.3 
0.28 0.54 0.18 
0.056 0.332 0.468 0.144 
0.6120000000
※AtCoderのテストケースより

[入力例]
1
0.50

[出力例(debug版)]
0 
0.5 0.5 
0.5000000000
※AtCoderのテストケースより

[入力例]
5
0.42 0.01 0.42 0.99 0.42

[出力例(debug版)]
0 
0.58 0.42 
0.5742 0.4216 0.0042 
0.333036 0.485692 0.179508 0.001764 
0.00333036 0.334563 0.48263 0.177731 0.00174636 
0.00193161 0.195445 0.420442 0.305788 0.0756597 0.000733471 
0.3821815872
※AtCoderのテストケースより

[入力例]
11
0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50

[出力例]
0.5000000000

[入力例]

0.30 0.60 0.80

[出力例(debug版)]

0.7 0.3

0.28 0.54 0.18

0.056 0.332 0.468 0.144

0.6120000000

※AtCoderのテストケースより

[入力例]

0.50

[出力例(debug版)]

0.5 0.5

0.5000000000

※AtCoderのテストケースより

[入力例]

0.42 0.01 0.42 0.99 0.42

[出力例(debug版)]

0.58 0.42

0.5742 0.4216 0.0042

0.333036 0.485692 0.179508 0.001764

0.00333036 0.334563 0.48263 0.177731 0.00174636

0.00193161 0.195445 0.420442 0.305788 0.0756597 0.000733471

0.3821815872

※AtCoderのテストケースより

[入力例]

0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50

[出力例]

0.5000000000

■参照サイト
Educational DP Contest / DP まとめコンテスト

2019年5月13日

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

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題H (H – Grid 1) を解いてみた.

■感想.
1. 途中の問題は, ほとんど解けてないが, なぜか本問を正答出来たので, アップロードしてみた.

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;

int main() {
    
    // 1. 入力情報取得.
    LL H, W;
    cin >> H >> W;
    string A[H];
    for(int i = 0; i < H; i++) cin >> A[i];
    
    // 2. 経路数を計算.
    LL dp[H][W] = {};
    // ゴール地点を, 1通りで設定.
    dp[H - 1][W - 1] = 1;
    for(LL i = H - 1; i >= 0; i--){
        for(LL j = W - 1; j >= 0; j--){
            string s = A[i];
            // 右.
            if(j < W - 1){
                string s = A[i];
                if(s[j] == '.' && s[j + 1] == '.') dp[i][j] = dp[i][j + 1], dp[i][j] %= MOD;
            }
            // 下.
            if(i < H - 1){
                string s = A[i], t = A[i + 1];
                if(s[j] == '.' && t[j] == '.') dp[i][j] = dp[i + 1][j], dp[i][j] %= MOD;
            }
            // 右 and 下.
            if(j < W - 1 && i < H - 1){
                string s = A[i], t = A[i + 1];
                if(s[j] == '.' && s[j + 1] == '.' && t[j] == '.'){
                    dp[i][j] = dp[i][j + 1] + dp[i + 1][j], dp[i][j] %= MOD;
                }
            }
        }
    }
    
    // for(LL i = 0; i < H; i++){
    //     for(LL j = 0; j < W; j++){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // 3. 後処理.
    cout << dp[0][0] << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 1e9 + 7;

int main() {

// 1. 入力情報取得.

LL H, W;

cin >> H >> W;

string A[H];

for(int i = 0; i < H; i++) cin >> A[i];

// 2. 経路数を計算.

LL dp[H][W] = {};

// ゴール地点を, 1通りで設定.

dp[H - 1][W - 1] = 1;

for(LL i = H - 1; i >= 0; i--){

for(LL j = W - 1; j >= 0; j--){

string s = A[i];

// 右.

if(j < W - 1){

string s = A[i];

if(s[j] == '.' && s[j + 1] == '.') dp[i][j] = dp[i][j + 1], dp[i][j] %= MOD;

}

// 下.

if(i < H - 1){

string s = A[i], t = A[i + 1];

if(s[j] == '.' && t[j] == '.') dp[i][j] = dp[i + 1][j], dp[i][j] %= MOD;

}

// 右 and 下.

if(j < W - 1 && i < H - 1){

string s = A[i], t = A[i + 1];

if(s[j] == '.' && s[j + 1] == '.' && t[j] == '.'){

dp[i][j] = dp[i][j + 1] + dp[i + 1][j], dp[i][j] %= MOD;

}

// for(LL i = 0; i < H; i++){

// for(LL j = 0; j < W; j++){

// cout << dp[i][j] << " ";

// }

// cout << endl;

// }

// 3. 後処理.

cout << dp[0][0] << endl;

return 0;

}

[入力例]
3 4
...#
.#..
....

[出力例(debug版)]
3 2 2 0 
1 0 2 1 
1 1 1 1 
3
※AtCoderのテストケースより

[入力例]
5 2
..
#.
..
.#
..

[出力例(debug版)]
0 0 
0 0 
1 0 
1 0 
1 1 
0
※AtCoderのテストケースより

[入力例]
5 5
..#..
.....
#...#
.....
..#..

[出力例(debug版)]
24 12 0 2 0 
12 12 6 2 0 
0 6 4 2 0 
2 2 2 2 1 
0 0 0 1 1 
24
※AtCoderのテストケースより

[入力例]
20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

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

[入力例]
100 100
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................

[出力例]
690285631

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

171

172

173

174

175

176

177

178

179

[入力例]

3 4

...#

.#..

....

[出力例(debug版)]

3 2 2 0

1 0 2 1

1 1 1 1

※AtCoderのテストケースより

[入力例]

5 2

[出力例(debug版)]

0 0

1 0

1 1

※AtCoderのテストケースより

[入力例]

5 5

..#..

.....

#...#

.....

..#..

[出力例(debug版)]

24 12 0 2 0

12 12 6 2 0

0 6 4 2 0

2 2 2 2 1

0 0 0 1 1

※AtCoderのテストケースより

[入力例]

20 20

....................

[出力例]

345263555

※AtCoderのテストケースより

[入力例]

100 100

....................................................................................................

[出力例]

690285631

■参照サイト
Educational DP Contest / DP まとめコンテスト

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

C++の練習を兼ねて, AtCoder Beginner Contest 006 の 問題D (D – トランプ挿入ソート) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 059 の 問題F (F – バイナリハック / Unhappy Hacking) を解いてみた.

C++の練習を兼ねて, Typical DP Contest の 問題A (A – コンテスト) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題P (P – Independent Set) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題M (M – Candies) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題I (I – Coins) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題H (H – Grid 1) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 006 の問題D (D – トランプ挿入ソート) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 059 の問題F (F – バイナリハック / Unhappy Hacking) を解いてみた.

C++の練習を兼ねて, Typical DP Contest の問題A (A – コンテスト) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題P (P – Independent Set) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題M (M – Candies) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題I (I – Coins) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題H (H – Grid 1) を解いてみた.