C++ | 個人用メモ帳

2019年7月13日2019年7月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 126 の問題F (F – XOR Matching) を解いてみた.

■感想.
1. 紙に書いて試行錯誤していたら, 規則性を抽出出来たので, 何とか正答に辿り着けた.
2. 相変わらず苦手な DP の訓練となったと思う.
3. とりあえず, 解説見る前に解けたので, 及第点は, 取れたように思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL dp[262262]; // 2 の 18乗 = 262144 より大きければ良いはず.

int main(){

    // 1. 入力情報取得.
    int M;
    LL K;
    scanf("%d %lld", &M, &K);
    
    // 2. 数列作成(K >= 2 の M乗).
    int l = 1 << M; // 数列の長さ.
    // sample_02 で, WA となったので, if文 を 修正.
    // if(K >= l){
    if(K >= l || (M == 1 && K == 1)){
        printf("%d\n", -1);
        return 0;
    }
    
    // 3. 数列作成(K < 2 の M乗).
    int base = l - 1, counter = 0;
    // 3-1. K == 0
    // ex.
    // M = 2, K = 0
    // 0 0 -> 1 0 0 1 -> 2 1 0 0 1 2 -> 3 2 1 0 0 1 2 3 とすれば良さそう.
    if(K == 0){
        dp[base] = K, dp[base + 1] = K;
        for(int i = 0; i < l; i++) if(i != K) counter++, dp[base - counter] = dp[base + 1 + counter] = i;
    }
    
    // 3-2. K > 0
    // M = 2, K = 1
    // 1 -> 0 1 0 -> 2 0 1 0 2 -> 3 2 0 1 0 2 3 -> 3 2 0 1 0 2 3 1 とすれば良さそう.
    // 
    // M = 2, K = 2
    // 2 -> 0 2 0 -> 1 0 2 0 1 -> 3 1 0 2 0 1 3 -> 3 1 0 2 0 1 3 2 とすれば良さそう.
    // 
    // M = 2, K = 3
    // 3 -> 0 3 0 -> 1 0 3 0 1 -> 2 1 0 3 0 1 2 -> 2 1 0 3 0 1 2 3 とすれば良さそう.
    if(K > 0){
        dp[base] = K, dp[2 * base + 1] = K;
        for(int i = 0; i < l; i++) if(i != K) counter++, dp[base - counter] = dp[base + counter] = i;
    }
    
    // 4. 後処理.
    for(int i = 0; i < 2 * l; i++) printf("%lld ", dp[i]);
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

LL dp[262262]; // 2 の 18乗 = 262144 より大きければ良いはず.

int main(){

// 1. 入力情報取得.

int M;

LL K;

scanf("%d %lld", &M, &K);

// 2. 数列作成(K >= 2 の M乗).

int l = 1 << M; // 数列の長さ.

// sample_02 で, WA となったので, if文を修正.

// if(K >= l){

if(K >= l || (M == 1 && K == 1)){

printf("%d\n", -1);

return 0;

}

// 3. 数列作成(K < 2 の M乗).

int base = l - 1, counter = 0;

// 3-1. K == 0

// ex.

// M = 2, K = 0

// 0 0 -> 1 0 0 1 -> 2 1 0 0 1 2 -> 3 2 1 0 0 1 2 3 とすれば良さそう.

if(K == 0){

dp[base] = K, dp[base + 1] = K;

for(int i = 0; i < l; i++) if(i != K) counter++, dp[base - counter] = dp[base + 1 + counter] = i;

}

// 3-2. K > 0

// M = 2, K = 1

// 1 -> 0 1 0 -> 2 0 1 0 2 -> 3 2 0 1 0 2 3 -> 3 2 0 1 0 2 3 1 とすれば良さそう.

// M = 2, K = 2

// 2 -> 0 2 0 -> 1 0 2 0 1 -> 3 1 0 2 0 1 3 -> 3 1 0 2 0 1 3 2 とすれば良さそう.

// M = 2, K = 3

// 3 -> 0 3 0 -> 1 0 3 0 1 -> 2 1 0 3 0 1 2 -> 2 1 0 3 0 1 2 3 とすれば良さそう.

if(K > 0){

dp[base] = K, dp[2 * base + 1] = K;

for(int i = 0; i < l; i++) if(i != K) counter++, dp[base - counter] = dp[base + counter] = i;

}

// 4. 後処理.

for(int i = 0; i < 2 * l; i++) printf("%lld ", dp[i]);

return 0;

}

[入力例]
1 0

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

[入力例]
1 1

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

[入力例]
5 58

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

[入力例]
3 7

[出力例]
6 5 4 3 2 1 0 7 0 1 2 3 4 5 6 7 

[入力例]
3 8

[出力例]
-1

[入力例]
5 1

[出力例]
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 1 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 1 

[入力例]
7 111

[出力例]
127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 111 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 111

[入力例]

1 0

[出力例]

1 0 0 1

※AtCoderテストケースより

[入力例]

1 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 58

[出力例]

-1

※AtCoderテストケースより

[入力例]

3 7

[出力例]

6 5 4 3 2 1 0 7 0 1 2 3 4 5 6 7

[入力例]

3 8

[出力例]

-1

[入力例]

5 1

[出力例]

31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 1 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 1

[入力例]

7 111

[出力例]

127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 111 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 111

■参照サイト
AtCoder Beginner Contest 126

2019年7月12日2019年7月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 126 の問題E (E – 1 or 2) を解いてみた.

■感想.
1. グラフの幅優先探索について, 復習できたので良かったと思う.
2. とりあえず, 解説見ずに解けたので良かったと思う.
3. AtCoder Beginner Contest 131 の問題F (F – Must Be Rectangular!) で, 深さ優先探索を用いて, グラフの連結成分をカウントしていったが, 本問も, グラフの連結成分をカウントする部分が, 似ているように見えた.

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

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

#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 1e5 + 1;
// const int MAX = 10;
int card[MAX];          // カードに関する連結成分番号を保存.
int connection[MAX];    // 各連結成分 の カード数 を保存.
vector<int> graph[MAX]; // カードの番号を, グラフの頂点に見立てる.

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param s: グラフの探索開始頂点.
// @param l: 連結成分番号(※1以上).
// @return: 特に無し.
void bfs(int s, int l){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点に, 連結成分番号を指定.
    card[s] = l;
    connection[l]++;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){

        // 4. キューから取り出す.
        int u = q.front();
        q.pop();

        // 5. 取り出した要素を処理.
        for(auto &e : graph[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(card[e] > 0)            continue;
            if(card[e] == 0 && e != s) card[e] = card[u], connection[l]++, q.push(e);
        }
    }
    return;
}

int main() {

    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);

    // 2. グラフ作成.
    for(int i = 0; i < M; i++){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        x--, y--;
        // x -> y
        graph[x].push_back(y);
        // y -> x
        graph[y].push_back(x);
    }
    
    // 3. 連結成分に分解.
    int c = 0;
    for(int i = 0; i < N; i++) if(graph[i].size() > 0 && card[i] == 0) c++, bfs(i, c);
    
    // グラフ連結情報確認.
    // for(int i = 0; i <= N; i++){
    //     printf("card[%d] = %d\n", i, card[i]);
    //     printf("connection[%d] = %d\n", i, connection[i]);
    // }
    
    // 4. 後処理.
    // -> 各連結成分 ごとに, 魔法 を 1回使用する必要があることと, 
    // 連結成分に含まれないカードは, それぞれ魔法を使用する必要があると見る.
    int ans = N;
    for(int i = 1; i < N; i++){
        if(connection[i] > 0) ans -= connection[i], ans++;
        else                  break;
    }
    printf("%d\n", ans);
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 1e5 + 1;

// const int MAX = 10;

int card[MAX]; // カードに関する連結成分番号を保存.

int connection[MAX]; // 各連結成分のカード数を保存.

vector<int> graph[MAX]; // カードの番号を, グラフの頂点に見立てる.

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

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

// ※bfsの動作確認用.

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

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

// @return: 特に無し.

void bfs(int s, int l){

// 1. 空のキュー.

queue<int> q;

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

// ※スタート地点に, 連結成分番号を指定.

card[s] = l;

connection[l]++;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(card[e] > 0) continue;

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

}

return;

}

int main() {

// 1. 入力情報取得.

int N, M;

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

// 2. グラフ作成.

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

int x, y, z;

scanf("%d %d %d", &x, &y, &z);

x--, y--;

// x -> y

graph[x].push_back(y);

// y -> x

graph[y].push_back(x);

}

// 3. 連結成分に分解.

int c = 0;

for(int i = 0; i < N; i++) if(graph[i].size() > 0 && card[i] == 0) c++, bfs(i, c);

// グラフ連結情報確認.

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

// printf("card[%d] = %d\n", i, card[i]);

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

// }

// 4. 後処理.

// -> 各連結成分ごとに, 魔法を 1回使用する必要があることと,

// 連結成分に含まれないカードは, それぞれ魔法を使用する必要があると見る.

int ans = N;

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

if(connection[i] > 0) ans -= connection[i], ans++;

else break;

}

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

return 0;

}

[入力例]
3 1
1 2 1

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

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

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

[入力例]
100000 1
1 100000 100

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

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

[出力例(debug版)]
card[0] = 1
connection[0] = 0
card[1] = 1
connection[1] = 3
card[2] = 1
connection[2] = 3
card[3] = 2
connection[3] = 4
card[4] = 2
connection[4] = 2
card[5] = 2
connection[5] = 2
card[6] = 3
connection[6] = 0
card[7] = 3
connection[7] = 0
card[8] = 3
connection[8] = 0
card[9] = 3
connection[9] = 0
card[10] = 0
connection[10] = 0
card[11] = 4
connection[11] = 0
card[12] = 5
connection[12] = 0
card[13] = 5
connection[13] = 0
card[14] = 4
connection[14] = 0
card[15] = 0
connection[15] = 0
6

[入力例]

3 1

1 2 1

[出力例(debug版)]

card[0] = 1

connection[0] = 0

card[1] = 1

connection[1] = 2

card[2] = 0

connection[2] = 0

card[3] = 0

connection[3] = 0

※AtCoderテストケースより

[入力例]

6 5

1 2 1

2 3 2

1 3 3

4 5 4

5 6 5

[出力例(debug版)]

card[0] = 1

connection[0] = 0

card[1] = 1

connection[1] = 3

card[2] = 1

connection[2] = 3

card[3] = 2

connection[3] = 0

card[4] = 2

connection[4] = 0

card[5] = 2

connection[5] = 0

card[6] = 0

connection[6] = 0

※AtCoderテストケースより

[入力例]

100000 1

1 100000 100

[出力例]

99999

※AtCoderテストケースより

[入力例]

15 9

1 2 1

1 3 2

4 5 1

4 6 4

7 8 2

7 9 4

7 10 12

12 15 1

13 14 3

[出力例(debug版)]

card[0] = 1

connection[0] = 0

card[1] = 1

connection[1] = 3

card[2] = 1

connection[2] = 3

card[3] = 2

connection[3] = 4

card[4] = 2

connection[4] = 2

card[5] = 2

connection[5] = 2

card[6] = 3

connection[6] = 0

card[7] = 3

connection[7] = 0

card[8] = 3

connection[8] = 0

card[9] = 3

connection[9] = 0

card[10] = 0

