5月, 2020 | 個人用メモ帳

2020年5月9日

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

C++の練習を兼ねて, AtCoder Regular Contest 032 の問題A (A – ホリドッグ) ～問題B (B – 道路工事) を解いてみた.

■感想.
1. 問題Bは, 連結成分を確認する点で, AtCoder Regular Contest 031 の問題B (B – 埋め立て) に, 似ているように思った.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int n;
    scanf("%d", &n);
    
    // 2. 出力.
    printf("%s\n", (n == 2) ? "WANWAN" : "BOWWOW");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int n;

scanf("%d", &n);

// 2. 出力.

printf("%s\n", (n == 2) ? "WANWAN" : "BOWWOW");

return 0;

}

[入力例]
2

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

[入力例]
5

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

[入力例]
1

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

[入力例]
999

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

[入力例]

[出力例]

WANWAN

※AtCoderのテストケースより

[入力例]

[出力例]

BOWWOW

※AtCoderのテストケースより

[入力例]

[出力例]

BOWWOW

※AtCoderのテストケースより

[入力例]

999

[出力例]

BOWWOW

※AtCoderのテストケースより

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

#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<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
const int MAX = 101010;
int connection[MAX]; // 連結成分番号.
vvi G(MAX);          // 交通情報.

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

int main(){
    
    // 1. 入力情報.
    int N, M, a, b;
    scanf("%d %d", &N, &M);
    rep(i, M){
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 各頂点に対する連結成分番号を設定.
    int id = 0;
    rep(i, N) if(connection[i] == 0) bfs(G, i, ++id);
    // rep(i, N) printf("i=%d con=%d\n", i, connection[i]);
    
    // 3. 連結成分番号の最大値.
    int ans = 0;
    rep(i, N) ans = max(ans, connection[i]);
    
    // 4. 出力.
    printf("%d\n", ans - 1);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<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

const int MAX = 101010;

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

vvi G(MAX); // 交通情報.

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

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

// ※bfsの動作確認用.

// @param G: グラフ.

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

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

// @return: 特に無し.

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

// 1. 空のキュー.

queue<int> q;

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

connection[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(connection[e] > 0) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int N, M, a, b;

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

rep(i, M){

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

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

int id = 0;

rep(i, N) if(connection[i] == 0) bfs(G, i, ++id);

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

// 3. 連結成分番号の最大値.

int ans = 0;

rep(i, N) ans = max(ans, connection[i]);

// 4. 出力.

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

return 0;

}

[入力例]
4 2
1 2
1 3

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

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

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

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

[出力例]
0

[入力例]
5 0

[出力例]
4

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

[出力例]
2

[入力例]

4 2

1 2

1 3

[出力例]

※AtCoderのテストケースより

[入力例]

6 4

1 2

2 3

1 3

5 6

[出力例]

※AtCoderのテストケースより

[入力例]

5 8

1 2

2 3

3 4

4 5

5 1

4 1

3 1

5 2

[出力例]

[入力例]

5 0

[出力例]

[入力例]

10 9

1 2

2 7

7 1

3 4

4 10

10 9

9 8

8 3

5 6

[出力例]

■参照サイト
AtCoder Regular Contest 031
AtCoder Regular Contest 032

2020年5月8日

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

C++の練習を兼ねて, AtCoder Regular Contest 030 の問題A (A – 閉路グラフ) ～問題B (B – ツリーグラフ) を解いてみた.

■感想.
1. 問題Bは, AtCoder Regular Contest 028 の問題C (C – 高橋王国の分割統治) に, 木dp の更新式が若干異なる感じで, 似ているように思った.
2. 木dp の訓練が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 出力.
    printf("%s\n", (K <= N / 2) ? "YES" : "NO");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 出力.

printf("%s\n", (K <= N / 2) ? "YES" : "NO");

return 0;

}

[入力例]
6
2

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

[入力例]
3
2

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

[入力例]
11
6

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

[入力例]
11
5

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

[入力例]

[出力例]

YES

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

YES

※AtCoderのテストケースより

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

// C++14 (GCC 5.4.1)
#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
const int LIMIT = 111;
int h[LIMIT];  // 宝石の情報.
int d[LIMIT];  // 頂点 x からの 距離 を 保存.
int dp[LIMIT]; // 部分木に含まれる経路数(木dp).

// グラフを幅優先探索する.
// 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. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    d[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. 訪問済であれば, 処理をスキップ.
            if(d[e] > 0)            continue;
            if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int n, x, a, b;
    scanf("%d %d", &n, &x);
    x--;
    rep(i, n) scanf("%d", &h[i]);
    vvi G(n);
    rep(i, n - 1){
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 頂点 x から 各頂点までの距離を計算.
    bfs(G, x, d);
    
    // 3. 頂点 x から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, n) pq.push({d[i], i}); // {距離, 頂点番号}
    
    // 4. 木dp.
    while(!pq.empty()){
        // 4-1. 頂点 v を一つ取り出す.
        P p = pq.top();
        pq.pop();
        
        // 4-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 4-3. 頂点 v を 根とする部分木に含まれる 経路数 を 集計.
        for(auto &u : G[v]){
            // 頂点 v の 子頂点 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                // 頂点 v の 周囲 の 頂点 u で, 頂点 x から, より遠いものを確認し, 子頂点 u までの経路数を加算.
                dp[v] += dp[u];
                // 子頂点 u を 根とする部分木 に 宝石が含まれる場合は, 1 を 加算.
                if(dp[u] || h[u]) dp[v]++;
            }
        }
    }
    // rep(i, n) printf("%d ", h[i]);
    // puts("");
    // rep(i, n) printf("%d ", dp[i]);
    // puts("");
    // rep(i, n) printf("%d ", d[i]);
    // puts("");
    
    // 5. 出力.
    printf("%d\n", dp[x] * 2);
    return 0;

}

100

101

102

103

// C++14 (GCC 5.4.1)

#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

const int LIMIT = 111;

int h[LIMIT]; // 宝石の情報.

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

int dp[LIMIT]; // 部分木に含まれる経路数(木dp).

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

// 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. 訪問済みフラグ設定.

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

d[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. 訪問済であれば, 処理をスキップ.

if(d[e] > 0) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int n, x, a, b;

scanf("%d %d", &n, &x);

x--;

rep(i, n) scanf("%d", &h[i]);

vvi G(n);

rep(i, n - 1){

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

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

bfs(G, x, d);

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

priority_queue pq;

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

// 4. 木dp.

while(!pq.empty()){

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

P p = pq.top();

pq.pop();

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

int v = p.b;

// 4-3. 頂点 v を根とする部分木に含まれる経路数を集計.

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

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

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

// 頂点 v の周囲の頂点 u で, 頂点 x から, より遠いものを確認し, 子頂点 u までの経路数を加算.

dp[v] += dp[u];

// 子頂点 u を根とする部分木に宝石が含まれる場合は, 1 を加算.

if(dp[u] || h[u]) dp[v]++;

}

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

// puts("");

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

// puts("");

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

// puts("");

// 5. 出力.

printf("%d\n", dp[x] * 2);

return 0;

}

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

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

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

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

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

[出力例]
10

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

[出力例]
16

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

[出力例]
12

[入力例]

5 1

1 0 1 0 1

1 2

2 3

2 4

1 5

[出力例]

※AtCoderテストケースより

[入力例]

3 2

0 1 0

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

8 1

1 0 1 1 1 0 1 0

5 6

1 5

2 4

2 1

3 2

7 4

8 4

[出力例]

[入力例]

13 1

1 1 1 0 0 1 0 1 0 0 1 0 1

13 8

12 8

8 11

9 6

6 10

8 4

7 4

2 4

2 3

6 5

5 1

2 1

[出力例]

[入力例]

11 3

0 0 1 0 0 0 1 0 0 1 0

11 8

8 10

9 2

2 8

7 6

6 5

3 5

2 3

1 3

4 3

[出力例]

■参照サイト
AtCoder Regular Contest 030
AtCoder Regular Contest 028

2020年5月6日2020年5月6日

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

C++の練習を兼ねて, AtCoder Regular Contest 028 の問題C (C – 高橋王国の分割統治) を解いてみた.

■感想.
1. 本問は, AtCoder Beginner Contest 160 の問題F (F – Distributing Integers) に, どことなく似ている感じがした.
2. 木dp の訓練が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#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
const int LIMIT = 101010;
int d[LIMIT];    // 頂点 0 からの 距離 を 保存.
int size[LIMIT]; // 木の大きさ.
int dp[LIMIT];   // 木dp.

// グラフを幅優先探索する.
// 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. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    d[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. 訪問済であれば, 処理をスキップ.
            if(d[e] > 0)            continue;
            if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, p;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        scanf("%d", &p);
        G[i + 1].pb(p);
        G[p].pb(i + 1);
    }
    
    // 2. 事前計算.
    rep(i, LIMIT) size[i] = 1;
    
    // 3. 頂点 0 から 各頂点までの距離を計算.
    bfs(G, 0, d);
    
    // 4. 頂点 0 から 遠い順 に並び替え.
    priority_queue<P> pq1, pq2;
    rep(i, N){
        // {距離, 頂点番号}
        pq1.push({d[i], i});
        pq2.push({d[i], i});
    }
    
    // 5. 部分木のサイズを取得.
    while(!pq1.empty()){
        // 5-1. 頂点 v を一つ取り出す.
        P p = pq1.top();
        pq1.pop();
        
        // 5-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 5-3. 頂点 v を 根とする部分木 の サイズ を 集計.
        for(auto &u : G[v]){
            // 頂点 v の 子頂点 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                // 頂点 v の 周囲 の 頂点 u で, 頂点 0 から, より遠いものを加算.
                size[v] += size[u];
            }
        }
    }
    
    // 6. 木dp.
    while(!pq2.empty()){
        // 6-1. 頂点 v を一つ取り出す.
        P p = pq2.top();
        pq2.pop();
        
        // 6-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 6-3. 木dp の 更新.
        for(auto &u : G[v]){
            if(d[u] < d[v]) dp[v] = max(dp[v], N - size[v]); // 頂点 u は, 頂点 v の 親頂点.
            else            dp[v] = max(dp[v], size[u]);     // 頂点 u は, 頂点 v の 子頂点.
        }
    }
    
    // 7. 出力.
    rep(i, N) printf("%d\n", dp[i]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#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

const int LIMIT = 101010;

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

int size[LIMIT]; // 木の大きさ.

int dp[LIMIT]; // 木dp.

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

// 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. 訪問済みフラグ設定.

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

d[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. 訪問済であれば, 処理をスキップ.

if(d[e] > 0) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int N, p;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

scanf("%d", &p);

G[i + 1].pb(p);

G[p].pb(i + 1);

}

// 2. 事前計算.

rep(i, LIMIT) size[i] = 1;

// 3. 頂点 0 から各頂点までの距離を計算.

bfs(G, 0, d);

// 4. 頂点 0 から遠い順に並び替え.

priority_queue pq1, pq2;

rep(i, N){

// {距離, 頂点番号}

pq1.push({d[i], i});

pq2.push({d[i], i});

}

// 5. 部分木のサイズを取得.

while(!pq1.empty()){

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

P p = pq1.top();

pq1.pop();

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

int v = p.b;

// 5-3. 頂点 v を根とする部分木のサイズを集計.

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

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

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

// 頂点 v の周囲の頂点 u で, 頂点 0 から, より遠いものを加算.

size[v] += size[u];

}

// 6. 木dp.

while(!pq2.empty()){

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

P p = pq2.top();

pq2.pop();

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

int v = p.b;

// 6-3. 木dp の更新.

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

if(d[u] < d[v]) dp[v] = max(dp[v], N - size[v]); // 頂点 u は, 頂点 v の親頂点.

else dp[v] = max(dp[v], size[u]); // 頂点 u は, 頂点 v の子頂点.

}

// 7. 出力.

rep(i, N) printf("%d\n", dp[i]);

return 0;

}

