C++ | 個人用メモ帳

2021年5月23日2021年5月23日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題036 (Max Manhattan Distance) を解いてみた.

■感想.
1. 問題036は, 何となく過去問の解説 (E – へんなコンパス) の座標変換が利用できるように見えたので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題036 をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
LL x[101010], y[101010];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    LL maxX = -1000000000, minX = 1000000000, maxY = -1000000000, minY = 1000000000;
    rep(i, N){
        LL tx, ty;
        scanf("%lld %lld", &tx, &ty);
        
        // 座標変換.
        // https://img.atcoder.jp/arc065/editorial.pdf
        x[i] = tx + ty;
        y[i] = tx - ty;
        
        // 最大値, 最小値を更新.
        maxX = max(maxX, x[i]);
        minX = min(minX, x[i]);
        maxY = max(maxY, y[i]);
        minY = min(minY, y[i]);
    }
    
    // 2. クエリ回答.
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int q;
        scanf("%d", &q);
        q--;
        
        // 2-2. マンハッタン距離(Manhattan Distance)の最大値を計算.
        LL md1 = abs(maxX - x[q]);
        LL md2 = abs(minX - x[q]);
        LL md3 = abs(maxY - y[q]);
        LL md4 = abs(minY - y[q]);
        // printf("md1=%lld md2=%lld md3=%lld md4=%lld\n", md1, md2, md3, md4);
        
        // 2-3. 出力.
        printf("%lld\n", max({md1, md2, md3, md4}));
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

LL x[101010], y[101010];

int main(){

// 1. 入力情報.

int N, Q;

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

LL maxX = -1000000000, minX = 1000000000, maxY = -1000000000, minY = 1000000000;

rep(i, N){

LL tx, ty;

scanf("%lld %lld", &tx, &ty);

// 座標変換.

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

x[i] = tx + ty;

y[i] = tx - ty;

// 最大値, 最小値を更新.

maxX = max(maxX, x[i]);

minX = min(minX, x[i]);

maxY = max(maxY, y[i]);

minY = min(minY, y[i]);

}

// 2. クエリ回答.

rep(i, Q){

// 2-1. クエリ入力情報.

int q;

scanf("%d", &q);

q--;

// 2-2. マンハッタン距離(Manhattan Distance)の最大値を計算.

LL md1 = abs(maxX - x[q]);

LL md2 = abs(minX - x[q]);

LL md3 = abs(maxY - y[q]);

LL md4 = abs(minY - y[q]);

// printf("md1=%lld md2=%lld md3=%lld md4=%lld\n", md1, md2, md3, md4);

// 2-3. 出力.

printf("%lld\n", max({md1, md2, md3, md4}));

}

return 0;

}

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

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

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

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

[入力例]
2 1
-1000000000 -1000000000
1000000000 1000000000
1

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

[入力例]
10 5
561 -1082
825 1097
-612 146
509 504
557 -432
1124 1052
-556 892
879 268
-443 -492
728 -161
1
2
5
7
8

[出力例]
3091
2857
2437
3091
2082

[入力例]
20 7
9255 3517
8803 1930
7712 11610
5698 5482
2622 1094
9391 3183
6736 2247
513 2829
6052 11932
5713 9332
4583 10316
7919 6528
9943 11127
6433 8429
7197 11285
7574 9936
4376 6452
3816 1900
991 4442
6557 566
2
5
6
8
4
5
9

[出力例]
12753
17354
12088
17728
9890
17354
14642

100

101

102

103

104

105

[入力例]

3 3

-1 2

1 1

-2 -3

[出力例]

※AtCoderのテストケースより

[入力例]

5 3

-2 -2

-1 -1

0 0

1 1

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

2 1

-1000000000 -1000000000

1000000000 1000000000

[出力例]

4000000000

※AtCoderのテストケースより

[入力例]

10 5

561 -1082

825 1097

-612 146

509 504

557 -432

1124 1052

-556 892

879 268

-443 -492

728 -161

[出力例]

3091

2857

2437

3091

2082

[入力例]

20 7

9255 3517

8803 1930

7712 11610

5698 5482

2622 1094

9391 3183

6736 2247

513 2829

6052 11932

5713 9332

4583 10316

7919 6528

9943 11127

6433 8429

7197 11285

7574 9936

4376 6452

3816 1900

991 4442

6557 566

[出力例]

12753

17354

12088

17728

9890

17354

14642

■参照サイト
036 – Max Manhattan Distance
AtCoder Regular Contest 065

2021年5月22日

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

C++の練習を兼ねて, AtCoder Grand Contest 020 の問題C (Median Sum) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 苦手なdpの訓練を積めたこと, および, bitsetの使い方を訓練できたのが非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc020/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[2020];