connection[10] = 0

card[11] = 4

connection[11] = 0

card[12] = 5

connection[12] = 0

card[13] = 5

connection[13] = 0

card[14] = 4

connection[14] = 0

card[15] = 0

connection[15] = 0

■参照サイト
AtCoder Beginner Contest 126

2019年7月10日2019年7月10日

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

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

■感想.
1. グラフの幅優先探索について, 復習できたので良かったと思う.
2. とりあえず, 解説見ずに解けたので良かったと思う.
3. bfs関数の第一引数を, G から &G に変更したところ, 実行時間が, 76[ms] から 59[ms] に改善した.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int MAX = 1e5 + 1;
struct edge{
    int v; // 次の頂点.
    LL  w; // 距離.
};
LL dist[MAX]; // 距離を保存

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @return: 特に無し.
void bfs(vector<vector<edge>> &G, int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    dist[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){

        // 4. キューから取り出す.
        int u = q.front();
        q.pop();

        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            // cout << "u=" << u << " e.v=" << e.v << " e.w=" << e.w << endl;
            if(dist[e.v] > 0)              continue;
            if(dist[e.v] == 0 && e.v != s) dist[e.v] = dist[u] + e.w, q.push(e.v);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    vector<vector<edge>> graph(N);
    for(LL i = 0; i < N - 1; i++){
        int u, v;
        LL w;
        scanf("%d %d %lld", &u, &v, &w);
        edge e1, e2;
        u--, v--;
        // u -> v
        e1.v = v, e1.w = w;
        graph[u].push_back(e1);
        // v -> u
        e2.v = u, e2.w = w;
        graph[v].push_back(e2);
    }
    
    // 2. 頂点を一つ固定して, そこから各頂点への距離を保存.
    bfs(graph, 0);
    // for(int i = 0; i < N; i++) printf("%lld ", dist[i]);
    // printf("\n");
    
    // 3. 出力 ～ 後処理.
    // 頂点 0 からの距離が, 偶数: 白色, 奇数: 黒色.
    for(int i = 0; i < N; i++){
        LL d = dist[i];
        if(d % 2 == 0) printf("%d\n", 0);
        else           printf("%d\n", 1);
    }
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

constexpr int MAX = 1e5 + 1;

struct edge{

int v; // 次の頂点.

LL w; // 距離.

};

LL dist[MAX]; // 距離を保存

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

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

// ※bfsの動作確認用.

// @param G: グラフ.

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

// @return: 特に無し.

void bfs(vector<vector<edge>> &G, int s){

// 1. 空のキュー.

queue<int> q;

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

// ※スタート地点は, 距離ゼロを指定.

dist[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

// cout << "u=" << u << " e.v=" << e.v << " e.w=" << e.w << endl;

if(dist[e.v] > 0) continue;

if(dist[e.v] == 0 && e.v != s) dist[e.v] = dist[u] + e.w, q.push(e.v);

}

return;

}

int main() {

// 1. 入力情報取得.

int N;

scanf("%d", &N);

vector<vector<edge>> graph(N);

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

int u, v;

LL w;

scanf("%d %d %lld", &u, &v, &w);

edge e1, e2;

u--, v--;

// u -> v

e1.v = v, e1.w = w;

graph[u].push_back(e1);

// v -> u

e2.v = u, e2.w = w;

graph[v].push_back(e2);

}

// 2. 頂点を一つ固定して, そこから各頂点への距離を保存.

bfs(graph, 0);

// for(int i = 0; i < N; i++) printf("%lld ", dist[i]);

// printf("\n");

// 3. 出力～後処理.

// 頂点 0 からの距離が, 偶数: 白色, 奇数: 黒色.

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

LL d = dist[i];

if(d % 2 == 0) printf("%d\n", 0);

else printf("%d\n", 1);

}

return 0;

}

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

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

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

[出力例(debug版)]
0 18 8 10 20 
0
0
0
0
0
※AtCoderテストケースより

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

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

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

[出力例(debug版)]
0 2 5 9 9 19 33 17 26 30 42 55 14 11 48 
0
0
1
1
1
1
1
1
0
0
0
1
0
1
0

[入力例]

1 2 2

2 3 1

[出力例(debug版)]

0 2 3

※AtCoderテストケースより

[入力例]

2 5 2

2 3 10

1 3 8

3 4 2

[出力例(debug版)]

0 18 8 10 20

※AtCoderテストケースより

[入力例]

1 2 2

1 3 1

1 4 1

1 5 1

[出力例(debug版)]

0 2 1 1 1

[入力例]

1 2 2

2 3 3

3 4 4

4 13 5

3 14 6

2 5 7

5 8 8

8 9 9

5 6 10

6 10 11

10 11 12

11 12 13

6 7 14

7 15 15

[出力例(debug版)]

0 2 5 9 9 19 33 17 26 30 42 55 14 11 48

■参照サイト
AtCoder Beginner Contest 126

2019年7月9日2019年7月10日

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

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

■感想.
1. とりあえず, 解説見ずに解けたので良かったと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
struct rewrite{
    int b;  // 操作するカード枚数の上限.
    LL  c;  // 書き換え後の整数.
    bool operator < (const rewrite& rhs) const{
        if(c > rhs.c) return true;
        else          return false;
    }
};
vector<rewrite> R;

int main() {
    
    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);
    LL ans = 0, A[N];
    for(int i = 0; i < N; i++) scanf("%lld", A + i), ans += A[i];
    for(int i = 0; i < M; i++){
        rewrite r;
        scanf("%d %lld", &r.b, &r.c);
        R.push_back(r);
    }
    
    // 2. 昇順sort.
    sort(A, A + N);
    
    // 3. 降順sort.
    sort(R.begin(), R.end());
    
    // 4. カードの書き換え作業.
    // なるべく小さいカードA[i]を, なるべく大きい整数 C[j] に, 書き換える.
    int index = 0;
    for(auto &r : R){
        // 4-1. index ～ (index + r.b)番目 までで, 書き換えるか確認.
        int upper = min(N, index + r.b);
        for(int i = index; i < upper; i++){
            // A[i] と比較し, C[j] が 大きければ, 書き換える.
            // C[j] が 小さければ, 書き換えを終了.
            if(A[i] < r.c) ans += r.c - A[i];
            else           break;
        }

        // 4-2. 次の整数 C[j] に書き換えるための準備.
        index += r.b;
        
        // 4-3. index が N以上 ならば, 書き換え出来ないので終了.
        if(index >= N) break;
    }

    // 5. 出力 ～ 後処理.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

struct rewrite{

int b; // 操作するカード枚数の上限.

LL c; // 書き換え後の整数.

bool operator < (const rewrite& rhs) const{

if(c > rhs.c) return true;

else return false;

}

};

vector<rewrite> R;

int main() {

// 1. 入力情報取得.

int N, M;

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

LL ans = 0, A[N];

for(int i = 0; i < N; i++) scanf("%lld", A + i), ans += A[i];

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

rewrite r;

scanf("%d %lld", &r.b, &r.c);

R.push_back(r);

}

// 2. 昇順sort.

sort(A, A + N);

// 3. 降順sort.

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

// 4. カードの書き換え作業.

// なるべく小さいカードA[i]を, なるべく大きい整数 C[j] に, 書き換える.

int index = 0;

for(auto &r : R){

// 4-1. index ～ (index + r.b)番目までで, 書き換えるか確認.

int upper = min(N, index + r.b);

for(int i = index; i < upper; i++){

// A[i] と比較し, C[j] が大きければ, 書き換える.

// C[j] が小さければ, 書き換えを終了.

if(A[i] < r.c) ans += r.c - A[i];

else break;

}

// 4-2. 次の整数 C[j] に書き換えるための準備.

index += r.b;

// 4-3. index が N以上ならば, 書き換え出来ないので終了.

if(index >= N) break;

}

// 5. 出力～後処理.

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

return 0;

}

[入力例]
1 1
3
1 2

[出力例]
3

[入力例]
3 4
3 7 10
7 3
5 9
3 10
1 11

[出力例]
31

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

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

[入力例]
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4

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

[入力例]
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000

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

[入力例]
1000 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000
1 987654321
2 329218107
3 109739369
4 36579789
5 12193263
6 4064421
7 1354807
8 451602
9 150534
10 50178
11 16726
12 5575
13 1858
14 619
15 206
16 68
17 22
18 7
19 2
20 0

[出力例]
2222713726

[入力例]

1 1

1 2

[出力例]

[入力例]

3 4

3 7 10

7 3

5 9

3 10

1 11

[出力例]

[入力例]

3 2

5 1 4

2 3

1 5

[出力例]

※AtCoderテストケースより

[入力例]

10 3

1 8 5 7 100 4 52 33 13 5

3 10

4 30

1 4

[出力例]

338

※AtCoderテストケースより

[入力例]

11 3

1 1 1 1 1 1 1 1 1 1 1

3 1000000000

4 1000000000

3 1000000000

[出力例]

10000000001

※AtCoderテストケースより

[入力例]

1000 20

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000

1 987654321

2 329218107

3 109739369

4 36579789

5 12193263

6 4064421

7 1354807

8 451602

9 150534

10 50178

11 16726

12 5575

13 1858

14 619

15 206

16 68

17 22

18 7

19 2

20 0

[出力例]

2222713726

■参照サイト
AtCoder Beginner Contest 127

2019年7月9日

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

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

■感想.
1. 方針が見えなかったので, 解答を参考にコーディングしてみた.
2. priority_queue の復習が出来たので, 良かったと思う.

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

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

// 解き直し.
// ABC 128解説.
// https://img.atcoder.jp/abc128/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL V[51];
typedef priority_queue<LL, vector<LL>, greater<LL>> PQ;