[入力例]
5
0
1
1
0

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

[入力例]
3
0
0

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

[入力例]
25
0
1
0
0
1
5
5
2
2
9
9
0
12
12
7
7
7
16
16
16
17
17
10
10
24

[出力例]
19
11
18
24
24
14
24
16
24
20
22
24
22
24
24
24
21
22
24
24
24
24
24
24
24

[入力例]
30
0
0
0
0
1
1
1
5
5
6
7
7
2
13
14
14
13
3
3
4
4
21
21
22
22
22
24
24
21

[出力例]
11
21
24
27
19
27
28
27
29
29
29
29
29
25
27
29
29
29
29
29
29
21
24
29
27
29
29
29
29
29

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

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

■参照サイト
AtCoder Regular Contest 028
AtCoder Beginner Contest 160

2020年5月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 028 の問題A (A – 小石を取るゲーム) ～問題B (B – 特別賞) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, A, B;
    scanf("%d %d %d", &N, &A, &B);
    
    // 2. 小石を取っていく.
    int res = N % (A + B);
    bool ans = (res > 0 && res <= A);
    
    // 3. 出力.
    printf("%s\n", ans ? "Ant" : "Bug");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N, A, B;

scanf("%d %d %d", &N, &A, &B);

// 2. 小石を取っていく.

