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

C++の練習を兼ねて, AtCoder Beginner Contest 113 の問題C（ID) ～問題D (Number of Amidakuji) を解いてみた.

■感想.
1. 問題C は, かなりゴリゴリ実装せざるを得なかった.
2. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.

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

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    LL N, M;
    cin >> N >> M;
    
    // Map of int and vector<int> in c++
    // https://stackoverflow.com/questions/15192534/map-of-int-and-vectorint-in-c
    // map の key:   県番号(Pi).
    // map の value: vector<pair<LL, LL>>: 誕生年(Yi), 市の番号.
    map<LL, vector<pair<LL, LL>>> m;
    FOR(i, 0, M) {
        LL p, y;
        cin >> p >> y;
        m[p].push_back(make_pair(y, i));
    }
    
    // ex.
    // [input]
    // 2 3
    // 1 32
    // 2 63
    // 1 12
    // 
    // [output]
    // city: 0 -> year: 32 belongs to Prefecture: 1
    // city: 2 -> year: 12 belongs to Prefecture: 1
    // city: 1 -> year: 63 belongs to Prefecture: 2
    // for(auto &p : m) for(auto &i : p.second) cout << "city: " << i.second << " -> year: " << i.first << " belongs to " << "Prefecture: " << p.first << endl;

    // 2. ID生成 ～ 出力.
    map<LL, string> ans;    // 市の番号, 市の認識番号 を 保存.
    for(auto &p : m) {
        
        // 2-1. 誕生年 で 昇順sort.
        vector<pair<LL, LL>> v = p.second;
        sort(v.begin(), v.end());
        
        // 2-2. 市の認識番号を作成.
        for(auto i = v.begin(); i != v.end(); ++i) {
            LL x = i - v.begin() + 1;
            ostringstream ss;
            // 上6桁: 県(Pi)
            ss << std::setw(6) << std::setfill('0') << p.first;
            // 下6桁: 市が, 県(Pi) で, x番目に誕生した
            ss << std::setw(6) << std::setfill('0') << x;
            string id(ss.str());
            // map に 保管して, 市の番号順に, 自動で昇順sort.
            ans[i->second] = id;
        }
    }
    
    // 3. 後処理.
    for(auto &a : ans) cout << a.second << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

LL N, M;

cin >> N >> M;

// Map of int and vector<int> in c++

// https://stackoverflow.com/questions/15192534/map-of-int-and-vectorint-in-c

// map の key: 県番号(Pi).

// map の value: vector<pair<LL, LL>>: 誕生年(Yi), 市の番号.

map<LL, vector<pair<LL, LL>>> m;

FOR(i, 0, M) {

LL p, y;

cin >> p >> y;

m[p].push_back(make_pair(y, i));

}

// ex.

// [input]

// 2 3

// 1 32

// 2 63

// 1 12

// [output]

// city: 0 -> year: 32 belongs to Prefecture: 1

// city: 2 -> year: 12 belongs to Prefecture: 1

// city: 1 -> year: 63 belongs to Prefecture: 2

// for(auto &p : m) for(auto &i : p.second) cout << "city: " << i.second << " -> year: " << i.first << " belongs to " << "Prefecture: " << p.first << endl;

// 2. ID生成～出力.

map<LL, string> ans; // 市の番号, 市の認識番号を保存.

for(auto &p : m) {

// 2-1. 誕生年で昇順sort.

vector<pair<LL, LL>> v = p.second;

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

// 2-2. 市の認識番号を作成.

for(auto i = v.begin(); i != v.end(); ++i) {

LL x = i - v.begin() + 1;

ostringstream ss;

// 上6桁: 県(Pi)

ss << std::setw(6) << std::setfill('0') << p.first;

// 下6桁: 市が, 県(Pi) で, x番目に誕生した

ss << std::setw(6) << std::setfill('0') << x;

string id(ss.str());

// map に保管して, 市の番号順に, 自動で昇順sort.

ans[i->second] = id;

}

// 3. 後処理.

for(auto &a : ans) cout << a.second << endl;

return 0;

}

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

// 解き直し.
// ABC 113 解説.
// https://img.atcoder.jp/abc113/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

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