int main() {
    
    // 1. 入力情報取得.
    LL N, K;
    scanf("%lld %lld", &N, &K);
    for(int i = 1; i <= N; i++) scanf("%lld", V + i);
    
    // 2. 解説通り.
    // 操作A, B を 行って, K - (A + B)回 捨てる操作.
    LL ans = 0;
    int upper = min(N, K);
    PQ pq0;

    // 2-1. 操作A で 宝石取り出す.
    for(int a = 0; a <= upper; a++){
        if(a > 0) pq0.push(V[a]);
        PQ pq1 = pq0;
        // cout << "a=" << a << " pq1=" << pq1.size() << endl;

        // 2-2. 操作B で 宝石取り出す.
        for(int b = 0; b <= upper - a; b++){
            if(b > 0) pq1.push(V[N + 1 - b]);
            PQ pq2 = pq1;
            int ret = K - (a + b);
            // cout << "b=" << b << " pq2=" << pq2.size() << endl;

            // 2-3. なるべく小さな負の価値の宝石を, 操作C, D で 戻す.
            LL total = 0;
            while(!pq2.empty()){
                LL v = pq2.top();
                pq2.pop();
                if(v < 0 && ret > 0) ret--;      // なるべく小さな負の価値の宝石を戻す.
                else                 total += v; // 宝石を戻さない場合は, キューが無くなるまで, 宝石の価値を加算.
            }
            // 2-4. 最大値を更新.
            ans = max(ans, total);
        }
        
    }

    // 3. 出力 ～ 後処理.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// ABC 128解説.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

LL V[51];

typedef priority_queue<LL, vector<LL>, greater<LL>> PQ;

int main() {

// 1. 入力情報取得.

LL N, K;

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

for(int i = 1; i <= N; i++) scanf("%lld", V + i);

// 2. 解説通り.

// 操作A, B を行って, K - (A + B)回捨てる操作.

LL ans = 0;

int upper = min(N, K);

PQ pq0;

// 2-1. 操作A で宝石取り出す.

for(int a = 0; a <= upper; a++){

if(a > 0) pq0.push(V[a]);

PQ pq1 = pq0;

// cout << "a=" << a << " pq1=" << pq1.size() << endl;

// 2-2. 操作B で宝石取り出す.

for(int b = 0; b <= upper - a; b++){

if(b > 0) pq1.push(V[N + 1 - b]);

PQ pq2 = pq1;

int ret = K - (a + b);

// cout << "b=" << b << " pq2=" << pq2.size() << endl;

// 2-3. なるべく小さな負の価値の宝石を, 操作C, D で戻す.

LL total = 0;

while(!pq2.empty()){

LL v = pq2.top();

pq2.pop();

if(v < 0 && ret > 0) ret--; // なるべく小さな負の価値の宝石を戻す.

else total += v; // 宝石を戻さない場合は, キューが無くなるまで, 宝石の価値を加算.

}

// 2-4. 最大値を更新.

ans = max(ans, total);

}

// 3. 出力～後処理.

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

return 0;

}

[入力例]
6 4
-10 8 2 1 2 6

[出力例(debug版)]
a=0 pq1=0
b=0 pq2=0
b=1 pq2=1
b=2 pq2=2
b=3 pq2=3
b=4 pq2=4
a=1 pq1=1
b=0 pq2=1
b=1 pq2=2
b=2 pq2=3
b=3 pq2=4
a=2 pq1=2
b=0 pq2=2
b=1 pq2=3
b=2 pq2=4
a=3 pq1=3
b=0 pq2=3
b=1 pq2=4
a=4 pq1=4
b=0 pq2=4
14
※AtCoderテストケースより

[入力例]
6 4
-6 -100 50 -2 -5 -3

[出力例(debug版)]
a=0 pq1=0
b=0 pq2=0
b=1 pq2=1
b=2 pq2=2
b=3 pq2=3
b=4 pq2=4
a=1 pq1=1
b=0 pq2=1
b=1 pq2=2
b=2 pq2=3
b=3 pq2=4
a=2 pq1=2
b=0 pq2=2
b=1 pq2=3
b=2 pq2=4
a=3 pq1=3
b=0 pq2=3
b=1 pq2=4
a=4 pq1=4
b=0 pq2=4
44
※AtCoderテストケースより

[入力例]
6 3
-6 -100 50 -2 -5 -3

[出力例(debug版)]
a=0 pq1=0
b=0 pq2=0
b=1 pq2=1
b=2 pq2=2
b=3 pq2=3
a=1 pq1=1
b=0 pq2=1
b=1 pq2=2
b=2 pq2=3
a=2 pq1=2
b=0 pq2=2
b=1 pq2=3
a=3 pq1=3
b=0 pq2=3
0
※AtCoderテストケースより

[入力例]
7 5
1 5 -10 15 12 -3 2

[出力例(debug版)]
a=0 pq1=0
b=0 pq2=0
b=1 pq2=1
b=2 pq2=2
b=3 pq2=3
b=4 pq2=4
b=5 pq2=5
a=1 pq1=1
b=0 pq2=1
b=1 pq2=2
b=2 pq2=3
b=3 pq2=4
b=4 pq2=5
a=2 pq1=2
b=0 pq2=2
b=1 pq2=3
b=2 pq2=4
b=3 pq2=5
a=3 pq1=3
b=0 pq2=3
b=1 pq2=4
b=2 pq2=5
a=4 pq1=4
b=0 pq2=4
b=1 pq2=5
a=5 pq1=5
b=0 pq2=5
29

[入力例]
47 85
-1 -12 -123 -1234 -12345 -123456 -1234567 -12345678 87654321 7654321 654321 54321 4321 321 21 1 -2 -23 -234 -2345 -23456 -234567 -2345678 -23456789 76543210 6543210 543210 43210 3210 210 10 0 -8 -78 -678 -5678 -45678 -345678 -2345678 -12345678 45678901 5678901 678901 78901 8901 901 1

[出力例]
231823625

[入力例]
50 100
543210 43210 3210 210 10 0 -8 -78 -678 -5678 -45678 -345678 -2345678 -12345678 45678901 5678901 678901 78901 8901 901 1 -7 -67 -567 -4567 -34567 -234567 -1234567 98765432 8765432 765432 65432 5432 432 32 2 -6 -56 -456 -3456 -23456 -1234567 0 76543210 6543210 543210 43210 3210 210 10

[出力例]
244759153

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

[入力例]

6 4

-10 8 2 1 2 6

[出力例(debug版)]

a=0 pq1=0

b=0 pq2=0

b=1 pq2=1

b=2 pq2=2

b=3 pq2=3

b=4 pq2=4

a=1 pq1=1

b=0 pq2=1

b=1 pq2=2

b=2 pq2=3

b=3 pq2=4

a=2 pq1=2

b=0 pq2=2

b=1 pq2=3

b=2 pq2=4

a=3 pq1=3

b=0 pq2=3

b=1 pq2=4

a=4 pq1=4

b=0 pq2=4

※AtCoderテストケースより

[入力例]

6 4

-6 -100 50 -2 -5 -3

[出力例(debug版)]

a=0 pq1=0

b=0 pq2=0

b=1 pq2=1

b=2 pq2=2

b=3 pq2=3

b=4 pq2=4

a=1 pq1=1

b=0 pq2=1

b=1 pq2=2

b=2 pq2=3

b=3 pq2=4

a=2 pq1=2

b=0 pq2=2

b=1 pq2=3

b=2 pq2=4

a=3 pq1=3

b=0 pq2=3

b=1 pq2=4

a=4 pq1=4

b=0 pq2=4

※AtCoderテストケースより

[入力例]

6 3

-6 -100 50 -2 -5 -3

[出力例(debug版)]

a=0 pq1=0

b=0 pq2=0

b=1 pq2=1

b=2 pq2=2

b=3 pq2=3

a=1 pq1=1

b=0 pq2=1

b=1 pq2=2

b=2 pq2=3

a=2 pq1=2

b=0 pq2=2

b=1 pq2=3

a=3 pq1=3

b=0 pq2=3

※AtCoderテストケースより

[入力例]

7 5

1 5 -10 15 12 -3 2

[出力例(debug版)]

a=0 pq1=0

b=0 pq2=0

b=1 pq2=1

b=2 pq2=2

b=3 pq2=3

b=4 pq2=4

b=5 pq2=5

a=1 pq1=1

b=0 pq2=1

b=1 pq2=2

b=2 pq2=3

b=3 pq2=4

b=4 pq2=5

a=2 pq1=2

b=0 pq2=2

b=1 pq2=3

b=2 pq2=4

b=3 pq2=5

a=3 pq1=3

b=0 pq2=3

b=1 pq2=4

b=2 pq2=5

a=4 pq1=4

b=0 pq2=4

b=1 pq2=5

a=5 pq1=5

b=0 pq2=5

[入力例]

47 85

-1 -12 -123 -1234 -12345 -123456 -1234567 -12345678 87654321 7654321 654321 54321 4321 321 21 1 -2 -23 -234 -2345 -23456 -234567 -2345678 -23456789 76543210 6543210 543210 43210 3210 210 10 0 -8 -78 -678 -5678 -45678 -345678 -2345678 -12345678 45678901 5678901 678901 78901 8901 901 1

[出力例]

231823625

[入力例]

50 100

543210 43210 3210 210 10 0 -8 -78 -678 -5678 -45678 -345678 -2345678 -12345678 45678901 5678901 678901 78901 8901 901 1 -7 -67 -567 -4567 -34567 -234567 -1234567 98765432 8765432 765432 65432 5432 432 32 2 -6 -56 -456 -3456 -23456 -1234567 0 76543210 6543210 543210 43210 3210 210 10

[出力例]

244759153

■参照サイト
AtCoder Beginner Contest 128

2019年7月8日

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

C++の練習を兼ねて, AtCoder Beginner Contest 133 の問題D (D – Rain Flows into Dams) を解いてみた.

■感想.
1. 相変わらず苦手な DP の訓練となったと思う.
2. 解答を見る前に, 解けたので, 及第点は取れたと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MAX = 1e5;
LL A[MAX];
LL dp[MAX];

int main() {

    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%d", A + i);
    
    // 2. 各山に降った雨の量を計算.
    // ex.
    // 以下のように, 各山に, 雨が降った(リットル: L)とする.
    // 山1 = 2 * x1 [L]
    // 山2 = 2 * x2 [L]
    // 山3 = 2 * x3 [L]
    // 山4 = 2 * x4 [L]
    // 山5 = 2 * x5 [L]
    // 
    // この場合, 各ダムは, 以下のように水が溜まるので, 
    // ダム1 = x1 + x2 [L]
    // ダム2 = x2 + x3 [L]
    // ダム3 = x3 + x4 [L]
    // ダム4 = x4 + x5 [L]
    // ダム5 = x5 + x1 [L]
    // => ダム1 - ダム2 + ダム3 - ダム4 + ダム5 で, 山1 の 降雨量 2 * x1 [L] が 抽出できる.
    // 2-1. 山1 の 降雨量 を 取得.
    LL r = 0;
    for(int i = 0; i < N; i++){
        if(i % 2 == 0) r += A[i];
        else           r -= A[i];
    }
    
    // 2-2. 山2 ～ 山N の 降雨量 を 取得.
    // ex.
    // 山2 は, ダム1: x1 + x2 から 山1 の 降雨量 2 * x1 [L] の 半分 を 引けば, 
    // x2 が残るので, 2 * x2 とすれば, 山2 の 降雨量 が 計算出来たことになる.
    dp[0] = r;
    for(int i = 1; i < N; i++) dp[i] = 2 * (A[i - 1] - dp[i - 1] / 2);

    // 3. 後処理.
    for(int i = 0; i < N; i++) printf("%lld ", dp[i]);
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int MAX = 1e5;

LL A[MAX];

LL dp[MAX];

int main() {

// 1. 入力情報取得.

int N;

scanf("%d", &N);

for(int i = 0; i < N; i++) scanf("%d", A + i);

// 2. 各山に降った雨の量を計算.

// ex.

// 以下のように, 各山に, 雨が降った(リットル: L)とする.

// 山1 = 2 * x1 [L]

// 山2 = 2 * x2 [L]

// 山3 = 2 * x3 [L]

// 山4 = 2 * x4 [L]

// 山5 = 2 * x5 [L]

// この場合, 各ダムは, 以下のように水が溜まるので,

// ダム1 = x1 + x2 [L]

// ダム2 = x2 + x3 [L]

// ダム3 = x3 + x4 [L]

// ダム4 = x4 + x5 [L]

// ダム5 = x5 + x1 [L]

// => ダム1 - ダム2 + ダム3 - ダム4 + ダム5 で, 山1 の降雨量 2 * x1 [L] が抽出できる.

// 2-1. 山1 の降雨量を取得.

LL r = 0;

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

if(i % 2 == 0) r += A[i];

else r -= A[i];

}

// 2-2. 山2 ～山N の降雨量を取得.

// ex.

// 山2 は, ダム1: x1 + x2 から山1 の降雨量 2 * x1 [L] の半分を引けば,

// x2 が残るので, 2 * x2 とすれば, 山2 の降雨量が計算出来たことになる.

dp[0] = r;

for(int i = 1; i < N; i++) dp[i] = 2 * (A[i - 1] - dp[i - 1] / 2);

// 3. 後処理.

for(int i = 0; i < N; i++) printf("%lld ", dp[i]);

return 0;

}

[入力例]
3
2 2 4

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

[入力例]
5
3 8 7 5 5

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

[入力例]
3
1000000000 1000000000 0

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

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

[出力例]
0 2 0 4 0 6 8 

[入力例]
101
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 99 97 95 93 91 89 87 85 83 81 79 77 75 73 71 69 67 65 63 61 59 57 55 53 51 49 47 45 43 41 39 37 35 33 31 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1 0

[出力例]
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 98 96 94 92 90 88 86 84 82 80 78 76 74 72 70 68 66 64 62 60 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 0

[入力例]

2 2 4

[出力例]

4 0 4

※AtCoderテストケースより

[入力例]

3 8 7 5 5

[出力例]

2 4 12 2 8

※AtCoderテストケースより

[入力例]

1000000000 1000000000 0

[出力例]

0 2000000000 0

※AtCoderテストケースより

[入力例]

1 1 2 2 3 7 4

[出力例]

0 2 0 4 0 6 8

[入力例]

101

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 99 97 95 93 91 89 87 85 83 81 79 77 75 73 71 69 67 65 63 61 59 57 55 53 51 49 47 45 43 41 39 37 35 33 31 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1 0

[出力例]

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 98 96 94 92 90 88 86 84 82 80 78 76 74 72 70 68 66 64 62 60 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 0

■参照サイト
AtCoder Beginner Contest 133

2019年7月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 131 の問題F (F – Must Be Rectangular!) を解いてみた.

■感想.
1. 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
2. 注意点として, 各連結成分の X, Y の頂点数(cVX, cVY) について, long long で計算しないと, テストケース(09.txt, 10.txt, 11.txt, 15.txt) で, WA となるので, 桁あふれに注意が必要だった.
3. 深さ優先探索(depth-first search) の復習も同時に出来たので, 良かったと思う.

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

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

// 解き直し.
// ABC 131解説.
// https://img.atcoder.jp/abc131/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
const int MAX_V = 1e5 + 1;
// const int MAX_V = 8;
using LL = long long;
int cX[MAX_V], cY[MAX_V];  // 各頂点X, Y ごとに, 連結成分番号を保存.
LL cVX[MAX_V], cVY[MAX_V]; // 各連結成分 の X, Y の 頂点数を保存.
vector<int> X[MAX_V], Y[MAX_V];

// 深さ優先探索(depth-first search).
// https://ja.wikipedia.org/wiki/深さ優先探索
// @param x: 探索開始の頂点X番号.
// @param l: 連結成分番号(※1以上).
// @return : 特に無し.
void dfs(int x, int l){

    // 1. 終了条件設定.
    // -> 連結成分番号が設定済みであれば, 終了.
    if(cX[x] > 0) return;
    
    // 2. 頂点 X について, 連結成分情報 を 設定.
    cX[x] = l, cVX[l]++;
    
    // 3. 頂点 X に, 隣接する 頂点 Y を 探索.
    for(auto &y : X[x]){
        
        if(cY[y] > 0) continue;
        // 3-1. 頂点 Y に, 連結成分 l を設定し, 連結成分のカウンターを +1 更新.
        cY[y] = l, cVY[l]++;
        
        // 3-2. 頂点 Y に, 隣接する 頂点 X を 探索(再帰処理).
        for(auto &nx : Y[y]){
            if(cX[nx] > 0) continue;
            dfs(nx, l);
        }
    }
}

int main() {

    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);

    // 以下, 解説通り.
    // 2. グラフ作成.
    for(int i = 0; i < N; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        // u -> v
        X[u].push_back(v);
        // v -> u
        Y[v].push_back(u);
    }
    
    // グラフ情報確認.
    // for(int i = 1; i < MAX_V; i++){
    //     if(X[i].size() > 0) for(auto &p : X[i]) printf("%d %d\n", i, p);
    // }
    
    // 3. 連結成分に分解.
    int c = 0;
    for(int i = 1; i < MAX_V; i++) if(X[i].size() > 0 && cX[i] == 0) c++, dfs(i, c);
    
    // グラフ連結情報確認.
    // for(int i = 1; i < MAX_V; i++){
    //     printf("cX[%d], cY[%d] = [%d, %d]\n", i, i, cX[i], cY[i]);
    //     printf("cVX[%d], cVY[%d] = [%lld, %lld]\n", i, i, cVX[i], cVY[i]);
    // }
    
    // 4. 後処理.
    // ※各連結成分 の X, Y の 頂点数(cVX, cVY) について, long long で 計算しないと, 
    // テストケース(09.txt, 10.txt, 11.txt, 15.txt) で, WA となるので要注意.
    LL ans = 0;
    for(int i = 1; i < MAX_V; i++) ans += cVX[i] * cVY[i];
    ans -= N; // 連結済 の 辺数 を 減算.
    printf("%lld\n", ans);
    return 0;

}

// 解き直し.

// ABC 131解説.

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

#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 1e5 + 1;

// const int MAX_V = 8;

using LL = long long;

int cX[MAX_V], cY[MAX_V]; // 各頂点X, Y ごとに, 連結成分番号を保存.

LL cVX[MAX_V], cVY[MAX_V]; // 各連結成分の X, Y の頂点数を保存.

vector<int> X[MAX_V], Y[MAX_V];

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

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

// @param x: 探索開始の頂点X番号.

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

// @return : 特に無し.

void dfs(int x, int l){

// 1. 終了条件設定.

// -> 連結成分番号が設定済みであれば, 終了.

if(cX[x] > 0) return;

// 2. 頂点 X について, 連結成分情報を設定.

cX[x] = l, cVX[l]++;

// 3. 頂点 X に, 隣接する頂点 Y を探索.

for(auto &y : X[x]){

if(cY[y] > 0) continue;

// 3-1. 頂点 Y に, 連結成分 l を設定し, 連結成分のカウンターを +1 更新.

cY[y] = l, cVY[l]++;

// 3-2. 頂点 Y に, 隣接する頂点 X を探索(再帰処理).

for(auto &nx : Y[y]){

if(cX[nx] > 0) continue;

dfs(nx, l);

}

int main() {

// 1. 入力情報取得.

int N;

scanf("%d", &N);

// 以下, 解説通り.

// 2. グラフ作成.

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

int u, v;

scanf("%d %d", &u, &v);

// u -> v

X[u].push_back(v);

// v -> u

Y[v].push_back(u);

}

// グラフ情報確認.

// for(int i = 1; i < MAX_V; i++){

// if(X[i].size() > 0) for(auto &p : X[i]) printf("%d %d\n", i, p);

// }

// 3. 連結成分に分解.

int c = 0;

for(int i = 1; i < MAX_V; i++) if(X[i].size() > 0 && cX[i] == 0) c++, dfs(i, c);

// グラフ連結情報確認.

// for(int i = 1; i < MAX_V; i++){

// printf("cX[%d], cY[%d] = [%d, %d]\n", i, i, cX[i], cY[i]);

// printf("cVX[%d], cVY[%d] = [%lld, %lld]\n", i, i, cVX[i], cVY[i]);

// }

// 4. 後処理.

// ※各連結成分の X, Y の頂点数(cVX, cVY) について, long long で計算しないと,

// テストケース(09.txt, 10.txt, 11.txt, 15.txt) で, WA となるので要注意.

LL ans = 0;

for(int i = 1; i < MAX_V; i++) ans += cVX[i] * cVY[i];

ans -= N; // 連結済の辺数を減算.

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

return 0;

}

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

[出力例(debug版)]
cX[1], cY[1] = [1, 1]
cVX[1], cVY[1] = [2, 2]
cX[2], cY[2] = [0, 0]
cVX[2], cVY[2] = [0, 0]
cX[3], cY[3] = [0, 0]
cVX[3], cVY[3] = [0, 0]
cX[4], cY[4] = [0, 0]
cVX[4], cVY[4] = [0, 0]
cX[5], cY[5] = [1, 1]
cVX[5], cVY[5] = [0, 0]
cX[6], cY[6] = [0, 0]
cVX[6], cVY[6] = [0, 0]
cX[7], cY[7] = [0, 0]
cVX[7], cVY[7] = [0, 0]
1
※AtCoderテストケースより

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

[出力例(debug版)]
cX[1], cY[1] = [1, 1]
cVX[1], cVY[1] = [5, 5]
cX[2], cY[2] = [1, 1]
cVX[2], cVY[2] = [0, 0]
cX[3], cY[3] = [1, 1]
cVX[3], cVY[3] = [0, 0]
cX[4], cY[4] = [1, 1]
cVX[4], cVY[4] = [0, 0]
cX[5], cY[5] = [1, 1]
cVX[5], cVY[5] = [0, 0]
cX[6], cY[6] = [0, 0]
cVX[6], cVY[6] = [0, 0]
cX[7], cY[7] = [0, 0]
cVX[7], cVY[7] = [0, 0]
16
※AtCoderテストケースより

[入力例]
27
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5
11 11
12 11
13 11
14 11
15 11
11 12
11 13
11 14
11 15
21 11
22 11
23 11
24 11
25 11
21 12
21 13
21 14
21 15

[出力例(debug版)]
cX[1], cY[1] = [1, 1]
cVX[1], cVY[1] = [5, 5]
cX[2], cY[2] = [1, 1]
cVX[2], cVY[2] = [10, 5]
cX[3], cY[3] = [1, 1]
cVX[3], cVY[3] = [0, 0]
cX[4], cY[4] = [1, 1]
cVX[4], cVY[4] = [0, 0]
cX[5], cY[5] = [1, 1]
cVX[5], cVY[5] = [0, 0]
cX[6], cY[6] = [0, 0]
cVX[6], cVY[6] = [0, 0]
cX[7], cY[7] = [0, 0]
cVX[7], cVY[7] = [0, 0]
cX[8], cY[8] = [0, 0]
cVX[8], cVY[8] = [0, 0]
cX[9], cY[9] = [0, 0]
cVX[9], cVY[9] = [0, 0]
cX[10], cY[10] = [0, 0]
cVX[10], cVY[10] = [0, 0]
cX[11], cY[11] = [2, 2]
cVX[11], cVY[11] = [0, 0]
cX[12], cY[12] = [2, 2]
cVX[12], cVY[12] = [0, 0]
cX[13], cY[13] = [2, 2]
cVX[13], cVY[13] = [0, 0]
cX[14], cY[14] = [2, 2]
cVX[14], cVY[14] = [0, 0]
cX[15], cY[15] = [2, 2]
cVX[15], cVY[15] = [0, 0]
cX[16], cY[16] = [0, 0]
cVX[16], cVY[16] = [0, 0]
cX[17], cY[17] = [0, 0]
cVX[17], cVY[17] = [0, 0]
cX[18], cY[18] = [0, 0]
cVX[18], cVY[18] = [0, 0]
cX[19], cY[19] = [0, 0]
cVX[19], cVY[19] = [0, 0]
cX[20], cY[20] = [0, 0]
cVX[20], cVY[20] = [0, 0]
cX[21], cY[21] = [2, 0]
cVX[21], cVY[21] = [0, 0]
cX[22], cY[22] = [2, 0]
cVX[22], cVY[22] = [0, 0]
cX[23], cY[23] = [2, 0]
cVX[23], cVY[23] = [0, 0]
cX[24], cY[24] = [2, 0]
cVX[24], cVY[24] = [0, 0]
cX[25], cY[25] = [2, 0]
cVX[25], cVY[25] = [0, 0]
cX[26], cY[26] = [0, 0]
cVX[26], cVY[26] = [0, 0]
cX[27], cY[27] = [0, 0]
cVX[27], cVY[27] = [0, 0]
cX[28], cY[28] = [0, 0]
cVX[28], cVY[28] = [0, 0]
cX[29], cY[29] = [0, 0]
cVX[29], cVY[29] = [0, 0]
48

[入力例]
100 
1 55
2 54
1 48
1 47
2 46
3 45
2 44
1 43
1 42
2 41
3 40
4 39
3 38
2 37
1 36
1 35
2 34
3 33
4 32
5 31
4 30
3 53
2 28
1 27
1 26
2 25
3 24
4 23
5 22
6 21
5 20
4 19
3 18
2 17
1 16
1 52
2 14
3 13
4 12
5 11
6 10
7 9
6 8
5 7
4 6
3 5
2 4
1 3
1 2
2 1
3 2
4 3
5 4
6 5
7 6
8 7
7 8
6 9
5 10
4 11
3 12
2 13
1 14
1 15
2 16
3 17
4 18
5 19
6 20
7 21
8 22
9 23
8 24
7 25
6 26
5 27
4 28
3 29
2 30
1 31
1 32
2 33
3 34
4 35
5 36
6 37
7 38
8 39
9 40
10 41
9 42
8 43
7 44
6 45
5 46
4 47
3 48
2 49
1 50
1 51

[出力例]
450

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

[入力例]

1 1

5 1

5 5

[出力例(debug版)]

cX[1], cY[1] = [1, 1]

cVX[1], cVY[1] = [2, 2]

cX[2], cY[2] = [0, 0]

cVX[2], cVY[2] = [0, 0]

cX[3], cY[3] = [0, 0]

cVX[3], cVY[3] = [0, 0]

cX[4], cY[4] = [0, 0]

cVX[4], cVY[4] = [0, 0]

cX[5], cY[5] = [1, 1]

cVX[5], cVY[5] = [0, 0]

cX[6], cY[6] = [0, 0]

cVX[6], cVY[6] = [0, 0]

cX[7], cY[7] = [0, 0]

cVX[7], cVY[7] = [0, 0]

※AtCoderテストケースより

[入力例]

1 1

2 1

3 1

4 1

5 1

1 2

1 3

1 4

1 5

[出力例(debug版)]

cX[1], cY[1] = [1, 1]

cVX[1], cVY[1] = [5, 5]

cX[2], cY[2] = [1, 1]

cVX[2], cVY[2] = [0, 0]

cX[3], cY[3] = [1, 1]

cVX[3], cVY[3] = [0, 0]

cX[4], cY[4] = [1, 1]

cVX[4], cVY[4] = [0, 0]

cX[5], cY[5] = [1, 1]

cVX[5], cVY[5] = [0, 0]

cX[6], cY[6] = [0, 0]

cVX[6], cVY[6] = [0, 0]

cX[7], cY[7] = [0, 0]

cVX[7], cVY[7] = [0, 0]

※AtCoderテストケースより

[入力例]

1 1

2 1

3 1

4 1

5 1

1 2

1 3

1 4

1 5

11 11

12 11

13 11

14 11

15 11

11 12

11 13

11 14

11 15

21 11

22 11

23 11

24 11

25 11

21 12

21 13

21 14

21 15

[出力例(debug版)]

cX[1], cY[1] = [1, 1]

cVX[1], cVY[1] = [5, 5]

cX[2], cY[2] = [1, 1]

cVX[2], cVY[2] = [10, 5]

cX[3], cY[3] = [1, 1]

cVX[3], cVY[3] = [0, 0]

cX[4], cY[4] = [1, 1]

cVX[4], cVY[4] = [0, 0]

cX[5], cY[5] = [1, 1]

cVX[5], cVY[5] = [0, 0]

cX[6], cY[6] = [0, 0]

cVX[6], cVY[6] = [0, 0]

cX[7], cY[7] = [0, 0]

cVX[7], cVY[7] = [0, 0]

cX[8], cY[8] = [0, 0]

cVX[8], cVY[8] = [0, 0]

cX[9], cY[9] = [0, 0]

cVX[9], cVY[9] = [0, 0]

cX[10], cY[10] = [0, 0]

cVX[10], cVY[10] = [0, 0]

cX[11], cY[11] = [2, 2]

cVX[11], cVY[11] = [0, 0]

cX[12], cY[12] = [2, 2]

cVX[12], cVY[12] = [0, 0]

cX[13], cY[13] = [2, 2]

cVX[13], cVY[13] = [0, 0]

cX[14], cY[14] = [2, 2]

cVX[14], cVY[14] = [0, 0]

cX[15], cY[15] = [2, 2]

cVX[15], cVY[15] = [0, 0]

cX[16], cY[16] = [0, 0]

cVX[16], cVY[16] = [0, 0]

cX[17], cY[17] = [0, 0]

cVX[17], cVY[17] = [0, 0]

cX[18], cY[18] = [0, 0]

cVX[18], cVY[18] = [0, 0]

cX[19], cY[19] = [0, 0]

cVX[19], cVY[19] = [0, 0]

cX[20], cY[20] = [0, 0]

cVX[20], cVY[20] = [0, 0]

cX[21], cY[21] = [2, 0]

cVX[21], cVY[21] = [0, 0]

cX[22], cY[22] = [2, 0]

cVX[22], cVY[22] = [0, 0]

cX[23], cY[23] = [2, 0]

cVX[23], cVY[23] = [0, 0]

cX[24], cY[24] = [2, 0]

cVX[24], cVY[24] = [0, 0]

cX[25], cY[25] = [2, 0]

cVX[25], cVY[25] = [0, 0]

cX[26], cY[26] = [0, 0]

cVX[26], cVY[26] = [0, 0]

cX[27], cY[27] = [0, 0]

cVX[27], cVY[27] = [0, 0]

cX[28], cY[28] = [0, 0]

cVX[28], cVY[28] = [0, 0]

cX[29], cY[29] = [0, 0]

cVX[29], cVY[29] = [0, 0]

[入力例]

100

1 55

2 54

1 48

1 47

2 46

3 45

2 44

1 43

1 42

2 41

3 40

4 39

3 38

2 37

1 36

1 35

2 34

3 33

4 32

5 31

4 30

3 53

2 28

1 27

1 26

2 25

3 24

4 23

5 22

6 21

5 20

4 19

3 18

2 17

1 16

1 52

2 14

3 13

4 12

5 11

6 10

7 9

6 8

5 7

4 6

3 5

2 4

1 3

1 2

2 1

3 2

4 3

5 4

6 5

7 6

8 7

7 8

6 9

5 10

4 11

3 12

2 13

1 14

1 15

2 16

3 17

4 18

5 19

6 20

7 21

8 22

9 23

8 24

7 25

6 26

5 27

4 28

3 29

2 30

1 31

1 32

2 33

3 34

4 35

5 36

6 37

7 38

8 39

9 40

10 41

9 42

8 43

7 44

6 45

5 46

4 47

3 48

2 49

1 50

1 51

[出力例]

450

■参照サイト
AtCoder Beginner Contest 131

2019年7月7日2019年7月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 131 の問題E (E – Friendships) を解いてみた.

■感想.
1. スターを作成すると, (N – 1) * (N – 2) / 2 となることまでは, 気付いたものの, 本問との結びつけが見えなかったので, 解答を参考に実装した.
2. 非常に面白い問題だと感じた, グラフ理論の知識を少しずつ増やしていく必要があると感じた.

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

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

// 解き直し.
// ABC 131解説.
// https://img.atcoder.jp/abc131/editorial.pdf
#include <bits/stdc++.h>
using namespace std;

int main() {
    
    // 1. 入力情報取得.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 以下, 解説通り.
    // -> 解が存在しない場合は, 終了.
    int upper = (N - 1) * (N - 2) / 2;
    if(K > upper){
        printf("%d\n", -1);
        return 0;
    }
    
    // 3. 頂点 1 を中心とするスターを作成後, 
    // 頂点 2 ～ 頂点 N の間に, 必要な本数だけ, 辺を追加し, 出力.
    // -> 必要な本数は, (upper - K)本 とする.
    int M = (N - 1) + (upper - K);
    printf("%d\n", M);
    for(int i = 1; i < N; i++) for(int j = i + 1; j <= N; j++) if(M > 0) printf("%d %d\n", i, j), M--;
    
    // 4. 後処理.
    return 0;
    
}

// 解き直し.

// ABC 131解説.

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

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

int N, K;

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

// 2. 以下, 解説通り.

// -> 解が存在しない場合は, 終了.

int upper = (N - 1) * (N - 2) / 2;

if(K > upper){

printf("%d\n", -1);

return 0;

}

// 3. 頂点 1 を中心とするスターを作成後,

// 頂点 2 ～頂点 N の間に, 必要な本数だけ, 辺を追加し, 出力.

// -> 必要な本数は, (upper - K)本とする.

int M = (N - 1) + (upper - K);

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

for(int i = 1; i < N; i++) for(int j = i + 1; j <= N; j++) if(M > 0) printf("%d %d\n", i, j), M--;

// 4. 後処理.

return 0;

}

[入力例]
5 3

[出力例]
7
1 2
1 3
1 4
1 5
2 3
2 4
2 5
※AtCoderテストケースより

[入力例]
5 8

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

[入力例]
5 6

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

[入力例]
2 0

[出力例]
1
1 2

[入力例]
2 1

[出力例]
-1

[入力例]
15 25

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

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

[入力例]

5 3

[出力例]

1 2

1 3

1 4

1 5

2 3

2 4

2 5

※AtCoderテストケースより

[入力例]

5 8

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 6

[出力例]

1 2

1 3

1 4

1 5

[入力例]

2 0

[出力例]

1 2

[入力例]

2 1

[出力例]

-1

[入力例]

15 25

[出力例]

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

1 10

1 11

1 12

1 13

1 14

1 15

2 3

2 4

2 5

2 6

2 7

2 8

2 9

2 10

2 11

2 12

2 13

2 14

2 15

3 4

3 5

3 6

3 7

3 8

3 9

3 10

3 11

3 12

3 13

3 14

3 15

4 5

4 6

4 7

4 8

4 9

4 10

4 11

4 12

4 13

4 14

4 15

5 6

5 7

5 8

5 9

5 10

5 11

5 12

5 13

5 14

5 15

6 7

6 8

6 9

6 10

6 11

6 12

6 13

6 14

6 15

7 8

7 9

7 10

7 11

7 12

7 13

7 14

7 15

8 9

8 10

8 11

■参照サイト
AtCoder Beginner Contest 131

2019年7月6日

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

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

■感想.
1. いくつかのテストケース(sub1_07.txt, sub1_09.txt, sub1_27.txt, sub1_28.txt) で, WA となったが, 簡単なテストケースで確認して, WA を解決出来たので良かったと思う.
2. 解答を見る前に, 解けたので, 及第点は取れたと思う.

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

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

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

int main() {

    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    vector<pair<LL, LL>> v;
    for(int i = 0; i < N; i++){
        LL a, b;
        scanf("%lld %lld", &a, &b);
        v.push_back(make_pair(b, a));
    }
    
    // 2. 〆切の時刻で, 昇順sort.
    sort(v.begin(), v.end());
    
    // 3. 区間をマージしていく.
    // [入力例]
    // ※〆切の時刻で, 昇順sort済.
    // 5
    // 2 4
    // 1 8
    // 1 9
    // 4 9
    // 3 12
    // -> 具体的には, 以下のような処理を想定.
    // 仕事1 => [2, 4]  … 開始時刻: 2, 終了時刻: 4
    // 仕事2 => [1, 4]  … 開始時刻: 1, 終了時刻: 4
    // 仕事3 => [0, 4]  … 開始時刻: 0, 終了時刻: 4
    // 仕事4 => [0, 8]  … 開始時刻: 0, 終了時刻: 8
    // 仕事5 => [0, 11] … 開始時刻: 0, 終了時刻: 11
    bool ans = true;
    LL l = v[0].first - v[0].second, r = v[0].first;
    // printf("[%lld, %lld]\n", l, r);
    // sub1_07.txt, sub1_09.txt, sub1_27.txt, sub1_28.txt で, 
    // WA版となった理由 と 推定し, ロジック追加.
    if(l < 0) ans = false; 

    for(int i = 1; i < N; i++){
        // 以下の条件で, 区間更新.
        LL a = v[i].second, b = v[i].first;
        
        // 3-1. 最小時刻が, ゼロの場合.
        if(l == 0) r += a;
        
        // 3-2. 最小時刻 が 0より大きく, かつ, 仕事にかかる時間が, 最小時刻 より 大きい場合.
        if(l > 0 && l < a) r += (a - l), l = 0;
        
        // 3-3. 最小時刻 が, 仕事にかかる時間以上に大きい場合.
        if(l >= a) l -= a;
        
        // 3-4. 仕事が〆切までに終了しているかチェック.
        // printf("[%lld, %lld]\n", l, r);
        if(r > b){
            ans = false;
            break;
        }
    }
    
    // 4. 後処理.
    if(ans) printf("%s\n", "Yes");
    else    printf("%s\n",  "No");
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

int N;

scanf("%d", &N);

vector<pair<LL, LL>> v;

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

LL a, b;

scanf("%lld %lld", &a, &b);

v.push_back(make_pair(b, a));

}

// 2. 〆切の時刻で, 昇順sort.

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

// 3. 区間をマージしていく.

// [入力例]

// ※〆切の時刻で, 昇順sort済.

// 5

// 2 4

// 1 8

// 1 9

// 4 9

// 3 12

// -> 具体的には, 以下のような処理を想定.

// 仕事1 => [2, 4] … 開始時刻: 2, 終了時刻: 4

// 仕事2 => [1, 4] … 開始時刻: 1, 終了時刻: 4

// 仕事3 => [0, 4] … 開始時刻: 0, 終了時刻: 4

// 仕事4 => [0, 8] … 開始時刻: 0, 終了時刻: 8

// 仕事5 => [0, 11] … 開始時刻: 0, 終了時刻: 11

bool ans = true;

LL l = v[0].first - v[0].second, r = v[0].first;

// printf("[%lld, %lld]\n", l, r);

// sub1_07.txt, sub1_09.txt, sub1_27.txt, sub1_28.txt で,

// WA版となった理由と推定し, ロジック追加.

if(l < 0) ans = false;

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

// 以下の条件で, 区間更新.

LL a = v[i].second, b = v[i].first;

// 3-1. 最小時刻が, ゼロの場合.

if(l == 0) r += a;

// 3-2. 最小時刻が 0より大きく, かつ, 仕事にかかる時間が, 最小時刻より大きい場合.

if(l > 0 && l < a) r += (a - l), l = 0;

// 3-3. 最小時刻が, 仕事にかかる時間以上に大きい場合.

if(l >= a) l -= a;

// 3-4. 仕事が〆切までに終了しているかチェック.

// printf("[%lld, %lld]\n", l, r);

if(r > b){

ans = false;

break;

}

// 4. 後処理.

if(ans) printf("%s\n", "Yes");

else printf("%s\n", "No");

return 0;

}

