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

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題A (A – 門限) ～問題B (B – 大事な数なのでZ回書きまLた。) を解いてみた.

■感想.
1. 問題B は, 実装方針が決まるまでに, 非常に苦労したものの, AC版となったので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトARC 027 解説をご覧下さい.

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

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

int main(){
    
    // 1. 入力情報.
    int h, m;
    scanf("%d %d", &h, &m);
    
    // 2. 門限までの時間を計算.
    int ans = 18 * 60;
    ans -= h * 60;
    ans -= m;
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int h, m;

scanf("%d %d", &h, &m);

// 2. 門限までの時間を計算.

int ans = 18 * 60;

ans -= h * 60;

ans -= m;

// 3. 出力.

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

return 0;

}

[入力例]
16 23

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

[入力例]
17 59

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

[入力例]
13 0

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

[入力例]
2 7

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

[入力例]

16 23

[出力例]

※AtCoderのテストケースより

[入力例]

17 59

[出力例]

※AtCoderのテストケースより

[入力例]

13 0

[出力例]

300

※AtCoderのテストケースより

[入力例]

2 7

[出力例]

953

※AtCoderのテストケースより

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

#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
using LL = long long;
using P = pair<char, char>;
#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
const int MAX = 55;
int connection[MAX]; // 連結成分番号を保存.
vvi G(MAX);

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param l: 連結成分番号(※1以上).
// @return: 特に無し.
void bfs(vvi &G, int s, int l){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    connection[s] = l;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(connection[e] > 0)            continue;
            if(connection[e] == 0 && e != s) connection[e] = l, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N;
    char c1[33], c2[33];
    scanf("%d %s %s", &N, c1, c2);
    
    // 2. グループ分け.
    // '0' ～ '9': 頂点  0 ～ 頂点  9
    // 'A' ～ 'Z': 頂点 10 ～ 頂点 35
    set<int> vertex; // 出現した頂点を保存.
    rep(i, N){
        char cx = c1[i], cy = c2[i];
        if(cx >= '0' && cx <= '9'){
            if(cy >= '0' && cy <= '9'){
                G[cx - '0'].pb(cy - '0');
                G[cy - '0'].pb(cx - '0');
                vertex.insert(cx - '0');
                vertex.insert(cy - '0');
            }else{
                G[cx - '0'].pb(cy - 'A' + 10);
                G[cy - 'A' + 10].pb(cx - '0');
                vertex.insert(cx - '0');
                vertex.insert(cy - 'A' + 10);
            }
        }else{
            if(cy >= '0' && cy <= '9'){
                G[cx - 'A' + 10].pb(cy - '0');
                G[cy - '0'].pb(cx - 'A' + 10);
                vertex.insert(cx - 'A' + 10);
                vertex.insert(cy - '0');
            }else{
                G[cx - 'A' + 10].pb(cy - 'A' + 10);
                G[cy - 'A' + 10].pb(cx - 'A' + 10);
                vertex.insert(cx - 'A' + 10);
                vertex.insert(cy - 'A' + 10);
            }
        }
    }
    
    // 3. 各頂点に対する連結成分番号を設定.
    int id = 0;
    rep(i, 36) if(vertex.count(i) && connection[i] == 0) bfs(G, i, ++id);
    // rep(i, 36) printf("i=%d con=%d\n", i, connection[i]);
    
    // 4. グループ番号ごとに, グループ化.
    vector<vector<char>> group(36);
    rep(i, 10) if(connection[i]) group[connection[i]].pb(i + '0');
    repx(i, 10, 36) if(connection[i]) group[connection[i]].pb(i - 10 + 'A');
    
    // 5. 元の文字を書き換え.
    // ex.
    // 6
    // PRBLMB
    // ARC027
    // 
    // -> この場合は, s1, s2 は, 以下のように書き換えることになる.
    // AR7027
    // AR7027
    rep(i, N){
        if(c1[i] >= 'A' && c1[i] <= 'Z'){
            int g = connection[c1[i] - 'A' + 10];
            c1[i] = group[g][0];
        }
        if(c2[i] >= 'A' && c2[i] <= 'Z'){
            int g = connection[c2[i] - 'A' + 10];
            c2[i] = group[g][0];
        }
    }
    string s1(c1), s2(c2);
    // printf("%s\n%s\n", s1.c_str(), s2.c_str());
    
    // 6. 数字が確定してない箇所を集計.
    LL ans = 1;
    rep(i, N) if(c1[i] >= 'A' && c1[i] <= 'Z' && c2[i] >= 'A' && c2[i] <= 'Z') ans *= 10LL;
    
    // 7. 先頭要素を考慮.
    if(c1[0] >= 'A' && c1[0] <= 'Z' && c2[0] >= 'A' && c2[0] <= 'Z') ans = ans / 10LL * 9LL;
    
    // 8. 重複要素を考慮.
    map<P, int> m;
    rep(i, N) m[{c1[i], c2[i]}]++;
    for(auto &p : m){
        P q = p.a;
        if(p.a.a >= 'A' && p.a.a <= 'Z') rep(i, p.b - 1) ans /= 10LL;
    }
    
    // 9. 出力.
    printf("%lld\n", ans);
    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

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<int>>;

using LL = long long;

using P = pair<char, char>;

#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

const int MAX = 55;

int connection[MAX]; // 連結成分番号を保存.

vvi G(MAX);

// グラフを幅優先探索する.

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

// ※bfsの動作確認用.

// @param G: グラフ.

// @param s: グラフの探索開始頂点.

// @param l: 連結成分番号(※1以上).

// @return: 特に無し.

void bfs(vvi &G, int s, int l){

// 1. 空のキュー.

queue<int> q;

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

connection[s] = l;

// 3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]){

// 6. 訪問済であれば, 処理をスキップ.

if(connection[e] > 0) continue;

if(connection[e] == 0 && e != s) connection[e] = l, q.push(e);

}

return;

}