int res = N % (A + B);

bool ans = (res > 0 && res <= A);

// 3. 出力.

printf("%s\n", ans ? "Ant" : "Bug");

return 0;

}

[入力例]
5 1 2

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

[入力例]
10 3 4

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

[入力例]
1 1 1

[出力例]
Ant

[入力例]
2 1 1

[出力例]
Bug

[入力例]
314 15 9

[出力例]
Ant

[入力例]
2718 28 182

[出力例]
Bug

[入力例]
14142 13 562

[出力例]
Ant

[入力例]
1202056 903 159

[出力例]
Bug

[入力例]

5 1 2

[出力例]

Bug

※AtCoderのテストケースより

[入力例]

10 3 4

[出力例]

Ant

※AtCoderのテストケースより

[入力例]

1 1 1

[出力例]

Ant

[入力例]

2 1 1

[出力例]

Bug

[入力例]

314 15 9

[出力例]

Ant

[入力例]

2718 28 182

[出力例]

Bug

[入力例]

14142 13 562

[出力例]

Ant

[入力例]

1202056 903 159

[出力例]

Bug

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

// C++14 (GCC 5.4.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 pb push_back
#define a first
#define b second
int x[101010]; // {順位, 年齢}

int main(){
    
    // 1. 入力情報.
    int N, K;
    priority_queue<P> pq1;
    priority_queue<P, vector<P>, greater<P> > pq2;
    scanf("%d %d", &N, &K);
    rep(i, N){
        scanf("%d", &x[i]);
        if(i < K - 1) pq1.push({x[i], i + 1}); // (K - 1)番目までの{年齢, 順位}
    }
    
    // 2. K番目に若い人は？
    rep(i, N - K + 1){
        // 2-1. 順位が, (i + K)位 の 参加者情報を取得.
        P cur = {x[i - 1 + K], i + K};
        pq1.push(cur);
        
        // 2-2. 取り出す.
        P p, q;
        int rank = 0;
        if(pq1.size() > K){
            p = pq1.top(); // (K + 1)番目
            pq1.pop();     // pq1 から 削除.
            pq2.push(p);   // pq2 へ 移動.
            p = pq1.top(); // K番目
            q = pq2.top(); // (K + 1)番目
            if(p.a > q.a){
                rank = q.b;
                pq1.pop();   // pq1 から 削除.
                pq2.pop();   // pq2 から 削除.
                pq1.push(q); // pq1 へ 追加.
                pq2.push(p); // pq2 へ 追加.
                // printf("1. p.a=%d p.b=%d q.a=%d q.b=%d\n", p.a, p.b, q.a, q.b);
            }else{
                rank = p.b;
                // printf("2. p.a=%d p.b=%d q.a=%d q.b=%d\n", p.a, p.b, q.a, q.b);
            }
        }else{
            p = pq1.top(); // K番目
            rank = p.b;
            // printf("3. p.a=%d p.b=%d\n", p.a, p.b);
        }
        
        // 2-3. 出力.
        printf("%d\n", rank);
    }
    return 0;
    
}

// C++14 (GCC 5.4.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 pb push_back

#define a first

#define b second

int x[101010]; // {順位, 年齢}

int main(){

// 1. 入力情報.

int N, K;

priority_queue pq1;

priority_queue<P, vector, greater > pq2;

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

rep(i, N){

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

if(i < K - 1) pq1.push({x[i], i + 1}); // (K - 1)番目までの{年齢, 順位}

}

// 2. K番目に若い人は？

rep(i, N - K + 1){

// 2-1. 順位が, (i + K)位の参加者情報を取得.

P cur = {x[i - 1 + K], i + K};

pq1.push(cur);

// 2-2. 取り出す.

P p, q;

int rank = 0;

if(pq1.size() > K){

p = pq1.top(); // (K + 1)番目

pq1.pop(); // pq1 から削除.

pq2.push(p); // pq2 へ移動.

p = pq1.top(); // K番目

q = pq2.top(); // (K + 1)番目

if(p.a > q.a){

rank = q.b;

pq1.pop(); // pq1 から削除.

pq2.pop(); // pq2 から削除.

pq1.push(q); // pq1 へ追加.

pq2.push(p); // pq2 へ追加.

// printf("1. p.a=%d p.b=%d q.a=%d q.b=%d\n", p.a, p.b, q.a, q.b);

}else{

rank = p.b;

// printf("2. p.a=%d p.b=%d q.a=%d q.b=%d\n", p.a, p.b, q.a, q.b);

}

}else{

p = pq1.top(); // K番目

rank = p.b;

// printf("3. p.a=%d p.b=%d\n", p.a, p.b);

}

// 2-3. 出力.

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

}

return 0;

}

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

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

[入力例]
3 1
2 3 1

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

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

[出力例]
2
4
4
6
9
9
9
3
3
3
3
3
3
3
12
12

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

[出力例]
6
8
3
2
2
5
5
1
14
14
9
9
9
9
12
12
12
12
12
12
17
17
17
27

[入力例]

5 2

4 5 3 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

3 1

2 3 1

[出力例]

※AtCoderのテストケースより

[入力例]

20 5

2 16 6 10 1 9 13 4 8 12 19 5 17 11 20 7 18 14 3 15

[出力例]