int main(){
    
    // 1. 入力情報.
    int N, aSum = 0;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a[i]);
        aSum += a[i];
    }
    
    // 2. dp更新.
    bitset<4040404> dp;
    rep(i, N){
        // 2-1. dpのコピー作成.
        bitset<4040404> pd = dp;
        
        // 2-2. dpを左シフトしたものを考慮.
        dp |= (pd <<= a[i]);
        
        // 2-3. 数列の値を, true に 設定.
        dp[a[i]] = true;
    }
    
    // 3. 中央値を探索.
    int ans = 0;
    repx(i, (aSum + 1) / 2, 4040404){
        if(dp[i]){
            ans = i;
            break;
        }
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

int a[2020];

int main(){

// 1. 入力情報.

int N, aSum = 0;

scanf("%d", &N);

rep(i, N){

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

aSum += a[i];

}

// 2. dp更新.

bitset<4040404> dp;

rep(i, N){

// 2-1. dpのコピー作成.

bitset<4040404> pd = dp;

// 2-2. dpを左シフトしたものを考慮.

dp |= (pd <<= a[i]);

// 2-3. 数列の値を, true に設定.

dp[a[i]] = true;

}

// 3. 中央値を探索.

int ans = 0;

repx(i, (aSum + 1) / 2, 4040404){

if(dp[i]){

ans = i;

break;

}

// 4. 出力.

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

return 0;

}

[入力例]
3
1 2 1

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

[入力例]
1
58

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

[入力例]
5
2 17 3 5 25

[出力例]
27

[入力例]
15
18 3 52 9 32 6 47 24 32 61 2 30 11 7 30

[出力例]
182

[入力例]
50
1129 874 831 311 622 469 1696 1673 489 989 1643 1090 1805 1352 1775 1811 1454 301 17 82 1456 912 765 879 220 1582 1634 1907 1924 1563 1710 426 1709 113 112 415 685 1922 767 658 492 1721 247 677 1186 538 1095 1231 319 1024

[出力例]
25151

[入力例]

1 2 1

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

2 17 3 5 25

[出力例]

[入力例]

18 3 52 9 32 6 47 24 32 61 2 30 11 7 30

[出力例]

182

[入力例]

1129 874 831 311 622 469 1696 1673 489 989 1643 1090 1805 1352 1775 1811 1454 301 17 82 1456 912 765 879 220 1582 1634 1907 1924 1563 1710 426 1709 113 112 415 685 1922 767 658 492 1721 247 677 1186 538 1095 1231 319 1024

[出力例]

25151

■参照サイト
AtCoder Grand Contest 020

2021年5月22日2021年5月22日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題043 (Maze Challenge with Lack of Sleep) を解いてみた.

■感想.
1. 問題043は, 01-BFS, ダイクストラ法の方針で, いくつか実装したものの, どれもAC版に到達できなかったので, 解説プログラムに, 一部手を加えた版(※)を提出して, ようやく, AC版に到達出来た.
※解説プログラムでは, 二次元座標で実装されているようです.
2. 問題自体は, 個人的には, 非常に面白く, さらに, 曲がった回数の情報をどのように管理するか(問題043 解説), について, 全く発想に出てこない概念だったので, 非常に勉強になったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題043 をご覧下さい.

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

// 解答不能.
// https://github.com/E869120/kyopro_educational_90/blob/main/sol/043.cpp
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
const int INF = 2020202020;
int board[1010][1010];
int d[1010101][4]; // 上下左右の4方向を記録.

int main() {
    
    // 1. 入力情報.
    int H, W, rs, cs, rt, ct;
    scanf("%d %d %d %d %d %d", &H, &W, &rs, &cs, &rt, &ct);
    rs--, cs--, rt--, ct--;
    rep(i, H){
        char c[1010];
        scanf("%s", c);
        rep(j, W) if(c[j] == '.') board[i][j] = 1;
    }
    
    // 2. 01-BFS(解説プログラムを一部修正).
    // 左 … 0, 上 … 1, 右 … 2, 下 … 3.
    auto bfs01 = [&](int s){
        // 2-1. 空のキュー.
        deque<P> dq; // {座標, 方向}.
        
        // 2-2. 探索開始地点 s をキュー に追加.
        rep(i, 4) d[s][i] = 0, dq.pub({s, i});
        
        // 2-3. キューが空になるまで繰り返し.
        while(!dq.empty()){
            // 2-4. キュー の 先頭要素を取り出す.
            P c = dq.front();
            dq.pof();
            
            // 2-5. 取り出した要素を処理.
            // x: 列方向, y: 行方向 で考える.
            int nx, ny, n, nc;
            int cx = c.a % W , cy = c.a / W;
            rep(i, 4){
                // 2-6. 訪問先の候補となるマスについて情報を取得.
                nx = cx + dx[i];
                ny = cy + dy[i];
                n = nx + ny * W;
                nc = d[c.a][c.b] + (c.b != i ? 1 : 0);
                
                // 2-7. 訪問不可能なマスは, 処理をスキップ.
                if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
                if(!board[ny][nx])                                  continue;
                
                // 2-8. よりコストが少ないマスは, 処理をスキップ.
                if(d[n][i] <= nc) continue;
                
                // 2-9. キューに追加.
                d[n][i] = nc;
                if(i != c.b) dq.pub({n, i});
                else         dq.puf({n, i});
            }
        }
        return;
    };
    rep(i, 1010101) rep(j, 4) d[i][j] = INF;
    bfs01(rs * W + cs);
    
    // 3. 出力.
    int ans = INF;
    rep(i, 4) ans = min(ans, d[rt * W + ct][i]);
    printf("%d", ans);
    return 0;
    
}

// 解答不能.

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/043.cpp

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define a first

#define b second

#define pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

const int INF = 2020202020;

int board[1010][1010];

int d[1010101][4]; // 上下左右の4方向を記録.

int main() {

// 1. 入力情報.

int H, W, rs, cs, rt, ct;

scanf("%d %d %d %d %d %d", &H, &W, &rs, &cs, &rt, &ct);

rs--, cs--, rt--, ct--;

rep(i, H){

char c[1010];

scanf("%s", c);

rep(j, W) if(c[j] == '.') board[i][j] = 1;

}

// 2. 01-BFS(解説プログラムを一部修正).

// 左 … 0, 上 … 1, 右 … 2, 下 … 3.

auto bfs01 = [&](int s){

// 2-1. 空のキュー.

deque<P> dq; // {座標, 方向}.

// 2-2. 探索開始地点 s をキューに追加.

rep(i, 4) d[s][i] = 0, dq.pub({s, i});

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

while(!dq.empty()){

// 2-4. キューの先頭要素を取り出す.

P c = dq.front();

dq.pof();

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

// x: 列方向, y: 行方向で考える.

int nx, ny, n, nc;

int cx = c.a % W , cy = c.a / W;

rep(i, 4){

// 2-6. 訪問先の候補となるマスについて情報を取得.

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * W;

nc = d[c.a][c.b] + (c.b != i ? 1 : 0);

// 2-7. 訪問不可能なマスは, 処理をスキップ.

if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue;

if(!board[ny][nx]) continue;

// 2-8. よりコストが少ないマスは, 処理をスキップ.

if(d[n][i] <= nc) continue;

// 2-9. キューに追加.

d[n][i] = nc;

if(i != c.b) dq.pub({n, i});

else dq.puf({n, i});

}

return;

};

rep(i, 1010101) rep(j, 4) d[i][j] = INF;

bfs01(rs * W + cs);

// 3. 出力.

int ans = INF;

rep(i, 4) ans = min(ans, d[rt * W + ct][i]);

printf("%d", ans);

return 0;

}

[入力例]
3 3
1 1
3 3
..#
#.#
#..

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

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

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

[入力例]
4 6
2 1
1 5
...#..
.#.##.
.#....
...##.

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

[入力例]
4 7
1 2
4 2
#......
..####.
.#####.
.......

[出力例]
2
※解説上のテストケースより

[入力例]
8 11
4 3
8 10
...........
.#.###..#..
.#......#..
...##..#...
.....#.#..#
#..#.......
.#...#.#.#.
#..#...#...

[出力例]
5

[入力例]
12 17
2 3
11 15
......#.#..#..#..
.#.#..#.........#
.#.#..#..#..#.#..
....#.#.#..#....#
..#.#.........#..
#...#.#.#.#.#.#.#
..#.....#.#.#.#.#
#...#.#.#....#...
......#....##.#.#
..#...#..#..#....
....#.#.#....#.#.
......#....#.....

[出力例]
8

[入力例]

3 3

1 1

3 3

..#

#.#

#..

[出力例]

※AtCoderテストケースより

[入力例]

3 3

2 1

2 3

#.#

...

#.#

[出力例]

※AtCoderテストケースより

[入力例]

4 6

2 1

1 5

...#..

.#.##.

.#....

...##.

[出力例]

※AtCoderテストケースより

[入力例]

4 7

1 2

4 2

#......

..####.

.#####.

.......

[出力例]

※解説上のテストケースより

[入力例]

8 11

4 3

8 10

...........

.#.###..#..

.#......#..

...##..#...

.....#.#..#

#..#.......

.#...#.#.#.

#..#...#...

[出力例]

[入力例]

12 17

2 3

11 15

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

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

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

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

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

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

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

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

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

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

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

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

[出力例]

■参照サイト
043 – Maze Challenge with Lack of Sleep

2021年5月18日2021年5月19日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題039 (Tree Distance) を解いてみた.

■感想.
1. 問題039は, 方針を決めるまでに苦労したものの, ある辺が, 部分木を考えた時に, 何回カウントされるかを, 追いかけていく動的計画法で解決しそうに見えたので実装したところ, AC版に到達出来た.
2. 苦手な動的計画法(木dp)の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題039 をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vvi = vector<vector<int>>;
using P = pair<LL, 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
LL subTree[101010]; // 部分木の大きさ.
LL dp[101010];      // 木dp.

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. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-5. 未訪問の頂点を処理.
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    // rep(i, N) printf("%lld ", d[i]);
    // puts("");
    
    // 3. 木dp更新準備.
    // 3-1. 頂点 1 から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}
    
    // 3-2. 葉について, dp初期化.
    rep(i, N) if(G[i].size() == 1) dp[i] = (LL)(N - 1);
    
    // 3-3. 但し, 根は, ゼロを設定.
    dp[0] = 0;
    
    // 4. 木dp.
    while(!pq.empty()){
        // 4-1. 頂点 v を一つ取り出す.
        P p = pq.top();
        pq.pop();
        
        // 4-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 4-3. 部分木更新.
        subTree[v]++;
        
        // 4-4. 頂点 v を 根とする部分木 の サイズ を 集計しながら, 木dp も 更新.
        for(auto &u : G[v]){
            // 頂点 v の 子供 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                // 頂点 v の 周囲 の 頂点 u で, 頂点 1 から, より遠いものを加算.
                subTree[v] += subTree[u];
                
                // 頂点 v の 周囲 の 頂点 u について, 木dp の 更新.
                dp[v] += dp[u];
            }
        }
        
        // 4-5. 部分木をベースに, 木dp更新.
        if(G[v].size() > 1) dp[v] += (LL)(N - subTree[v]) * subTree[v];
    }
    
    // 5. 出力.
    printf("%lld\n", dp[0]);
    return 0;
    
}

100

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vvi = vector<vector<int>>;

using P = pair<LL, 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

LL subTree[101010]; // 部分木の大きさ.

LL dp[101010]; // 木dp.

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. 頂点 1 から各頂点までの距離を計算.

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

auto bfs = [&](vvi &G, int s, int* d){

// 2-1. 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

// 2-3. キューから取り出す.

int u = q.front();

q.pop();

// 2-4. 取り出した要素を処理.

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

// 2-5. 未訪問の頂点を処理.

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

}

return;

};

