個人用メモ帳

2020年10月29日2020年10月29日

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

C++の練習を兼ねて, AtCoder Regular Contest 088 の問題E (Papple Sort) を解いてみた.

■感想.
1. E問題は, 方針が全く見えず, 解説を確認して, AC版に到達できたので, 良かったと思う.
2. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc088/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
#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
#define all(x) x.begin(), x.end()
int a[26], b[202020], c[202020], S[26][202020], tCount[26], T[26][202020], per[202020];

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

int main(){
    
    // 1. 入力情報.
    char s[202020];
    scanf("%s", s);
    string str(s);
    int l = str.size();
    
    // 2. 各文字に対して, 出現回数を割り当てる.
    rep(i, l){
        // 2-1. 各文字の出現回数.
        int idx = str[i] - 'a';
        a[idx]++;
        
        // 2-2. 各文字(位置)に対する出現回数.
        b[i] = a[idx];
        
        // 2-3. 各文字, 出現回数 に 紐づく 出現位置 を 保存.
        S[idx][a[idx]] = i + 1;
    }
    
    // 3. 奇数回しか出てこない文字を調査.
    int odd = 0;
    rep(i, 26) if(a[i] & 1) odd++;
    if(odd >= 2){
        puts("-1");
        return 0;
    }
    
    // 4. 回文作成後 の 左, 中央, 右 の 位置判定.
    rep(i, l){
        int idx = str[i] - 'a';
        // 4-1. 奇数(最大1つ).
        if(a[idx] & 1){
            if(b[i] * 2 == a[idx] + 1)     c[i] = 2; // 中央.
            else if(b[i] * 2 < a[idx] + 1) c[i] = 1; // 左.
            else if(b[i] * 2 > a[idx] + 1) c[i] = 3; // 右.
        }
        // 4-2. 偶数.
        if(!(a[idx] & 1)){
            if(b[i] * 2 <= a[idx]) c[i] = 1; // 左.
            else                   c[i] = 3; // 右.
        }
    }
    
    // 5. 文字列 X 作成.
    vector<P> X;
    rep(i, l) X.pb({c[i], i});
    sort(all(X));
    // rep(i, l) printf("o=%d p=%d\n", X[i].a, X[i].b);
    
    // 6. 変換: X -> T.
    // 左, 中央のみ対応する.
    rep(i, (l + 1) / 2){
        // 6-1. 文字列 X から 一文字取得.
        P p = X[i];
        
        // 6-2. 出現回数を保存.
        int x = str[p.b] - 'a';
        int y = ++tCount[x];
        
        // 6-3. 文字列 T における 位置情報 を保存.
        if(y * 2 <= a[x] + 1){
            T[x][y] = i + 1;
            T[x][a[x] + 1 - y] = l - i;
        }
    }
    // rep(i, 26){
    //     repx(j, 1, a[i] + 1) printf("i=%d j=%d s=%d t=%d\n", i, j, S[i][j], T[i][j]);
    // }
    
    // 7. 順列 per を 作成.
    // -> S[i][j] -> T[i][j] への変換を保存.
    rep(i, 26) repx(j, 1, a[i] + 1) per[S[i][j]] = T[i][j];
    
    // 8. バブルソートの交換回数を集計.
    BIT<LL> ft(l + 1);
    LL ans = 0;
    repx(i, 1, l + 1){
        // 8-1. per[i] に, 1 を 加算.
        ft.add(per[i], 1LL);
        
        // 8-2. 区間[0, per[i]] の 合計は？
        LL t = ft.sum(0, per[i] + 1);
        
        // 8-3. 転倒数を集計.
        ans += (LL)per[i] - t;
    }
    
    // 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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

#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

#define all(x) x.begin(), x.end()

int a[26], b[202020], c[202020], S[26][202020], tCount[26], T[26][202020], per[202020];

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] += x;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x += d[i];

return x;

}

T sum(int l, int r){

return sum(r - 1) - sum(l - 1);

}

};