[入力例]

30 7

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

[出力例]

■参照サイト
AtCoder Regular Contest 028

2020年5月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 166 の問題E (E – This Message Will Self-Destruct in 5s) を解いてみた.

■感想.
1. 式変形を使って, 数え上げの回数を減らすことが出来たので, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#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--)
LL a[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. a[j] - j を 保存.
    // -> i < j と 仮定して, j - i = a[j] + a[i] とすると, 
    // -(a[i] - i) - 2 * i = (a[j] - j) と 変形できる.
    map<LL, LL> m;
    rep(j, N){
        LL b = a[j] - j;
        m[b]++;
    }
    
    // 3. 条件を満たすペアを検索.
    LL ans = 0;
    rep(i, N){
        LL b = -(a[i] - i) - 2 * i;
        if(m.count(b)) ans += m[b];
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

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

LL a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. a[j] - j を保存.

// -> i < j と仮定して, j - i = a[j] + a[i] とすると,

// -(a[i] - i) - 2 * i = (a[j] - j) と変形できる.

map<LL, LL> m;

rep(j, N){

LL b = a[j] - j;

m[b]++;

}

// 3. 条件を満たすペアを検索.

LL ans = 0;

rep(i, N){

LL b = -(a[i] - i) - 2 * i;

if(m.count(b)) ans += m[b];

}

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
54

[入力例]
300
150 13 144 128 198 138 130 129 221 203 42 20 127 62 177 228 194 26 211 216 27 34 196 170 132 230 162 159 105 144 174 148 197 82 207 63 231 66 191 84 172 214 25 73 136 30 114 68 80 53 214 5 156 152 131 161 15 193 30 53 174 94 25 25 143 94 13 9 91 4 32 199 192 31 6 96 64 61 153 209 108 160 134 211 199 19 42 59 203 160 14 203 99 78 178 90 50 215 90 141 124 53 145 43 23 171 10 116 189 152 11 115 104 3 80 117 4 199 64 194 116 125 42 58 230 182 72 207 65 126 1 197 54 128 58 46 6 222 72 201 82 36 97 79 118 186 139 215 83 224 30 192 163 199 103 161 178 127 66 39 52 108 158 14 81 21 40 41 64 66 116 32 149 82 111 207 73 65 3 224 62 45 185 80 209 125 185 198 54 91 216 33 216 220 24 82 179 177 84 65 86 181 182 26 35 55 95 71 48 152 122 142 93 122 83 215 219 172 222 221 163 127 102 220 7 143 101 196 191 49 209 125 2 196 9 155 36 108 177 92 103 155 120 40 179 231 211 119 125 47 195 131 57 74 192 5 211 4 228 58 196 3 88 164 42 125 233 103 219 153 229 168 193 227 146 100 224 172 231 187 140 151 143 76 59 52 41 163 175 77 146 177 161 18 27 233 227 33 195 7

[出力例]
70

[入力例]

2 3 3 1 3 1

[出力例]

※AtCoderテストケースより

[入力例]

5 2 4 2 8 8

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

[出力例]

※AtCoderテストケースより

[入力例]

100

23 48 2 36 20 33 2 42 19 34 26 14 12 43 29 2 5 49 3 8 2 29 31 22 31 7 42 42 34 18 6 10 35 19 33 41 27 13 34 22 4 34 13 7 39 34 3 29 24 39 9 36 19 5 26 26 10 6 3 2 38 45 20 50 14 43 27 43 44 11 1 13 2 38 31 11 2 23 42 39 16 33 39 32 24 47 32 10 27 12 4 32 16 2 32 12 21 30 14 29

[出力例]

[入力例]

300

150 13 144 128 198 138 130 129 221 203 42 20 127 62 177 228 194 26 211 216 27 34 196 170 132 230 162 159 105 144 174 148 197 82 207 63 231 66 191 84 172 214 25 73 136 30 114 68 80 53 214 5 156 152 131 161 15 193 30 53 174 94 25 25 143 94 13 9 91 4 32 199 192 31 6 96 64 61 153 209 108 160 134 211 199 19 42 59 203 160 14 203 99 78 178 90 50 215 90 141 124 53 145 43 23 171 10 116 189 152 11 115 104 3 80 117 4 199 64 194 116 125 42 58 230 182 72 207 65 126 1 197 54 128 58 46 6 222 72 201 82 36 97 79 118 186 139 215 83 224 30 192 163 199 103 161 178 127 66 39 52 108 158 14 81 21 40 41 64 66 116 32 149 82 111 207 73 65 3 224 62 45 185 80 209 125 185 198 54 91 216 33 216 220 24 82 179 177 84 65 86 181 182 26 35 55 95 71 48 152 122 142 93 122 83 215 219 172 222 221 163 127 102 220 7 143 101 196 191 49 209 125 2 196 9 155 36 108 177 92 103 155 120 40 179 231 211 119 125 47 195 131 57 74 192 5 211 4 228 58 196 3 88 164 42 125 233 103 219 153 229 168 193 227 146 100 224 172 231 187 140 151 143 76 59 52 41 163 175 77 146 177 161 18 27 233 227 33 195 7

[出力例]

■参照サイト
AtCoder Beginner Contest 166

2020年5月4日2020年5月4日

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

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

■感想.
1. A, B について, 確認する必要のある範囲を絞り込めたので, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#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 X;
    scanf("%lld", &X);
    
    // 2. A, B を 求める.
    // 上限は, 1019663401 = 120 * 120 * 120 * 120 * 120 - 119 * 119 * 119 * 119 * 119
    int A = 0, B = 0;
    repx(i, -120, 121){
        repx(j, -120, 121){
            LL a = (LL)j;
            LL b = (LL)i;
            if(a * a * a * a * a - b * b * b * b * b == X){
                A = j;
                B = i;
                break;
            }
        }
    }
    
    // 3. 出力.
    assert(!(A == 0 && B == 0));
    printf("%d %d\n", A, B);
    return 0;
    
}

#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 X;

scanf("%lld", &X);

// 2. A, B を求める.

// 上限は, 1019663401 = 120 * 120 * 120 * 120 * 120 - 119 * 119 * 119 * 119 * 119

int A = 0, B = 0;

repx(i, -120, 121){

repx(j, -120, 121){

LL a = (LL)j;

LL b = (LL)i;

if(a * a * a * a * a - b * b * b * b * b == X){

A = j;

B = i;

break;

}

// 3. 出力.

assert(!(A == 0 && B == 0));

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

return 0;

}

[入力例]
33

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

[入力例]
1

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

※上記のプログラムだと以下のように出力される.
1 0

[入力例]
464148982

[出力例]
55 33

[入力例]
2705364300

[出力例]
77 17

[入力例]
373767689

[出力例]
52 23

[入力例]

[出力例]

2 -1

※AtCoderテストケースより

[入力例]

[出力例]

0 -1

※AtCoderテストケースより

※上記のプログラムだと以下のように出力される.

1 0

[入力例]

464148982

[出力例]

55 33

[入力例]

2705364300

[出力例]

77 17

[入力例]

373767689

[出力例]

52 23

■参照サイト
AtCoder Beginner Contest 166

2020年5月4日

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

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

■感想.
1. 方針が全く分からなかったので, 解説を確認して, 実装したところ, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc165/editorial.pdf
#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. 解説通り.
    if(M & 1){
        rep(i, M / 2)     printf("%d %d\n", i + 1, M - i);
        rep(i, M / 2 + 1) printf("%d %d\n", M + 1 + i, 2 * M + 1 - i);
    }else{
        rep(i, M / 2) printf("%d %d\n", i + 1, M + 1 - i);
        rep(i, M / 2) printf("%d %d\n", M + 2 + i, 2 * M + 1 - i);
    }
    return 0;
    
}

// 解き直し.

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

#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. 解説通り.

if(M & 1){

rep(i, M / 2) printf("%d %d\n", i + 1, M - i);

rep(i, M / 2 + 1) printf("%d %d\n", M + 1 + i, 2 * M + 1 - i);

}else{

rep(i, M / 2) printf("%d %d\n", i + 1, M + 1 - i);

rep(i, M / 2) printf("%d %d\n", M + 2 + i, 2 * M + 1 - i);

}

return 0;

}