int d[N];

rep(i, N) d[i] = 0;

bfs(G, 0, d);

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

// puts("");

// 3. 木dp更新準備.

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

priority_queue<P> pq;

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

// 3-2. 葉について, dp初期化.

rep(i, N) if(G[i].size() == 1) dp[i] = (LL)(N - 1);

// 3-3. 但し, 根は, ゼロを設定.

dp[0] = 0;

// 4. 木dp.

while(!pq.empty()){

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

P p = pq.top();

pq.pop();

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

int v = p.b;

// 4-3. 部分木更新.

subTree[v]++;

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

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

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

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

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

subTree[v] += subTree[u];

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

dp[v] += dp[u];

}

// 4-5. 部分木をベースに, 木dp更新.

if(G[v].size() > 1) dp[v] += (LL)(N - subTree[v]) * subTree[v];

}

// 5. 出力.

printf("%lld\n", dp[0]);

return 0;

}

[入力例]
2
1 2

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

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

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

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

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

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

[出力例]
98

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

[出力例]
185

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

[出力例]
757

[入力例]

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 3

1 4

[出力例]

※AtCoderテストケースより

[入力例]

1 2

3 1

4 2

2 5

3 6

3 7

8 4

4 9

10 5

11 7

7 12

[出力例]

211

※AtCoderテストケースより

[入力例]

1 2

5 1

3 2

2 4

5 6

6 7

8 6

6 9

[出力例]

[入力例]

1 2

2 3

3 4

3 5

2 6

1 12

1 7

7 8

7 9

7 10

7 11

[出力例]

185

[入力例]

1 20

2 20

2 6

6 8

7 6

7 9

7 10

7 11

3 20

3 5

3 4

4 13

4 12

4 14

14 17

14 16

14 15

18 20

18 19

[出力例]

757

■参照サイト
039 – Tree Distance

2021年5月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 201 の問題C (Secret Number) ～問題D (Game in Momotetsu World) を解いてみた.

■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){
    
    // 1. 入力情報.
    char S[22];
    scanf("%s", S);
    
    // 2. 暗証番号(4桁)としてありうるものは？
    int ans = 0;
    rep(i, 10000){
        // 2-1. 暗証番号候補(4桁)を作成.
        string cPass = to_string(i);
        
        // 2-2. 集合に保存.
        int l = cPass.size();
        set<int> st;
        if(l < 4) st.insert(0);
        rep(j, l) st.insert(cPass[j] - '0');
        
        // 2-3. 条件を満たすかチェック.
        bool ok = true;
        rep(j, 10){
            if(S[j] == 'o' && !st.count(j)) ok = false;
            if(S[j] == 'x' && st.count(j))  ok = false;
        }
        
        // 2-4. インクリメント.
        if(ok) ans++;
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){

// 1. 入力情報.

char S[22];

scanf("%s", S);

// 2. 暗証番号(4桁)としてありうるものは？

int ans = 0;

rep(i, 10000){

// 2-1. 暗証番号候補(4桁)を作成.

string cPass = to_string(i);

// 2-2. 集合に保存.

int l = cPass.size();

set<int> st;

if(l < 4) st.insert(0);

rep(j, l) st.insert(cPass[j] - '0');

// 2-3. 条件を満たすかチェック.

bool ok = true;

rep(j, 10){

if(S[j] == 'o' && !st.count(j)) ok = false;

if(S[j] == 'x' && st.count(j)) ok = false;

}

// 2-4. インクリメント.

if(ok) ans++;

}

// 3. 出力.

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

return 0;

}

[入力例]
ooo???xxxx

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

[入力例]
o?oo?oxoxo

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

[入力例]
xxxxx?xxxo

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

[入力例]
xxoxx?oxxo

[出力例]
60

[入力例]
x?o?x?o?xo

[出力例]
132

[入力例]
??????????

[出力例]
10000

[入力例]

ooo???xxxx

[出力例]

108

※AtCoderテストケースより

[入力例]

o?oo?oxoxo

[出力例]

※AtCoderテストケースより

[入力例]

xxxxx?xxxo

[出力例]

※AtCoderテストケースより

[入力例]

xxoxx?oxxo

[出力例]

[入力例]

x?o?x?o?xo

[出力例]

132

[入力例]

??????????

[出力例]

10000

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

// 解き直し.
// https://atcoder.jp/contests/abc201/editorial/480
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int board[2020][2020], dp[2020][2020];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[2020];
        scanf("%s", c);
        rep(j, W) board[i][j] = (c[j] == '+') ? 1 : -1;
    }
    
    // 2. dp更新.
    repr(i, H - 1, 0){
        repr(j, W - 1, 0){
            bool t = (i + j) & 1;
            if(t){
                if(i < H - 1){
                    if(j < W - 1) dp[i][j] = min(dp[i][j + 1] - board[i][j + 1], dp[i + 1][j] - board[i + 1][j]);
                    else          dp[i][j] = dp[i + 1][j] - board[i + 1][j];
                }else{
                    if(j < W - 1) dp[i][j] = dp[i][j + 1] - board[i][j + 1];
                    else          dp[i][j] = 0;
                }
            }else{
                if(i < H - 1){
                    if(j < W - 1) dp[i][j] = max(dp[i][j + 1] + board[i][j + 1], dp[i + 1][j] + board[i + 1][j]);
                    else          dp[i][j] = dp[i + 1][j] + board[i + 1][j];
                }else{
                    if(j < W - 1) dp[i][j] = dp[i][j + 1] + board[i][j + 1];
                    else          dp[i][j] = 0;
                }
            }
        }
    }
    
    // 3. 出力.
    string ans = "Draw";
    if(dp[0][0] > 0) ans = "Takahashi";
    if(dp[0][0] < 0) ans = "Aoki";
    printf("%s\n", ans.c_str());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc201/editorial/480

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