int main() {
    
    // 1. 入力情報取得.
    LL H, W, K;
    cin >> H >> W >> K;
    
    // 2. 解説通り.
    // DP を 使うとのこと.
    // DP(h, x): 縦から h 列目を通過した(横棒を通った場合も含む)直後に, 左から x本目の縦棒にいる場合の数.
    // DP(h, x) の 遷移先は, DP(h + 1, x - 1), DP(h + 1, x), DP(h + 1, x + 1) の 3種類.
    LL DP[H + 1][W + 1] = {};
    DP[0][1] = 1;
    
    // 2-1. (h + 1)列目の横棒の全配置は, 何通り？
    // W本の縦棒から, 正しいあみだくじの条件を満たすように横棒を配置することに注意.
    // ex.
    // 
    // W = 0 -> 1通り.
    // W = 1 -> 1通り.
    // W = 2 -> 2通り.
    // W = 3 -> 3通り.
    // W = 4 -> 5通り(※横棒:"_", 横棒無し: "." とすると, ... _.. ._. .._ _._ の5通り).
    // ...
    // -> 解説通り, フィボナッチ数列と同じになっていることが分かる.
    LL BAR[W + 1] = {};
    BAR[0] = 1;
    BAR[1] = 1;
    FOR(i, 2, W + 1) BAR[i] = BAR[i - 1] + BAR[i - 2];
    
    // 2-2. DP更新.
    FOR(h, 1, H + 1) {
        FOR(x, 1, W + 1) {
            // 2-2-1. DP(h, x) -> DP(h + 1, x - 1)
            // 左から, x本目 -> (x - 1)本目に遷移するには, 
            // x > 1 の場合で, 
            // ① (x - 1)本目 と x本目       との間に, 横棒が必要.
            // ② (x - 2)本目 と (x - 1)本目 との間は, 横棒が無い状態.
            // ③ (x + 1)本目 と x本目       との間は, 横棒が無い状態.
            // -> 場合の数としては, 左から(x - 2)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数 なので,
            // X = BAR[x - 2] × BAR[W - (x + 1) + 1] と分かる.
            if(x > 1) {
                LL X = BAR[x - 2] * BAR[W - x];
                DP[h][x - 1] += X * DP[h - 1][x];
                DP[h][x - 1] %= MOD;
            }
            
            // 2-2-2. DP(h, x) -> DP(h + 1, x)
            // 左から, x本目 -> x本目のように留まるためには, 
            // (x - 1)本目 と x本目, x本目 と (x + 1)本目 との間に, それぞれ横棒が無い状態.
            // x == 1 または x == W の場合.
            // -> 場合の数としては, (W - 1)本についての横棒配置数 なので, Y = BAR[W - 1] と分かる.
            if(x == 1 || x == W) {
                LL Y = BAR[W - 1];
                DP[h][x] += Y * DP[h - 1][x];
                DP[h][x] %= MOD;
            }
            // x > 1 かつ x < W の場合.
            // -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数 なので,
            // Y = BAR[x - 1] × BAR[W - (x + 1) + 1] と分かる.
            if(x > 1 && x < W) {
                LL Y = BAR[x - 1] * BAR[W - x];
                DP[h][x] += Y * DP[h - 1][x];
                DP[h][x] %= MOD;
            }

            // 2-2-3. DP(h, x) -> DP(h + 1, x + 1)
            // 左から, x本目 -> (x + 1)本目に遷移するには, 
            // x < W の場合で, 
            // ① (x + 1)本目 と x本目       との間に, 横棒が必要.
            // ② (x + 2)本目 と (x + 1)本目 との間は, 横棒が無い状態.
            // ③ (x - 1)本目 と x本目       との間に, 横棒が無い状態.
            // -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 2)本目以降の横棒配置数 なので,
            // Z = BAR[x - 1] × BAR[W - (x + 2) + 1] と分かる.
            if(x < W) {
                LL Z = BAR[x - 1] * BAR[W - x - 1];
                DP[h][x + 1] += Z * DP[h - 1][x];
                DP[h][x + 1] %= MOD;
            }
        }
    }
    
    // 3. 出力 ～ 後処理.
    // FOR(h, 0, H + 1) {
    //     FOR(x, 0, W + 1) {
    //         cout << DP[h][x] << " ";
    //     }
    //     cout << endl;
    // }
    LL ans = 0LL;
    FOR(i, 0, W + 1) {
        LL val = DP[H][i];
        if(i == K) {
            ans = val;
            break;
        }
    }
    cout << ans << endl;
    return 0;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

// 解き直し.

// ABC 113 解説.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

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

int main() {

// 1. 入力情報取得.

LL H, W, K;

cin >> H >> W >> K;

// 2. 解説通り.

// DP を使うとのこと.

// DP(h, x): 縦から h 列目を通過した(横棒を通った場合も含む)直後に, 左から x本目の縦棒にいる場合の数.

// DP(h, x) の遷移先は, DP(h + 1, x - 1), DP(h + 1, x), DP(h + 1, x + 1) の 3種類.

LL DP[H + 1][W + 1] = {};

DP[0][1] = 1;

// 2-1. (h + 1)列目の横棒の全配置は, 何通り？

// W本の縦棒から, 正しいあみだくじの条件を満たすように横棒を配置することに注意.

// ex.

// W = 0 -> 1通り.

// W = 1 -> 1通り.

// W = 2 -> 2通り.

// W = 3 -> 3通り.

// W = 4 -> 5通り(※横棒:"_", 横棒無し: "." とすると, ... _.. ._. .._ _._ の5通り).

// ...

// -> 解説通り, フィボナッチ数列と同じになっていることが分かる.

LL BAR[W + 1] = {};

BAR[0] = 1;

BAR[1] = 1;

FOR(i, 2, W + 1) BAR[i] = BAR[i - 1] + BAR[i - 2];

// 2-2. DP更新.

FOR(h, 1, H + 1) {

FOR(x, 1, W + 1) {

// 2-2-1. DP(h, x) -> DP(h + 1, x - 1)

// 左から, x本目 -> (x - 1)本目に遷移するには,

// x > 1 の場合で,

// ① (x - 1)本目と x本目との間に, 横棒が必要.

// ② (x - 2)本目と (x - 1)本目との間は, 横棒が無い状態.

// ③ (x + 1)本目と x本目との間は, 横棒が無い状態.

// -> 場合の数としては, 左から(x - 2)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数なので,

// X = BAR[x - 2] × BAR[W - (x + 1) + 1] と分かる.

if(x > 1) {

LL X = BAR[x - 2] * BAR[W - x];

DP[h][x - 1] += X * DP[h - 1][x];

DP[h][x - 1] %= MOD;

}

// 2-2-2. DP(h, x) -> DP(h + 1, x)

// 左から, x本目 -> x本目のように留まるためには,

// (x - 1)本目と x本目, x本目と (x + 1)本目との間に, それぞれ横棒が無い状態.

// x == 1 または x == W の場合.

// -> 場合の数としては, (W - 1)本についての横棒配置数なので, Y = BAR[W - 1] と分かる.

if(x == 1 || x == W) {

LL Y = BAR[W - 1];

DP[h][x] += Y * DP[h - 1][x];

DP[h][x] %= MOD;

}

// x > 1 かつ x < W の場合.

// -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数なので,

// Y = BAR[x - 1] × BAR[W - (x + 1) + 1] と分かる.

if(x > 1 && x < W) {

LL Y = BAR[x - 1] * BAR[W - x];

DP[h][x] += Y * DP[h - 1][x];

DP[h][x] %= MOD;

}

// 2-2-3. DP(h, x) -> DP(h + 1, x + 1)

// 左から, x本目 -> (x + 1)本目に遷移するには,

// x < W の場合で,

// ① (x + 1)本目と x本目との間に, 横棒が必要.

// ② (x + 2)本目と (x + 1)本目との間は, 横棒が無い状態.

// ③ (x - 1)本目と x本目との間に, 横棒が無い状態.

// -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 2)本目以降の横棒配置数なので,

// Z = BAR[x - 1] × BAR[W - (x + 2) + 1] と分かる.

if(x < W) {

LL Z = BAR[x - 1] * BAR[W - x - 1];

DP[h][x + 1] += Z * DP[h - 1][x];

DP[h][x + 1] %= MOD;

}

// 3. 出力～後処理.

// FOR(h, 0, H + 1) {

// FOR(x, 0, W + 1) {

// cout << DP[h][x] << " ";

// }

// cout << endl;

// }

LL ans = 0LL;

FOR(i, 0, W + 1) {

LL val = DP[H][i];

if(i == K) {

ans = val;

break;

}

cout << ans << endl;

return 0;

}

[入力例]
1 3 2

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

[入力例]
1 3 1

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

[入力例]
2 3 3

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

[入力例]
2 3 1

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

[入力例]
7 1 1

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

[入力例]
2 5 1

[出力例(debug版)]
0 1 0 0 0 0 
0 5 3 0 0 0 
0 34 24 6 0 0 
34

[入力例]
2 5 2

[出力例(debug版)]
0 1 0 0 0 0 
0 5 3 0 0 0 
0 34 24 6 0 0 
24

[入力例]
15 8 5

[出力例(debug版)]
0 1 0 0 0 0 0 0 0 
0 21 13 0 0 0 0 0 0 
0 610 442 104 0 0 0 0 0 
0 18556 14508 5200 1040 0 0 0 0 
0 578280 471432 209664 67600 9360 0 0 0 
0 18272496 15323568 7802080 3194880 748800 93600 0 0 
0 582928800 499165472 279370624 132683200 40921920 8985600 748800 0 
0 730655810 302190416 790085697 152251485 897833593 558979200 81619200 9734400 
0 272247285 747686381 581409218 265131456 427559120 574956604 659430365 265471993 
0 437115833 910411283 935352977 639096009 549135846 750339658 623383374 147506500 
0 14779025 676149 639897790 882192358 492298204 483859826 24285514 201620285 
0 319149462 320099547 65697279 62546938 162802402 859023284 807653953 549737639 
0 863432743 835815293 237422192 60398457 595191235 833628041 518276800 43991654 
0 997686216 989601843 89261909 636919834 807734929 436175245 978514139 661423085 
0 816234264 548839857 714203523 716030842 210054737 884266168 808585704 610568410 
0 275837517 459591596 978283490 772990360 437760187 717491536 523132651 333550601 
437760187
※AtCoderテストケースより

[入力例]

1 3 2

[出力例(debug版)]

0 1 0 0

0 2 1 0

※AtCoderテストケースより

[入力例]

1 3 1

[出力例(debug版)]

0 1 0 0

0 2 1 0

※AtCoderテストケースより

[入力例]

2 3 3

[出力例(debug版)]

0 1 0 0

0 2 1 0

0 5 3 1

※AtCoderテストケースより

[入力例]

2 3 1

[出力例(debug版)]

0 1 0 0

0 2 1 0

0 5 3 1

※AtCoderテストケースより

[入力例]

7 1 1

[出力例(debug版)]

0 1

※AtCoderテストケースより

[入力例]

2 5 1

[出力例(debug版)]

0 1 0 0 0 0

0 5 3 0 0 0

0 34 24 6 0 0

[入力例]

2 5 2

[出力例(debug版)]

0 1 0 0 0 0

0 5 3 0 0 0

0 34 24 6 0 0

[入力例]

15 8 5

[出力例(debug版)]

0 1 0 0 0 0 0 0 0

0 21 13 0 0 0 0 0 0

0 610 442 104 0 0 0 0 0

0 18556 14508 5200 1040 0 0 0 0

0 578280 471432 209664 67600 9360 0 0 0

0 18272496 15323568 7802080 3194880 748800 93600 0 0

0 582928800 499165472 279370624 132683200 40921920 8985600 748800 0

0 730655810 302190416 790085697 152251485 897833593 558979200 81619200 9734400

0 272247285 747686381 581409218 265131456 427559120 574956604 659430365 265471993

0 437115833 910411283 935352977 639096009 549135846 750339658 623383374 147506500

0 14779025 676149 639897790 882192358 492298204 483859826 24285514 201620285

0 319149462 320099547 65697279 62546938 162802402 859023284 807653953 549737639

0 863432743 835815293 237422192 60398457 595191235 833628041 518276800 43991654

0 997686216 989601843 89261909 636919834 807734929 436175245 978514139 661423085

0 816234264 548839857 714203523 716030842 210054737 884266168 808585704 610568410

0 275837517 459591596 978283490 772990360 437760187 717491536 523132651 333550601

437760187

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 113

C++の練習を兼ねて, AtCoder Beginner Contest 113 の 問題C（ID) ～ 問題D (Number of Amidakuji) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 113 の問題C（ID) ～問題D (Number of Amidakuji) を解いてみた.

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