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

C++の練習を兼ねて, AtCoder Beginner Contest 041 の問題C（背の順) ～問題D（徒競走) を解いてみた.

■感想.
1. 問題C は, iterate の逆順ループについて, 大変参考になったと思う.
2. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.

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

■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. 入力情報取得.
    int N;
    cin >> N;
    map<LL, int> m;
    
    // 2. N人の生徒の身長情報, 出席番号を保存.
    FOR(i, 0, N) {
        LL a;
        cin >> a;
        m[a] = i;
        m[a]++;
    }
    
    // 3. 出力 ～ 後処理.
    // how to iterate in reverse over a map in c++.
    // https://stackoverflow.com/questions/732160/how-to-iterate-in-reverse-over-a-map-in-c
    for(auto i = m.rbegin(); i != m.rend(); ++i) cout << i->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. 入力情報取得.

int N;

cin >> N;

map<LL, int> m;

// 2. N人の生徒の身長情報, 出席番号を保存.

FOR(i, 0, N) {

LL a;

cin >> a;

m[a] = i;

m[a]++;

}

// 3. 出力～後処理.

// how to iterate in reverse over a map in c++.

// https://stackoverflow.com/questions/732160/how-to-iterate-in-reverse-over-a-map-in-c

for(auto i = m.rbegin(); i != m.rend(); ++i) cout << i->second << endl;

return 0;

}

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

// 解き直し.
// ABC 041 解説.
// http://abc041.contest.atcoder.jp/data/abc/041/editorial.pdf
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
    
struct information {
    int x;    // 先にゴールしたうさぎ.
    int y;    // 後からゴールしたうさぎ.
};

// n桁の0埋めの数字を作る.
// https://gin0606.hatenablog.com/entry/2013/12/24/134138
// @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない).
// @param d: 0埋め後の桁数.
string fillText(string s, int d) {
    string ret = s;
    while(ret.size() < d) ret = "0" + ret;
    return ret;
}

// Use of dynamic bitset to convert decimal numbers.
// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers
// 10進数 → 2進数.
// @param n: 2進数へ変換したい10進数.
// @param d: 2進数表記する桁数.
// @return: 2進数.
string decimalToBinary(int n, int d) {
    if(n == 0) return fillText("0", d);
    string ret;
    int ln = abs(n);
    while(ln) {
        ret = string((ln & 1) ? "1" : "0") + ret;
        ln /= 2;
    }
    ret = fillText(ret, d);
    if(n < 0) ret = "-" + ret;
    return ret;
}

// 2進数 → 10進数.
// @param n: 10進数へ変換したい2進数.
// @return ret: 10進数.
int binaryToDecimal(string b) {
    int ret = 0;
    int size = b.size();
    FOR(i, 0, size) ret += ((b[i] - '0') << (size - i - 1));
    return ret;
}