int board[2020][2020], dp[2020][2020];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

char c[2020];

scanf("%s", c);

rep(j, W) board[i][j] = (c[j] == '+') ? 1 : -1;

}

// 2. dp更新.

repr(i, H - 1, 0){

repr(j, W - 1, 0){

bool t = (i + j) & 1;

if(t){

if(i < H - 1){

if(j < W - 1) dp[i][j] = min(dp[i][j + 1] - board[i][j + 1], dp[i + 1][j] - board[i + 1][j]);

else dp[i][j] = dp[i + 1][j] - board[i + 1][j];

}else{

if(j < W - 1) dp[i][j] = dp[i][j + 1] - board[i][j + 1];

else dp[i][j] = 0;

}

}else{

if(i < H - 1){

if(j < W - 1) dp[i][j] = max(dp[i][j + 1] + board[i][j + 1], dp[i + 1][j] + board[i + 1][j]);

else dp[i][j] = dp[i + 1][j] + board[i + 1][j];

}else{

if(j < W - 1) dp[i][j] = dp[i][j + 1] + board[i][j + 1];

else dp[i][j] = 0;

}

// 3. 出力.

string ans = "Draw";

if(dp[0][0] > 0) ans = "Takahashi";

if(dp[0][0] < 0) ans = "Aoki";

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

return 0;

}

[入力例]
3 3
---
+-+
+--

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

[入力例]
2 4
+++-
-+-+

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

[入力例]
1 1
-

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

[入力例]
1 2
-+

[出力例]
Takahashi

[入力例]
3 4
+-+-
+++-
+-+-

[出力例]
Aoki

[入力例]
6 7
-++-+-+
++--+++
+++--+-
--+++--
----+-+
---+---

[出力例]
Aoki

[入力例]
8 10
+++-+----+
+--+-+++++
-+--+-+---
+-++----++
++--++-++-
+-----+-++
-++-+-----
-+++-+-+--

[出力例]
Draw

[入力例]
9 12
+++---+-++--
+--+-+++--++
+--+-++---+-
+++---++----
-+---+---+++
+--+++---+--
-++------+++
-+--+---+++-
-++-+++-++--

[出力例]
Takahashi

[入力例]

3 3

---

+-+

+--

[出力例]

Takahashi

※AtCoderテストケースより

[入力例]

2 4

+++-

-+-+

[出力例]

Aoki

※AtCoderテストケースより

[入力例]

1 1

[出力例]

Draw

※AtCoderテストケースより

[入力例]

1 2

[出力例]

Takahashi

[入力例]

3 4

+-+-

+++-

+-+-

[出力例]

Aoki

[入力例]

6 7

-++-+-+

++--+++

+++--+-

--+++--

----+-+

---+---

[出力例]

Aoki

[入力例]

8 10

+++-+----+

+--+-+++++

-+--+-+---

+-++----++

++--++-++-

+-----+-++

-++-+-----

-+++-+-+--

[出力例]

Draw

[入力例]

9 12

+++---+-++--

+--+-+++--++

+--+-++---+-

+++---++----

-+---+---+++

+--+++---+--

-++------+++

-+--+---+++-

-++-+++-++--

[出力例]

Takahashi

■参照サイト
マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）

2021年5月12日2021年5月12日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題008 (AtCounter) を解いてみた.

■感想.
1. 問題008は, 方針を決めるまでに苦労したものの, 動的計画法で行けそうに見えたので実装したところ, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 非常に面白い問題に感じた(※本家の解説プログラムが, 汎用的に見え, 非常に勉強になったと思う).
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題008 をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
LL dpl[101010], dpr[101010], dp[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    char S[101010];
    scanf("%d %s", &N, S);
    
    // 2. atc を 取り出す方法(dpl更新).
    LL a = 0, t = 0;
    rep(i, N){
        // 前回分設定.
        dpl[i + 1] = dpl[i];
        
        // 'a' が 出現した場合.
        if(S[i] == 'a') a++, a %= MOD;
        
        // 't' が 出現した場合.
        if(S[i] == 't') t += a, t %= MOD;
        
        // 'c' が 出現した場合.
        if(S[i] == 'c') dpl[i + 1] += t, dpl[i + 1] %= MOD;
    }
    // rep(i, N + 1) printf("%lld ", dpl[i]);
    // puts("");
    
    // 3. der を 取り出す方法(dpr更新).
    LL e = 0, r = 0;
    repr(i, N - 1, 0){
        // 前回分設定.
        dpr[i] = dpr[i + 1];
        
        // 'r' が 出現した場合.
        if(S[i] == 'r') r++, r %= MOD;
        
        // 'e' が 出現した場合.
        if(S[i] == 'e') e += r, e %= MOD;
        
        // 'd' が 出現した場合.
        if(S[i] == 'd') dpr[i] += e, dpr[i] %= MOD;
    }
    // rep(i, N + 1) printf("%lld ", dpr[i]);
    // puts("");
    
    // 4. atcoder を 取り出す方法(dp更新).
    rep(i, N){
        // 前回分設定.
        dp[i + 1] = dp[i];
        
        // 'o' が 出現した場合.
        if(i && S[i] == 'o'){
            // 'o' よりも左側について, atc を 取り出す 方法は？
            LL atc = dpl[i];
            
            // 'o' よりも右側について, der を 取り出す 方法は？
            LL der = dpr[i];
            
            // 集計.
            dp[i + 1] += atc * der;
            dp[i + 1] %= MOD;
        }
    }
    // rep(i, N + 1) printf("%lld ", dp[i]);
    // puts("");
    
    // 5. 出力.
    printf("%lld\n", dp[N]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

const LL MOD = 1e9 + 7;

LL dpl[101010], dpr[101010], dp[101010];

int main(){

// 1. 入力情報.

int N;

char S[101010];

scanf("%d %s", &N, S);

// 2. atc を取り出す方法(dpl更新).

LL a = 0, t = 0;

rep(i, N){

// 前回分設定.

dpl[i + 1] = dpl[i];

// 'a' が出現した場合.

if(S[i] == 'a') a++, a %= MOD;

// 't' が出現した場合.

if(S[i] == 't') t += a, t %= MOD;

// 'c' が出現した場合.

if(S[i] == 'c') dpl[i + 1] += t, dpl[i + 1] %= MOD;

}

// rep(i, N + 1) printf("%lld ", dpl[i]);

// puts("");

// 3. der を取り出す方法(dpr更新).

LL e = 0, r = 0;

repr(i, N - 1, 0){

// 前回分設定.

dpr[i] = dpr[i + 1];

// 'r' が出現した場合.

if(S[i] == 'r') r++, r %= MOD;

// 'e' が出現した場合.

if(S[i] == 'e') e += r, e %= MOD;

// 'd' が出現した場合.

if(S[i] == 'd') dpr[i] += e, dpr[i] %= MOD;

}

// rep(i, N + 1) printf("%lld ", dpr[i]);

// puts("");

// 4. atcoder を取り出す方法(dp更新).

rep(i, N){

// 前回分設定.

dp[i + 1] = dp[i];

// 'o' が出現した場合.

if(i && S[i] == 'o'){

// 'o' よりも左側について, atc を取り出す方法は？

LL atc = dpl[i];

// 'o' よりも右側について, der を取り出す方法は？

LL der = dpr[i];

// 集計.

dp[i + 1] += atc * der;

dp[i + 1] %= MOD;

}

// rep(i, N + 1) printf("%lld ", dp[i]);

// puts("");

// 5. 出力.

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

return 0;

}

[入力例]
10
attcordeer

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

[入力例]
41
btwogablwetwoiehocghiewobadegwhoihegnldir

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

[入力例]
140
aaaaaaaaaaaaaaaaaaaattttttttttttttttttttccccccccccccccccccccooooooooooooooooooooddddddddddddddddddddeeeeeeeeeeeeeeeeeeeerrrrrrrrrrrrrrrrrrrr

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

[入力例]
18
eatstatcocdoeoderr

[出力例]
56

[入力例]
50
ratfmdaiccdiotnclcdatcoktduoetsdeadmkrdxruwrxrsfkp

[出力例]
264

[入力例]
100
zamtahacydohcrokatcoergatcloivatcbiorkxsgogudkedhserwrbedqeenoriuboncxdlexremderzoxakobiosbdzeqrhiyg

[出力例]
8937

[入力例]

attcordeer

[出力例]

※AtCoderテストケースより

[入力例]

btwogablwetwoiehocghiewobadegwhoihegnldir

[出力例]

※AtCoderテストケースより

[入力例]

140

aaaaaaaaaaaaaaaaaaaattttttttttttttttttttccccccccccccccccccccooooooooooooooooooooddddddddddddddddddddeeeeeeeeeeeeeeeeeeeerrrrrrrrrrrrrrrrrrrr

[出力例]

279999993

※AtCoderテストケースより

[入力例]

eatstatcocdoeoderr

[出力例]

[入力例]

ratfmdaiccdiotnclcdatcoktduoetsdeadmkrdxruwrxrsfkp

[出力例]

264

[入力例]

100

zamtahacydohcrokatcoergatcloivatcbiorkxsgogudkedhserwrbedqeenoriuboncxdlexremderzoxakobiosbdzeqrhiyg

[出力例]

8937

■参照サイト
008 – AtCounter

2021年5月9日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題013 (Passing) を解いてみた.

■感想.
1. 問題013は, ダイクストラ法を使う方針で, 何とかAC版に到達出来た.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題013 をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL INF = 202020202020202020;
const int MAX = 101010;

struct edge{
    int t; // 次の頂点.
    LL c;  // 所要時間.
    bool operator < (const edge &E) const { return c > E.c; }
};

vector<edge> G[MAX];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        a--;
        b--;
        edge e1;
        e1.t = b;
        e1.c = c;
        G[a].pb(e1);
        
        edge e2;
        e2.t = a;
        e2.c = c;
        G[b].pb(e2);
    }
    
    // 2. 出発地点から, 目的地点までの最短時間を求める(ダイクストラ法).
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    LL d1[N], d2[N];
    rep(i, N) d1[i] = d2[i] = INF;
    auto dijkstra = [&](int s, LL* d){
        // 2-1. 空のキュー.
        priority_queue<edge> pq;
        
        // 2-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0});
        
        // 2-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 2-4. 探索を継続するために, 頂点を取得.
            int u = pq.top().t;
            LL c  = pq.top().c;
            pq.pop();
            
            // 2-5. より小さい距離が設定済みなら, Skip.
            if(d[u] < c) continue;
            
            // 2-6. 各隣接する頂点について, 所要時間を確認し, 最短時間を更新.
            rep(i, G[u].size()){
                // 最短時間更新.
                int nu = G[u][i].t;
                LL nc  = c + G[u][i].c;
                if(d[nu] > nc) d[nu] = nc, pq.push({nu, nc});
            }
        }
        return;
    };
    
    // 3. 街 1 -> 街 1 ～ N.
    dijkstra(0, d1);
    
    // 4. 街 N -> 街 1 ～ N.
    dijkstra(N - 1, d2);
    
    // 5. 出力.
    rep(i, N) printf("%lld\n", d1[i] + d2[i]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

const LL INF = 202020202020202020;

const int MAX = 101010;

struct edge{

int t; // 次の頂点.

LL c; // 所要時間.

bool operator < (const edge &E) const { return c > E.c; }

};

vector<edge> G[MAX];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, M){

int a, b;

LL c;

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

a--;

b--;

edge e1;

e1.t = b;

e1.c = c;

G[a].pb(e1);

edge e2;

e2.t = a;

e2.c = c;

G[b].pb(e2);

}

// 2. 出発地点から, 目的地点までの最短時間を求める(ダイクストラ法).

// https://ja.wikipedia.org/wiki/ダイクストラ法

LL d1[N], d2[N];

rep(i, N) d1[i] = d2[i] = INF;

auto dijkstra = [&](int s, LL* d){

// 2-1. 空のキュー.

priority_queue<edge> pq;

// 2-2. 始点設定.

d[s] = 0;

pq.push({s, 0});

// 2-3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 2-4. 探索を継続するために, 頂点を取得.

int u = pq.top().t;

LL c = pq.top().c;

pq.pop();

// 2-5. より小さい距離が設定済みなら, Skip.

if(d[u] < c) continue;

// 2-6. 各隣接する頂点について, 所要時間を確認し, 最短時間を更新.

rep(i, G[u].size()){

// 最短時間更新.

int nu = G[u][i].t;

LL nc = c + G[u][i].c;

if(d[nu] > nc) d[nu] = nc, pq.push({nu, nc});

}

return;

};

// 3. 街 1 -> 街 1 ～ N.

dijkstra(0, d1);

// 4. 街 N -> 街 1 ～ N.

dijkstra(N - 1, d2);

// 5. 出力.

rep(i, N) printf("%lld\n", d1[i] + d2[i]);

return 0;

}

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

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

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

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

[入力例]
4 3
1 2 314
1 3 159
1 4 265

[出力例]
265
893
583
265
※AtCoderテストケースより

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

[出力例]
11
11
13
11
13
27
33
21
13
23
25
11

[入力例]

7 9

1 2 2

1 3 3

2 5 2

3 4 1

3 5 4

4 7 5

5 6 1

5 7 6

6 7 3

[出力例]

※AtCoderテストケースより

[入力例]

4 3

1 2 1

2 3 10

3 4 100

[出力例]

111

※AtCoderテストケースより

[入力例]

4 3

1 2 314

1 3 159

1 4 265

[出力例]

265

893

583

265

※AtCoderテストケースより

[入力例]

12 17

1 2 2

1 3 5

2 5 3

2 4 8

2 9 5

3 8 4

3 9 1

8 9 6

8 10 1

10 11 2

8 11 2

9 12 7

12 4 1

5 4 7

5 6 7

5 7 10

6 7 4

[出力例]

■参照サイト
013 – Passing

2021年5月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 200 の問題C (Ringo’s Favorite Numbers 2) ～問題D (Happy Birthday! 2) を解いてみた.

■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
LL b[202];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        int a;
        scanf("%d", &a);
        a %= 200;
        b[a]++;
    }
    
    // 2. 条件を満たす整数の個数を計算.
    LL ans = 0;
    rep(i, 200) if(b[i]) ans += (b[i] - 1) * b[i] / 2;
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

LL b[202];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

int a;

scanf("%d", &a);

a %= 200;

b[a]++;

}