[入力例]
1
2 1

[出力例(debug版)]
[-1, 1]
No

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

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

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

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

[入力例]
3
334 1000
334 1000
334 1000

[出力例(debug版)]
[666, 1000]
[332, 1000]
[0, 1002]
No
※AtCoderテストケースより

[入力例]
30
384 8895
1725 9791
170 1024
4 11105
2 6
578 1815
702 3352
143 5141
1420 6980
24 1602
849 999
76 7586
85 5570
444 4991
719 11090
470 10708
1137 4547
455 9003
110 9901
15 8578
368 3692
104 1286
3 4
366 12143
7 6649
610 2374
152 7324
4 7042
292 11386
334 5720

[出力例(debug版)]
[1, 4]
[0, 5]
[0, 854]
[0, 1024]
[0, 1128]
[0, 1152]
[0, 1730]
[0, 2340]
[0, 3042]
[0, 3410]
[0, 4547]
[0, 4991]
[0, 5134]
[0, 5219]
[0, 5553]
[0, 5560]
[0, 6980]
[0, 6984]
[0, 7136]
[0, 7212]
[0, 7227]
[0, 7611]
[0, 8066]
[0, 9791]
[0, 9901]
[0, 10371]
[0, 11090]
[0, 11094]
[0, 11386]
[0, 11752]
Yes
※AtCoderテストケースより