[入力例]
4 1

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

[入力例]
7 3

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

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

[入力例]
6 2

[出力例]
1 3
4 5

[入力例]
12 4

[出力例]
1 5
2 4
6 9
7 8

[入力例]

4 1

[出力例]

2 3

※AtCoderテストケースより

[入力例]

7 3

[出力例]

1 6

2 5

3 4

※AtCoderテストケースより

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

1 3

4 7

5 6

[入力例]

6 2

[出力例]

1 3

4 5

[入力例]

12 4

[出力例]

1 5

2 4

6 9

7 8

■参照サイト
AtCoder Beginner Contest 165

2020年5月3日

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

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

■感想.
1. 方針が全く分からなかったので, 解説を確認して, 実装したところ, 何とかAC版となった.
2. ただし, 木dp, 全方位木dp という馴染みのないものを実装することになったため, 非常に苦労したものの, 新しい知識が増えたので良かったと思う.
3. あと, 幅優先探索の復習も出来たので, 非常に良かったと思った.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// コメント修正して再提出.
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
const LL MOD = 1e9 + 7;
const int LIMIT = 202020;
LL FAC[LIMIT], INV[LIMIT];
int d[LIMIT];    // 頂点 1 からの 距離 を 保存.
int size[LIMIT]; // 木の大きさ.
LL dp[LIMIT];    // 木dp.

// グラフを幅優先探索する.
// 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. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    d[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. 訪問済であれば, 処理をスキップ.
            if(d[e] > 0)            continue;
            if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e);
        }
    }
    return;
}

// 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, a, b;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // ※ 以下, 解説通り.
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2);
    rep(i, LIMIT)     size[i] = 1, dp[i] = 1;
    
    // 3. 頂点 1 から 各頂点までの距離を計算.
    bfs(G, 0, d);
    
    // 4. 頂点 1 から 遠い順, 近い順 に並び替え.
    priority_queue<P> fPq;
    priority_queue<P, vector<P>, greater<P>> nPq;
    rep(i, N){
        // {距離, 頂点番号}
        fPq.push({d[i], i});
        nPq.push({d[i], i});
    }
    
    // 5. 木dp.
    while(!fPq.empty()){
        // 5-1. 頂点 v を一つ取り出す.
        P p = fPq.top();
        fPq.pop();
        
        // 5-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 5-3. 頂点 v を 根とする部分木 の サイズ を 集計しながら, 木dp も 更新.
        for(auto &u : G[v]){
            // 頂点 v の 子供 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                // 頂点 v の 周囲 の 頂点 u で, 頂点 1 から, より遠いものを加算.
                size[v] += size[u];
                // 頂点 v の 周囲 の 頂点 u について, 木dp の 更新.
                dp[v] *= dp[u];
                dp[v] %= MOD;
                dp[v] *= INV[size[u]];
                dp[v] %= MOD;
            }
        }
        
        // 5-4. 頂点 v を 根とする部分木 の サイズ を 考慮し, 木dp を 更新.
        dp[v] *= FAC[size[v] - 1];
        dp[v] %= MOD;
    }
    
    // 6. 全方位木dp.
    while(!nPq.empty()){
        // 6-1. 頂点 u を一つ取り出す.
        P p = nPq.top();
        nPq.pop();
        
        // 6-2. 頂点 u の 頂点番号は？
        int u = p.b;
        
        // 6-3. 頂点 u の 周囲の頂点 を見ながら, 自身(u) を 集計.
        LL dpu = dp[u];
        for(auto &v : G[u]){
            // もともと, 頂点 v が 頂点 u の 親頂点 である場合.
            if(d[u] > d[v]){
                // 頂点 v の dp[v] を 再計算.
                dpu *= dp[v];
                dpu %= MOD;
                
                // 頂点 u の 分 を 割り戻す.
                dpu *= mPow(dp[u], MOD - 2);
                dpu %= MOD;
                dpu *= FAC[size[u]];
                dpu %= MOD;
                
                // 頂点 u の 子頂点 を 考慮.
                dpu *= INV[size[u] - 1];
                dpu %= MOD;
                
                // 頂点 v が 子頂点 の 立場 になったので, 再計算.
                dpu *= INV[N - 1];
                dpu %= MOD;
                dpu *= FAC[N - 1 - size[u]];
                dpu %= MOD;
                
                // 頂点 u が 親になるので, 頂点 v が 子頂点 とした場合について 逆元 を 乗ずる.
                dpu *= FAC[N - 1];
                dpu %= MOD;
                dpu *= INV[N - size[u]];
                dpu %= MOD;
            }
        }
        
        // 6-4. 木dp の 更新.
        dp[u] = dpu;
    }
    
    // 7. 出力.
    rep(i, N) printf("%lld\n", dp[i]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

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

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

const LL MOD = 1e9 + 7;

const int LIMIT = 202020;

LL FAC[LIMIT], INV[LIMIT];

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

int size[LIMIT]; // 木の大きさ.

LL dp[LIMIT]; // 木dp.

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

// 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. 訪問済みフラグ設定.

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

d[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. 訪問済であれば, 処理をスキップ.

if(d[e] > 0) continue;

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

}

return;

}