// 2. 条件を満たす整数の個数を計算.

LL ans = 0;

rep(i, 200) if(b[i]) ans += (b[i] - 1) * b[i] / 2;

// 3. 出力.

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

return 0;

}

[入力例]
6
123 223 123 523 200 2000

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

[入力例]
5
1 2 3 4 5

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

[入力例]
8
199 100 200 400 300 500 600 200

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

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

[出力例]
65

[入力例]

123 223 123 523 200 2000

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

199 100 200 400 300 500 600 200

[出力例]

※AtCoderテストケースより

[入力例]

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

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc200/editorial/1246
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
int a[202], memo[202];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a[i]);
        a[i] %= 200;
    }
    
    // 2. 探索を行う.
    int u = min(N, 8), lb = 0, lc = 0;
    vvi D(202);
    vi B, C;
    bool ok = false;
    rep(i, 1 << u){
        // 2-1. 初期化.
        B.clear();
        
        // 2-2. 数列 B を, i の bit が 1 と見做して保存.
        rep(j, u) if(i & (1 << (u - 1 - j))) B.pb(j);
        
        // 2-3. 数列 B について, 和を計算.
        lb = B.size();
        int bSum = 0;
        if(lb == 0) continue;
        rep(j, lb) bSum += a[B[j]];
        bSum %= 200;
        
        // 2-4. 二回目出現パターンか確認.
        if(memo[bSum]){
            ok = true;
            C = D[bSum];
            lc = C.size();
            break;
        }
        
        // 2-5. 数列の保存など.
        memo[bSum]++;
        D[bSum] = B;
    }
    
    // 3. 出力.
    if(ok){
        puts("Yes");
        printf("%d ", lb);
        rep(i, lb){
            printf("%d", B[i] + 1);
            printf("%s", (i < lb - 1) ? " " : "\n");
        }
        printf("%d ", lc);
        rep(i, lc){
            printf("%d", C[i] + 1);
            printf("%s", (i < lc - 1) ? " " : "\n");
        }
    }else{
        puts("No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc200/editorial/1246

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

int a[202], memo[202];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

a[i] %= 200;

}

// 2. 探索を行う.

int u = min(N, 8), lb = 0, lc = 0;

vvi D(202);

vi B, C;

bool ok = false;

rep(i, 1 << u){

// 2-1. 初期化.

B.clear();

// 2-2. 数列 B を, i の bit が 1 と見做して保存.

rep(j, u) if(i & (1 << (u - 1 - j))) B.pb(j);

// 2-3. 数列 B について, 和を計算.

lb = B.size();

int bSum = 0;

if(lb == 0) continue;

rep(j, lb) bSum += a[B[j]];

bSum %= 200;

// 2-4. 二回目出現パターンか確認.

if(memo[bSum]){

ok = true;

C = D[bSum];

lc = C.size();

break;

}

// 2-5. 数列の保存など.

memo[bSum]++;

D[bSum] = B;

}

// 3. 出力.

if(ok){

puts("Yes");

printf("%d ", lb);

rep(i, lb){

printf("%d", B[i] + 1);

printf("%s", (i < lb - 1) ? " " : "\n");

}

printf("%d ", lc);

rep(i, lc){

printf("%d", C[i] + 1);

printf("%s", (i < lc - 1) ? " " : "\n");

}

}else{

puts("No");

}

return 0;

}