[入力例]
50 
25 150
24 160
23 170
22 180
21 190
20 200
19 210
18 220
17 230
16 240
15 250
14 260
13 270
12 280
11 290
10 300
9 310
8 320
7 330
6 340
5 350
4 360
3 370
2 380
1 390
1 400
2 410
3 420
4 430
5 440
6 450
7 460
8 470
9 480
10 490
11 500
12 510
13 520
14 530
15 540
16 550
17 560
18 570
19 580
20 590
21 600
22 610
23 620
24 630
25 640

[出力例(debug版)]
[125, 150]
[101, 150]
[78, 150]
[56, 150]
[35, 150]
[15, 150]
[0, 154]
[0, 172]
[0, 189]
[0, 205]
[0, 220]
[0, 234]
[0, 247]
[0, 259]
[0, 270]
[0, 280]
[0, 289]
[0, 297]
[0, 304]
[0, 310]
[0, 315]
[0, 319]
[0, 322]
[0, 324]
[0, 325]
[0, 326]
[0, 328]
[0, 331]
[0, 335]
[0, 340]
[0, 346]
[0, 353]
[0, 361]
[0, 370]
[0, 380]
[0, 391]
[0, 403]
[0, 416]
[0, 430]
[0, 445]
[0, 461]
[0, 478]
[0, 496]
[0, 515]
[0, 535]
[0, 556]
[0, 578]
[0, 601]
[0, 625]
[0, 650]
No