int main() {

    // 1. 入力情報取得.
    int N, M;
    cin >> N >> M;
    vector<information> v;
    FOR(i, 0, M) {
        information info;
        cin >> info.x >> info.y;
        info.x--;
        info.y--;
        v.push_back(info);
    }
    // for(auto &p : v) cout << p.x << " " << p.y << endl;
    
    // 2. 解説通り.
    // f(S): 頂点集合S を トポロジカルソートする方法の通り数.
    // f(S) の 漸化式.
    // f(S): f(φ) = 1  (S = φ)
    // f(S): f(φ) = Σf(S - {v}) (otherwise, v∈(v から S - {v} へ向かう有向辺がない S の部分集合))
    
    // 2-1. 各頂点集合S について, f(S) を 確認.
    // ex. N = 5, S = {0, 1, 3} の 場合, 11010 (index としては, 26 = 16 + 8 + 2) と表現.
    int LIMIT = 1 << N;
    LL ans[LIMIT] = {};
    ans[0] = 1;
    FOR(i, 0, LIMIT) {
        string b = decimalToBinary(i, N);
        // cout << "i=" << i << " b=" << b << endl;
        // 2-2. b に対応する頂点集合S の 各頂点x で, 
        // x から S - {x} に向かう有向辺があるか, 無いかを確認.
        FOR(j, 0, b.size()) {
            // 2-3. S - {x} を 作成(x は j と紐づいている).
            string sb = b;
            sb[j] = '0';
            // cout << "b=" << b << "  sb=" << sb << endl;
            if(b[j] == '1') {
                // 2-4. 観客の情報と照合(ここでは, 頂点x を 先にゴールしたうさぎと見る).
                bool exist = false;
                for(auto &p : v) {
                    // 2-5. 有向辺が有る場合(解説上の 頂点集合Xs の条件を満たしてない).
                    // は, フラグ exist を更新して, 照合作業を抜ける.
                    if(j == p.x && sb[p.y] == '1') {
                        // ex.
                        // [入力例]
                        // 3 2
                        // 2 1
                        // 2 3
                        // -> 以下のような照合を確認できた.
                        // b=011  sb=001 p.x=1 p.y=2
                        // b=110  sb=100 p.x=1 p.y=0
                        // b=111  sb=101 p.x=1 p.y=0
                        // cout << "b=" << b << "  sb=" << sb << endl;
                        // cout << "p.x=" << p.x << " p.y=" << p.y << endl;
                        exist = true;
                        break;
                    }
                }
                // 2-6. 有向辺が無い場合(解説上の 頂点集合Xs の条件を満たしている).
                // は, 漸化式 f(S) を更新.
                if(!exist) {
                    int sbIndex = binaryToDecimal(sb);
                    ans[i] += ans[sbIndex];
                }
            }
        }
    }
    
    // cout << binaryToDecimal("010100") << endl;  // 20
    // cout << binaryToDecimal("1100111") << endl; // 103
    // FOR(i, 0, LIMIT) cout << ans[i] << endl;
    
    // 3. 出力 ～ 後処理.
    // U: 全頂点集合 として f(U) の index を 指定.
    cout << ans[LIMIT - 1] << 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

128

129

130

131

// 解き直し.

// ABC 041 解説.

// http://abc041.contest.atcoder.jp/data/abc/041/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

struct information {

int x; // 先にゴールしたうさぎ.

int y; // 後からゴールしたうさぎ.

};

// n桁の0埋めの数字を作る.

// https://gin0606.hatenablog.com/entry/2013/12/24/134138

// @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない).

// @param d: 0埋め後の桁数.

string fillText(string s, int d) {

string ret = s;

while(ret.size() < d) ret = "0" + ret;

return ret;

}

// Use of dynamic bitset to convert decimal numbers.

// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers

// 10進数 → 2進数.

// @param n: 2進数へ変換したい10進数.

// @param d: 2進数表記する桁数.

// @return: 2進数.

string decimalToBinary(int n, int d) {

if(n == 0) return fillText("0", d);

string ret;

int ln = abs(n);

while(ln) {

ret = string((ln & 1) ? "1" : "0") + ret;

ln /= 2;

}

ret = fillText(ret, d);

if(n < 0) ret = "-" + ret;

return ret;

}

// 2進数 → 10進数.

// @param n: 10進数へ変換したい2進数.

// @return ret: 10進数.

int binaryToDecimal(string b) {

int ret = 0;

int size = b.size();

FOR(i, 0, size) ret += ((b[i] - '0') << (size - i - 1));

return ret;

}

int main() {

// 1. 入力情報取得.

int N, M;

cin >> N >> M;

vector<information> v;

FOR(i, 0, M) {

information info;

cin >> info.x >> info.y;

info.x--;

info.y--;

v.push_back(info);

}

// for(auto &p : v) cout << p.x << " " << p.y << endl;

// 2. 解説通り.

// f(S): 頂点集合S をトポロジカルソートする方法の通り数.

// f(S) の漸化式.

// f(S): f(φ) = 1 (S = φ)

// f(S): f(φ) = Σf(S - {v}) (otherwise, v∈(v から S - {v} へ向かう有向辺がない S の部分集合))

// 2-1. 各頂点集合S について, f(S) を確認.

// ex. N = 5, S = {0, 1, 3} の場合, 11010 (index としては, 26 = 16 + 8 + 2) と表現.

int LIMIT = 1 << N;

LL ans[LIMIT] = {};

ans[0] = 1;

FOR(i, 0, LIMIT) {

string b = decimalToBinary(i, N);

// cout << "i=" << i << " b=" << b << endl;

// 2-2. b に対応する頂点集合S の各頂点x で,

// x から S - {x} に向かう有向辺があるか, 無いかを確認.

FOR(j, 0, b.size()) {

// 2-3. S - {x} を作成(x は j と紐づいている).

string sb = b;

sb[j] = '0';

// cout << "b=" << b << " sb=" << sb << endl;

if(b[j] == '1') {

// 2-4. 観客の情報と照合(ここでは, 頂点x を先にゴールしたうさぎと見る).

bool exist = false;

for(auto &p : v) {

// 2-5. 有向辺が有る場合(解説上の頂点集合Xs の条件を満たしてない).

// は, フラグ exist を更新して, 照合作業を抜ける.

if(j == p.x && sb[p.y] == '1') {

// ex.

// [入力例]

// 3 2

// 2 1

// 2 3

// -> 以下のような照合を確認できた.

// b=011 sb=001 p.x=1 p.y=2

// b=110 sb=100 p.x=1 p.y=0

// b=111 sb=101 p.x=1 p.y=0

// cout << "b=" << b << " sb=" << sb << endl;

// cout << "p.x=" << p.x << " p.y=" << p.y << endl;

exist = true;

break;

}

// 2-6. 有向辺が無い場合(解説上の頂点集合Xs の条件を満たしている).

// は, 漸化式 f(S) を更新.

if(!exist) {

int sbIndex = binaryToDecimal(sb);

ans[i] += ans[sbIndex];

}

// cout << binaryToDecimal("010100") << endl; // 20

// cout << binaryToDecimal("1100111") << endl; // 103

// FOR(i, 0, LIMIT) cout << ans[i] << endl;

// 3. 出力～後処理.

// U: 全頂点集合として f(U) の index を指定.

cout << ans[LIMIT - 1] << endl;

return 0;

}

[入力例]
3 2
2 1
2 3

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

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

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

[入力例]
16 1
1 2

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

[入力例]
3 2
1 2
2 3

[出力例]
1
※兎1 -> 兎2 -> 兎3 の 1通りに決まる.

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

[出力例]
15
※以下の15通りある.
兎1 -> 兎5 -> 兎2 -> 兎4 -> 兎3
兎1 -> 兎5 -> 兎4 -> 兎2 -> 兎3
兎1 -> 兎4 -> 兎5 -> 兎2 -> 兎3
兎4 -> 兎1 -> 兎5 -> 兎2 -> 兎3
兎1 -> 兎2 -> 兎5 -> 兎4 -> 兎3
兎1 -> 兎2 -> 兎4 -> 兎5 -> 兎3
兎1 -> 兎4 -> 兎2 -> 兎5 -> 兎3
兎4 -> 兎1 -> 兎2 -> 兎5 -> 兎3
兎1 -> 兎2 -> 兎4 -> 兎3 -> 兎5
兎1 -> 兎4 -> 兎2 -> 兎3 -> 兎5
兎4 -> 兎1 -> 兎2 -> 兎3 -> 兎5
兎5 -> 兎1 -> 兎2 -> 兎4 -> 兎3
兎5 -> 兎1 -> 兎4 -> 兎2 -> 兎3
兎5 -> 兎4 -> 兎1 -> 兎2 -> 兎3
兎4 -> 兎5 -> 兎1 -> 兎2 -> 兎3

[入力例]

3 2

2 1

2 3

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1 2

2 3

3 5

1 4

4 5

[出力例]

※AtCoderテストケースより

[入力例]

16 1

1 2

[出力例]

10461394944000

※AtCoderテストケースより

[入力例]

3 2

1 2

2 3

[出力例]

※兎1 -> 兎2 -> 兎3 の 1通りに決まる.

[入力例]

5 3

1 2

2 3

4 3

[出力例]

※以下の15通りある.

兎1 -> 兎5 -> 兎2 -> 兎4 -> 兎3

兎1 -> 兎5 -> 兎4 -> 兎2 -> 兎3

兎1 -> 兎4 -> 兎5 -> 兎2 -> 兎3

兎4 -> 兎1 -> 兎5 -> 兎2 -> 兎3

兎1 -> 兎2 -> 兎5 -> 兎4 -> 兎3

兎1 -> 兎2 -> 兎4 -> 兎5 -> 兎3

兎1 -> 兎4 -> 兎2 -> 兎5 -> 兎3

兎4 -> 兎1 -> 兎2 -> 兎5 -> 兎3

兎1 -> 兎2 -> 兎4 -> 兎3 -> 兎5

兎1 -> 兎4 -> 兎2 -> 兎3 -> 兎5

兎4 -> 兎1 -> 兎2 -> 兎3 -> 兎5

兎5 -> 兎1 -> 兎2 -> 兎4 -> 兎3

兎5 -> 兎1 -> 兎4 -> 兎2 -> 兎3

兎5 -> 兎4 -> 兎1 -> 兎2 -> 兎3

兎4 -> 兎5 -> 兎1 -> 兎2 -> 兎3

■参照サイト
AtCoder Beginner Contest 041

C++の練習を兼ねて, AtCoder Beginner Contest 041 の 問題C（背の順) ～ 問題D（徒競走) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 041 の問題C（背の順) ～問題D（徒競走) を解いてみた.

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