[入力例]
5
180 186 189 191 218

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

[入力例]
2
123 523

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

[入力例]
6
2013 1012 2765 2021 508 6971

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

[入力例]
20
539 476 114 457 693 610 624 703 255 989 64 193 1034 400 303 745 1141 8 1178 981

[出力例]
Yes
2 5 6
1 8

※ 実際, A5 + A6 = 693 + 610 = 1303, A8 = 703 となり, 200 で割った余りが等しい.

[入力例]
25
325 3753 8849 7696 2933 11238 517 11809 10209 6511 7962 1041 2041 8832 3662 2965 2129 1003 11291 7125 431 11666 11999 990 10996

[出力例]
Yes
3 4 5 8
1 6

※ 実際, A4 + A5 + A8 = 7696 + 2933 + 11809 = 22438, A6 = 11238 となり, 200 で割った余りが等しい.

[入力例]

180 186 189 191 218

[出力例]

Yes

1 1

2 3 4

※AtCoderテストケースより

[入力例]

123 523

[出力例]

Yes

1 1

1 2

※AtCoderテストケースより

[入力例]

2013 1012 2765 2021 508 6971

[出力例]

※AtCoderテストケースより

[入力例]

539 476 114 457 693 610 624 703 255 989 64 193 1034 400 303 745 1141 8 1178 981

[出力例]

Yes

2 5 6

1 8

※ 実際, A5 + A6 = 693 + 610 = 1303, A8 = 703 となり, 200 で割った余りが等しい.

[入力例]

325 3753 8849 7696 2933 11238 517 11809 10209 6511 7962 1041 2041 8832 3662 2965 2129 1003 11291 7125 431 11666 11999 990 10996