[入力例]
50 
25 200
24 220
23 240
22 260
21 280
20 300
19 320
18 340
17 360
16 380
15 400
14 420
13 440
12 460
11 480
10 500
9 520
8 540
7 560
6 580
5 600
4 620
3 640
2 660
1 680
1 700
2 720
3 740
4 760
5 780
6 800
7 820
8 840
9 860
10 880
11 900
12 920
13 940
14 960
15 980
16 1000
17 1020
18 1040
19 1060
20 1080
21 1100
22 1120
23 1140
24 1160
25 1180

[出力例(debug版)]
[175, 200]
[151, 200]
[128, 200]
[106, 200]
[85, 200]
[65, 200]
[46, 200]
[28, 200]
[11, 200]
[0, 205]
[0, 220]
[0, 234]
[0, 247]
[0, 259]
[0, 270]
[0, 280]
[0, 289]
[0, 297]
[0, 304]
[0, 310]
[0, 315]
[0, 319]
[0, 322]
[0, 324]
[0, 325]
[0, 326]
[0, 328]
[0, 331]
[0, 335]
[0, 340]
[0, 346]
[0, 353]
[0, 361]
[0, 370]
[0, 380]
[0, 391]
[0, 403]
[0, 416]
[0, 430]
[0, 445]
[0, 461]
[0, 478]
[0, 496]
[0, 515]
[0, 535]
[0, 556]
[0, 578]
[0, 601]
[0, 625]
[0, 650]
Yes

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

[入力例]

2 1

[出力例(debug版)]

[-1, 1]

[入力例]

1 4

2 4

1 4

[出力例(debug版)]

[3, 4]

[2, 4]

[0, 4]

Yes

[入力例]

2 4

1 9

1 8

4 9

3 12

[出力例(debug版)]

[2, 4]

[1, 4]

[0, 4]

[0, 8]

[0, 11]

Yes

※AtCoderテストケースより

[入力例]

334 1000

[出力例(debug版)]

[666, 1000]

[332, 1000]

[0, 1002]

※AtCoderテストケースより

[入力例]

384 8895

1725 9791

170 1024

4 11105

2 6

578 1815

702 3352

143 5141

1420 6980

24 1602

849 999

76 7586

85 5570

444 4991

719 11090

470 10708

1137 4547

455 9003

110 9901

15 8578

368 3692

104 1286

3 4

366 12143

7 6649

610 2374

152 7324

4 7042

292 11386

334 5720

[出力例(debug版)]

[1, 4]

[0, 5]

[0, 854]

[0, 1024]

[0, 1128]

[0, 1152]

[0, 1730]

[0, 2340]

[0, 3042]

[0, 3410]

[0, 4547]

[0, 4991]

[0, 5134]

[0, 5219]

[0, 5553]

[0, 5560]

[0, 6980]

[0, 6984]

[0, 7136]

[0, 7212]

[0, 7227]

[0, 7611]

[0, 8066]

[0, 9791]

[0, 9901]

[0, 10371]

[0, 11090]

[0, 11094]

[0, 11386]

[0, 11752]

Yes

※AtCoderテストケースより

[入力例]

25 150

24 160

23 170

22 180

21 190

20 200

19 210

18 220

17 230

16 240

15 250

14 260

13 270

12 280

11 290

10 300

9 310

8 320

7 330

6 340

5 350

4 360

3 370

2 380

1 390

1 400

2 410

3 420

4 430

5 440

6 450

7 460

8 470

9 480

10 490

11 500

12 510

13 520

14 530

15 540

16 550

17 560

18 570

19 580

20 590

21 600

22 610

23 620

24 630

25 640

[出力例(debug版)]

[125, 150]

[101, 150]

[78, 150]

[56, 150]

[35, 150]

[15, 150]

[0, 154]

[0, 172]

[0, 189]

[0, 205]

[0, 220]

[0, 234]

[0, 247]

[0, 259]

[0, 270]

[0, 280]

[0, 289]

[0, 297]

[0, 304]

[0, 310]

[0, 315]

[0, 319]

[0, 322]

[0, 324]

[0, 325]

[0, 326]

[0, 328]