// 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, a, b;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// ※ 以下, 解説通り.

// 2. 事前計算.

FAC[0] = 1;

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

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

rep(i, LIMIT) size[i] = 1, dp[i] = 1;

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

bfs(G, 0, d);

// 4. 頂点 1 から遠い順, 近い順に並び替え.

priority_queue fPq;

priority_queue<P, vector, greater> nPq;

rep(i, N){

// {距離, 頂点番号}

fPq.push({d[i], i});

nPq.push({d[i], i});

}

// 5. 木dp.

while(!fPq.empty()){

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

P p = fPq.top();

fPq.pop();

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

int v = p.b;

// 5-3. 頂点 v を根とする部分木のサイズを集計しながら, 木dp も更新.

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

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

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

// 頂点 v の周囲の頂点 u で, 頂点 1 から, より遠いものを加算.

size[v] += size[u];

// 頂点 v の周囲の頂点 u について, 木dp の更新.

dp[v] *= dp[u];

dp[v] %= MOD;

dp[v] *= INV[size[u]];

dp[v] %= MOD;

}

// 5-4. 頂点 v を根とする部分木のサイズを考慮し, 木dp を更新.

dp[v] *= FAC[size[v] - 1];

dp[v] %= MOD;

}

// 6. 全方位木dp.

while(!nPq.empty()){

// 6-1. 頂点 u を一つ取り出す.

P p = nPq.top();

nPq.pop();

// 6-2. 頂点 u の頂点番号は？

int u = p.b;

// 6-3. 頂点 u の周囲の頂点を見ながら, 自身(u) を集計.

LL dpu = dp[u];

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

// もともと, 頂点 v が頂点 u の親頂点である場合.

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

// 頂点 v の dp[v] を再計算.

dpu *= dp[v];

dpu %= MOD;

// 頂点 u の分を割り戻す.

dpu *= mPow(dp[u], MOD - 2);

dpu %= MOD;

dpu *= FAC[size[u]];

dpu %= MOD;

// 頂点 u の子頂点を考慮.

dpu *= INV[size[u] - 1];

dpu %= MOD;

// 頂点 v が子頂点の立場になったので, 再計算.

dpu *= INV[N - 1];

dpu %= MOD;

dpu *= FAC[N - 1 - size[u]];

dpu %= MOD;

// 頂点 u が親になるので, 頂点 v が子頂点とした場合について逆元を乗ずる.

dpu *= FAC[N - 1];

dpu %= MOD;

dpu *= INV[N - size[u]];

dpu %= MOD;

}

// 6-4. 木dp の更新.

dp[u] = dpu;

}

// 7. 出力.

rep(i, N) printf("%lld\n", dp[i]);

return 0;

}

[入力例]
3
1 2
1 3

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

[入力例]
2
1 2

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

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

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

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

[出力例]
40
280
840
120
120
504
72
72
※AtCoderテストケースより

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

[出力例]
7200
2700
12600
270
270
15120
1512
8640
864
864
864

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

[出力例]
12600
2700
7200
270
270
15120
1512
8640
864
864
864

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

[出力例]
627806444
840488480
156951611
625311831
258203730
982276504
488606323
982276504
930423334
930423334
740986430
930423334
930423334
431390325
381265594
875216061
875216061
876944500
504321101
504321101
733041513
539230173
384807545
742732080
931645289
185683020
185683020
687298118
687298118
742732080

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

[入力例]

1 2

1 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

3 5

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

3 5

3 6

6 7

6 8

[出力例]

280

840

120

504

※AtCoderテストケースより

[入力例]

1 2

2 4

2 5

1 3

3 6

7 6

6 8

8 9

8 10

8 11

[出力例]

7200

2700

12600

270

15120

1512

8640

864

[入力例]

3 2

2 4

2 5

1 3

1 6

7 6

6 8

8 9

8 10

8 11

[出力例]

12600

2700

7200

270

15120

1512

8640

864

[入力例]

1 2

1 3

5 1

4 1

6 2

2 7

2 8

6 9

6 10

7 11

8 12

8 13

3 14

4 19

4 20

14 15

14 18

15 16

15 17

5 21

5 22

22 23

22 24

22 30

23 25

23 26

23 27

25 28

25 29

[出力例]

627806444

840488480

156951611

625311831

258203730

982276504

488606323

982276504

930423334

740986430

930423334

431390325

381265594

875216061

876944500

504321101

733041513

539230173

384807545

742732080

931645289

185683020

687298118

742732080

■参照サイト
AtCoder Beginner Contest 160

2020年5月3日

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

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

■感想.
1. 非負整数 x を何とか抽出できたので, AC版となったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL A, B, N;
    scanf("%lld %lld %lld", &A, &B, &N);
    
    // 2. 非負整数 x を 計算.
    LL x = (N >= B) ? max(B - 1LL, 1LL) : N;
    
    // 3. 最大値を計算.
    LL ans = A * x / B - A * (x / B);
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL A, B, N;

scanf("%lld %lld %lld", &A, &B, &N);

// 2. 非負整数 x を計算.

LL x = (N >= B) ? max(B - 1LL, 1LL) : N;

// 3. 最大値を計算.

LL ans = A * x / B - A * (x / B);