[出力例]

Yes

3 4 5 8

1 6

※ 実際, A4 + A5 + A8 = 7696 + 2933 + 11809 = 22438, A6 = 11238 となり, 200 で割った余りが等しい.

■参照サイト
京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）

2021年5月8日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題034 (There are few types of elements) を解いてみた.

■感想.
1. 問題034は, 実装に苦労したものの, 何とかAC版に到達出来た.
2. 尺取り法の復習ができたので非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題034 をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[101010];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 連続する部分列で最大の長さを計算(尺取り法).
    map<int, int> m;
    int ans = 0, s = 0;
    rep(l, N){
        // 2-1. index を 保存.
        int idx = 0;
        
        // 2-2. r を 伸ばしていく.
        repx(r, s, N){
            // 要素をカウントアップ.
            m[a[r]]++;
            
            // index 更新.
            idx = max(l + 1, r - 1);
            
            // 要素の種類数が, K を超えたら, 処理を中断.
            if(m.size() > K){
                // 要素の種類数が, K を超えたので, mapから除去.
                m.erase(a[r]);
                
                // 次回処理における, 二重カウント防止のため, 処理.
                if(m.count(a[s])){
                    // 要素をカウントダウン.
                    m[a[s]]--;
                    
                    // 要素数が, 0 ならば, 種類数を減らす.
                    if(m[a[s]] == 0) m.erase(a[s]);
                }
                
                // Skip.
                break;
            }
            
            // 最大値更新.
            ans = max(ans, r - l + 1);
        }
        
        // 2-3. 次回 の s を 設定.
        s = idx;
        
        // 2-4. 次回 の l に向けて準備.
        if(m.count(a[l])){
            // 要素をカウントダウン.
            m[a[l]]--;
            
            // 要素数が, 0 ならば, 種類数を減らす.
            if(m[a[l]] == 0) m.erase(a[l]);
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

int a[101010];

int main(){

// 1. 入力情報.

int N, K;

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

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

// 2. 連続する部分列で最大の長さを計算(尺取り法).

map<int, int> m;

int ans = 0, s = 0;

rep(l, N){

// 2-1. index を保存.

int idx = 0;

// 2-2. r を伸ばしていく.

repx(r, s, N){

// 要素をカウントアップ.

m[a[r]]++;

// index 更新.

idx = max(l + 1, r - 1);

// 要素の種類数が, K を超えたら, 処理を中断.

if(m.size() > K){

// 要素の種類数が, K を超えたので, mapから除去.

m.erase(a[r]);

// 次回処理における, 二重カウント防止のため, 処理.

if(m.count(a[s])){

// 要素をカウントダウン.

m[a[s]]--;

// 要素数が, 0 ならば, 種類数を減らす.

if(m[a[s]] == 0) m.erase(a[s]);

}

// Skip.

break;

}

// 最大値更新.

ans = max(ans, r - l + 1);

}

// 2-3. 次回の s を設定.

s = idx;

// 2-4. 次回の l に向けて準備.

if(m.count(a[l])){

// 要素をカウントダウン.

m[a[l]]--;

// 要素数が, 0 ならば, 種類数を減らす.

if(m[a[l]] == 0) m.erase(a[l]);

}

// 3. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
6

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

[出力例]
5

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

[出力例]
7

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

[出力例]
10

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

[出力例]
10

[入力例]

5 1

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 1 2 4 2

[出力例]

※AtCoderテストケースより

[入力例]

10 2

1 2 3 4 4 3 2 1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

10 2

2 3 1 3 2 1 1 1 1 1

[出力例]

[入力例]

10 1

2 3 1 3 2 1 1 1 1 1

[出力例]

[入力例]

20 3

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

[出力例]

[入力例]

32 3

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

[出力例]

[入力例]

52 3

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

[出力例]

■参照サイト
034 – There are few types of elements

2021年5月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 088 の問題F (Christmas Tree) を解いてみた.

■感想.
1. 問題Fは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 実装に非常に苦労したものの, 二分探索(応用版), および, 幅優先探索を復習することが出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc088/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
using vp = vector<P>;
#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
#define all(x) x.begin(), x.end()

int main(){

    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. A の 値は？
    int A = 0, root = -1;
    rep(i, N){
        int size = G[i].size();
        if(size & 1) A++;
        if(size == 1 && root == -1) root = i;
    }
    A /= 2;
    
    // 3. 根 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 3-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 3-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 3-5. 訪問済であれば, 処理をスキップ.
                if(d[e])            continue;
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, root, d);
    // printf("root=%d\n", root);
    // rep(i, N) printf("%d ", d[i]);
    
    // 4. 内側の二分探索用の判定関数.
    auto f = [&](vp &x, int im, int om, int* dp) -> bool{
        int xSize = x.size();
        int dpMax = x[im].a;
        if(dpMax > om) return false;
        vi nv;
        rep(i, xSize) if(i != im) nv.pb(x[i].a);
        int nvSize = nv.size();
        rep(i, nvSize / 2){
            int s = i;
            int e = nvSize - 1 - i;
            dpMax = max(dpMax, nv[s] + nv[e]);
        }
        return (dpMax <= om);
    };
    
    // 5. 外側の二分探索用の判定関数.
    auto g = [&](int om) -> bool{
        // 5-1. 初期化.
        bool ok = true;
        priority_queue<P> pq;
        int dp[101010];
        rep(i, N){
            if(i == root) continue;
            if(G[i].size() == 1 && i != root){
                dp[i] = 1;
            }else{
                dp[i] = 101010;
                pq.push({d[i], i});
            }
        }
        
        // 5-2. dp更新.
        while(!pq.empty()){
            // 終了条件.
            if(!ok) break;
            
            // 頂点 v を一つ取り出す.
            P p = pq.top();
            pq.pop();
            
            // 頂点 v の 頂点番号は？
            int v = p.b;
            
            // 頂点 v の 子頂点 を 保存.
            vp a;
            for(auto &u : G[v]) if(d[u] > d[v]) a.pb({dp[u], u});
            
            // sort.
            sort(all(a));
            
            // サイズチェック.
            int aSize = a.size();
            
            // サイズ 0 なら次へ.
            if(aSize == 0) continue;
            
            // 内側の二分探索.
            // 奇数の場合.
            if(aSize & 1){
                int il = -1, ih = aSize, im;
                while(il + 1 < ih){
                    im = (il + ih) >> 1;
                    if(f(a, im, om, dp)) ih = im;
                    else                 il = im;
                }
                if(a[ih].a + 1 > om || !f(a, ih, om, dp)){
                    ok = false;
                    break;
                }
                
                // 残ったパス(ih番目)から親方向に伸ばす.
                dp[v] = min(dp[v], a[ih].a + 1);
            }
            
            // 偶数の場合.
            if(!(aSize & 1)){
                // パターン 1.
                int dpMax = 0;
                rep(i, aSize / 2){
                    int s = i;
                    int e = aSize - 1 - i;
                    dpMax = max(dpMax, a[s].a + a[e].a);
                }
                
                // パターン 2.
                a.pop_back(); // 端点とする頂点を除外.
                int il = -1, ih = aSize, im;
                while(il + 1 < ih){
                    im = (il + ih) >> 1;
                    if(f(a, im, om, dp)) ih = im;
                    else                 il = im;
                }
                if(dpMax > om && !f(a, ih, om, dp)){
                    ok = false;
                    break;
                }
                if(dpMax <= om){
                    dp[v] = 1;
                    continue;
                }
                if(a[ih].a + 1 > om){
                    ok = false;
                    break;
                }
                
                // 残ったパス(ih番目)から親方向に伸ばす.
                dp[v] = min(dp[v], a[ih].a + 1);
            }
        }
        
        // 5-3. 結果を返却.
        return ok;
    };
    
    // 6. B の 値は？
    // 外側の二分探索.
    int ol = 0, oh = N, om;
    while(ol + 1 < oh){
        om = (ol + oh) >> 1;
        if(g(om)) oh = om;
        else      ol = om;
        // printf("oh=%d ol=%d om=%d\n", oh, ol, om);
    }
    
    // 7. 出力.
    int B = oh;
    printf("%d %d\n", A, B);
    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

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using vp = vector<P>;

#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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. A の値は？

int A = 0, root = -1;

rep(i, N){

int size = G[i].size();

if(size & 1) A++;

if(size == 1 && root == -1) root = i;

}

A /= 2;

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

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

auto bfs = [&](vvi &G, int s, int* d){

// 3-1. 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

// 3-3. キューから取り出す.

int u = q.front();

q.pop();

// 3-4. 取り出した要素を処理.

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

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

if(d[e]) continue;

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

}

return;

};

int d[N];

rep(i, N) d[i] = 0;

bfs(G, root, d);

// printf("root=%d\n", root);

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

// 4. 内側の二分探索用の判定関数.

auto f = [&](vp &x, int im, int om, int* dp) -> bool{

int xSize = x.size();

int dpMax = x[im].a;

if(dpMax > om) return false;

vi nv;

rep(i, xSize) if(i != im) nv.pb(x[i].a);

int nvSize = nv.size();

rep(i, nvSize / 2){

int s = i;

int e = nvSize - 1 - i;

dpMax = max(dpMax, nv[s] + nv[e]);

}

return (dpMax <= om);

};

// 5. 外側の二分探索用の判定関数.

auto g = [&](int om) -> bool{

// 5-1. 初期化.

bool ok = true;

priority_queue<P> pq;

int dp[101010];

rep(i, N){

if(i == root) continue;

if(G[i].size() == 1 && i != root){

dp[i] = 1;

}else{

dp[i] = 101010;

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

}

// 5-2. dp更新.

while(!pq.empty()){

// 終了条件.

if(!ok) break;

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

P p = pq.top();

pq.pop();

// 頂点 v の頂点番号は？

int v = p.b;

// 頂点 v の子頂点を保存.

vp a;

for(auto &u : G[v]) if(d[u] > d[v]) a.pb({dp[u], u});

// sort.

sort(all(a));

// サイズチェック.

int aSize = a.size();

// サイズ 0 なら次へ.

if(aSize == 0) continue;

// 内側の二分探索.

// 奇数の場合.

if(aSize & 1){

int il = -1, ih = aSize, im;

while(il + 1 < ih){

im = (il + ih) >> 1;

if(f(a, im, om, dp)) ih = im;

else il = im;

}

if(a[ih].a + 1 > om || !f(a, ih, om, dp)){

ok = false;

break;

}

// 残ったパス(ih番目)から親方向に伸ばす.

dp[v] = min(dp[v], a[ih].a + 1);

}

// 偶数の場合.

if(!(aSize & 1)){

// パターン 1.

int dpMax = 0;

rep(i, aSize / 2){

int s = i;

int e = aSize - 1 - i;

dpMax = max(dpMax, a[s].a + a[e].a);

}

// パターン 2.

a.pop_back(); // 端点とする頂点を除外.

int il = -1, ih = aSize, im;

while(il + 1 < ih){

im = (il + ih) >> 1;

if(f(a, im, om, dp)) ih = im;

else il = im;

}

if(dpMax > om && !f(a, ih, om, dp)){

ok = false;

break;

}

if(dpMax <= om){

dp[v] = 1;

continue;

}

if(a[ih].a + 1 > om){

ok = false;

break;

}

// 残ったパス(ih番目)から親方向に伸ばす.

dp[v] = min(dp[v], a[ih].a + 1);

}

// 5-3. 結果を返却.

return ok;

};

// 6. B の値は？

// 外側の二分探索.

int ol = 0, oh = N, om;

while(ol + 1 < oh){

om = (ol + oh) >> 1;

if(g(om)) oh = om;

else ol = om;

// printf("oh=%d ol=%d om=%d\n", oh, ol, om);

}

// 7. 出力.

int B = oh;

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
8 3

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

[出力例]
10 6

100

101

102

103

104

105

[入力例]

1 2

2 3

2 4

4 5

4 6

6 7

[出力例]

3 2

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

4 5

5 6

5 7

5 8

[出力例]

2 5

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

2 5

6 5

6 7

7 8

5 9

10 5

[出力例]

3 4

※AtCoderテストケースより

[入力例]

1 2

3 2

4 2

3 6

3 5

4 8

4 7

5 10

5 11

5 9

9 12

9 13

10 18

10 19

10 20

7 14

14 15

15 16

15 17

[出力例]

8 3

[入力例]

1 32

3 32

2 32

6 32

1 9

1 10

6 5

8 11

5 33

33 4

33 8

33 7

16 15

4 16

7 12

7 13

7 14

9 21

10 17

10 18

10 19

10 20

20 22

20 23

20 24

31 25

14 26

26 27

26 28

26 29

26 30

26 31

[出力例]

10 6

■参照サイト
AtCoder Regular Contest 088

C++の練習を兼ねて, 競プロ典型 90 問 の 問題036 (Max Manhattan Distance) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 020 の 問題C (Median Sum) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題043 (Maze Challenge with Lack of Sleep) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題039 (Tree Distance) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 201 の 問題C (Secret Number) ～ 問題D (Game in Momotetsu World) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題008 (AtCounter) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題013 (Passing) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 200 の 問題C (Ringo’s Favorite Numbers 2) ～ 問題D (Happy Birthday! 2) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題034 (There are few types of elements) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 088 の 問題F (Christmas Tree) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題036 (Max Manhattan Distance) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 020 の問題C (Median Sum) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題043 (Maze Challenge with Lack of Sleep) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題039 (Tree Distance) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 201 の問題C (Secret Number) ～問題D (Game in Momotetsu World) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題008 (AtCounter) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題013 (Passing) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 200 の問題C (Ringo’s Favorite Numbers 2) ～問題D (Happy Birthday! 2) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題034 (There are few types of elements) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 088 の問題F (Christmas Tree) を解いてみた.