[0, 331]

[0, 335]

[0, 340]

[0, 346]

[0, 353]

[0, 361]

[0, 370]

[0, 380]

[0, 391]

[0, 403]

[0, 416]

[0, 430]

[0, 445]

[0, 461]

[0, 478]

[0, 496]

[0, 515]

[0, 535]

[0, 556]

[0, 578]

[0, 601]

[0, 625]

[0, 650]

[入力例]

25 200

24 220

23 240

22 260

21 280

20 300

19 320

18 340

17 360

16 380

15 400

14 420

13 440

12 460

11 480

10 500

9 520

8 540

7 560

6 580

5 600

4 620

3 640

2 660

1 680

1 700

2 720

3 740

4 760

5 780

6 800

7 820

8 840

9 860

10 880

11 900

12 920

13 940

14 960

15 980

16 1000

17 1020

18 1040

19 1060

20 1080

21 1100

22 1120

23 1140

24 1160

25 1180

[出力例(debug版)]

[175, 200]

[151, 200]

[128, 200]

[106, 200]

[85, 200]

[65, 200]

[46, 200]

[28, 200]

[11, 200]

[0, 205]

[0, 220]

[0, 234]

[0, 247]

[0, 259]

[0, 270]

[0, 280]

[0, 289]

[0, 297]

[0, 304]

[0, 310]

[0, 315]

[0, 319]

[0, 322]

[0, 324]

[0, 325]

[0, 326]

[0, 328]

[0, 331]

[0, 335]

[0, 340]

[0, 346]

[0, 353]

[0, 361]

[0, 370]

[0, 380]

[0, 391]

[0, 403]

[0, 416]

[0, 430]

[0, 445]

[0, 461]

[0, 478]

[0, 496]

[0, 515]

[0, 535]

[0, 556]

[0, 578]

[0, 601]

[0, 625]

[0, 650]

Yes

■参照サイト
AtCoder Beginner Contest 131

2019年7月6日

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

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

■感想.
1. 解答を見る前に, 解けたので, 及第点は取れたと思う.
2. 復習したい問題が, たくさん残っているので, 時間取って進めていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2002;
char grid[MAX][MAX];
int r[MAX][MAX], c[MAX][MAX];
int rGrid[MAX][MAX], cGrid[MAX][MAX];

int main() {
    
    // 1. 入力情報取得.
    int H, W;
    scanf("%d %d", &H, &W);
    for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) grid[i][j] = '#';
    for(int i = 0; i < H; i++) scanf("%s", grid + i), grid[i][W] = '#'; // delete null character `\0`.
    
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%c", grid[i][j]);
    //     printf("\n");
    // }
    
    // 2. 行方向で照らされるマスの個数をカウント.
    for(int i = 0; i < H; i++){
        int rIndex = 1;
        for(int j = 0; j < W; j++){
            // '.' が 連続出現している場合は, カウントアップ.
            if(grid[i][j] == '.') r[i][rIndex]++, rGrid[i][j] = rIndex;
            // '.' の 連続出現が終わったら, rIndex を インクリメントして, 次のカウントアップに備える.
            if(grid[i][j] == '#' && j > 0 && grid[i][j - 1] == '.') rIndex++;
        }
    }

    // 3. 列方向で照らされるマスの個数をカウント.
    for(int j = 0; j < W; j++){
        int cIndex = 1;
        for(int i = 0; i < H; i++){
            // '.' が 連続出現している場合は, カウントアップ.
            if(grid[i][j] == '.') c[j][cIndex]++, cGrid[i][j] = cIndex;
            // '.' の 連続出現が終わったら, cIndex を インクリメントして, 次のカウントアップに備える.
            if(grid[i][j] == '#' && i > 0 && grid[i - 1][j] == '.') cIndex++;
        }
    }
    
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%d ", rGrid[i][j]);
    //     printf("\n");
    // }
    // printf("\n");
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%d ", r[i][j]);
    //     printf("\n");
    // }
    // printf("\n");
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%d ", cGrid[i][j]);
    //     printf("\n");
    // }
    // printf("\n");
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%d ", c[i][j]);
    //     printf("\n");
    // }
    
    // 4. 照らされるマスの個数の最大値を計算.
    int ans = 0;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            int rIndex = rGrid[i][j], cIndex = cGrid[i][j];
            int count = r[i][rIndex] + c[j][cIndex] - 1;
            ans = max(ans, count);
        }
    }

    // 5. 出力 ～ 後処理.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2002;

char grid[MAX][MAX];

int r[MAX][MAX], c[MAX][MAX];

int rGrid[MAX][MAX], cGrid[MAX][MAX];

int main() {

// 1. 入力情報取得.

int H, W;

scanf("%d %d", &H, &W);

for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) grid[i][j] = '#';

for(int i = 0; i < H; i++) scanf("%s", grid + i), grid[i][W] = '#'; // delete null character `\0`.

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

// for(int j = 0; j < W + 1; j++) printf("%c", grid[i][j]);

// printf("\n");

// }

// 2. 行方向で照らされるマスの個数をカウント.

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

int rIndex = 1;

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

// '.' が連続出現している場合は, カウントアップ.

if(grid[i][j] == '.') r[i][rIndex]++, rGrid[i][j] = rIndex;

// '.' の連続出現が終わったら, rIndex をインクリメントして, 次のカウントアップに備える.

if(grid[i][j] == '#' && j > 0 && grid[i][j - 1] == '.') rIndex++;

}

// 3. 列方向で照らされるマスの個数をカウント.

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

int cIndex = 1;

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

// '.' が連続出現している場合は, カウントアップ.

if(grid[i][j] == '.') c[j][cIndex]++, cGrid[i][j] = cIndex;

// '.' の連続出現が終わったら, cIndex をインクリメントして, 次のカウントアップに備える.

if(grid[i][j] == '#' && i > 0 && grid[i - 1][j] == '.') cIndex++;

}

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

// for(int j = 0; j < W + 1; j++) printf("%d ", rGrid[i][j]);

// printf("\n");

// }

// printf("\n");

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

// for(int j = 0; j < W + 1; j++) printf("%d ", r[i][j]);

// printf("\n");

// }

// printf("\n");

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

// for(int j = 0; j < W + 1; j++) printf("%d ", cGrid[i][j]);

// printf("\n");

// }

// printf("\n");

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

// for(int j = 0; j < W + 1; j++) printf("%d ", c[i][j]);

// printf("\n");

// }

// 4. 照らされるマスの個数の最大値を計算.

int ans = 0;

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

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

int rIndex = rGrid[i][j], cIndex = cGrid[i][j];

int count = r[i][rIndex] + c[j][cIndex] - 1;

ans = max(ans, count);

}

// 5. 出力～後処理.

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

return 0;

}

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

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

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

0 1 1 0 1 1 0 
1 1 1 1 1 0 0 
1 1 1 1 0 2 0 
0 1 0 1 2 2 0 
0 0 0 0 0 0 0 

0 2 0 0 0 0 0 
0 4 0 0 0 0 0 
0 3 0 0 0 0 0 
0 3 0 0 0 0 0 
0 2 1 0 0 0 0 
8
※AtCoderテストケースより

[入力例]
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

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

0 2 3 1 0 0 0 0 0 
0 4 3 0 0 0 0 0 0 
0 6 0 0 0 0 0 0 0 
0 2 2 0 0 0 0 0 0 
0 3 2 1 0 0 0 0 0 
0 4 1 0 0 0 0 0 0 
0 3 3 0 0 0 0 0 0 
0 1 2 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 

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

0 2 2 0 0 0 0 0 0 
0 2 2 1 0 0 0 0 0 
0 2 3 0 0 0 0 0 0 
0 3 3 0 0 0 0 0 0 
0 1 1 2 0 0 0 0 0 
0 8 0 0 0 0 0 0 0 
0 3 2 0 0 0 0 0 0 
0 3 3 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
13
※AtCoderテストケースより

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

[出力例]
37

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

[入力例]

4 6

#..#..

.....#

....#.

#.#...

[出力例(debug版)]

0 1 1 0 2 2 0

1 1 1 1 1 0 0

1 1 1 1 0 2 0

0 1 0 2 2 2 0

0 0 0 0 0 0 0

0 2 2 0 0 0 0

0 5 0 0 0 0 0

0 4 1 0 0 0 0

0 1 3 0 0 0 0

0 0 0 0 0 0 0

0 1 1 0 1 1 0

1 1 1 1 1 0 0

1 1 1 1 0 2 0

0 1 0 1 2 2 0

0 0 0 0 0 0 0

0 2 0 0 0 0 0

0 4 0 0 0 0 0

0 3 0 0 0 0 0

0 2 1 0 0 0 0

※AtCoderテストケースより

[入力例]

8 8

..#...#.

....#...

##......

..###..#

...#..#.

##....#.

#...#...

###.#..#

[出力例(debug版)]

1 1 0 2 2 2 0 3 0

1 1 1 1 0 2 2 2 0

0 0 1 1 1 1 1 1 0

1 1 0 0 0 2 2 0 0

1 1 1 0 2 2 0 3 0

0 0 1 1 1 1 0 2 0

0 1 1 1 0 2 2 2 0

0 0 0 1 0 2 2 0 0

0 0 0 0 0 0 0 0 0

0 2 3 1 0 0 0 0 0

0 4 3 0 0 0 0 0 0

0 6 0 0 0 0 0 0 0

0 2 2 0 0 0 0 0 0

0 3 2 1 0 0 0 0 0

0 4 1 0 0 0 0 0 0

0 3 3 0 0 0 0 0 0

0 1 2 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

1 1 0 1 1 1 0 1 0

1 1 1 1 0 1 1 1 0

0 0 1 1 2 1 1 1 0

2 2 0 0 0 1 1 0 0

2 2 2 0 3 1 0 2 0

0 0 2 2 3 1 0 2 0

0 3 2 2 0 1 2 2 0

0 0 0 2 0 1 2 0 0

0 0 0 0 0 0 0 0 0

0 2 2 0 0 0 0 0 0

0 2 2 1 0 0 0 0 0

0 2 3 0 0 0 0 0 0

0 3 3 0 0 0 0 0 0

0 1 1 2 0 0 0 0 0

0 8 0 0 0 0 0 0 0

0 3 2 0 0 0 0 0 0

0 3 3 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

※AtCoderテストケースより

[入力例]

100 100

........#.........##..#.#.##..#.#..#..#...##...#...#....#........##.....#..#.##.##..#..#....#...###.

#...#..#...#....##..#....#...#.#.....#...#..#.#..#...#.....#..##...#......#.....##....###....#..#.#.

............#.......##.##.....##....#.#.#.......#....##.#......#.#....#...###....#...#....#.#....#..

.#...#.#...#..##.#...#.#...###..............#..##........#......#....#.#.#.....#.........#.##.###...

.........##...##..#.....#.#.###..#....#.#..##...#..#...#.....###.##........#..#......##.#.#....#.#..

.....##......#.......##...#.#....#...............#.....##..#..#...#.....##..#..#.##...........#.##..

....#.........##.##.#.#.##.#####..#...#........####.##...##....#...#.....#...#.#.#..........#.....#.

.#.#.....#..#....#........#.#.###.....#...#.#.........#......#....#.#........##.##..#.##.#...#....##