// 4. 出力.

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

return 0;

}

[入力例]
5 7 4

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

[入力例]
11 10 9

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

[入力例]
1 1 1

[出力例]
0

[入力例]
314159 2653589793 23846264338

[出力例]
314158

[入力例]
314159 2653589793 2384626433

[出力例]
282316

[入力例]

5 7 4

[出力例]

※AtCoderテストケースより

[入力例]

11 10 9

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1

[出力例]

[入力例]

314159 2653589793 23846264338

[出力例]

314158

[入力例]

314159 2653589793 2384626433

[出力例]

282316

■参照サイト
AtCoder Beginner Contest 165

2020年5月2日

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

C++の練習を兼ねて, AtCoder Regular Contest 026 の問題C (C – 蛍光灯) を解いてみた.

■感想.
1. 方針が全く分からなかったので, 解説を確認して, 実装したところ, 何とかAC版となった.
2. 遅延評価セグメント木が必要なため, 下記のライブラリを拝借させて頂いた.
3. 遅延評価セグメント木の復習が出来たので, 良かった思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc026
#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
#define all(x) x.begin(), x.end()
#define INF 101010101010
LL dp[101010];

struct light{
    int l, r; // 蛍光灯の左端, 右端.
    LL c;     // 蛍光灯を点灯するのにかかる費用.
    bool operator < (const light& rhs) const{
        if(l != rhs.l) return l < rhs.l;
        else           return r > rhs.r;
    }
};

// ※※※ 以下のライブラリを使用(一部改変) ※※※.
// 遅延評価セグメント木をソラで書きたいあなたに.
// http://tsutaj.hatenablog.com/entry/2017/03/30/224339
// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726
struct LazySegmentTree{
private:
    int n;
    vector<LL> node, lazy;
public:
    LazySegmentTree(vector<LL> v){
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);
        // 元配列 の 値 を, セグメント木のノード に 保存.
        rep(i, sz) node[i + n - 1] = v[i];
        repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }
    void eval(int k, int l, int r){
        if(lazy[k] != 0) {
            node[k] = lazy[k];
            if(r - l > 1) {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void update(int a, int b, LL x, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] = x;
            eval(k, l, r);
        }else{
            update(a, b, x, 2 * k + 1,           l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2,           r);
            node[k] = min(node[2 * k + 1], node[2 * k + 2]);
        }
    }
    LL query(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return INF;
        if(a <= l && r <= b) return node[k];
        LL vl = query(a, b, 2 * k + 1,           l, (l + r) / 2);
        LL vr = query(a, b, 2 * k + 2, (l + r) / 2,           r);
        return min(vl, vr);
    }

};