int main(){

// 1. 入力情報.

int N;

char c1[33], c2[33];

scanf("%d %s %s", &N, c1, c2);

// 2. グループ分け.

// '0' ～ '9': 頂点 0 ～頂点 9

// 'A' ～ 'Z': 頂点 10 ～頂点 35

set<int> vertex; // 出現した頂点を保存.

rep(i, N){

char cx = c1[i], cy = c2[i];

if(cx >= '0' && cx <= '9'){

if(cy >= '0' && cy <= '9'){

G[cx - '0'].pb(cy - '0');

G[cy - '0'].pb(cx - '0');

vertex.insert(cx - '0');

vertex.insert(cy - '0');

}else{

G[cx - '0'].pb(cy - 'A' + 10);

G[cy - 'A' + 10].pb(cx - '0');

vertex.insert(cx - '0');

vertex.insert(cy - 'A' + 10);

}

}else{

if(cy >= '0' && cy <= '9'){

G[cx - 'A' + 10].pb(cy - '0');

G[cy - '0'].pb(cx - 'A' + 10);

vertex.insert(cx - 'A' + 10);

vertex.insert(cy - '0');

}else{

G[cx - 'A' + 10].pb(cy - 'A' + 10);

G[cy - 'A' + 10].pb(cx - 'A' + 10);

vertex.insert(cx - 'A' + 10);

vertex.insert(cy - 'A' + 10);

}

// 3. 各頂点に対する連結成分番号を設定.

int id = 0;

rep(i, 36) if(vertex.count(i) && connection[i] == 0) bfs(G, i, ++id);

// rep(i, 36) printf("i=%d con=%d\n", i, connection[i]);

// 4. グループ番号ごとに, グループ化.

vector<vector<char>> group(36);

rep(i, 10) if(connection[i]) group[connection[i]].pb(i + '0');

repx(i, 10, 36) if(connection[i]) group[connection[i]].pb(i - 10 + 'A');

// 5. 元の文字を書き換え.

// ex.

// 6

// PRBLMB

// ARC027

// -> この場合は, s1, s2 は, 以下のように書き換えることになる.

// AR7027

rep(i, N){

if(c1[i] >= 'A' && c1[i] <= 'Z'){

int g = connection[c1[i] - 'A' + 10];

c1[i] = group[g][0];

}

if(c2[i] >= 'A' && c2[i] <= 'Z'){

int g = connection[c2[i] - 'A' + 10];

c2[i] = group[g][0];

}

string s1(c1), s2(c2);

// printf("%s\n%s\n", s1.c_str(), s2.c_str());

// 6. 数字が確定してない箇所を集計.

LL ans = 1;

rep(i, N) if(c1[i] >= 'A' && c1[i] <= 'Z' && c2[i] >= 'A' && c2[i] <= 'Z') ans *= 10LL;

// 7. 先頭要素を考慮.

if(c1[0] >= 'A' && c1[0] <= 'Z' && c2[0] >= 'A' && c2[0] <= 'Z') ans = ans / 10LL * 9LL;

// 8. 重複要素を考慮.

map<P, int> m;

rep(i, N) m[{c1[i], c2[i]}]++;

for(auto &p : m){

P q = p.a;

if(p.a.a >= 'A' && p.a.a <= 'Z') rep(i, p.b - 1) ans /= 10LL;

}

// 9. 出力.

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

return 0;

}

[入力例]
4
1XYX
1Z48

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

[入力例]
3
XXX
YYY

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

[入力例]
6
PRBLMB
ARC027

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

[入力例]
1
A
B

[出力例]
9

[入力例]
12
PRBLMBZQAOIJ
ARC02718C30F

[出力例]
100

[入力例]
10
WWWWXXXYYZ
XXXXYYYZZA

[出力例]
9

[入力例]
15
AAAAABBBBCCCDDE
BBBBBCCCCDDDEEF

[出力例]
9

[入力例]
18
1BCDEFGHIJKLMNOPQR
ABCDEFGHIJKLMNOPQR

[出力例]
100000000000000000

[入力例]
16
1BCDEFGHI3KLM5OP
ABCD2FGHIJK4MNOP

[出力例]
100000000000

[入力例]
17
ACEG1IKLMNO2QR3TU
BDFHIJLMNOPQRSTUV

[出力例]
90000

[入力例]

1XYX

1Z48

[出力例]

※AtCoderのテストケースより

[入力例]

XXX

YYY

[出力例]

※AtCoderのテストケースより

[入力例]

PRBLMB

ARC027

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

PRBLMBZQAOIJ

ARC02718C30F

[出力例]

100

[入力例]

WWWWXXXYYZ

XXXXYYYZZA

[出力例]

[入力例]

AAAAABBBBCCCDDE

BBBBBCCCCDDDEEF

[出力例]

[入力例]

1BCDEFGHIJKLMNOPQR

ABCDEFGHIJKLMNOPQR

[出力例]

100000000000000000

[入力例]

1BCDEFGHI3KLM5OP

ABCD2FGHIJK4MNOP

[出力例]

100000000000

[入力例]

ACEG1IKLMNO2QR3TU

BDFHIJLMNOPQRSTUV

[出力例]

90000

■参照サイト
AtCoder Regular Contest 027

C++の練習を兼ねて, AtCoder Regular Contest 027 の 問題A (A – 門限) ～ 問題B (B – 大事な数なのでZ回書きまLた。) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題A (A – 門限) ～問題B (B – 大事な数なのでZ回書きまLた。) を解いてみた.

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