.##.#..#...##...#######....#.##.###..........##....##..#..##.##.##...#....#...####...#.#.#...###.#..

....#....#....#.##.#.....#...#...#.....#..#.####........#.#..##...#....#..##....#.#...#........#....

##...###.#...#.#.#.....#.......##.##....#..#..#.#.#..#..#.###...#.#.....#..#.##.##..#.#..#.#......#.

#.#.##.....#......#......#..#.##......###.##.....#.#..##....#...#.#..#........###.#...###......#.#..

#...##.#....#....#....#.....#...##.##.#....#.....#....#.....#....#....#..#....####.........#....#...

..#..##.#....#.#######..#...#.......#.#.##.#.....#...#....##.###..........#..#.#....#....#..##.##...

......#.#.#.........#.....#..#..##.....##.......#.#.#....#####.#..#...##.......#...###...#..#..##.##

#.#.#..........#......#...#...#.#.........#......##..###...........##...####..##.#..#.......#.....##

........#.#..............#.#.#.##....#.....##....#.....#.....#...#........#....######.#..###........

......#.......#...#..#.#...#.....##...#.#..####.........##..##.......#...##...#..####.#..#.#....#..#

.......#....#.#.#...##.##...##........#...#........#..#.#..#.##...#......####......#......#.........

###..#....##...#..#..#..#......#..#.#......#..####.##.....####.#...#..##...#...##...##...#...#....#.

.##......#....######.#.....#......##.#...#.##.##..##............####..###........#.#...#..#..#.##...

#..##....#.#.......###..#.......#.#..#.#.#.##.....#.....#....#...##........#.#......#.#.....#....##.

#.....#....#.#..#...##.#....#..#.....#.##.......#....##..#.##....#..##..#........#.........#.....###

..##.##...##......#.##...#.#.#.#...#..#...###......##.#...###.......##..........#......#..#..#...##.

#...#..#....#....###.#.......#..##..##.....#......#...........##.....#..###..##..#.#.....#..###..#..

..#..#..#.##....##...#....#......##.#...##..#....#.##....###.#....#......##.....#..#...#...##.......

...#...#..#..#..#...###..#..##............#...##...#.#.....##.#.....#.......#.##..#......#.....##...

..#....#........#.#...#....#..#.......#..#.....#.#....#.........#...###.....##.##.##.....##.#.....#.

.#.#..##...#.##..#..#.##.#..#...##........#.#.#....#..#.#..#....#..#..#..##.#.......##....###....##.

...#..##..#.##..#...#..##.#.#........#.....#.#.....#.##.###......#..###....##....#....#.##....#..###

.......#....####...#.....#..##...#...#..#....#.##.#.#....#..#...#.........##.#..##.......#.....##...

###..#...#.#..##...##..##.##.#.#.....#....#......#........#......#.....#........#..#..........#.#.#.

#...#....#...####....#..#..#...#.#...#.#.##....#...#...#...#...#.#.#..#...#.#..#....#.#.....##.#....

...#..##..##.....#.#..#..#.##.##.#..#....#..#......#.##.....#.....#.........#...###.##.....#...###..

..#.####...#.#....#.##...#.......#.....###......#..##......###.##...##...#...##......#.#..#.#..#....

##.##.#.##.#......#..#.......#....#........#.#.##.....##...##.#.....#..#....#..#.##.#...#..###..#.#.

....####.....#.....#.##.#.#..##...##.##.#.#...##.#..#..#....#...#.#..#....##...###...#..##.#..#...##

.#..#..#.#..#..##.....#.##.......#.#...##..........#..#.##.#.....#....#..#...#.......###..#.#..#.#..

......#.#....#..#.#.......#...#.....#.##..#.#..#.#.#.#.#..##.#...#...#..#...#....##..#.#.#.#....###.

#.#..#.##.#.......#............##.#.#..#.....#...#....##.............#..#.....#.....#.#....#....#...

#.....#.#.........#....##.###.....#..#...##...#.....#...#....#.#...###...####.#...#.#...#...........

.#....#....#.#....##.#..#...##.#...###....#.....##.##..###...#.#.#....#...#...#.....#.#####.#.#.....

##.###....#........#..#....#....##....##.#.#..##..###....#..##....#.#...##....#..#.#.#.#...#.##....#

...#..##.##..........#....#...#....#.##.###.#....#.##....#............#.#..#.##...##...#.#.....#.#.#

#....#....#.#...##......#.#.#....#...##....###...#..#...#...#.###...#....##..#....#..##...#......#..

......#..#......###..###....#....#.#............#.##..##.....#.#...#........#...#...####.....##...#.

.#.#..#...#.......#......#.................#.###.###..#.##...#.#.#......#..#..#.....#..#..####......

#.......#.#...#..#..#..#.#...##.#.#.###.##........#.......#......##...###....#...##...#.....###.....

...#.....#...#..##...#.....###......#....#....#.....##.#........###.....#....#.....###...#.#....##..

........###.........#.....#.#..#.#.###..###.......#.###.....#.#..##..##.......#.#.#..##.#..#.#..#.#.

.#..#.....#.##.####.........#......####...##..#.......#..#...##.#............#.#......##....##.##..#

..#..#.#...#......##.....###...#....#.#.##....#..##.#.#..#..#..#........#....#...#..#....#...##...#.

#..#.#..#......#.#..#..#.###....#....#...#.#..#.....##..#...#.#.#.#....#...#.........#...####.#..##.

..#....##.#..#.#.....#..#........#....#.#.#.#...#####.......#.##....#.#.#..##...#...##.....#.#.#..#.

#..#.###......##..........#..........####..##.#..#.#..#.......#..#....#.##..#.#....#..#.....#...####

#.#.#..........#####.#....##...#........##.##.#.#..#.#..#.#.##............#.##.#....#.#..#...#.#....

.....##..#.#..##....#...##...........#.#..#........###.#........#..###.#......##.##..####..##.....#.

#....#....##................#.....###....#...#####............#...##....#...#.#.#......##..#..#.....

.................#.........##..##..............#.#...#....#.##.#.#..#...#...#.##...........#...##...

#....#.#......#.#..#.#...##........##.###....#...#.#....#.#....#......#.#.#.#.#.....#.............##

.##.##...#.....#..#.....#.#..##....#..#.....#..#.....##.......#.##..#.....##.#.#..#...##.........###

###..#..............#.##....#..#.#..###...#.###..##......#..##.##...#...#.#..#..#.##...###.#...#....

.......#....#.#..#.#.....###.......#.#..##..#..#......##.#..#.#....##..#......#........#......#..##.

.#.#....#..#....#....#.#.#...#..#...#.#..#....##...##....#.#####.#..##......#..##...##.#....#..#....

.#......#....#..#.....##..#..##...#....#...#..##.#..#..##.............####.##.#.........#.##.#....#.

#..##.......#..##...#..#.###..#..#....##..###.###..###..#....................##.....#.#..#..#.#.....

#.###.#.#..#.....###.#.##...#.#....#...#.#..#.###.##.##.#.##..#..#......................##.##....#..

.......#................#....#....#...#.........#.#.#..###.#...###.....#............#..#............

............##..##...#.......#..#..##.....#..#.....###..#.####..#.....##.....##.#.#..#..#.##.#.....#

......#..###.......#...#..#..#.....#....#..........#....................#.#..#..#.##....#....###....

..#..#.......#....#..##..#.#..####.#..#.#......###...##...#..#........#.....##.#.#.#............##.#

..##.#.#......##.....#.#.#...##..#........#.##....#......#.....#.#.#..##..#..#......#...#.......##..

...##..##.#...#...#........#.#..##......##.#....#...#..#..##....#....#.##..#....#..#..#.....##.##..#

.........#..........#..#....#.#......#.##....#..##...##...#.##...##..#.##.........#...#.#...#...#...

##.......##.#.#.#.#....##..#......##..##....#.....##.##.###...##.#..#...##..##.#.....#..#.#..#..##..

#.#.....##.....#.....##..##..#.#...#.....#.#..##.......#......##.#...#.#.......##.##.....#....#.####

.........##...##..................##...#...##...##..#.#..#..#..........#.#.........#.....###..#..#..

....###.##.........##.##..............##.#...#.#..#.#...#...#..#.##........#...#.#.............#....

..#..##..#.#.......#.###...#...#.#...##.#........#.....#.##.#.........#..#.....#...##...#....##...#.

#....####.##...#.###.....##.#.####.#.#...#....#............#..#...#.........#.....#...#...........##

.#......#....#.......#..#...##....#.#.##.#..#.#........##.#..#.#......#...#.#..##........#...#....#.

....#....#.....#..##...##..#..#..#....#.#..#...#......###.......#.......###.........##.#...###.###..

..##...#...##.#...#.#...##....#....#..........#.##.....#.#...#.....#..#...##.####...##..#.##.#...##.

.......#.##......#..#.#.......##....#..##..#....#.###.#...#.#.#...#.#..#.##..#..##.#.....#...###.#..

#.........#.#....###.......##..........#..#...#####......#....#...#.#.#.###.#.#.####..#...#.........

####..#.###..#.#....#..#...#..#...##..##..#....#.#....##.....##.......##....#.#....#.##.......#.....

##.........#......#....#.....#.##...#....#.....###...##..##.#.#........####.....#..#.#####...#...##.

...#....#......#.#.......#....#.....#.#.........#.#...##...##....##.#.#.....#....###....###...#..#..

#.#........#..#.##...#..#.....#..#...#..##.##....#.#.####.#.......#....##..#.#....#..#..............

............#.##...#....###...#.#...........#.#..#.......#....#........###..#..#...###..###..#.###..

.#..####..#..#......#...##..#....#..#....#....#......#.......##......#...##..#....#.#..#..#..#...##.

#..#...##.##.##.#.#....#......#.....#.........##....#..........####.....#..#.###..#....###..#.#.#.#.

##..##..##.....#.####......##....#...#.....#..##..##......#.#.#.#...........#.....#..#.#.#.........#

.##....##...........##........#.........##......#..#.#...#........#.#.##.##..#........#...#........#

.#..#......#..........###.#..##.#.#......#...###.....##...#..##....####......#......................

...#...#..#.#..#..#...#....###.##.#.........#...#.##....#.#..##.#.....#....#.....##....#.##.##......

.##........#.......##...#....##.#.###.#.#.....#..#.....##..#.#.....###......#..#...#...#........#..#

.........#....................#..##....#.#...#..#..#...#.........#.....#..##.....#.#.##..#...#...#..

#.....##....#.....#..#...#....##..#...##........#.##.#....#.##..#...........##..##.#.#...#..###....#

....#.##..#.#...#..##..............#..#..##..........##....#..##..#....#####..###..##...#.##.##..#..

[出力例]

■参照サイト
AtCoder Beginner Contest 129

C++の練習を兼ねて, AtCoder Beginner Contest 126 の 問題F (F – XOR Matching) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 126 の 問題E (E – 1 or 2) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 133 の 問題D (D – Rain Flows into Dams) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 131 の 問題F (F – Must Be Rectangular!) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 131 の 問題E (E – Friendships) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 126 の問題F (F – XOR Matching) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 126 の問題E (E – 1 or 2) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 133 の問題D (D – Rain Flows into Dams) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 131 の問題F (F – Must Be Rectangular!) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 131 の問題E (E – Friendships) を解いてみた.

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

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