int main(){

// 1. 入力情報.

char s[202020];

scanf("%s", s);

string str(s);

int l = str.size();

// 2. 各文字に対して, 出現回数を割り当てる.

rep(i, l){

// 2-1. 各文字の出現回数.

int idx = str[i] - 'a';

a[idx]++;

// 2-2. 各文字(位置)に対する出現回数.

b[i] = a[idx];

// 2-3. 各文字, 出現回数に紐づく出現位置を保存.

S[idx][a[idx]] = i + 1;

}

// 3. 奇数回しか出てこない文字を調査.

int odd = 0;

rep(i, 26) if(a[i] & 1) odd++;

if(odd >= 2){

puts("-1");

return 0;

}

// 4. 回文作成後の左, 中央, 右の位置判定.

rep(i, l){

int idx = str[i] - 'a';

// 4-1. 奇数(最大1つ).

if(a[idx] & 1){

if(b[i] * 2 == a[idx] + 1) c[i] = 2; // 中央.

else if(b[i] * 2 < a[idx] + 1) c[i] = 1; // 左.

else if(b[i] * 2 > a[idx] + 1) c[i] = 3; // 右.

}

// 4-2. 偶数.

if(!(a[idx] & 1)){

if(b[i] * 2 <= a[idx]) c[i] = 1; // 左.

else c[i] = 3; // 右.

}

// 5. 文字列 X 作成.

vector<P> X;

rep(i, l) X.pb({c[i], i});

sort(all(X));

// rep(i, l) printf("o=%d p=%d\n", X[i].a, X[i].b);

// 6. 変換: X -> T.

// 左, 中央のみ対応する.

rep(i, (l + 1) / 2){

// 6-1. 文字列 X から一文字取得.

P p = X[i];

// 6-2. 出現回数を保存.

int x = str[p.b] - 'a';

int y = ++tCount[x];

// 6-3. 文字列 T における位置情報を保存.

if(y * 2 <= a[x] + 1){

T[x][y] = i + 1;

T[x][a[x] + 1 - y] = l - i;

}

// rep(i, 26){

// repx(j, 1, a[i] + 1) printf("i=%d j=%d s=%d t=%d\n", i, j, S[i][j], T[i][j]);

// }

// 7. 順列 per を作成.

// -> S[i][j] -> T[i][j] への変換を保存.

rep(i, 26) repx(j, 1, a[i] + 1) per[S[i][j]] = T[i][j];

// 8. バブルソートの交換回数を集計.

BIT<LL> ft(l + 1);

LL ans = 0;

repx(i, 1, l + 1){

// 8-1. per[i] に, 1 を加算.

ft.add(per[i], 1LL);

// 8-2. 区間[0, per[i]] の合計は？

LL t = ft.sum(0, per[i] + 1);

// 8-3. 転倒数を集計.

ans += (LL)per[i] - t;

}

// 9. 出力.

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

return 0;

}

[入力例]
eel

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

[入力例]
ataatmma

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

[入力例]
snuke

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

[入力例]
abcabcabcabcabcabc

[出力例]
9

[入力例]
abracadabra

[出力例]
-1

[入力例]
edaceabdaeabcaedabaeadbaecabdaeabaedcabeadabeadcabadabd

[出力例]
88

[入力例]

eel

[出力例]

※AtCoderテストケースより

[入力例]

ataatmma

[出力例]

※AtCoderテストケースより

[入力例]

snuke

[出力例]

-1

※AtCoderテストケースより

[入力例]

abcabcabcabcabcabc

[出力例]

[入力例]

abracadabra

[出力例]

-1

[入力例]

edaceabdaeabcaedabaeadbaecabdaeabaedcabeadabeadcabadabd

[出力例]

■参照サイト
AtCoder Regular Contest 088
Binary Indexed Tree (Fenwick Tree)

2020年10月27日2020年10月27日

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

C++の練習を兼ねて, AtCoder Regular Contest 083 の問題E (Bichrome Tree) を解いてみた.

■感想.
1. E問題は, 方針が全く見えず, 解説を確認して, AC版に到達できたので, 良かったと思う.
2. 問題文で問われている内容を理解するのに, 時間かかってしまったように思う.
3. 木dp の訓練, 幅優先探索の復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc083/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
#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
#define a first
#define b second
int d[1010];   // 頂点 1 からの 距離 を 保存.
int x[1010];   // 重み(数列).
int dpX[1010]; // 木dp(頂点 i を 根 とみた 部分木 で 同じ色).
int dpY[1010]; // 木dp(頂点 i を 根 とみた 部分木 で 異なる色).

// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param d: 探索開始地点からの距離.
// @return: 特に無し.
void bfs(vvi &G, int s, int* d){
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 探索地点 s をキュー q に追加.
    q.push(s);
    
    // 3. キューが空になるまで繰り返し.
    while(!q.empty()){
        // 4. 頂点を一つ取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 隣接する頂点を確認.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(d[e])            continue;
            if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, p;
    scanf("%d", &N);
    vvi G(N);
    repx(i, 1, N){
        scanf("%d", &p);
        p--;
        G[i].pb(p);
        G[p].pb(i);
    }
    rep(i, N) scanf("%d", &x[i]);
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    bfs(G, 0, d);
    // rep(i, N) printf("%d ", d[i]);
    // puts("");
    
    // 3. 頂点 1 から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}
    
    // 4. 木dp.
    bool ok = true;
    while(!pq.empty()){
        // 4-1. 頂点 v を一つ取り出す.
        P p = pq.top();
        pq.pop();
        
        // 4-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 4-3. 配列宣言.
        int z[5050], xy = 0, wSum = 0;
        memset(z, 0, sizeof(z));
        
        // 4-4. スタート地点は, 1 を 設定.
        z[0] = 1;
        
        // 4-5. 頂点 v を 根とする部分木 について, 木dp を 更新.
        // printf("1. v=%d\n", v);
        for(auto &u : G[v]){
            // 頂点 v の 子供 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                // 頂点 v の 子供について, 重みの総和 を 集計.
                xy += x[u];   // 頂点 u の 重み(※同じ色, 子孫).
                xy += dpY[u]; // 頂点 u の 重み(※異なる色, 子孫).
                
                // 頂点 v の 子供について, 重みの総和(最小値) を 集計.
                wSum += min(x[u], dpY[u]);
                
                // 頂点 v の 子供について, 同色のものの重みの和が, x[v]以下となるか？
                // Typical DP Contest (A - コンテスト) を ベース に 実装.
                // https://atcoder.jp/contests/tdpc/tasks/tdpc_contest
                repr(i, x[v], 0){
                    if(z[i]){
                        if(i + x[u]   <= x[v]) z[i + x[u]]   = 1;
                        if(i + dpY[u] <= x[v]) z[i + dpY[u]] = 1;
                    }
                    // printf("2. u=%d dpX=%d dpY=%d\n", u, dpX[u], dpY[u]);
                }
            }
        }
        
        // 4-6. x[v]以下となる z[i] を 探索.
        int maxZ = 0;
        rep(i, x[v] + 1) if(z[i]) maxZ = i;
        
        // 4-7. 割り当てを行う.
        if(wSum <= x[v]){
            dpX[v] = x[v] - maxZ;
            dpY[v] = xy + dpX[v] - x[v];
        }else{
            ok = false;
            break;
        }
    }
    // rep(i, N) printf("%d ", dpX[i]);
    // puts("");
    // rep(i, N) printf("%d ", dpY[i]);
    // puts("");
    
    // 5. 出力.
    printf("%s\n", ok ? "POSSIBLE" : "IMPOSSIBLE");
    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

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<int>>;

using P = pair<int, int>;

#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

#define a first

#define b second

int d[1010]; // 頂点 1 からの距離を保存.

int x[1010]; // 重み(数列).

int dpX[1010]; // 木dp(頂点 i を根とみた部分木で同じ色).

int dpY[1010]; // 木dp(頂点 i を根とみた部分木で異なる色).

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

// ※bfsの動作確認用.

// @param G: グラフ.

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

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

// @return: 特に無し.

void bfs(vvi &G, int s, int* d){

// 1. 空のキュー.

queue<int> q;

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

q.push(s);

// 3. キューが空になるまで繰り返し.

while(!q.empty()){

// 4. 頂点を一つ取り出す.

int u = q.front();

q.pop();

// 5. 隣接する頂点を確認.

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

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

if(d[e]) continue;

if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);

}

return;

}

int main(){

// 1. 入力情報.

int N, p;

scanf("%d", &N);

vvi G(N);

repx(i, 1, N){

scanf("%d", &p);

p--;

G[i].pb(p);

G[p].pb(i);

}

rep(i, N) scanf("%d", &x[i]);

// 2. 頂点 1 から各頂点までの距離を計算.

bfs(G, 0, d);

// rep(i, N) printf("%d ", d[i]);

// puts("");

// 3. 頂点 1 から遠い順に並び替え.

priority_queue<P> pq;

rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}

// 4. 木dp.

bool ok = true;

while(!pq.empty()){

// 4-1. 頂点 v を一つ取り出す.

P p = pq.top();

pq.pop();

// 4-2. 頂点 v の頂点番号は？

int v = p.b;

// 4-3. 配列宣言.

int z[5050], xy = 0, wSum = 0;

memset(z, 0, sizeof(z));

// 4-4. スタート地点は, 1 を設定.

z[0] = 1;

// 4-5. 頂点 v を根とする部分木について, 木dp を更新.

// printf("1. v=%d\n", v);

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

// 頂点 v の子供に相当する頂点 u を選択.

if(d[u] > d[v]){

// 頂点 v の子供について, 重みの総和を集計.

xy += x[u]; // 頂点 u の重み(※同じ色, 子孫).

xy += dpY[u]; // 頂点 u の重み(※異なる色, 子孫).

// 頂点 v の子供について, 重みの総和(最小値) を集計.

wSum += min(x[u], dpY[u]);

// 頂点 v の子供について, 同色のものの重みの和が, x[v]以下となるか？

// Typical DP Contest (A - コンテスト) をベースに実装.

// https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

repr(i, x[v], 0){

if(z[i]){

if(i + x[u] <= x[v]) z[i + x[u]] = 1;

if(i + dpY[u] <= x[v]) z[i + dpY[u]] = 1;

}

// printf("2. u=%d dpX=%d dpY=%d\n", u, dpX[u], dpY[u]);

}

// 4-6. x[v]以下となる z[i] を探索.

int maxZ = 0;

rep(i, x[v] + 1) if(z[i]) maxZ = i;

// 4-7. 割り当てを行う.

if(wSum <= x[v]){

dpX[v] = x[v] - maxZ;

dpY[v] = xy + dpX[v] - x[v];

}else{

ok = false;

break;

}

// rep(i, N) printf("%d ", dpX[i]);

// puts("");

// rep(i, N) printf("%d ", dpY[i]);

// puts("");

// 5. 出力.

printf("%s\n", ok ? "POSSIBLE" : "IMPOSSIBLE");

return 0;

}

[入力例]
3
1 1
4 3 2

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

[入力例]
3
1 2
1 2 3

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

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

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

[入力例]
1

0

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

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

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

[入力例]
10
1 4 1 4 4 4 9 1 9
1 1 1 1 1 1 1 1 1 1

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

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

[出力例(debug版)]
0 2 3 0 2 5 0 0 3 6 1 
12 0 0 3 0 0 1 3 0 0 0 
POSSIBLE

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

[出力例(debug版)]
1 3 1 0 0 0 1 2 5 3 1 1 2 3 2 
13 0 4 11 0 1 0 0 0 0 0 2 0 0 0 
POSSIBLE

[入力例]

1 1

4 3 2

[出力例]

POSSIBLE

※AtCoderテストケースより

[入力例]

1 2

1 2 3

[出力例]

IMPOSSIBLE

※AtCoderテストケースより

[入力例]

1 1 1 3 4 5 5

4 1 6 2 2 1 3 3

[出力例]

POSSIBLE

※AtCoderテストケースより

[入力例]

[出力例]

POSSIBLE

※AtCoderテストケースより

[入力例]

1 4 1 4

5 4 2 3 1

[出力例(debug版)]

1 4 2 0 1

3 0 0 0 0

POSSIBLE

[入力例]

1 4 1 4 4 4 9 1 9

1 1 1 1 1 1 1 1 1 1

[出力例(debug版)]

0 1 1 0 1 1 1 1 0 1

0 0 0 3 0 0 0 0 1 0

IMPOSSIBLE

[入力例]

7 8 1 8 8 1 1 4 4 7

10 2 3 6 2 5 2 7 3 6 1

[出力例(debug版)]

0 2 3 0 2 5 0 0 3 6 1

12 0 0 3 0 0 1 3 0 0 0

POSSIBLE

[入力例]

1 1 1 4 4 5 5 6 6 6 3 3 12 12

12 3 5 1 3 8 1 2 5 3 1 4 2 3 2

[出力例(debug版)]

1 3 1 0 0 0 1 2 5 3 1 1 2 3 2

13 0 4 11 0 1 0 0 0 0 0 2 0 0 0

POSSIBLE

■参照サイト
AtCoder Regular Contest 083

2020年10月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題D (Powers) を解いてみた.

■感想.
1. D問題は, 方針が全く見えず, 解説を確認して, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc106/editorial/238
// 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--)
const LL MOD = 998244353;
LL FAC[333], INV[333], A[333], B[333], a[202020];

// 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 % MOD;
}

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%lld", &a[i]);
    FAC[0] = 1;
    repx(i, 1, 333) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, 333)     INV[i] = mPow(FAC[i], MOD - 2LL);
    
    // 2. 各 k について, 前計算.
    rep(k, K + 1){
        rep(i, N){
            A[k] += mPow(a[i], (LL)k) * INV[k];
            A[k] %= MOD;
        }
    }
    
    // 3. Σ{(A[i] + A[i]) の X 乗} を 計算.
    repx(k, 1, K + 1){
        rep(i, N){
            B[k] += mPow(2LL * a[i], (LL)k);
            B[k] %= MOD;
        }
    }
    
    // 4. 各 X について出力.
    repx(X, 1, K + 1){
        // ΣΣ{(A[i] + A[j]) の X 乗}
        LL p = FAC[X], q = 0, ans = 0;
        rep(k, X + 1){
            q += A[k] * A[X - k];
            q %= MOD;
        }
        ans = p * q % MOD;
        
        // B[X] を 減算.
        ans = (ans + MOD - B[X]) % MOD;
        
        // 2で割る.
        ans *= mPow(2LL, MOD - 2LL);
        ans %= MOD;
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc106/editorial/238

// 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--)

const LL MOD = 998244353;

LL FAC[333], INV[333], A[333], B[333], a[202020];

// 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 % MOD;

}

int main(){

// 1. 入力情報.

int N, K;

scanf("%d %d", &N, &K);

rep(i, N) scanf("%lld", &a[i]);

FAC[0] = 1;

repx(i, 1, 333) FAC[i] = (LL)i * FAC[i - 1] % MOD;

rep(i, 333) INV[i] = mPow(FAC[i], MOD - 2LL);

// 2. 各 k について, 前計算.

rep(k, K + 1){

rep(i, N){

A[k] += mPow(a[i], (LL)k) * INV[k];

A[k] %= MOD;

}

// 3. Σ{(A[i] + A[i]) の X 乗} を計算.

repx(k, 1, K + 1){

rep(i, N){

B[k] += mPow(2LL * a[i], (LL)k);

B[k] %= MOD;

}

// 4. 各 X について出力.

repx(X, 1, K + 1){

// ΣΣ{(A[i] + A[j]) の X 乗}

LL p = FAC[X], q = 0, ans = 0;

rep(k, X + 1){

q += A[k] * A[X - k];

q %= MOD;

}

ans = p * q % MOD;

// B[X] を減算.

ans = (ans + MOD - B[X]) % MOD;

// 2で割る.

ans *= mPow(2LL, MOD - 2LL);

ans %= MOD;

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

}

return 0;

}

[入力例]
3 3
1 2 3

[出力例]
12
50
216
※AtCoderのテストケースより

[入力例]
10 10
1 1 1 1 1 1 1 1 1 1

[出力例]
90
180
360
720
1440
2880
5760
11520
23040
46080
※AtCoderのテストケースより

[入力例]
2 5
1234 5678

[出力例]
6912
47775744
805306038
64822328
838460992
※AtCoderのテストケースより

[入力例]
11 15
3 1 4 1 5 9 2 6 5 3 5 9

[出力例]
440
4024
40760
446824
5207600
63633664
806442440
529246574
276765460
647550404
683255879
424664316
795223705
754320595
396556895

[入力例]

3 3

1 2 3

[出力例]

216

※AtCoderのテストケースより

[入力例]

10 10

1 1 1 1 1 1 1 1 1 1

[出力例]

180

360

720

1440

2880

5760

11520

23040

46080

※AtCoderのテストケースより

[入力例]

2 5

1234 5678

[出力例]

6912

47775744

805306038

64822328

838460992

※AtCoderのテストケースより

[入力例]

11 15

3 1 4 1 5 9 2 6 5 3 5 9

[出力例]

440

4024

40760

446824

5207600

63633664

806442440

529246574

276765460

647550404

683255879

424664316

795223705

754320595

396556895

■参照サイト
AtCoder Regular Contest 106

2020年10月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題C (Solutions) を解いてみた.

■感想.
1. C問題は, 方針が全く見えず, 解説を確認して, AC版に到達できたので, 良かったと思う.
2. 個人的には, 区間スケジューリングに関する性質を知ることが出来て, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc106/editorial/242
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#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--)

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. 条件分岐に応じて, 出力.
    // 2-1. 以下の三条件の場合.
    // M < 0
    // M = N
    // M = N - 1 && N >= 2
    if(M < 0 || M == N || (M == N - 1 && N >= 2)){
        puts("-1");
        return 0;
    }
    
    // 2-2. M = 0 の 場合.
    if(M == 0){
        rep(i, N){
            int s = 2 * i + 1;
            int g = s + 1;
            printf("%d %d\n", s, g);
        }
    }
    
    // 2-3. M >= 1 && M <= N - 2 の 場合.
    if(M >= 1 && M <= N - 2){
        // 1つの大きな区間.
        printf("%d %d\n", 1, 2 * (M + 2));
        
        // M + 1 個 の 区間.
        rep(i, M + 1){
            int s = 2 * (i + 1);
            int g = s + 1;
            printf("%d %d\n", s, g);
        }
        
        // 残りの N - M - 2 個 の 区間.
        rep(i, N - M - 2){
            int s = 2 * (M + 2 + i) + 1;
            int g = s + 1;
            printf("%d %d\n", s, g);
        }
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc106/editorial/242

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

#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--)

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

// 2. 条件分岐に応じて, 出力.

// 2-1. 以下の三条件の場合.

// M < 0

// M = N

// M = N - 1 && N >= 2

if(M < 0 || M == N || (M == N - 1 && N >= 2)){

puts("-1");

return 0;

}

// 2-2. M = 0 の場合.

if(M == 0){

rep(i, N){

int s = 2 * i + 1;

int g = s + 1;

printf("%d %d\n", s, g);

}

// 2-3. M >= 1 && M <= N - 2 の場合.

if(M >= 1 && M <= N - 2){

// 1つの大きな区間.

printf("%d %d\n", 1, 2 * (M + 2));

// M + 1 個の区間.

rep(i, M + 1){

int s = 2 * (i + 1);

int g = s + 1;

printf("%d %d\n", s, g);

}

// 残りの N - M - 2 個の区間.

rep(i, N - M - 2){

int s = 2 * (M + 2 + i) + 1;

int g = s + 1;

printf("%d %d\n", s, g);

}

return 0;

}

[入力例]
5 1

[出力例]
1 10
8 12
13 20
11 14
2 4
※AtCoderのテストケースより

※ 但し, 上記のプログラムでは, 以下の内容が出力される.
1 6
2 3
4 5
7 8
9 10

[入力例]
10 -10

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

[入力例]
7 0

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

[入力例]
12 7

[出力例]
1 18
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
19 20
21 22
23 24

[入力例]

5 1

[出力例]

1 10

8 12

13 20

11 14

2 4

※AtCoderのテストケースより

※ 但し, 上記のプログラムでは, 以下の内容が出力される.

1 6

2 3

4 5

7 8

9 10

[入力例]

10 -10

[出力例]

-1

※AtCoderのテストケースより

[入力例]

7 0

[出力例]

1 2

3 4

5 6

7 8

9 10

11 12

13 14

[入力例]

12 7

[出力例]

1 18

2 3

4 5

6 7

8 9

10 11

12 13

14 15

16 17

19 20

21 22

23 24

■参照サイト
AtCoder Regular Contest 106

2020年10月25日2020年10月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 090 の問題D (People on a Line) を解いてみた.

■感想.
1. D問題は, 方針が見えなかったので, 解説をベースに, AC版に到達できたので, 良かったと思う.
2. 幅優先探索(応用版, 重み付き有向グラフ)の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc090/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#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
int connection[101010]; // 連結成分番号を保存.
int x[101010];          // 各頂点への割り当てる整数.

struct edge{
    int v; // 次の頂点.
    int c; // コスト.
};

vector<edge> G[101010];

// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param s: グラフの探索開始頂点.
// @param l: 連結成分番号(※1以上).
// @return: 特に無し.
void bfs(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.v]) continue;
            if(!connection[e.v] && e.v != s){
                connection[e.v] = l;
                x[e.v] += x[u] + e.c; // 位置 x を 割り当てる.
                q.push(e.v);
            }
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    map<P, int> m;
    rep(i, M){
        int l, r, d;
        scanf("%d %d %d", &l, &r, &d);
        l--, r--;
        G[l].pb({r, d});
        G[r].pb({l, -d});
        m[{l, r}] = d;
        m[{r, l}] = -d;
    }
    
    // 2. 探索を行い, 各連結成分ごとに, 位置 x を 割り当てる.
    int idx = 0;
    rep(i, N) if(!connection[i]) bfs(i, ++idx);
    
    // 3. 割り当てた位置 x を チェック.
    bool ok = true;
    for(auto &e : m){
        // 3-1. 辺(l, r) について, 距離 d を 取得.
        int l = e.a.a, r = e.a.b, d = e.b;
        
        // 3-2. x[r] - x[l] と d を 比較.
        // printf("x[%d]=%d x[%d]=%d %d\n", r, x[r], l, x[l], d);
        if(x[r] - x[l] != d){
            ok = false;
            break;
        }
    }
    
    // 4. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

#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

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

int x[101010]; // 各頂点への割り当てる整数.

struct edge{

int v; // 次の頂点.

int c; // コスト.

};

vector<edge> G[101010];

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

// ※bfsの動作確認用.

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

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

// @return: 特に無し.

void bfs(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.v]) continue;

if(!connection[e.v] && e.v != s){

connection[e.v] = l;

x[e.v] += x[u] + e.c; // 位置 x を割り当てる.

q.push(e.v);

}

return;

}

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

map<P, int> m;

rep(i, M){

int l, r, d;

scanf("%d %d %d", &l, &r, &d);

l--, r--;

G[l].pb({r, d});

G[r].pb({l, -d});

m[{l, r}] = d;

m[{r, l}] = -d;

}

// 2. 探索を行い, 各連結成分ごとに, 位置 x を割り当てる.

int idx = 0;

rep(i, N) if(!connection[i]) bfs(i, ++idx);

// 3. 割り当てた位置 x をチェック.

bool ok = true;

for(auto &e : m){

// 3-1. 辺(l, r) について, 距離 d を取得.

int l = e.a.a, r = e.a.b, d = e.b;

// 3-2. x[r] - x[l] と d を比較.

// printf("x[%d]=%d x[%d]=%d %d\n", r, x[r], l, x[l], d);

if(x[r] - x[l] != d){

ok = false;

break;

}

// 4. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

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

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

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

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

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

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

[入力例]
10 3
8 7 100
7 9 100
9 8 100

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

[入力例]
100 0

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

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

[出力例]
Yes

[入力例]

3 3

1 2 1

2 3 1

1 3 2

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 3

1 2 1

2 3 1

1 3 5

[出力例]

※AtCoderテストケースより

[入力例]

4 3

2 1 1

2 3 5

3 4 2

[出力例]

Yes

※AtCoderテストケースより

[入力例]

10 3

8 7 100

7 9 100

9 8 100

[出力例]

※AtCoderテストケースより

[入力例]

100 0

[出力例]

Yes

※AtCoderテストケースより

[入力例]

7 10

1 2 5

1 3 7

1 4 11

3 2 -2

3 4 4

4 2 -6

4 3 -4

5 6 2

5 7 12

7 6 -10

[出力例]

Yes

■参照サイト
AtCoder Regular Contest 090

2020年10月25日

■感想.
1. A問題は, A, B が 0 のパターンを, 除外する必要があることを見落としていたので, AC版到達までに苦労した.
2. B問題は, 方針が見えなかったので, 解説をベースに, AC版に到達できたので, 良かったと思う.
3. B問題で解説されていたグラフの性質は, 知らなかった内容であるため, 非常に勉強になったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// コメント修正して, 再提出.
// 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

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 数式を満たす (A, B) は？
    // 01_test_11, 01_test_12, 01_test_17 で, WA版.
    // -> A, B が 0 の パターンは, 除外する必要がある.
    // 2-1. 3 の 冪乗.
    // 3 の 38乗 = 1350851717672992089
    vector<LL> pow3, pow5;
    LL n3 = 1LL;
    while(n3 < 1e18) n3 *= 3LL, pow3.pb(n3);
    
    // 2-2. 5 の 冪乗.
    // 5 の 26乗 = 1490116119384765625
    LL n5 = 1LL;
    while(n5 < 1e18) n5 *= 5LL, pow5.pb(n5);
    
    // 3. N と等しくなる場合があるか？
    int A = -1, B = -1;
    rep(i, pow3.size()){
        rep(j, pow5.size()){
            if(pow3[i] + pow5[j] == N){
                A = i + 1;
                B = j + 1;
                break;
            }
        }
    }
    
    // 4. 出力.
    if(A == -1 && B == -1) puts("-1");
    else                   printf("%d %d\n", A, B);
    return 0;
    
}

// コメント修正して, 再提出.

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

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 数式を満たす (A, B) は？

// 01_test_11, 01_test_12, 01_test_17 で, WA版.

// -> A, B が 0 のパターンは, 除外する必要がある.

// 2-1. 3 の冪乗.

// 3 の 38乗 = 1350851717672992089

vector<LL> pow3, pow5;

LL n3 = 1LL;

while(n3 < 1e18) n3 *= 3LL, pow3.pb(n3);

// 2-2. 5 の冪乗.

// 5 の 26乗 = 1490116119384765625

LL n5 = 1LL;

while(n5 < 1e18) n5 *= 5LL, pow5.pb(n5);

// 3. N と等しくなる場合があるか？

int A = -1, B = -1;

rep(i, pow3.size()){

rep(j, pow5.size()){

if(pow3[i] + pow5[j] == N){

A = i + 1;

B = j + 1;

break;

}

// 4. 出力.

if(A == -1 && B == -1) puts("-1");

else printf("%d %d\n", A, B);

return 0;

}

[入力例]
106

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

[入力例]
1024

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

[入力例]
10460353208

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

[入力例]
63177032

[出力例]
15 11

[入力例]
1610228062568

[出力例]
25 17

[入力例]
748307129767950488

[出力例]
37 25

[入力例]

106

[出力例]

4 2

※AtCoderのテストケースより

[入力例]

1024

[出力例]

-1

※AtCoderのテストケースより

[入力例]

10460353208

[出力例]

21 1

※AtCoderのテストケースより

[入力例]

63177032

[出力例]

15 11

[入力例]

1610228062568

[出力例]

25 17

[入力例]

748307129767950488

[出力例]

37 25

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

// 解き直し.
// https://atcoder.jp/contests/arc106/editorial/247
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
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
#define a first
#define b second
LL a[202020], b[202020];
int connection[202020];    // 連結成分番号を保存.
LL ca[202020], cb[202020]; // 連結成分ごとの a, b の 総和.

// グラフを幅優先探索する.
// 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])            continue;
            if(!connection[e] && e != s) connection[e] = l, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, N) scanf("%lld", &b[i]);
    vvi G(N);
    rep(i, M){
        int c, d;
        scanf("%d %d", &c, &d);
        c--, d--;
        G[c].pb(d);
        G[d].pb(c);
    }
    
    // 2. 探索を行い, 連結成分に分割.
    int idx = 0;
    rep(i, N) if(!connection[i]) bfs(G, i, ++idx);
    
    // 3. 各連結成分ごとに, a, b の 総和を計算.
    rep(i, N){
        ca[connection[i]] += a[i];
        cb[connection[i]] += b[i];
    }
    
    // 4. 各連結成分ごとに, a, b の 総和が等しいかチェック.
    bool ok = true;
    rep(i, N){
        if(ca[i] != cb[i]){
            ok = false;
            break;
        }
    }
    
    // 5. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc106/editorial/247

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

#define a first

#define b second

LL a[202020], b[202020];

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

LL ca[202020], cb[202020]; // 連結成分ごとの a, b の総和.

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

// 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]) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

rep(i, N) scanf("%lld", &a[i]);

rep(i, N) scanf("%lld", &b[i]);

vvi G(N);

rep(i, M){

int c, d;

scanf("%d %d", &c, &d);

c--, d--;

G[c].pb(d);

G[d].pb(c);

}

// 2. 探索を行い, 連結成分に分割.

int idx = 0;

rep(i, N) if(!connection[i]) bfs(G, i, ++idx);

// 3. 各連結成分ごとに, a, b の総和を計算.

rep(i, N){

ca[connection[i]] += a[i];

cb[connection[i]] += b[i];

}

// 4. 各連結成分ごとに, a, b の総和が等しいかチェック.

bool ok = true;

rep(i, N){

if(ca[i] != cb[i]){

ok = false;

break;

}

// 5. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

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

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

[入力例]
1 0
5
5

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

[入力例]
2 1
1 1
2 1
1 2

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

[入力例]
17 9
-905371741 -999219903 969314057 -989982132 -87720225 -175700172 -993990465 929461728 895449935 -999016241 782467448 -906404298 578539175 9684413 -619191091 -952046546 125053320
-440503430 -997661446 -912471383 -995879434 932992245 -928388880 -616761933 929461728 210953513 -994677396 648190629 -530944122 578539175 9684413 595786809 -952046546 125053320
2 10
6 12
9 11
11 5
7 6
3 15
3 1
1 9
10 4

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

[入力例]

3 2

1 2 3

2 2 2

1 2

2 3

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 0

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

2 1

1 1

2 1

1 2

[出力例]

※AtCoderのテストケースより

[入力例]

17 9

-905371741 -999219903 969314057 -989982132 -87720225 -175700172 -993990465 929461728 895449935 -999016241 782467448 -906404298 578539175 9684413 -619191091 -952046546 125053320

-440503430 -997661446 -912471383 -995879434 932992245 -928388880 -616761933 929461728 210953513 -994677396 648190629 -530944122 578539175 9684413 595786809 -952046546 125053320

2 10

6 12

9 11

11 5

7 6

3 15

3 1

1 9

10 4

[出力例]

Yes

※AtCoderのテストケースより

■参照サイト
AtCoder Regular Contest 106

2020年10月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 005 の問題A (大好き高橋君) ～問題B (P-CASカードと高橋君) を解いてみた.

■感想.
1. 実装に苦労したものの, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#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--)
const string x[] = { "TAKAHASHIKUN", "Takahashikun", "takahashikun" };

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 高橋君を表す単語が現れる回数は？
    int ans = 0;
    rep(i, N){
        char c[111];
        scanf("%s", c);
        string w(c);
        // 最後の単語で出現するピリオドを除去.
        if(i == N - 1) w.pop_back();
        if(w.size() != 12) continue;
        rep(k, 3) if(x[k] == w) ans++;
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

#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--)

const string x[] = { "TAKAHASHIKUN", "Takahashikun", "takahashikun" };

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 高橋君を表す単語が現れる回数は？

int ans = 0;

rep(i, N){

char c[111];

scanf("%s", c);

string w(c);

// 最後の単語で出現するピリオドを除去.

if(i == N - 1) w.pop_back();

if(w.size() != 12) continue;

rep(k, 3) if(x[k] == w) ans++;

}

// 3. 出力.

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

return 0;

}

[入力例]
5
Takahashikun is not an eel.

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

[入力例]
5
TAKAHASHIKUN loves TAKAHASHIKUN and takahashikun.

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

[入力例]
6
He is not takahasikun but Takahashikun.

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

[入力例]
1
takahashikunTAKAHASHIKUNtakahashikun.

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

[入力例]
18
You should give Kabayaki to Takahashikun on July twenty seventh if you suspect that he is an eel.

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

[入力例]

Takahashikun is not an eel.

[出力例]

※AtCoderのテストケースより

[入力例]

TAKAHASHIKUN loves TAKAHASHIKUN and takahashikun.

[出力例]

※AtCoderのテストケースより

[入力例]

He is not takahasikun but Takahashikun.

[出力例]

※AtCoderのテストケースより

[入力例]

takahashikunTAKAHASHIKUNtakahashikun.

[出力例]

※AtCoderのテストケースより

[入力例]

You should give Kabayaki to Takahashikun on July twenty seventh if you suspect that he is an eel.

[出力例]

※AtCoderのテストケースより

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#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
char board[33][33];
const int C0 =  9;
const int C1 = 18;
const int C2 = 34;

int main(){
    
    // 1. 入力情報.
    int x, y;
    char w[22];
    scanf("%d %d %s", &y, &x, w);
    x--, y--;
    x += C0, y += C0;
    string W(w);
    memset(board, '#', sizeof(board));
    rep(i, C0){
        char c[22];
        scanf("%s", c);
        rep(j, C0) board[i + C0][j + C0] = c[j];
    }
    
    // 2. 基準とする乱数表から八方向に対して, 転記.
    // 変換ルール.
    // i = 18 - i  | i = 18 - i | i = 18 - i
    // j = 18 - j  | j = j      | j = 34 - j
    //             |            |
    // ------------|------------|------------
    // i = i       |            | i = i
    // j = 18 - j  |    基準    | j = 34 - j
    //             |            |
    // ------------|------------|------------
    // i = 34 - i  | i = 34 - i | i = 34 - i
    // j = 18 - j  | j = j      | j = 34 - j
    //             |            |
    rep(i, C0){
        rep(j, C0){
            // 2-0. 基準となる乱数表の座標.
            int bi = i + C0;
            int bj = j + C0;
            
            // 2-1. 左上.
            board[C1 - bi][C1 - bj] = board[bi][bj];
            
            // 2-2. 上.
            board[C1 - bi][bj]      = board[bi][bj];
            
            // 2-3. 右上.
            board[C1 - bi][C2 - bj] = board[bi][bj];
            
            // 2-4. 右.
            board[bi][C2 - bj]      = board[bi][bj];
            
            // 2-5. 右下.
            board[C2 - bi][C2 - bj] = board[bi][bj];
            
            // 2-6. 下.
            board[C2 - bi][bj]      = board[bi][bj];
            
            // 2-7. 左下.
            board[C2 - bi][C1 - bj] = board[bi][bj];
            
            // 2-8. 左.
            board[bi][C1 - bj]      = board[bi][bj];
        }
    }
    // rep(i, 33){
    //     rep(j, 33) printf("%c", board[i][j]);
    //     puts("");
    // }
    
    // 3. 数字 を 4文字取り出す.
    string ans = "";
    rep(i, 4){
        // 3-1. 左上.
        if(W == "LU") ans.pb(board[x - i][y - i]);
        
        // 3-2. 上.
        if(W == "U") ans.pb(board[x - i][y]);
        
        // 3-3. 右上.
        if(W == "RU") ans.pb(board[x - i][y + i]);
        
        // 3-4. 右.
        if(W == "R") ans.pb(board[x][y + i]);
        
        // 3-5. 右下.
        if(W == "RD") ans.pb(board[x + i][y + i]);
        
        // 3-6. 下.
        if(W == "D") ans.pb(board[x + i][y]);
        
        // 3-7. 左下.
        if(W == "LD") ans.pb(board[x + i][y - i]);
        
        // 3-8. 左.
        if(W == "L") ans.pb(board[x][y - i]);
    }
    
    // 4. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

#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

char board[33][33];

const int C0 = 9;

const int C1 = 18;

const int C2 = 34;

int main(){

// 1. 入力情報.

int x, y;

char w[22];

scanf("%d %d %s", &y, &x, w);

x--, y--;

x += C0, y += C0;

string W(w);

memset(board, '#', sizeof(board));

rep(i, C0){

char c[22];

scanf("%s", c);

rep(j, C0) board[i + C0][j + C0] = c[j];

}

// 2. 基準とする乱数表から八方向に対して, 転記.

// 変換ルール.

// i = 18 - i | i = 18 - i | i = 18 - i

// j = 18 - j | j = j | j = 34 - j

// | |

// ------------|------------|------------

// i = i | | i = i

// j = 18 - j | 基準 | j = 34 - j

// | |

// ------------|------------|------------

// i = 34 - i | i = 34 - i | i = 34 - i

// j = 18 - j | j = j | j = 34 - j

// | |

rep(i, C0){

rep(j, C0){

// 2-0. 基準となる乱数表の座標.

int bi = i + C0;

int bj = j + C0;

// 2-1. 左上.

board[C1 - bi][C1 - bj] = board[bi][bj];

// 2-2. 上.

board[C1 - bi][bj] = board[bi][bj];

// 2-3. 右上.

board[C1 - bi][C2 - bj] = board[bi][bj];

// 2-4. 右.

board[bi][C2 - bj] = board[bi][bj];

// 2-5. 右下.

board[C2 - bi][C2 - bj] = board[bi][bj];

// 2-6. 下.

board[C2 - bi][bj] = board[bi][bj];

// 2-7. 左下.

board[C2 - bi][C1 - bj] = board[bi][bj];

// 2-8. 左.

board[bi][C1 - bj] = board[bi][bj];

}

// rep(i, 33){

// rep(j, 33) printf("%c", board[i][j]);

// puts("");

// }

// 3. 数字を 4文字取り出す.

string ans = "";

rep(i, 4){

// 3-1. 左上.

if(W == "LU") ans.pb(board[x - i][y - i]);

// 3-2. 上.

if(W == "U") ans.pb(board[x - i][y]);

// 3-3. 右上.

if(W == "RU") ans.pb(board[x - i][y + i]);

// 3-4. 右.

if(W == "R") ans.pb(board[x][y + i]);

// 3-5. 右下.

if(W == "RD") ans.pb(board[x + i][y + i]);

// 3-6. 下.

if(W == "D") ans.pb(board[x + i][y]);

// 3-7. 左下.

if(W == "LD") ans.pb(board[x + i][y - i]);

// 3-8. 左.

if(W == "L") ans.pb(board[x][y - i]);

}

// 4. 出力.

printf("%s\n", ans.c_str());

return 0;

}

[入力例]
3 5 R
790319030
091076399
143245946
590051196
398226115
442567154
112705290
716433235
221041645

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

[入力例]
8 9 LU
206932999
471100777
973172688
108989704
246954192
399039569
944715218
003664867
219006823

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

[入力例]
5 7 D
271573743
915078603
102553534
996473623
595593497
573572507
340348994
253066837
643845096

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

[入力例]
2 2 LU
729142134
509607882
640003027
215270061
214055727
745319402
777708131
018697986
277156993

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

[入力例]
8 7 RD
985877833
469488482
218647263
856777094
012249580
845463670
919136580
011130808
874387671

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

[入力例]

3 5 R

790319030

091076399

143245946

590051196

398226115

442567154

112705290

716433235

221041645

[出力例]

8226

※AtCoderのテストケースより

[入力例]

8 9 LU

206932999

471100777

973172688

108989704

246954192

399039569

944715218

003664867

219006823

[出力例]

2853

※AtCoderのテストケースより

[入力例]

5 7 D

271573743

915078603

102553534

996473623

595593497

573572507

340348994

253066837

643845096

[出力例]

4646

※AtCoderのテストケースより

[入力例]

2 2 LU

729142134

509607882

640003027

215270061

214055727

745319402

777708131

018697986

277156993

[出力例]

0700

※AtCoderのテストケースより

[入力例]

8 7 RD

985877833

469488482

218647263

856777094

012249580

845463670

919136580

011130808

874387671

[出力例]

8878

※AtCoderのテストケースより

■参照サイト
AtCoder Regular Contest 005

2020年10月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 050 の問題A (大文字と小文字) ～問題B (花束) を解いてみた.

■感想.
1. 問題B は, 方針が見えなかったので, 解説を参考に, ようやくAC版となった.
2. 二分探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報.
    char C[11], c[11];
    scanf("%s %s", C, c);
    
    // 2. 出力.
    printf("%s\n", (c[0] - C[0] == 32) ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

char C[11], c[11];

scanf("%s %s", C, c);

// 2. 出力.

printf("%s\n", (c[0] - C[0] == 32) ? "Yes" : "No");

return 0;

}

[入力例]
A a

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

[入力例]
B c

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

[入力例]
Z z

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

[入力例]

A a

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

B c

[出力例]

※AtCoderのテストケースより

[入力例]

Z z

[出力例]

Yes

※AtCoderのテストケースより

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

// 解き直し.
// https://img.atcoder.jp/data/arc/050/review.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--)

int main(){
    
    // 1. 入力情報.
    LL R, B, x, y;
    scanf("%lld %lld %lld %lld", &R, &B, &x, &y);
    
    // 2. 花束の個数の最大値は？
    LL l = 0, h = min(R, B) + 1, m;
    auto f = [](LL m, LL R, LL B, LL x, LL y) -> bool {
        LL r = (R - m) / (x - 1);
        LL b = (B - m) / (y - 1);
        return (r + b >= m);
    };
    // 二分探索で確認してみる.
    while(l + 1 < h){
        m = (h + l) >> 1;
        if(f(m, R, B, x, y)) l = m;
        else                 h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 3. 出力.
    printf("%lld\n", l);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/data/arc/050/review.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--)

int main(){

// 1. 入力情報.

LL R, B, x, y;

scanf("%lld %lld %lld %lld", &R, &B, &x, &y);

// 2. 花束の個数の最大値は？

LL l = 0, h = min(R, B) + 1, m;

auto f = [](LL m, LL R, LL B, LL x, LL y) -> bool {

LL r = (R - m) / (x - 1);

LL b = (B - m) / (y - 1);

return (r + b >= m);

};

// 二分探索で確認してみる.

while(l + 1 < h){

m = (h + l) >> 1;

if(f(m, R, B, x, y)) l = m;

else h = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

// 3. 出力.

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

return 0;

}

[入力例]
5 5
3 4

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

[入力例]
10 20
2 2

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

[入力例]
1 1
2 2

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

[入力例]
10000000000 10000000000
4 3

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

[入力例]
31415926535897932 38462643383279502 
88419 71693

[出力例]
891787311937

[入力例]
1414213562 37309504880
16887 24209

[出力例]
1624792

[入力例]

5 5

3 4

[出力例]

※AtCoderのテストケースより

[入力例]

10 20

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

1 1

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

10000000000 10000000000

4 3

[出力例]

4545454545

※AtCoderのテストケースより

[入力例]

31415926535897932 38462643383279502

88419 71693

[出力例]

891787311937

[入力例]

1414213562 37309504880

16887 24209

[出力例]

1624792

■参照サイト
AtCoder Regular Contest 050

2020年10月17日

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

C++の練習を兼ねて, AtCoder Regular Contest 044 の問題A (素数判定) ～問題B (最短路問題) を解いてみた.

■感想.
1. 問題B は, 数え上げ部分で, 方針が見えなかったので, 解説を参考に, ようやくAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#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

// 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<int, int> div(int X){
    
    // 1. X を 2で割り切れなくなるまで割っていく.
    map<int, int> ret;
    while(!(X % 2)) ret[2]++, X >>= 1;
    
    // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    repex(i, 3, sqrt(X) + 1, 2){
        while(!(X % i)){
            ret[i]++;
            X /= i;
        }
    }
    
    // 3. X が 2 より 大きな素数であれば, 追加.
    if(X > 2) ret[X]++;
    
    // 4. 出力.
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 素因数分解.
    map<int, int> m = div(N);
    
    // 3. 素数判定.
    // 3-1. 1 の 場合.
    if(N == 1){
        puts("Not Prime");
        return 0;
    }
    
    // 3-2. 素数の場合.
    bool ok = false;
    // ex.
    // 125 は, Not Prime の はず.
    // -> test_03.txt, test_06.txt, test_07.txt の WA版 になった理由.
    // if(m.size() == 1) ok = true;
    if(m.size() == 1){
        int c = m.begin()->b;
        if(c == 1){
            puts("Prime");
            return 0;
        }
    }
    
    // 3-3. 合成数の場合.
    string n = to_string(N);
    int d = n.size();
    int f = 2;
    
    // 1 の 位 が 偶数でも, 5 でない.
    int d1 = n[d - 1] - '0';
    if(d1 % 2 != 0 && d1 != 5) f--;
    
    // 各桁の和.
    int d2 = 0;
    rep(i, d) d2 += n[i] - '0', d2 %= 3;
    if(d2 % 3 != 0) f--;
    
    // 判定.
    if(f == 0) ok = true;
    
    // 4. 出力.
    printf("%s\n", ok ? "Prime" : "Not Prime");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

#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

// 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<int, int> div(int X){

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

map<int, int> ret;

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

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

repex(i, 3, sqrt(X) + 1, 2){

while(!(X % i)){

ret[i]++;

X /= i;

}

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

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

// 4. 出力.

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 素因数分解.

map<int, int> m = div(N);

// 3. 素数判定.

// 3-1. 1 の場合.

if(N == 1){

puts("Not Prime");

return 0;

}

// 3-2. 素数の場合.

bool ok = false;

// ex.

// 125 は, Not Prime のはず.

// -> test_03.txt, test_06.txt, test_07.txt の WA版になった理由.

// if(m.size() == 1) ok = true;

if(m.size() == 1){

int c = m.begin()->b;

if(c == 1){

puts("Prime");

return 0;

}

// 3-3. 合成数の場合.

string n = to_string(N);

int d = n.size();

int f = 2;

// 1 の位が偶数でも, 5 でない.

int d1 = n[d - 1] - '0';

if(d1 % 2 != 0 && d1 != 5) f--;

// 各桁の和.

int d2 = 0;

rep(i, d) d2 += n[i] - '0', d2 %= 3;

if(d2 % 3 != 0) f--;

// 判定.

if(f == 0) ok = true;

// 4. 出力.

printf("%s\n", ok ? "Prime" : "Not Prime");

return 0;

}

[入力例]
42

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

[入力例]
49

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

[入力例]
3

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

[入力例]
1

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

[入力例]
125

[出力例]
Not Prime

[入力例]
12345678

[出力例]
Not Prime

[入力例]
1234567

[出力例]
Prime

[入力例]
123456789

[出力例]
Not Prime

[入力例]

[出力例]

Not Prime

※AtCoderのテストケースより

[入力例]

[出力例]

Prime

※AtCoderのテストケースより

[入力例]

[出力例]

Prime

※AtCoderのテストケースより

[入力例]

[出力例]

Not Prime

※AtCoderのテストケースより

[入力例]

125

[出力例]

Not Prime

[入力例]

12345678

[出力例]

Not Prime

[入力例]

1234567

[出力例]

Prime

[入力例]

123456789

[出力例]

Not Prime

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc044
// 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--)
const LL MOD = 1e9 + 7;
const int LIMIT = 101010;
int a[LIMIT], d[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 % MOD;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a[i]);
        d[a[i]]++;
    }
    
    // 2. グラフの個数は？
    // 2-1. 頂点 1 の 距離が, 0 より 大きい場合, または, 距離 0 が 複数個ある場合.
    if(a[0] || d[0] > 1){
        puts("0");
        return 0;
    }
    
    // 3-2. それ以外の場合.
    LL ans = 1;
    int count = 1, bef = 1;
    repx(i, 1, 101010){
        // 距離 i の 頂点数.
        int cur = d[i];
        
        // 頂点数 が N 未満で, 距離 i の 頂点がない.
        if(count < N && cur == 0){
            puts("0");
            break;
        }
        
        // グラフの個数をカウント.
        // 距離 i - 1 と 距離 i の 頂点同士 の 結び付き方.
        LL t = mPow(2LL, (LL)bef);
        t += MOD - 1;
        t %= MOD;
        ans *= mPow(t, (LL)cur);
        ans %= MOD;
        
        // 距離 i の 頂点同士 の 結び付き方.
        ans *= mPow(2LL, (LL)(cur - 1) * (LL)cur / 2LL);
        ans %= MOD;
        
        // 確認した頂点数 を 保存.
        count += cur;
        
        // 前回分更新.
        bef = cur;
        
        // 頂点数 が N に 到達したら, 終了.
        if(count == N){
            printf("%lld\n", ans);
            break;
        }
    }
    return 0;
    
}

// 解き直し.

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

// 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--)

const LL MOD = 1e9 + 7;

const int LIMIT = 101010;

int a[LIMIT], d[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 % MOD;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

scanf("%d", &a[i]);

d[a[i]]++;

}

// 2. グラフの個数は？

// 2-1. 頂点 1 の距離が, 0 より大きい場合, または, 距離 0 が複数個ある場合.

if(a[0] || d[0] > 1){

puts("0");

return 0;

}

// 3-2. それ以外の場合.

LL ans = 1;

int count = 1, bef = 1;

repx(i, 1, 101010){

// 距離 i の頂点数.

int cur = d[i];

// 頂点数が N 未満で, 距離 i の頂点がない.

if(count < N && cur == 0){

puts("0");

break;

}

// グラフの個数をカウント.

// 距離 i - 1 と距離 i の頂点同士の結び付き方.

LL t = mPow(2LL, (LL)bef);

t += MOD - 1;

t %= MOD;

ans *= mPow(t, (LL)cur);

ans %= MOD;

// 距離 i の頂点同士の結び付き方.

ans *= mPow(2LL, (LL)(cur - 1) * (LL)cur / 2LL);

ans %= MOD;

// 確認した頂点数を保存.

count += cur;

// 前回分更新.

bef = cur;

// 頂点数が N に到達したら, 終了.

if(count == N){

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

break;

}

return 0;

}

[入力例]
4
0 1 1 2

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

[入力例]
4
0 1 2 0

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

[入力例]
3
1 1 2

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

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

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

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

[出力例]
930127887

[入力例]

0 1 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

0 1 2 0

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

0 1 1 2 2 4 3 2 4 5 3 3 2 1 5 4 2

[出力例]

855391686

※AtCoderのテストケースより

[入力例]

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

[出力例]

930127887

■参照サイト
AtCoder Regular Contest 044

2020年10月13日2020年10月13日

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

C++の練習を兼ねて, AtCoder Regular Contest 078 の問題E (Awkward Response) を解いてみた.

■感想.
1. 方針が見えなかったので, 解説を参考に, ようやくAC版となった.
2. 標準出力で投げる整数は, 1 ～ 1e18 の範囲に限定されることについて, 問題文を読み落としていたので, バグに気付くまでに, 非常に苦労した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc078/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

int main(){
    
    // 1. 10 の べき乗 を 保存.
    vector<LL> p10;
    p10.pb(1);
    repx(i, 1, 19) p10.pb(10 * p10[i - 1]);
    // rep(i, 19) printf("%lld\n", p10[i]);
    
    // 2. N の 桁数L を 計算.
    // 2-1. N が 10 の (L - 1)乗 でない場合.
    int L1 = 0;
    rep(k, 19){
        printf("? %lld\n", p10[k]);
        fflush(stdout);
        char ans[11];
        scanf("%s", ans);
        if(ans[0] == 'Y') L1 = k + 1;
        else              break;
    }
    
    // 2-2. N が 10 の (L - 1)乗 である場合.
    int L2 = 0;
    if(L1 == 19){
        // 21.txt - 30.txt で, WA判定となった原因.
        // -> 標準出力で投げる整数は, 1 ～ 1e18 の 範囲に限定されることに注意.
        // -> 2 * p10[k] で, k = 18 の 場合に, 条件を満たさくなっていた.
        // repr(k, 18, 0){
        repr(k, 17, 0){
            printf("? %lld\n", 2 * p10[k]);
            fflush(stdout);
            char ans[11];
            scanf("%s", ans);
            if(ans[0] == 'Y') L2 = k + 1;
            else              break;
        }
    }
    
    // 3. N が 10 の (L - 1)乗 である場合.
    if(L2){
        printf("! %lld\n", p10[L2 - 1]);
        fflush(stdout);
        return 0;
    }
    
    // 4. N が 10 の (L - 1)乗 でない場合.
    // 二分探索で確認してみる.
    LL l = p10[L1 - 1], h = p10[L1], m;
    while(l + 1 < h){
        m = (h + l) >> 1;
        printf("? %lld\n", 10 * m);
        fflush(stdout);
        char ans[11];
        scanf("%s", ans);
        if(ans[0] == 'Y') h = m;
        else              l = m;
    }
    printf("! %lld\n", h);
    fflush(stdout);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/arc078/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

int main(){

// 1. 10 のべき乗を保存.

vector<LL> p10;

p10.pb(1);

repx(i, 1, 19) p10.pb(10 * p10[i - 1]);

// rep(i, 19) printf("%lld\n", p10[i]);

// 2. N の桁数L を計算.

// 2-1. N が 10 の (L - 1)乗でない場合.

int L1 = 0;

rep(k, 19){

printf("? %lld\n", p10[k]);

fflush(stdout);

char ans[11];

scanf("%s", ans);

if(ans[0] == 'Y') L1 = k + 1;

else break;

}

// 2-2. N が 10 の (L - 1)乗である場合.

int L2 = 0;

if(L1 == 19){

// 21.txt - 30.txt で, WA判定となった原因.

// -> 標準出力で投げる整数は, 1 ～ 1e18 の範囲に限定されることに注意.

// -> 2 * p10[k] で, k = 18 の場合に, 条件を満たさくなっていた.

// repr(k, 18, 0){

repr(k, 17, 0){

printf("? %lld\n", 2 * p10[k]);

fflush(stdout);

char ans[11];

scanf("%s", ans);

if(ans[0] == 'Y') L2 = k + 1;

else break;

}

// 3. N が 10 の (L - 1)乗である場合.

if(L2){

printf("! %lld\n", p10[L2 - 1]);

fflush(stdout);

return 0;

}

// 4. N が 10 の (L - 1)乗でない場合.

// 二分探索で確認してみる.

LL l = p10[L1 - 1], h = p10[L1], m;

while(l + 1 < h){

m = (h + l) >> 1;

printf("? %lld\n", 10 * m);

fflush(stdout);

char ans[11];

scanf("%s", ans);

if(ans[0] == 'Y') h = m;

else l = m;

}

printf("! %lld\n", h);

fflush(stdout);

return 0;

}

※インタラクティブな問題のため, 入出力は, 未記載としている.

1	※インタラクティブな問題のため, 入出力は, 未記載としている.

■参照サイト
AtCoder Regular Contest 078

個人用メモ帳

投稿

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

C++の練習を兼ねて, AtCoder Regular Contest 088 の問題E (Papple Sort) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 083 の問題E (Bichrome Tree) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題D (Powers) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題C (Solutions) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 090 の問題D (People on a Line) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題A (106) ～問題B (Values) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 005 の問題A (大好き高橋君) ～問題B (P-CASカードと高橋君) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 050 の問題A (大文字と小文字) ～問題B (花束) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 044 の問題A (素数判定) ～問題B (最短路問題) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 078 の問題E (Awkward Response) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 088 の 問題E (Papple Sort) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 083 の 問題E (Bichrome Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 106 の 問題D (Powers) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 106 の 問題C (Solutions) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 090 の 問題D (People on a Line) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 106 の 問題A (106) ～ 問題B (Values) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 005 の 問題A (大好き高橋君) ～ 問題B (P-CASカードと高橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 050 の 問題A (大文字と小文字) ～ 問題B (花束) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 044 の 問題A (素数判定) ～ 問題B (最短路問題) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 078 の 問題E (Awkward Response) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 088 の問題E (Papple Sort) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 083 の問題E (Bichrome Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題D (Powers) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題C (Solutions) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 090 の問題D (People on a Line) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題A (106) ～問題B (Values) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 005 の問題A (大好き高橋君) ～問題B (P-CASカードと高橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 050 の問題A (大文字と小文字) ～問題B (花束) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 044 の問題A (素数判定) ～問題B (最短路問題) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 078 の問題E (Awkward Response) を解いてみた.