int main(){
    
    // 1. 入力情報.
    int N, L;
    scanf("%d %d", &N, &L);
    
    // 2. 蛍光灯を保存.
    vector<light> v;
    rep(i, N){
        int l, r;
        LL c;
        scanf("%d %d %lld", &l, &r, &c);
        light x;
        x.l = l + 1, x.r = r + 1, x.c = c;
        v.pb(x);
    }
    
    // 以下, 解説通り.
    // 3. sort.
    sort(all(v));
    
    // 4. 遅延伝播セグメント木を用意.
    LazySegmentTree seg(vector<LL>(101010, 0));
    rep(i, 101010) dp[i] = INF;
    repx(i, 1, 101010) seg.update(i, i + 1, INF);
    
    // 5. dp更新.
    rep(i, N){
        // 蛍光灯の情報を一つ取得.
        int l = v[i].l;
        int r = v[i].r;
        LL c  = v[i].c;
        
        // dp[l] ～ dp[r] の 最小値 を 取得.
        LL tmp = seg.query(l - 1, r);
        
        // dp[r] の 更新.
        dp[r] = min(dp[r], tmp + c);
        
        // SegmentTree の 更新.
        seg.update(r - 1, r, dp[r]);
        
        // printf("l=%d r=%d c=%lld tmp=%lld\n", l, r, c, tmp);
        // rep(i, L + 2) printf("%lld ", seg.query(i, i + 1));
        // puts("");
        // rep(i, L + 2) printf("%lld ", dp[i]);
        // puts("");
    }
    
    // 6. 出力.
    // rep(i, L + 2) printf("%lld ", dp[i]);
    // puts("");
    printf("%lld\n", dp[L + 1]);
    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

// 解き直し.

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

#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

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

#define INF 101010101010

LL dp[101010];

struct light{

int l, r; // 蛍光灯の左端, 右端.

LL c; // 蛍光灯を点灯するのにかかる費用.

bool operator < (const light& rhs) const{

if(l != rhs.l) return l < rhs.l;

else return r > rhs.r;

}

};

// ※※※ 以下のライブラリを使用(一部改変) ※※※.

// 遅延評価セグメント木をソラで書きたいあなたに.

// http://tsutaj.hatenablog.com/entry/2017/03/30/224339

// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726

struct LazySegmentTree{

private:

int n;

vector<LL> node, lazy;

public:

LazySegmentTree(vector<LL> v){

int sz = (int)v.size();

n = 1; while(n < sz) n *= 2;

node.resize(2 * n - 1);

lazy.resize(2 * n - 1, 0);

// 元配列の値を, セグメント木のノードに保存.

rep(i, sz) node[i + n - 1] = v[i];

repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];

}

void eval(int k, int l, int r){

if(lazy[k] != 0) {

node[k] = lazy[k];

if(r - l > 1) {

lazy[2 * k + 1] += lazy[k] / 2;

lazy[2 * k + 2] += lazy[k] / 2;

}

lazy[k] = 0;

}

void update(int a, int b, LL x, int k = 0, int l = 0, int r = -1){

if(r < 0) r = n;

eval(k, l, r);

if(b <= l || r <= a) return;

if(a <= l && r <= b){

lazy[k] = x;

eval(k, l, r);

}else{

update(a, b, x, 2 * k + 1, l, (l + r) / 2);

update(a, b, x, 2 * k + 2, (l + r) / 2, r);

node[k] = min(node[2 * k + 1], node[2 * k + 2]);

}

LL query(int a, int b, int k = 0, int l = 0, int r = -1){

if(r < 0) r = n;

eval(k, l, r);

if(b <= l || r <= a) return INF;

if(a <= l && r <= b) return node[k];

LL vl = query(a, b, 2 * k + 1, l, (l + r) / 2);

LL vr = query(a, b, 2 * k + 2, (l + r) / 2, r);

return min(vl, vr);

}

};

int main(){

// 1. 入力情報.

int N, L;

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

// 2. 蛍光灯を保存.

vector<light> v;

rep(i, N){

int l, r;

LL c;

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

light x;

x.l = l + 1, x.r = r + 1, x.c = c;

v.pb(x);

}

// 以下, 解説通り.

// 3. sort.

sort(all(v));

// 4. 遅延伝播セグメント木を用意.

LazySegmentTree seg(vector<LL>(101010, 0));

rep(i, 101010) dp[i] = INF;

repx(i, 1, 101010) seg.update(i, i + 1, INF);

// 5. dp更新.

rep(i, N){

// 蛍光灯の情報を一つ取得.

int l = v[i].l;

int r = v[i].r;

LL c = v[i].c;

// dp[l] ～ dp[r] の最小値を取得.

LL tmp = seg.query(l - 1, r);

// dp[r] の更新.

dp[r] = min(dp[r], tmp + c);

// SegmentTree の更新.

seg.update(r - 1, r, dp[r]);

// printf("l=%d r=%d c=%lld tmp=%lld\n", l, r, c, tmp);

// rep(i, L + 2) printf("%lld ", seg.query(i, i + 1));

// puts("");

// rep(i, L + 2) printf("%lld ", dp[i]);

// puts("");

}

// 6. 出力.

// rep(i, L + 2) printf("%lld ", dp[i]);

// puts("");

printf("%lld\n", dp[L + 1]);

return 0;

}

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

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

[入力例]
8 10
0 2 1
2 3 1
0 4 1
0 2 1
3 7 1
0 10 1080
8 10 1
9 10 1

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

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

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

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

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

[入力例]
50 10000
0 200 45862
100 400 19945
200 600 17915
300 800 19465
400 1000 34803
500 1200 93461
600 1400 48616
700 1600 49099
800 1800 34606
900 2000 15496
1000 2200 89294
1100 2400 82648
1200 2600 89730
1300 2800 90761
1400 3000 3857
1500 3200 11030
1600 3400 51166
1700 3600 4678
1800 3800 95199
1900 4000 64122
2000 4200 19257
2100 4400 46096
2200 4600 59981
2300 4800 42505
2400 5000 46394
2500 5200 18534
2600 5400 93404
2700 5600 74100
2800 5800 4510
2900 6000 62913
3000 6200 70761
3100 6400 16118
3200 6600 24552
3300 6800 14180
3400 7000 81350
3500 7200 23663
3600 7400 56717
3700 7600 29262
3800 7800 2880
3900 8000 19465
4000 8200 73247
4100 8400 89105
4200 8600 79489
4300 8800 58709
4400 9000 14275
4500 9200 27125
4600 9400 71437
4700 9600 23357
4800 9800 88389
4900 10000 97890

[出力例]
218650

100

101

102

103

104

105

106

107

108

109

110

111

[入力例]

5 5

0 1 1

1 2 1

2 4 3

3 5 1

2 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

8 10

0 2 1

2 3 1

0 4 1

0 2 1

3 7 1

0 10 1080

8 10 1

9 10 1

[出力例]

1080

※AtCoderのテストケースより

[入力例]

10 10

0 1 1

1 2 1

2 3 1

3 4 1

4 5 1

0 5 4

5 7 2

6 8 3

8 10 1

2 9 3

[出力例]

※AtCoderのテストケースより

[入力例]

5 5

0 1 100000

1 2 100000

2 3 100000

3 4 100000

4 5 100000

[出力例]

500000

※AtCoderのテストケースより

[入力例]

50 10000

0 200 45862

100 400 19945

200 600 17915

300 800 19465

400 1000 34803

500 1200 93461

600 1400 48616

700 1600 49099

800 1800 34606

900 2000 15496

1000 2200 89294

1100 2400 82648

1200 2600 89730

1300 2800 90761

1400 3000 3857

1500 3200 11030

1600 3400 51166

1700 3600 4678

1800 3800 95199

1900 4000 64122

2000 4200 19257

2100 4400 46096

2200 4600 59981

2300 4800 42505

2400 5000 46394

2500 5200 18534

2600 5400 93404

2700 5600 74100

2800 5800 4510

2900 6000 62913

3000 6200 70761

3100 6400 16118

3200 6600 24552

3300 6800 14180

3400 7000 81350

3500 7200 23663

3600 7400 56717

3700 7600 29262

3800 7800 2880

3900 8000 19465

4000 8200 73247

4100 8400 89105

4200 8600 79489

4300 8800 58709

4400 9000 14275

4500 9200 27125

4600 9400 71437

4700 9600 23357

4800 9800 88389

4900 10000 97890

[出力例]

218650

■参照サイト
AtCoder Regular Contest 026
遅延評価セグメント木をソラで書きたいあなたに

C++の練習を兼ねて, AtCoder Regular Contest 032 の 問題A (A – ホリドッグ) ～ 問題B (B – 道路工事) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 030 の 問題A (A – 閉路グラフ) ～ 問題B (B – ツリーグラフ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 028 の 問題C (C – 高橋王国の分割統治) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 028 の 問題A (A – 小石を取るゲーム) ～ 問題B (B – 特別賞) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 166 の 問題E (E – This Message Will Self-Destruct in 5s) を解いてみた.

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

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

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

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

C++の練習を兼ねて, AtCoder Regular Contest 026 の 問題C (C – 蛍光灯) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 032 の問題A (A – ホリドッグ) ～問題B (B – 道路工事) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 030 の問題A (A – 閉路グラフ) ～問題B (B – ツリーグラフ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 028 の問題C (C – 高橋王国の分割統治) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 028 の問題A (A – 小石を取るゲーム) ～問題B (B – 特別賞) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 166 の問題E (E – This Message Will Self-Destruct in 5s) を解いてみた.

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

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

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

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

C++の練習を兼ねて, AtCoder Regular Contest 026 の問題C (C – 蛍光灯) を解いてみた.