個人用メモ帳

2022年4月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 150 の問題F (Xor Shift) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. クヌース–モリス–プラット(Knuth–Morris–Pratt algorithm)法を学習できたので, 非常に良かったと思う.
3. 本問では, 周期を知る必要が出てきたため, KMP法を, 最大2回まで実施する形で対応した.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

// https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
// -> 照合が一致する複数の箇所を抽出するように拡張した版.
template<typename T>
struct KMP{
    vi M;  // 部分マッチテーブル.
    T S;   // テキスト.
    T W;   // 単語.
    int E; // 実行回数.
    KMP(T s, T w, int e = 1): S(s), W(w), E(e) {}
    void makeTable(){
        int i = 2, j = 0, n = W.size();
        vi t(n + 1);
        t[0] = -1;
        t[1] = 0;
        while(i < n){
            // 第一のケース.
            if(W[i - 1] == W[j]){
                t[i] = j + 1;
                ++i;
                ++j;
                continue;
            }
            
            // 第二のケース.
            if(j){
                j = t[j];
                continue;
            }
            
            // 第三のケース.
            t[i] = 0;
            ++i;
        }
        
        // 生成結果.
        M = t;
    }
    vi search(){
        vi ret;    // マッチした位置を保存.
        int m = 0; // S 内 の 現在照合中の開始位置.
        int i = 0; // W 内 の 現在位置.
        while(m + i < S.size() && E){
            if(W[i] == S[m + i]){
                ++i;
                if(i == W.size()){
                    ret.pb(m); // マッチした位置を保存.
                    ++m;       // 次へ.
                    i = 0;     // 初期化.
                    --E;       // デクリメント.
                }
                continue;
            }
            m += (i - M[i]);
            if(i) i = M[i];
        }
        return ret;
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi a(N), b(N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. 数列 c, d 作成.
    vi c, d;
    rep(i, N * 2 - 1) c.pb(a[i % N] ^ a[(i + 1) % N]);
    rep(i, N * 1 - 0) d.pb(b[i % N] ^ b[(i + 1) % N]);
    
    // ex. 
    // 以下の場合, 11 77 111 123 150 が出力される.
    // KMP<string> kmp("aopqrssttuuabracadabrapqrabra cadabrapqrpqrsabraceadabraroutxowiystabrcadabraabracadabraabdracadabraxyzabcdefghabracadabraiabracadabra deded xyzdeded abracadabraopqtdhg abracadabrajjtxhg", "abracadabra", 5);
    // kmp.makeTable();
    // vi v = kmp.search();
    // for(auto &p : v) printf("%d ", p);
    // puts("");
    
    // 3. KMP法(k の 抽出).
    KMP<vi> kmp(c, d, 2);
    kmp.makeTable();
    vi ks = kmp.search();
    // for(auto &k : ks) printf("%d ", k);
    // puts("");
    
    // 4. 周期を考慮.
    if(ks.size() == 2){
        int f = ks[1] - ks[0];
        while(f + ks.back() < N) ks.pb(f + ks.back());
    }
    
    // 5. x の 抽出.
    vp ans;
    for(auto &k : ks) ans.pb({k, a[k] ^ b[0]});
    
    // 6. sort.
    sort(all(ans));
    
    // 7. 出力.
    for(auto &p : ans) printf("%d %d\n", p.a, p.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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vi = vector<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 a first

#define b second

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

#define pb push_back

// https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法

// -> 照合が一致する複数の箇所を抽出するように拡張した版.

template<typename T>

struct KMP{

vi M; // 部分マッチテーブル.

T S; // テキスト.

T W; // 単語.

int E; // 実行回数.

KMP(T s, T w, int e = 1): S(s), W(w), E(e) {}

void makeTable(){

int i = 2, j = 0, n = W.size();

vi t(n + 1);

t[0] = -1;

t[1] = 0;

while(i < n){

// 第一のケース.

if(W[i - 1] == W[j]){

t[i] = j + 1;

++i;

++j;

continue;

}

// 第二のケース.

if(j){

j = t[j];

continue;

}

// 第三のケース.

t[i] = 0;

++i;

}

// 生成結果.

M = t;

}

vi search(){

vi ret; // マッチした位置を保存.

int m = 0; // S 内の現在照合中の開始位置.

int i = 0; // W 内の現在位置.

while(m + i < S.size() && E){

if(W[i] == S[m + i]){

++i;

if(i == W.size()){

ret.pb(m); // マッチした位置を保存.

++m; // 次へ.

i = 0; // 初期化.

--E; // デクリメント.

}

continue;

}

m += (i - M[i]);

if(i) i = M[i];

}

return ret;

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi a(N), b(N);

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

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

// 2. 数列 c, d 作成.

vi c, d;

rep(i, N * 2 - 1) c.pb(a[i % N] ^ a[(i + 1) % N]);

rep(i, N * 1 - 0) d.pb(b[i % N] ^ b[(i + 1) % N]);

// ex.

// 以下の場合, 11 77 111 123 150 が出力される.

// KMP<string> kmp("aopqrssttuuabracadabrapqrabra cadabrapqrpqrsabraceadabraroutxowiystabrcadabraabracadabraabdracadabraxyzabcdefghabracadabraiabracadabra deded xyzdeded abracadabraopqtdhg abracadabrajjtxhg", "abracadabra", 5);

// kmp.makeTable();

// vi v = kmp.search();

// for(auto &p : v) printf("%d ", p);

// puts("");

// 3. KMP法(k の抽出).

KMP<vi> kmp(c, d, 2);

kmp.makeTable();

vi ks = kmp.search();

// for(auto &k : ks) printf("%d ", k);

// puts("");

// 4. 周期を考慮.

if(ks.size() == 2){

int f = ks[1] - ks[0];

while(f + ks.back() < N) ks.pb(f + ks.back());

}

// 5. x の抽出.

vp ans;

for(auto &k : ks) ans.pb({k, a[k] ^ b[0]});

// 6. sort.

sort(all(ans));

// 7. 出力.

for(auto &p : ans) printf("%d %d\n", p.a, p.b);

return 0;

}

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

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

[入力例]
5
0 0 0 0 0
2 2 2 2 2

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

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

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

[入力例]
2
1 2
0 0

[出力例]

※AtCoderテストケースより

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

[出力例]
0 2
1 2
2 2

[入力例]
4
1 0 1 0
0 1 0 1

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

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

[出力例]
1 0
4 0
7 0
10 0
13 0

[入力例]
18
0 1 2 8 5 7 0 1 2 8 5 7 0 1 2 8 5 7
6 5 15 2 0 7 6 5 15 2 0 7 6 5 15 2 0 7

[出力例]
1 7
7 7
13 7

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

[出力例]
1 1
5 1
9 1
13 1
17 1
21 1

[入力例]

0 2 1

1 2 3

[出力例]

1 3

※AtCoderテストケースより

[入力例]

0 0 0 0 0

2 2 2 2 2

[出力例]

0 2

1 2

2 2

3 2

4 2

※AtCoderテストケースより

[入力例]

0 1 3 7 6 4

1 5 4 6 2 3

[出力例]

2 2

5 5

※AtCoderテストケースより

[入力例]

1 2

0 0

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1

3 3 3

[出力例]

0 2

1 2

2 2

[入力例]

1 0 1 0

0 1 0 1

[出力例]

0 1

1 0

2 1

3 0

[入力例]

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

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

[出力例]

1 0

4 0

7 0

10 0

13 0

[入力例]

0 1 2 8 5 7 0 1 2 8 5 7 0 1 2 8 5 7

6 5 15 2 0 7 6 5 15 2 0 7 6 5 15 2 0 7

[出力例]

1 7

7 7

13 7

[入力例]

1 2 5 2 1 2 5 2 1 2 5 2 1 2 5 2 1 2 5 2 1 2 5 2

3 4 3 0 3 4 3 0 3 4 3 0 3 4 3 0 3 4 3 0 3 4 3 0

[出力例]

1 1

5 1

9 1

13 1

17 1

21 1

■参照サイト
AtCoder Beginner Contest 150

2022年4月11日

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

C++の練習を兼ねて, AtCoder Regular Contest 006 の問題B (あみだくじ) を解いてみた.

■感想.
1. 問題Bは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 入力情報に半角スペースがあったため, getchar関数を使って実装した.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[33][33]; // i行目で, j列目 と (j + 1)列目 を 入れ替えるか？

int main(){
    
    // 1. 入力情報.
    int N, L, ans = 0;
    scanf("%d %d", &N, &L);
    getchar();
    rep(i, L + 1){
        int j = 0;
        while(1){
            int c = getchar();
            if(c == '\n' || c == EOF) break;
            if(c == '-') a[i][(j + 1) / 2] = 1;
            if(c == 'o') ans = (j / 2) + 1;
            ++j;
        }
    }
    
    // 2. あみだくじを辿る.
    repr(i, L - 1, 0){
        // 左端.
        if(ans == 1){
            if(a[i][1]) ++ans;
            continue;
        }
        
        // 中央.
        if(ans > 1 && ans < N){
            int d = 0;
            if(a[i][ans - 1]) --d;
            if(a[i][ans + 0]) ++d;
            ans += d;
            continue;
        }
        
        // 右端.
        if(ans == N){
            if(a[i][N - 1]) --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 a[33][33]; // i行目で, j列目と (j + 1)列目を入れ替えるか？

int main(){

// 1. 入力情報.

int N, L, ans = 0;

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

getchar();

rep(i, L + 1){

int j = 0;

while(1){

int c = getchar();

if(c == '\n' || c == EOF) break;

if(c == '-') a[i][(j + 1) / 2] = 1;

if(c == 'o') ans = (j / 2) + 1;

++j;

}

// 2. あみだくじを辿る.

repr(i, L - 1, 0){

// 左端.

if(ans == 1){

if(a[i][1]) ++ans;

continue;

}

// 中央.

if(ans > 1 && ans < N){

int d = 0;

if(a[i][ans - 1]) --d;

if(a[i][ans + 0]) ++d;

ans += d;

continue;

}

// 右端.

if(ans == N){

if(a[i][N - 1]) --ans;

}

// 3. 出力.

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

return 0;

}

[入力例]
3 2
| |-|
|-| |
o    

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

[入力例]
10 2
| |-| |-| |-| |-| |
|-| |-| |-| |-| |-|
            o      

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

[入力例]
1 5
|
|
|
|
|
o

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

[入力例]
4 2
| | | |
| | | |
      o

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

[入力例]
9 8
| | | | | | | | |
|-| | |-| | |-| |
| | |-| | |-| | |
| |-| | | | | |-|
| | | |-| | | |-|
| | |-| |-| | | |
|-| | |-| | |-| |
| | | | | |-| | |
            o    

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

[入力例]
3 3
| |-|
|-| |
| |-|
    o

[出力例]
1

[入力例]
5 7
| |-| | |
|-| |-| |
| |-| |-|
| | |-| |
| |-| |-|
|-| |-| |
| |-| |-|
  o      

[出力例]
2

[入力例]
10 11
| |-| | | |-| | | |
| |-| | | | |-| | |
| | |-| | | |-| | |
| |-| |-| |-| |-| |
| |-| | |-| | |-| |
| | |-| |-| | | |-|
|-| |-| | | |-| | |
| | | |-| |-| |-| |
| | |-| |-| | |-| |
|-| |-| | |-| | |-|
| | | |-| | | | | |
        o          

[出力例]
3

100

[入力例]

3 2

| |-|

|-| |

[出力例]

※AtCoderテストケースより

[入力例]

10 2

| |-| |-| |-| |-| |

|-| |-| |-| |-| |-|

[出力例]

※AtCoderテストケースより

[入力例]

1 5

[出力例]

※AtCoderテストケースより

[入力例]

4 2

| | | |

[出力例]

※AtCoderテストケースより

[入力例]

9 8

| | | | | | | | |

|-| | |-| | |-| |

| | |-| | |-| | |

| |-| | | | | |-|

| | | |-| | | |-|

| | |-| |-| | | |

|-| | |-| | |-| |

| | | | | |-| | |

[出力例]

※AtCoderテストケースより

[入力例]

3 3

| |-|

|-| |

| |-|

[出力例]

[入力例]

5 7

| |-| | |

|-| |-| |

| |-| |-|

| | |-| |

| |-| |-|

|-| |-| |

| |-| |-|

[出力例]

[入力例]

10 11

| |-| | | |-| | | |

| |-| | | | |-| | |

| | |-| | | |-| | |

| |-| |-| |-| |-| |

| |-| | |-| | |-| |

| | |-| |-| | | |-|

|-| |-| | | |-| | |

| | | |-| |-| |-| |

| | |-| |-| | |-| |

|-| |-| | |-| | |-|

| | | |-| | | | | |

[出力例]

■参照サイト
AtCoder Regular Contest 006

2022年4月10日

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

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題A (Larger Score) を解いてみた.

■感想.
1. 問題Aは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にあるロジックで, 操作回数の最小値が計算できることが, 非常に印象深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc138/editorial/3746
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using PQ = priority_queue<int>;
using vi = vector<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 a first
#define b second
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vi a(N);
    vp op(N);
    rep(i, N){
        scanf("%d", &a[i]);
        op[i].a = a[i];
        op[i].b = -i;
    }
    
    // 2. sort.
    sort(all(op));
    
    // 3. 操作回数の最小値は？
    int ans = 2020202020;
    PQ pq;
    for(auto &p : op){
        int i = -p.b;
        if(i < K){
            pq.push(i);
            continue;
        }
        if(!pq.empty()){
            int j = pq.top();
            if(i >= K && a[j] < a[i]) ans = min(ans, i - j);
        }
    }
    
    // 4. 出力.
    printf("%d\n", (ans == 2020202020) ? -1 : ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc138/editorial/3746

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using PQ = priority_queue<int>;

using vi = vector<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 a first

#define b second

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

int main(){

// 1. 入力情報.

int N, K;

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

vi a(N);

vp op(N);

rep(i, N){

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

op[i].a = a[i];

op[i].b = -i;

}

// 2. sort.

sort(all(op));

// 3. 操作回数の最小値は？

int ans = 2020202020;

PQ pq;

for(auto &p : op){

int i = -p.b;

if(i < K){

pq.push(i);

continue;

}

if(!pq.empty()){

int j = pq.top();

if(i >= K && a[j] < a[i]) ans = min(ans, i - j);

}

// 4. 出力.

printf("%d\n", (ans == 2020202020) ? -1 : ans);

return 0;

}

[入力例]
4 2
2 1 1 2

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

[入力例]
3 1
3 2 1

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

[入力例]
20 13
90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054

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

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

[出力例]
2

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

[出力例]
2

[入力例]
20 5
33 77 55 88 121 30 33 22 34 78 56 123 89 125 11 222 99 5 100 50

[出力例]
7

[入力例]
100 7
1111 3333 1112 3333 2222 3333 2223 100 282 208 1111 138 257 173 88 1111 345 234 118 1110 252 65 91 234 30 234 108 260 21 126 57 97 95 1110 200 234 234 72 1111 77 1111 66 99 222 1110 170 282 281 345 1111 292 226 174 209 1110 122 1110 219 179 345 167 345 1110 169 193 345 1111 170 234 1 1110 211 100 345 1110 211 1110 100 211 133 123 1110 222 108 78 1111 197 345 100 100 1000 1112 1113 2223 3334 2224 1110 1111 100 101

[出力例]
88

[入力例]

4 2

2 1 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

3 1

3 2 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

20 13

90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054

[出力例]

※AtCoderのテストケースより

[入力例]

7 3

3 2 5 1 6 3 7

[出力例]

[入力例]

10 3

3 1 4 1 5 9 2 6 5 3

[出力例]

[入力例]

20 5

33 77 55 88 121 30 33 22 34 78 56 123 89 125 11 222 99 5 100 50

[出力例]

[入力例]

100 7

1111 3333 1112 3333 2222 3333 2223 100 282 208 1111 138 257 173 88 1111 345 234 118 1110 252 65 91 234 30 234 108 260 21 126 57 97 95 1110 200 234 234 72 1111 77 1111 66 99 222 1110 170 282 281 345 1111 292 226 174 209 1110 122 1110 219 179 345 167 345 1110 169 193 345 1111 170 234 1 1110 211 100 345 1110 211 1110 100 211 133 123 1110 222 108 78 1111 197 345 100 100 1000 1112 1113 2223 3334 2224 1110 1111 100 101

[出力例]

■参照サイト
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)

2022年4月8日

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

C++の練習を兼ねて, AtCoder Beginner Contest 150 の問題D (Semi Common Multiple) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL M;
    scanf("%d %lld", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 2 で 割り切れる回数.
    set<int> st;
    rep(i, N){
        LL b = a[i];
        int x = 0;
        while(!(b & 1)){
            b >>= 1;
            ++x;
        }
        st.insert(x);
    }
    
    // 3. 例外.
    if(st.size() > 1){
        puts("0");
        return 0;
    }
    
    // 4. 最小公倍数.
    LL lcm = a[0] / 2;
    repx(i, 1, N){
        LL g = __gcd(lcm, a[i] / 2);
        lcm /= g;
        lcm *= (a[i] / 2);
    }
    
    // 5. 集計(85.txt で WA版となったので, ロジック修正).
    M += (lcm - M % lcm);
    LL ans = M / lcm / 2;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[101010];

int main(){

// 1. 入力情報.

int N;

LL M;

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

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

// 2. 2 で割り切れる回数.

set<int> st;

rep(i, N){

LL b = a[i];

int x = 0;

while(!(b & 1)){

b >>= 1;

++x;

}

st.insert(x);

}

// 3. 例外.

if(st.size() > 1){

puts("0");

return 0;

}

// 4. 最小公倍数.

LL lcm = a[0] / 2;

repx(i, 1, N){

LL g = __gcd(lcm, a[i] / 2);

lcm /= g;

lcm *= (a[i] / 2);

}

// 5. 集計(85.txt で WA版となったので, ロジック修正).

M += (lcm - M % lcm);

LL ans = M / lcm / 2;

// 6. 出力.

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

return 0;

}

[入力例]
2 50
6 10

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

[入力例]
3 100
14 22 40

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

[入力例]
5 1000000000
6 6 2 6 2

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

[入力例]
5 987654321
70 210 350 490 630

[出力例]
44792

[入力例]
10 1000000000
14 70 70 98 98 126 154 154 178 178

[出力例]
232

[入力例]
7 20200110
40 56 104 24 88 136 168

[出力例]
10

[入力例]
12 20220408
24 24 40 56 40 24 24 104 56 136 56 40

[出力例]
109

[入力例]

2 50

6 10

[出力例]

※AtCoderテストケースより

[入力例]

3 100

14 22 40

[出力例]

※AtCoderテストケースより

[入力例]

5 1000000000

6 6 2 6 2

[出力例]

166666667

※AtCoderテストケースより

[入力例]

5 987654321

70 210 350 490 630

[出力例]

44792

[入力例]

10 1000000000

14 70 70 98 98 126 154 154 178 178

[出力例]

232

[入力例]

7 20200110

40 56 104 24 88 136 168

[出力例]

[入力例]

12 20220408

24 24 40 56 40 24 24 104 56 136 56 40

[出力例]

109

■参照サイト
AtCoder Beginner Contest 150

2022年4月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 165 の問題F (LIS on Tree) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. LIS(Longest increase subsequence) を学習できたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc165/editorial.pdf
// 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
#define all(x) x.begin(), x.end()
const int INF = 2020202020;
int a[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    vi dp(N), ans(N);
    auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m){
        // 終了条件.
        if(m[cur]) return;
        
        // 訪問済みフラグ設定.
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            // Skip.
            if(nex == bef) continue;
            
            // dp更新.
            int at = lower_bound(all(dp), a[nex]) - dp.begin();
            int pd = dp[at];
            dp[at] = a[nex];
            
            // 狭義単調増加な数列の長さの最大値は？
            // -> 解説上 の LIS(Longest increase subsequence) の ロジック を 考慮すると, 
            //    初期化で, INF を設定するので, (INF - 1) の インデックス を 採用すれば, 良さそうに見える.
            ans[nex] = lower_bound(all(dp), INF - 1) - dp.begin();
            
            // 次へ.
            self(self, G, nex, cur, m);
            
            // dp戻し.
            dp[at] = pd;
        }
    };
    int memo[N];
    ans[0] = 1;
    rep(i, N) memo[i] = 0, dp[i] = INF;
    dp[0] = a[0];
    dfs(dfs, G, 0, -1, memo);
    
    // 3. 出力.
    rep(i, N) printf("%d\n", ans[i]);
    return 0;
    
}

// 解き直し.

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

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

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

const int INF = 2020202020;

int a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

vvi G(N);

rep(i, N - 1){

int u, v;

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

--u;

--v;

G[u].pb(v);

G[v].pb(u);

}

// 2. dfs.

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

vi dp(N), ans(N);

auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m){

// 終了条件.

if(m[cur]) return;

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

m[cur] = 1;

// 隣接頂点.

for(auto &nex : G[cur]){

// Skip.

if(nex == bef) continue;

// dp更新.

int at = lower_bound(all(dp), a[nex]) - dp.begin();

int pd = dp[at];

dp[at] = a[nex];

// 狭義単調増加な数列の長さの最大値は？

// -> 解説上の LIS(Longest increase subsequence) のロジックを考慮すると,

// 初期化で, INF を設定するので, (INF - 1) のインデックスを採用すれば, 良さそうに見える.

ans[nex] = lower_bound(all(dp), INF - 1) - dp.begin();

// 次へ.

self(self, G, nex, cur, m);

// dp戻し.

dp[at] = pd;

}

};

int memo[N];

ans[0] = 1;

rep(i, N) memo[i] = 0, dp[i] = INF;

dp[0] = a[0];

dfs(dfs, G, 0, -1, memo);

// 3. 出力.

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

return 0;

}

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

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

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

[出力例]
1
2
2
2
3

[入力例]
12
2 3 5 6 11 12 15 17 18 22 24 27
1 2
2 5
2 4
6 4
7 1
7 8
7 9
9 10
4 3
3 11
3 12

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

[入力例]
20
1 3 4 7 8 11 12 17 21 25 28 31 33 49 55 77 100 101 123 222
1 6
1 7
1 9
18 9
19 9
20 9
3 7
3 10
3 11
16 11
17 11
8 7
8 5
5 2
5 4
2 12
2 13
13 14
13 15

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

[入力例]

1 2 5 3 4 6 7 3 2 4

1 2

2 3

3 4

4 5

3 6

6 7

1 8

8 9

9 10

[出力例]

※AtCoderテストケースより

[入力例]

2 5 7 9 10

1 2

4 1

5 4

3 4

[出力例]

[入力例]

2 3 5 6 11 12 15 17 18 22 24 27

1 2

2 5

2 4

6 4

7 1

7 8

7 9

9 10

4 3

3 11

3 12

[出力例]

[入力例]

1 3 4 7 8 11 12 17 21 25 28 31 33 49 55 77 100 101 123 222

1 6

1 7

1 9

18 9

19 9

20 9

3 7

3 10

3 11

16 11

17 11

8 7

8 5

5 2

5 4

2 12

2 13

13 14

13 15

[出力例]

■参照サイト
AtCoder Beginner Contest 165

2022年4月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 153 の問題E (Crested Ibis vs Monster) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc153/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--)
const int INF = 2020202020;
int a[1010], b[1010], dp[20202];

int main(){
    
    // 1. 入力情報.
    int H, N, aMax = 0;
    scanf("%d %d", &H, &N);
    rep(i, N){
        scanf("%d %d", &a[i], &b[i]);
        aMax = max(aMax, a[i]);
    }
    
    // 2. 初期化.
    rep(i, 20202) dp[i] = INF;
    dp[0] = 0;
    
    // 3. dp更新.
    rep(i, H + aMax + 1){
        // N種類の魔法を試す.
        // -> 前回のモンスターの体力 i から, 今回のモンスターの体力 i + a[j] を 減らすには？
        rep(j, N){
            int na = i + a[j];
            if(na <= H + aMax) dp[na] = min(dp[na], dp[i] + b[j]);
        }
    }
    
    // 4. 最小値は？
    int ans = INF;
    repx(i, H, H + aMax + 1) ans = min(ans, dp[i]);
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

const int INF = 2020202020;

int a[1010], b[1010], dp[20202];

int main(){

// 1. 入力情報.

int H, N, aMax = 0;

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

rep(i, N){

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

aMax = max(aMax, a[i]);

}

// 2. 初期化.

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

dp[0] = 0;

// 3. dp更新.

rep(i, H + aMax + 1){

// N種類の魔法を試す.

// -> 前回のモンスターの体力 i から, 今回のモンスターの体力 i + a[j] を減らすには？

rep(j, N){

int na = i + a[j];

if(na <= H + aMax) dp[na] = min(dp[na], dp[i] + b[j]);

}

// 4. 最小値は？

int ans = INF;

repx(i, H, H + aMax + 1) ans = min(ans, dp[i]);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
100 6
1 1
2 3
3 9
4 27
5 81
6 243

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

[入力例]
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

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

[入力例]
2020 12
64 35
55 121
51 31
45 64
60 103
66 69
77 110
25 39
8 19
75 110
80 100
3 12

[出力例]
1112

[入力例]
2022 20
11 12
19 22
2 5
5 7
16 17
17 18
6 8
19 20
22 23
7 8
13 18
16 18
7 8
9 10
10 11
24 25
6 7
18 19
9 10
5 6

[出力例]
2107

[入力例]

9 3

8 3

4 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

100 6

1 1

2 3

3 9

4 27

5 81

6 243

[出力例]

100

※AtCoderテストケースより

[入力例]

9999 10

540 7550

691 9680

700 9790

510 7150

415 5818

551 7712

587 8227

619 8671

588 8228

176 2461

[出力例]

139815

※AtCoderテストケースより

[入力例]

2020 12

64 35

55 121

51 31

45 64

60 103

66 69

77 110

25 39

8 19

75 110

80 100

3 12

[出力例]

1112

[入力例]

2022 20

11 12

19 22

2 5

5 7

16 17

17 18

6 8

19 20

22 23

7 8

13 18

16 18

7 8

9 10

10 11

24 25

6 7

18 19

9 10

5 6

[出力例]

2107

■参照サイト
AtCoder Beginner Contest 153

2022年4月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 135 の問題D (Digits Parade) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc135/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
LL dp[101010][13]; // 先頭 i 文字まで見て, 13 で割った余りが, j となるもの.

int main(){
    
    // 1. 入力情報.
    char s[101010];
    scanf("%s", s);
    int N = strlen(s);
    
    // 2. dp更新.
    // -> 空文字を, 1通りと数えておく.
    dp[0][0] = 1;
    rep(i, N){
        // i文字目が, '?'.
        if(s[i] == '?'){
            // 前回, 13 で割った余りが, j だった.
            rep(j, 13){
                // '0' ～ '9' まで試す.
                rep(k, 10){
                    // 桁上がりするので, 今回の余りは, 10 * j に 変わるので注意.
                    int r = (10 * j + k) % 13;
                    dp[i + 1][r] += dp[i][j];
                    dp[i + 1][r] %= MOD;
                }
            }
        }
        
        // i文字目が, '?' 以外.
        if(s[i] != '?'){
            // 前回, 13 で割った余りが, j だった.
            rep(j, 13){
                // 桁上がりするので, 今回の余りは, 10 * j に 変わるので注意.
                int r = (10 * j + (s[i] - '0')) % 13;
                dp[i + 1][r] += dp[i][j];
                dp[i + 1][r] %= MOD;
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[N][5]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

LL dp[101010][13]; // 先頭 i 文字まで見て, 13 で割った余りが, j となるもの.

int main(){

// 1. 入力情報.

char s[101010];

scanf("%s", s);

int N = strlen(s);

// 2. dp更新.

// -> 空文字を, 1通りと数えておく.

dp[0][0] = 1;

rep(i, N){

// i文字目が, '?'.

if(s[i] == '?'){

// 前回, 13 で割った余りが, j だった.

rep(j, 13){

// '0' ～ '9' まで試す.

rep(k, 10){

// 桁上がりするので, 今回の余りは, 10 * j に変わるので注意.

int r = (10 * j + k) % 13;

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

dp[i + 1][r] %= MOD;

}

// i文字目が, '?' 以外.

if(s[i] != '?'){

// 前回, 13 で割った余りが, j だった.

rep(j, 13){

// 桁上がりするので, 今回の余りは, 10 * j に変わるので注意.

int r = (10 * j + (s[i] - '0')) % 13;

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

dp[i + 1][r] %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
??2??5

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

[入力例]
?44

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

[入力例]
7?4

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

[入力例]
?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???

[出力例]
153716888

[入力例]
1??

[出力例]
7

[入力例]
8???

[出力例]
77

[入力例]
8?81??5?

[出力例]
770

[入力例]
82?25?2503?760185?8??617???15835658?2??55??69762??

[出力例]
763846179

[入力例]
770727717?82808??9252191127251971298727583?17?0269?92731199011800680299961836881090875568506192396795068779998??5658266906993298105838?6215212993530867??8915??7211?996?689272?268952?963316055136811370?7353119560?177725?5880?772?860?9295165577?26008?660701267631371153559915505880883629?139?55553309952?231626768000805?5523169206293?5922?2587?27086?37536268560938053207122?920180623765?29?79391789039?2821?1??727?769?38?807?393?92989?7?371592?53?36271150?9516516013963?297376665763?5176?71673305667722

[出力例]
869231461

[入力例]

??2??5

[出力例]

768

※AtCoderテストケースより

[入力例]

?44

[出力例]

※AtCoderテストケースより

[入力例]

7?4

[出力例]

※AtCoderテストケースより

[入力例]

?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???

[出力例]

153716888

[入力例]

1??

[出力例]

[入力例]

8???

[出力例]

[入力例]

8?81??5?

[出力例]

770

[入力例]

82?25?2503?760185?8??617???15835658?2??55??69762??

[出力例]

763846179

[入力例]

770727717?82808??9252191127251971298727583?17?0269?92731199011800680299961836881090875568506192396795068779998??5658266906993298105838?6215212993530867??8915??7211?996?689272?268952?963316055136811370?7353119560?177725?5880?772?860?9295165577?26008?660701267631371153559915505880883629?139?55553309952?231626768000805?5523169206293?5922?2587?27086?37536268560938053207122?920180623765?29?79391789039?2821?1??727?769?38?807?393?92989?7?371592?53?36271150?9516516013963?297376665763?5176?71673305667722

[出力例]

869231461

■参照サイト
AtCoder Beginner Contest 135

2022年4月2日

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

C++の練習を兼ねて, AtCoder Beginner Contest 149 の問題F (Surrounded Nodes) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc149/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
const LL MOD = 1e9 + 7;
LL mPow2[202020], c[202020];

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. 事前計算.
    mPow2[0] = 1;
    repx(i, 1, 202020) mPow2[i] = (mPow2[i - 1] * (LL)(5e8 + 4)) % MOD;
    rep(i, 202020) c[i] = (MOD + 1 - mPow2[i]) % MOD;
    // rep(i, N) printf("c[%d]=%lld\n", i, c[i]);
    
    // 3. dfs(部分木サイズ).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s){
        // 部分木サイズ(往路).
        ++s[cur];
        
        // 終了条件.
        if(m[cur]) return;
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]) if(nex != bef) self(self, G, nex, cur, m, s);
        
        // 部分木サイズ(復路).
        if(bef != -1) s[bef] += s[cur];
    };
    int subTree[N], memo[N];
    rep(i, N) subTree[i] = memo[i] = 0;
    dfs(dfs, G, 0, -1, memo, subTree);
    // rep(i, N) printf("subTree[%d]=%d\n", i, subTree[i]);
    
    // 4. S の 辺数(期待値).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    LL ans = 0;
    function<void(vvi&, int, int, int*)> f = [&](vvi &G, int cur, int bef, int* m){
        // 終了条件.
        if(m[cur]) return;
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            // 親頂点か否か.
            if(nex == bef) continue;
            
            // S に含まれる辺数の期待値を加算.
            ans += c[subTree[nex]] * c[N - subTree[nex]] % MOD;
            ans %= MOD;
            
            // 次へ.
            f(G, nex, cur, m);
        }
    };
    rep(i, N) memo[i] = 0;
    f(G, 0, -1, memo);
    
    // 5. S の 頂点数(期待値).
    // 5-1. 頂点数は, 辺数よりも, 1 多い.
    ++ans;
    ans %= MOD;
    
    // 5-2. 空グラフ除外.
    ans += (MOD - mPow2[N]);
    ans %= MOD;
    
    // 6. 黒く塗られた頂点数(期待値, 減算).
    ans += MOD - N * (LL)(5e8 + 4) % MOD;
    ans %= MOD;
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

const LL MOD = 1e9 + 7;

LL mPow2[202020], c[202020];

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. 事前計算.

mPow2[0] = 1;

repx(i, 1, 202020) mPow2[i] = (mPow2[i - 1] * (LL)(5e8 + 4)) % MOD;

rep(i, 202020) c[i] = (MOD + 1 - mPow2[i]) % MOD;

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

// 3. dfs(部分木サイズ).

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

auto dfs = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s){

// 部分木サイズ(往路).

++s[cur];

// 終了条件.

if(m[cur]) return;

m[cur] = 1;

// 隣接頂点.

for(auto &nex : G[cur]) if(nex != bef) self(self, G, nex, cur, m, s);

// 部分木サイズ(復路).

if(bef != -1) s[bef] += s[cur];

};

int subTree[N], memo[N];

rep(i, N) subTree[i] = memo[i] = 0;

dfs(dfs, G, 0, -1, memo, subTree);

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

// 4. S の辺数(期待値).

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

LL ans = 0;

function<void(vvi&, int, int, int*)> f = [&](vvi &G, int cur, int bef, int* m){

// 終了条件.

if(m[cur]) return;

m[cur] = 1;

// 隣接頂点.

for(auto &nex : G[cur]){

// 親頂点か否か.

if(nex == bef) continue;

// S に含まれる辺数の期待値を加算.

ans += c[subTree[nex]] * c[N - subTree[nex]] % MOD;

ans %= MOD;

// 次へ.

f(G, nex, cur, m);

}

};

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

f(G, 0, -1, memo);

// 5. S の頂点数(期待値).

// 5-1. 頂点数は, 辺数よりも, 1 多い.

++ans;

ans %= MOD;

// 5-2. 空グラフ除外.

ans += (MOD - mPow2[N]);

ans %= MOD;

// 6. 黒く塗られた頂点数(期待値, 減算).

ans += MOD - N * (LL)(5e8 + 4) % MOD;

ans %= MOD;

// 7. 出力.

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

return 0;

}

[入力例]
3
1 2
2 3

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

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

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

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

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

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

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

[入力例]
2
1 2

[出力例]
0

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

[出力例]
781250007

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

[出力例]
697387702

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

[出力例]
783004770

100

101

102

103

104

105

106

[入力例]

1 2

2 3

[出力例]

125000001

※AtCoderのテストケースより

[入力例]

1 2

2 3

3 4

[出力例]

375000003

※AtCoderのテストケースより

[入力例]

1 2

1 3

1 4

[出力例]

250000002

※AtCoderのテストケースより

[入力例]

4 7

3 1

2 6

5 2

7 1

2 7

[出力例]

570312505

※AtCoderのテストケースより

[入力例]

1 2

[出力例]

[入力例]

2 1

3 1

1 5

2 6

2 7

4 3

5 8

5 9

5 10

[出力例]

781250007

[入力例]

1 2

1 3

1 4

2 5

2 6

2 7

3 8

3 9

3 10

4 11

4 12

4 13

[出力例]

697387702

[入力例]

1 2

1 3

4 2

5 2

6 2

7 3

8 3

9 3

4 10

4 11

5 12

5 13

12 14

12 15

7 16

7 17

9 18

9 19

18 20

[出力例]

783004770

■参照サイト
AtCoder Beginner Contest 149

2022年4月1日

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

C++の練習を兼ねて, AtCoder Beginner Contest 152 の問題D (Handstand 2) ～問題E (Flatten) を解いてみた.

■感想.
1. 問題D, Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 両問ともに, 解説のロジックで, 計算できることが, 非常に印象深く残ったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc152/editorial.pdf
#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 c[10][10];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. c[i][j] を 計算(解説通り).
    rep(n, N){
        string sn = to_string(n + 1);
        int i = sn.front() - '0';
        int j = sn.back() - '0';
        ++c[i][j];
    }
    
    // 3. 集計.
    // -> 解説の数式を適用.
    LL ans = 0;
    rep(i, 10) rep(j, 10) ans += c[i][j] * c[j][i];
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

#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 c[10][10];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. c[i][j] を計算(解説通り).

rep(n, N){

string sn = to_string(n + 1);

int i = sn.front() - '0';

int j = sn.back() - '0';

++c[i][j];

}

// 3. 集計.

// -> 解説の数式を適用.

LL ans = 0;

rep(i, 10) rep(j, 10) ans += c[i][j] * c[j][i];

// 4. 出力.

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

return 0;

}

[入力例]
25

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

[入力例]
1

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

[入力例]
100

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

[入力例]
2020

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

[入力例]
200000

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

[入力例]
333

[出力例]
1152

[入力例]
8849

[出力例]
783233

[入力例]
21230

[出力例]
4507137

[入力例]
20200119

[出力例]
4080448480152
※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]
123456789

[出力例]
152415789971049
※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100

[出力例]

108

※AtCoderテストケースより

[入力例]

2020

[出力例]

40812

※AtCoderテストケースより

[入力例]

200000

[出力例]

400000008

※AtCoderテストケースより

[入力例]

333

[出力例]

1152

[入力例]

8849

[出力例]

783233

[入力例]

21230

[出力例]

4507137

[入力例]

20200119

[出力例]

4080448480152

※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

123456789

[出力例]

152415789971049

※整数 N が, 問題文の制約条件から範囲外であるケース.

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

// 解き直し.
// https://img.atcoder.jp/abc152/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using MP = map<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
const LL MOD = 1e9 + 7;
int b[1010101];
LL a[10101];

// Efficient program to print all prime factors of a given number
// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
// 与えられた正整数についての素因数分解を計算.
// @param X: 素因数分解を行う整数.
// @return ret: 素因数分解 の 結果 を 返却.
MP div(int X){
    // X を 2で割り切れなくなるまで割っていく.
    map<int, int> ret;
    while(!(X % 2)) ++ret[2], X >>= 1;
    
    // X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    repex(i, 3, sqrt(X) + 1, 2){
        while(!(X % i)){
            ++ret[i];
            X /= i;
        }
    }
    
    // X が 2 より 大きな素数であれば, 追加.
    if(X > 2) ++ret[X];
    
    // 出力.
    return ret;
}

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 素数を取得.
    repx(i, 2, 1010101){
        if(b[i]) continue;
        repex(j, i * 2, 1010101, i) b[j]++;
    }
    
    // 3. 素数を集計.
    MP lcm;
    repx(i, 2, 1010101) if(!b[i]) lcm[i] = 0;
    
    // 4. 素因数分解を行う.
    rep(i, N){
        MP m = div(a[i]);
        for(auto &p : m) lcm[p.a] = max(lcm[p.a], p.b);
    }
    
    // 5. L を 計算(解説通り).
    LL L = 1;
    for(auto &p : lcm){
        rep(i, p.b){
            L *= (LL)p.a;
            L %= MOD;
        }
    }
    
    // 6. 集計.
    // -> 解説の数式を適用.
    LL ans = 0;
    rep(i, N){
        ans += L * mPow((LL)a[i], MOD - 2);
        ans %= MOD;
    }
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using MP = map<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

const LL MOD = 1e9 + 7;

int b[1010101];

LL a[10101];

// Efficient program to print all prime factors of a given number

// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

// 与えられた正整数についての素因数分解を計算.

// @param X: 素因数分解を行う整数.

// @return ret: 素因数分解の結果を返却.

MP div(int X){

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

map<int, int> ret;

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

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

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

while(!(X % i)){

++ret[i];

X /= i;

}

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

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

// 出力.

return ret;

}

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

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 素数を取得.

repx(i, 2, 1010101){

if(b[i]) continue;

repex(j, i * 2, 1010101, i) b[j]++;

}

// 3. 素数を集計.

MP lcm;

repx(i, 2, 1010101) if(!b[i]) lcm[i] = 0;

// 4. 素因数分解を行う.

rep(i, N){

MP m = div(a[i]);

for(auto &p : m) lcm[p.a] = max(lcm[p.a], p.b);

}

// 5. L を計算(解説通り).

LL L = 1;

for(auto &p : lcm){

rep(i, p.b){

L *= (LL)p.a;

L %= MOD;

}

// 6. 集計.

// -> 解説の数式を適用.

LL ans = 0;

rep(i, N){

ans += L * mPow((LL)a[i], MOD - 2);

ans %= MOD;

}

// 7. 出力.

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

return 0;

}

[入力例]
3
2 3 4

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

[入力例]
5
12 12 12 12 12

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

[入力例]
3
1000000 999999 999998

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

[入力例]
3
1 2 3

[出力例]
11

[入力例]
5
2 6 12 24 108

[出力例]
173

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

[出力例]
611

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

[出力例]
7381

[入力例]
11
78 108 34 111 19 73 52 85 9 36 64

[出力例]
606380251

[入力例]

2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

12 12 12 12 12

[出力例]

※AtCoderテストケースより

[入力例]

1000000 999999 999998

[出力例]

996989508

※AtCoderテストケースより

[入力例]

1 2 3

[出力例]

[入力例]

2 6 12 24 108

[出力例]

173

[入力例]

3 1 4 1 5 9 2

[出力例]

611

[入力例]

1 2 3 4 5 6 7 8 9 10

[出力例]

7381

[入力例]

78 108 34 111 19 73 52 85 9 36 64

[出力例]

606380251

■参照サイト
AtCoder Beginner Contest 152

2022年4月1日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの(特に, 二分探索後に, 幸福度を計算する箇所), 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc149/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = 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 all(x) x.begin(), x.end()
int hCum[202020];
LL aCum[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL M;
    scanf("%d %lld", &N, &M);
    vi a(N);
    map<int, int> ma;
    ma[0] = 0;
    rep(i, N){
        scanf("%d", &a[i]);
        hCum[a[i]]++;
        ma[a[i]]++;
    }
    
    // 2. sort.
    sort(all(a));
    reverse(all(a));
    
    // 3. 累積和.
    repr(i, 202020 - 2, 0) hCum[i] += hCum[i + 1];
    rep(i, N) aCum[i + 1] = aCum[i] + (LL)a[i];
    
    // 4. 評価関数.
    auto f = [&](int m) -> bool {
        // 4-1. 定数 m 以上になる握手の方法の通り数.
        // -> 左手で握手する人を決めて, 右手で握手できる人数を加算.
        LL c = 0;
        rep(i, N){
            int r = max(0, m - a[i]);
            c += (LL)hCum[r];
        }
        
        // 4-2. 判定結果.
        return (c >= M);
    };
    
    // 5. 二分探索で確認してみる.
    int l = -1, h = 2e5 + 1, m;
    while(l + 1 < h){
        int m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
    }
    
    // 6. 集計.
    // 6-1. 最小でない幸福度.
    LL ans = 0, mCur = M;
    rep(i, N){
        // 残りの握手回数をチェック.
        int r = max(0, h - a[i]);
        if(mCur < (LL)hCum[r]) break;
        
        // 左手.
        ans += (LL)a[i] * (LL)hCum[r];
        
        // 右手.
        ans += aCum[hCum[r]];
        
        // 残りの握手回数を減算.
        mCur -= (LL)hCum[r];
    }
    
    // 6-2. 最小の幸福度.
    rep(i, N){
        // 残りの握手回数をチェック.
        int r = l - a[i];
        if(r < 0) continue;
        
        // 終了条件.
        if(mCur < (LL)ma[r]){
            // 左手.
            ans += (LL)a[i] * mCur;
            
            // 右手.
            ans += (LL)r * mCur;
            
            // 終了.
            break;
        }
        
        // 左手.
        ans += (LL)a[i] * (LL)ma[r];
        
        // 右手.
        ans += (LL)r * (LL)ma[r];
        
        // 残りの握手回数を減算.
        mCur -= (LL)ma[r];
    }
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = 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 all(x) x.begin(), x.end()

int hCum[202020];

LL aCum[202020];

int main(){

// 1. 入力情報.

int N;

LL M;

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

vi a(N);

map<int, int> ma;

ma[0] = 0;

rep(i, N){

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

hCum[a[i]]++;

ma[a[i]]++;

}

// 2. sort.

sort(all(a));

reverse(all(a));

// 3. 累積和.

repr(i, 202020 - 2, 0) hCum[i] += hCum[i + 1];

rep(i, N) aCum[i + 1] = aCum[i] + (LL)a[i];

// 4. 評価関数.

auto f = [&](int m) -> bool {

// 4-1. 定数 m 以上になる握手の方法の通り数.

// -> 左手で握手する人を決めて, 右手で握手できる人数を加算.

LL c = 0;

rep(i, N){

int r = max(0, m - a[i]);

c += (LL)hCum[r];

}

// 4-2. 判定結果.

return (c >= M);

};

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

int l = -1, h = 2e5 + 1, m;

while(l + 1 < h){

int m = (h + l) >> 1;

if(f(m)) l = m;

else h = m;

}

// 6. 集計.

// 6-1. 最小でない幸福度.

LL ans = 0, mCur = M;

rep(i, N){

// 残りの握手回数をチェック.

int r = max(0, h - a[i]);

if(mCur < (LL)hCum[r]) break;

// 左手.

ans += (LL)a[i] * (LL)hCum[r];

// 右手.

ans += aCum[hCum[r]];

// 残りの握手回数を減算.

mCur -= (LL)hCum[r];

}

// 6-2. 最小の幸福度.

rep(i, N){

// 残りの握手回数をチェック.

int r = l - a[i];

if(r < 0) continue;

// 終了条件.

if(mCur < (LL)ma[r]){

// 左手.

ans += (LL)a[i] * mCur;

// 右手.

ans += (LL)r * mCur;

// 終了.

break;

}

// 左手.

ans += (LL)a[i] * (LL)ma[r];

// 右手.

ans += (LL)r * (LL)ma[r];

// 残りの握手回数を減算.

mCur -= (LL)ma[r];

}

// 7. 出力.

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

return 0;

}

[入力例]
5 3
10 14 19 34 33

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

[入力例]
9 14
1 3 5 110 24 21 34 5 3

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

[入力例]
9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

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

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

[出力例]
38

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

[出力例]
270

[入力例]
50 2022
33 60 77 9 77 34 98 109 88 77 9 104 103 46 67 6 25 119 55 77 120 65 71 67 77 8 19 56 90 73 57 77 116 76 33 111 63 92 18 50 12 28 77 72 39 69 77 116 112 96

[出力例]
300009

[入力例]
5000 20220401
13 18 8 6 25 9 22 5 11 7 8 10 3 10 10 22 6 8 7 23 19 15 21 27 23 27 12 9 6 6 13 16 16 17 20 12 11 16 6 17 6 6 1 25 7 13 1 17 21 11 16 12 22 20 3 11 7 22 23 18 16 21 1 2 7 9 17 15 19 21 17 2 22 12 22 8 20 17 10 8 17 25 18 11 18 21 2 7 10 25 16 17 21 23 9 7 17 17 21 10 23 19 18 11 18 20 6 15 10 5 12 2 17 19 10 12 27 3 19 15 8 8 15 23 13 17 12 23 3 3 15 2 25 7 27 12 25 10 18 22 2 17 12 7 11 13 19 27 17 5 9 3 17 7 27 12 9 25 12 10 9 22 7 23 17 10 13 6 21 19 13 9 2 9 15 23 7 16 22 20 13 17 18 25 17 17 3 25 1 22 5 7 5 8 18 11 5 3 8 17 1 6 8 9 18 3 21 23 22 9 12 1 1 19 27 21 13 8 20 2 25 1 15 25 20 25 22 27 8 17 7 27 27 7 17 22 17 21 10 17 17 18 21 12 21 22 9 17 6 27 8 25 12 10 9 12 12 15 11 6 27 13 21 10 2 17 7 20 9 8 20 7 11 19 3 25 11 11 16 13 3 19 11 19 6 8 25 11 6 13 17 8 1 22 10 17 12 7 1 5 3 21 20 13 7 7 5 20 1 27 16 23 8 23 6 10 15 2 20 6 25 17 23 21 22 2 7 11 9 13 10 3 9 23 8 22 18 8 2 13 10 20 10 10 11 18 9 8 8 27 17 17 15 7 22 10 23 5 3 17 15 22 6 23 15 17 3 6 13 2 25 20 13 22 23 7 9 5 9 13 13 21 23 10 27 17 25 23 11 23 27 25 23 19 27 25 20 7 9 15 22 3 13 7 25 18 17 15 22 5 8 7 25 7 10 17 18 7 16 2 15 13 17 22 12 19 23 21 27 17 7 17 13 16 27 23 1 11 22 19 7 23 19 25 18 7 9 13 8 13 25 20 22 11 3 18 18 23 15 9 21 3 27 1 5 21 25 17 19 8 1 11 3 15 22 18 27 10 27 13 9 8 13 13 18 9 16 20 23 16 18 3 9 15 7 12 19 22 13 10 6 3 2 13 22 3 22 15 15 27 16 10 2 17 1 7 2 6 5 1 7 7 10 17 3 10 6 8 6 13 7 20 2 7 11 25 7 16 11 16 20 23 19 18 27 25 5 13 7 11 17 1 11 5 1 12 6 3 7 17 17 16 8 10 19 15 20 12 17 8 2 10 7 9 8 7 3 13 8 20 10 1 17 17 3 3 23 12 8 17 8 8 20 10 10 20 23 11 6 13 18 5 25 22 7 5 11 6 19 9 17 13 2 13 12 7 5 23 27 3 25 6 7 15 17 7 16 23 19 8 11 12 27 2 15 7 12 18 8 12 16 8 11 7 1 15 10 9 8 10 1 13 21 1 10 5 22 3 17 20 10 17 25 25 19 18 12 2 8 17 12 6 15 11 22 7 9 1 8 23 21 7 10 7 10 11 10 1 25 2 5 7 19 13 16 17 9 17 16 10 19 25 22 12 7 17 16 17 12 2 22 8 6 20 9 21 11 16 1 7 17 22 6 8 23 19 5 2 17 6 21 9 25 19 1 1 25 11 25 10 18 23 9 7 23 11 7 22 8 27 10 16 12 6 13 20 11 3 8 7 10 2 9 20 11 23 2 13 25 17 23 17 7 11 11 3 23 1 20 16 16 16 13 7 7 13 16 2 6 10 17 11 20 16 19 12 8 17 3 6 13 27 10 17 20 17 10 10 12 23 10 22 8 7 11 15 6 7 12 15 22 1 8 18 13 21 12 25 6 20 20 27 2 16 27 5 27 7 10 18 22 13 3 23 27 22 6 17 13 13 21 22 17 22 7 20 17 3 8 1 21 16 12 5 18 17 5 18 22 19 19 25 13 13 7 9 15 25 25 10 7 17 16 9 22 16 25 8 8 11 21 5 2 1 27 22 13 8 2 13 9 19 5 11 2 17 3 17 19 10 11 1 16 8 15 17 11 7 22 23 8 7 8 23 20 19 1 27 12 13 20 7 6 11 18 1 16 8 15 17 3 17 16 5 16 25 9 16 11 21 17 10 17 15 7 1 13 12 27 7 23 10 5 16 6 18 2 22 1 19 15 3 17 17 13 21 18 16 6 2 13 8 10 25 17 9 6 12 2 7 19 16 6 12 11 3 15 9 9 11 3 7 25 16 13 7 3 20 20 1 25 21 7 27 22 12 9 6 16 15 22 3 7 1 18 8 12 10 10 8 3 16 20 16 9 27 2 18 22 16 25 8 21 27 5 18 21 5 17 25 16 22 17 15 17 12 27 20 11 10 11 9 19 3 25 16 3 19 9 12 22 6 15 20 9 20 13 10 7 17 15 19 2 7 8 25 16 3 12 18 20 1 17 11 9 27 22 2 11 9 27 7 23 23 16 22 25 3 11 9 10 11 7 27 12 16 20 12 10 8 9 15 16 11 17 17 13 25 3 21 23 12 16 13 5 21 1 7 23 21 7 21 22 17 20 19 16 20 2 12 17 5 8 17 9 16 19 10 17 11 8 15 23 13 25 13 2 8 10 3 9 2 7 22 18 22 18 1 8 9 27 6 1 5 1 8 7 18 8 8 9 21 27 9 9 21 17 7 23 8 3 13 25 9 23 27 6 6 6 15 7 3 13 17 19 11 20 15 7 10 10 3 15 25 23 15 17 8 7 22 25 17 7 9 16 19 27 19 15 7 6 8 7 23 15 18 9 25 27 21 6 18 19 23 9 18 25 11 25 18 17 15 10 15 17 21 27 22 20 5 2 16 12 22 17 2 17 10 12 16 5 3 2 20 9 22 6 27 2 12 21 16 6 12 25 13 7 7 5 10 12 17 7 17 23 13 17 25 19 6 17 19 11 17 23 3 12 12 1 18 27 8 7 13 27 1 12 5 16 13 19 11 17 20 21 7 23 23 3 10 8 1 22 12 22 7 18 6 7 10 5 12 17 18 17 11 20 15 22 21 22 23 20 12 2 15 7 23 11 11 22 17 12 1 6 12 27 8 18 7 12 16 21 20 1 25 7 22 8 27 20 25 20 17 15 12 17 16 8 18 11 15 17 11 12 18 8 15 17 9 7 10 20 17 8 23 5 12 3 12 17 23 6 8 15 16 12 12 12 25 15 21 10 10 22 17 2 17 27 19 7 22 11 10 19 27 7 5 18 3 21 1 8 3 25 15 5 7 6 19 21 12 23 11 17 8 15 22 21 8 11 19 20 7 11 1 11 16 9 6 21 18 12 9 2 1 18 23 7 12 11 17 3 17 19 8 8 6 23 17 6 15 27 18 20 25 23 10 13 23 17 21 6 23 8 23 6 7 3 25 21 11 1 7 7 23 25 8 9 16 5 16 3 5 2 27 10 25 19 5 13 25 1 6 17 13 1 17 10 1 1 18 20 27 1 10 23 3 25 10 2 9 17 18 17 25 9 9 9 9 6 17 16 27 1 22 6 9 2 27 10 16 2 5 10 7 17 21 10 8 16 18 22 23 22 13 18 27 27 17 23 3 25 27 3 3 23 17 6 1 18 7 23 7 9 27 8 13 9 25 15 3 2 9 19 11 17 8 19 18 17 12 8 25 12 6 11 27 7 25 1 3 17 5 6 12 16 9 2 7 7 2 6 17 1 19 25 7 2 21 6 19 6 1 7 1 2 7 2 10 23 19 7 21 17 10 1 3 23 12 25 15 6 19 21 6 1 11 7 5 22 9 25 13 25 7 8 25 1 11 27 23 8 25 13 17 17 17 16 18 6 13 25 18 23 5 7 20 17 7 11 11 19 7 25 18 19 25 12 16 11 8 9 8 7 17 23 3 20 19 3 13 2 9 10 23 23 12 5 5 2 5 15 21 21 23 17 7 11 16 17 7 20 23 17 11 10 19 8 27 25 15 5 25 15 15 12 18 10 7 2 20 11 17 6 15 5 16 1 21 8 9 20 25 17 12 9 21 7 13 8 17 27 27 7 17 27 21 10 7 20 13 7 22 17 7 15 1 12 17 25 19 17 7 20 23 1 27 1 12 13 25 11 18 22 7 5 25 16 3 19 5 15 10 19 7 2 3 7 8 10 15 21 23 23 8 8 7 17 27 8 17 3 22 12 19 9 20 1 7 6 27 18 6 20 6 13 7 16 21 9 1 20 2 9 8 7 11 27 27 7 10 11 27 25 16 3 1 22 1 2 12 2 17 27 19 16 3 25 22 17 2 27 18 13 7 15 27 2 13 1 3 15 19 17 7 10 18 25 6 11 8 11 11 15 13 16 7 25 25 7 11 22 6 3 11 1 23 7 3 11 17 20 10 3 22 27 7 2 12 6 7 17 19 16 22 17 3 5 19 10 9 19 13 20 11 19 9 21 15 10 20 9 27 17 11 22 27 10 11 5 6 12 8 27 16 7 19 17 22 2 5 2 9 10 18 6 9 3 18 12 12 12 1 17 17 10 9 5 9 5 1 16 2 17 3 19 25 16 27 23 15 15 9 7 11 20 5 6 6 20 25 19 19 20 12 20 8 9 7 27 11 13 8 9 27 6 7 21 1 17 17 18 9 2 17 21 11 20 2 10 7 8 17 21 18 13 13 2 21 17 3 1 17 13 7 16 19 21 22 10 17 7 13 13 27 6 9 5 12 17 3 1 16 6 18 13 23 6 16 21 7 9 17 20 9 13 23 7 1 10 8 27 17 16 13 11 21 20 25 17 9 11 21 3 22 11 7 6 13 12 7 23 7 21 20 25 11 22 20 1 23 2 23 25 17 20 20 2 16 27 15 27 27 21 11 13 8 10 20 13 17 5 22 6 17 17 18 27 8 13 22 3 3 13 23 1 17 17 16 12 19 3 27 3 7 19 7 12 3 9 9 7 23 23 1 23 10 16 20 18 13 25 13 1 17 18 9 10 6 2 23 7 13 16 7 22 11 3 10 5 7 22 18 6 16 1 2 17 2 23 12 8 5 10 11 7 15 18 5 17 15 23 12 17 17 22 10 16 17 15 17 3 23 17 27 17 25 15 12 18 11 5 5 11 7 6 25 19 5 9 19 20 19 19 21 15 21 6 19 27 18 13 22 20 18 10 12 9 7 20 17 5 17 17 20 5 22 13 16 3 17 13 20 11 21 19 21 19 6 1 21 10 18 9 6 18 27 12 12 17 1 7 16 23 12 22 17 21 23 25 9 8 2 8 19 20 5 17 11 20 11 12 25 7 21 20 19 15 27 7 10 9 13 1 5 21 17 19 18 27 16 7 10 7 22 7 25 22 25 1 17 13 2 3 13 23 16 17 27 3 25 13 18 7 21 21 15 3 9 18 3 12 27 5 10 13 25 27 10 25 1 10 23 1 17 22 10 7 23 12 3 1 12 17 10 17 23 17 17 27 3 7 25 27 1 18 8 12 2 7 5 27 21 15 8 20 15 16 16 10 7 16 16 15 27 11 20 27 3 5 18 22 1 12 9 13 16 6 21 19 7 17 17 1 21 16 27 1 23 21 12 5 15 13 1 23 15 13 7 21 12 19 10 17 7 7 3 1 11 7 21 1 1 7 11 16 22 1 8 7 3 7 21 7 19 12 11 23 23 17 3 20 7 2 17 1 2 16 8 10 17 3 10 12 20 10 23 22 23 19 2 17 7 12 3 2 5 12 21 19 20 27 20 9 3 2 7 13 13 3 11 1 27 6 12 19 8 20 22 1 2 8 6 23 9 11 2 13 13 9 20 3 15 19 5 11 7 17 23 23 20 11 27 13 20 11 21 16 16 11 5 3 23 13 18 12 17 11 13 11 2 2 27 21 11 25 7 25 7 18 1 1 20 9 21 23 3 17 6 17 1 6 15 7 27 2 10 19 20 5 19 8 20 27 11 12 7 5 25 21 16 10 16 1 15 12 7 25 9 27 15 7 21 15 11 13 19 10 13 17 11 25 17 5 18 23 10 25 25 20 7 3 5 22 21 15 12 7 7 21 23 27 5 15 17 10 6 6 21 10 19 20 15 3 6 8 10 12 19 19 15 3 21 22 15 8 5 8 1 9 20 5 1 7 9 20 19 23 18 23 17 25 22 17 27 27 17 8 22 8 22 12 17 21 11 10 8 2 21 13 12 19 8 2 15 1 27 7 17 1 10 12 7 17 5 23 12 9 18 13 7 3 9 7 15 9 27 6 17 18 15 11 19 18 15 8 5 25 20 17 1 9 1 12 25 16 16 17 21 15 23 1 5 15 12 22 19 11 3 5 7 8 3 15 22 18 16 9 12 11 17 5 12 9 6 18 7 9 2 6 1 17 5 1 25 27 10 20 12 19 23 22 13 21 15 11 3 10 16 17 19 1 17 3 3 13 2 8 3 16 1 17 17 25 17 27 25 1 17 22 19 21 7 17 12 6 21 3 7 5 21 3 1 6 12 20 6 6 1 7 20 20 12 19 6 17 19 23 6 17 5 16 9 1 12 7 18 15 7 1 10 20 15 7 6 5 15 5 13 3 7 10 13 23 17 7 7 7 19 20 6 7 1 8 5 9 20 21 17 3 27 17 6 3 5 6 21 17 27 8 12 10 10 17 11 12 20 7 17 19 12 16 8 6 13 16 12 25 1 1 17 13 16 7 12 1 7 16 15 6 8 23 25 22 13 25 7 19 18 22 23 16 5 6 20 10 1 25 8 19 6 23 5 20 7 17 25 6 22 18 12 18 25 15 3 27 9 8 17 3 27 7 8 10 6 15 18 7 3 10 19 3 13 20 17 10 15 19 6 3 11 25 15 2 15 18 18 22 23 22 7 7 13 9 11 11 12 22 1 5 10 6 25 16 17 17 1 2 22 23 10 3 21 23 18 1 7 3 27 7 13 21 17 25 10 16 25 16 27 6 25 6 17 22 7 7 8 18 16 22 3 8 16 19 27 2 22 27 12 21 13 23 23 23 13 21 11 18 3 25 22 19 23 25 9 11 10 11 5 19 8 15 13 16 3 2 15 5 15 19 20 17 9 6 11 17 16 27 7 15 23 16 20 25 8 7 23 3 22 15 21 3 1 23 15 10 27 27 15 27 3 25 5 10 13 22 25 15 7 22 15 21 8 1 17 7 11 12 27 22 20 10 7 2 7 2 12 25 12 8 20 7 16 5 23 5 6 17 25 15 20 16 15 7 25 12 2 16 21 7 16 21 25 17 18 8 23 17 9 8 10 27 20 11 9 7 12 25 15 1 12 21 25 5 5 17 19 19 7 19 11 12 19 21 23 23 21 21 8 6 20 20 3 22 3 18 13 23 19 13 17 17 13 3 2 13 18 9 22 22 6 19 18 6 17 22 17 8 18 16 18 19 10 17 23 19 27 20 9 5 21 12 18 17 6 1 13 7 17 2 3 25 10 27 20 25 2 1 1 16 5 21 25 5 23 2 23 20 10 22 21 7 13 10 16 9 1 23 13 11 7 21 13 20 25 13 13 6 17 7 17 27 7 8 17 18 15 17 10 13 23 27 17 25 17 5 21 7 7 7 17 23 9 1 23 18 18 20 3 21 8 17 2 6 23 27 7 1 18 18 23 8 16 23 15 10 17 1 6 1 6 18 23 2 17 12 9 2 18 10 11 16 17 19 25 22 27 13 15 12 13 2 6 22 27 21 16 20 17 27 11 17 8 15 3 8 5 7 9 21 11 17 23 21 23 1 13 20 11 17 2 5 6 16 22 13 2 17 22 18 23 7 20 1 3 1 7 25 18 6 6 11 21 5 17 3 17 5 27 18 2 15 7 25 7 16 7 25 13 15 10 5 17 11 2 9 6 11 2 8 27 15 3 3 17 12 8 19 5 6 27 13 8 12 2 6 25 23 17 22 18 6 16 8 6 23 12 15 18 21 1 5 18 18 1 3 6 15 27 10 27 12 25 13 11 6 11 19 17 22 23 22 3 17 8 10 9 7 17 17 9 6 20 18 15 7 2 7 18 19 8 7 8 16 2 7 15 25 13 13 22 23 10 20 13 11 16 11 20 7 21 1 12 17 25 6 20 8 10 10 21 15 9 7 2 7 16 13 17 22 20 20 11 7 19 21 9 20 6 15 21 6 6 7 17 12 7 23 7 2 27 16 7 12 21 17 23 20 9 8 3 20 12 25 27 10 23 23 21 3 5 22 9 8 16 10 7 1 25 21 13 19 1 21 6 23 7 10 11 16 7 5 17 1 27 12 17 16 21 8 27 9 23 1 1 16 10 10 20 9 3 20 17 12 23 11 16 5 3 8 8 3 7 1 27 12 1 16 1 5 7 7 17 11 8 8 17 11 7 15 7 1 21 15 1 12 13 16 10 15 17 27 23 19 20 7 7 17 20 18 12 27 6 21 15 1 20 17 17 3 9 3 27 20 12 7 23 16 7 5 23 7 6 23 18 3 22 22 11 18 20 27 2 18 11 25 12 3 13 17 11 3 5 5 12 3 8 22 2 23 9 23 16 17 12 17 2 18 7 15 25 19 13 7 22 23 16 2 21 13 1 25 9 19 9 6 7 27 5 1 27 10 25 17 8 17 5 21 23 13 18 19 10 3 15 27 9 5 23 3 15 20 1 17 3 7 9 19 27 18 15 7 15 1 7 7 11 5 23 16 20 23 5 7 1 8 13 10 21 22 5 5 17 21 15 5 7 16 13 18 17 17 6 17 18 21 22 23 15 19 13 22 9 12 7 23 1 23 27 21 25 21 20 19 17 3 16 19 3 6 15 7 9 19 5 11 2 5 7 3 7 25 5 11 7 18 7 22 10 20 1 1 22 5 15 22 16 10 21 3 3 6 6 9 16 15 19 10 20 25 21 7 22 27 9 9 5 17 23 12 5 18 11 6 15 19 17 19 10 2 15 1 27 5 5 9 3 11 16 12 17 17 23 11 18 9 13 23 12 16 6 17 23 6 2 6 17 6 7 3 20 21 7 11 3 8 19 13 2 8 2 27 6 16 2 17 25 15 6 12 17 8 11 19 2 11 7 9 9 18 2 6 17 8 5 25 17 22 22 15 16 16 17 13 27 11 6 18 7 10 12 3 12 22 23 27 12 22 13 3 7 16 27 11 7 17 2 12 11 18 7 9 19 9 7 22 15 8 17 5 16 17 17 23 22 13 1 11 7 21 19 18 17 5 23 6 7 5 1 17 6 19 23 1 7 7 1 17 7 27 11 3 11 7 1 3 2 27 22 16 3 20 17 2 20 9 10 7 22 16 7 3 20 17 2 16 8 17 11 16 8 10 7 22 10 7 2 7 23 17 12 7 11 7 8 2 8 10 19 18 7 21 8 15 9 8 7 23 20 17 1 22 10 10 1 11 9 19 12 22 6 13 21 11 19 27 3 20 23 25 12 7 16 20 1 11 6 18 7 11 5 13 16 9 10 25 20 17 11 3 22 7 25 17 6 25 11 12 9 2 15 17 7 15 13 17 22 17 23 17 21 17 5 16 17 16 5 17 15 8 12 10 22 17 17 13 17 7 6 3 16 20 16 16 7 27 3 8 17 5 17 15 25 3 22 21 17 12 7 16 22 17 7 25 1 27 8 3 11 16 7 7 8 1 21 7 2 3 7 13 1 17 17 1 6 12 5 6 23 6 7 10 20 9 18 9 25 15 1 15 22 20 9 7 22 20 9 1 25 9 9 5 27 5 13 21 17 19 25 17 3 21 13 17 9 9 7 27 17 3 22 13 16 19 6 11 12 15 6 3 16 8 1 12 12 1 23 22 7 27 27 8 20 11 25 7 21 1 19 23 27 18 17 3 17 3 17 7 2 13 21 13 1 3 11 20 6 2 16 22 3 9 16 20 25 15 1 23 5 18 6 19 1 11 17 6 19 23 15 9 17 13 25 7 21 11 7 8 10 27 1 15 12 20 9 13 5 19 7 10 18 10 15 2 17 1 18 13 21 12 8 1 20 19 22 23 8 22 11 15 18 11 23 11 13 7 27 10 12 7 6 5 3 25 18 13 5 7 27 13 17 23 10 17 18 27 3 8 18 3 23 3 16 25 22 6 3 21 3 13 22 6 11 8 15 25 3 13 15 17 2 7 2 19 10 3 12 9 11 7 16 2 20 12 19 8 19 12 6 25 23 7 12 7 25 10 23 9 21 25 27 12 16 16 8 10 11 9 17 22 17 25 9 12 23 5 23 20 21 19 15 5 1 17 11 7 25 23 15 6 9 3 8 13 22 17 9 9 10 17 12 8 10 17 13 6 19 22 3 27 13 2 6 2 17 10 11 8 17 13 23 8 6 13 2 6 22 21 22 19 17 3 9 18 25 22 5 16 6 5 16 3 23 13 15 13 19 9 6 17 23 21 21 10 18 17 1 8 6 21 23 11 13 2 9 9 5 17 17 13 20 19 7 3 8 1 9 13 21 1 16 17 18 19 9 13 19 7 17 8 23 20 10 9 5 23 13 21 3 18 3 2 13 13 7 11 27 7 10 6 11 2 1 3 22 20 17 5 22 11 21 23 7 20 15 9 1 1 10 9 13 19 13 25 17 8 12 2 2 9 2 1 7 22 6 9 22 9 18 5 18 7 6 25 15 17 25 23 18 6 1 3 3 19 25 10 23 6 16 9 27 12 22 18 16 21 11 6 16 2 10 5 16 17 19 20 17 15 10 19 21 3 17 22 22 21 21 6 22 10 23 5 18 2 22 8 17 23 23 13 3 7 11 11 12 22 21 5 10 13 10 1 7 3 17 10 22 6 9 9 19 25 25 22 2 16 25 22 7 21 8 9 27 5 11 13 2 5 19 20 19 10 8 22 6 15 7 16 12 13 2 18 21 21 10 25 19 3 21 18 22 15 8 13 17 7 7 7 27 5 2 2 16 7 3 17 2 21 27 5 17 21 21 1 2 12 17 15 25 16 3 13 23 1 1 6 23 1 17 17 20 16 13 25 27 15 1 10 21 20 7 7 17 7 27 7 17 3 11 1 18 18 18 15 7 1 19 2 10 25 27 7 8 11 22 13 2 9 23 13 11 16 17 25 17 27 5 18 27 8 2 7 16 3 23 2 11 8 6 12 6 27 3 10 9 9 1 12 9 10 21 8 19 2 12 7 6 18 3 16 17 9 19 7 17 16 27 20 16 19 19 1 19 1 10 21 25 17 8 23 9 5 13 11 8 11 7 2 25 18 17 7 23 1 7 3 16 7 3

[出力例]
610372398

[入力例]

5 3

10 14 19 34 33

[出力例]

202

※AtCoderテストケースより

[入力例]

9 14

1 3 5 110 24 21 34 5 3

[出力例]

1837

※AtCoderテストケースより

[入力例]

9 73

67597 52981 5828 66249 75177 64141 40773 79105 16076

[出力例]

8128170

※AtCoderテストケースより

[入力例]

6 8

1 1 3 2 2 1

[出力例]

[入力例]

18 12

8 8 7 2 11 9 8 10 7 8 12 4 11 10 1 1 5 8

[出力例]

270

[入力例]

50 2022

33 60 77 9 77 34 98 109 88 77 9 104 103 46 67 6 25 119 55 77 120 65 71 67 77 8 19 56 90 73 57 77 116 76 33 111 63 92 18 50 12 28 77 72 39 69 77 116 112 96

[出力例]

300009

[入力例]

5000 20220401

13 18 8 6 25 9 22 5 11 7 8 10 3 10 10 22 6 8 7 23 19 15 21 27 23 27 12 9 6 6 13 16 16 17 20 12 11 16 6 17 6 6 1 25 7 13 1 17 21 11 16 12 22 20 3 11 7 22 23 18 16 21 1 2 7 9 17 15 19 21 17 2 22 12 22 8 20 17 10 8 17 25 18 11 18 21 2 7 10 25 16 17 21 23 9 7 17 17 21 10 23 19 18 11 18 20 6 15 10 5 12 2 17 19 10 12 27 3 19 15 8 8 15 23 13 17 12 23 3 3 15 2 25 7 27 12 25 10 18 22 2 17 12 7 11 13 19 27 17 5 9 3 17 7 27 12 9 25 12 10 9 22 7 23 17 10 13 6 21 19 13 9 2 9 15 23 7 16 22 20 13 17 18 25 17 17 3 25 1 22 5 7 5 8 18 11 5 3 8 17 1 6 8 9 18 3 21 23 22 9 12 1 1 19 27 21 13 8 20 2 25 1 15 25 20 25 22 27 8 17 7 27 27 7 17 22 17 21 10 17 17 18 21 12 21 22 9 17 6 27 8 25 12 10 9 12 12 15 11 6 27 13 21 10 2 17 7 20 9 8 20 7 11 19 3 25 11 11 16 13 3 19 11 19 6 8 25 11 6 13 17 8 1 22 10 17 12 7 1 5 3 21 20 13 7 7 5 20 1 27 16 23 8 23 6 10 15 2 20 6 25 17 23 21 22 2 7 11 9 13 10 3 9 23 8 22 18 8 2 13 10 20 10 10 11 18 9 8 8 27 17 17 15 7 22 10 23 5 3 17 15 22 6 23 15 17 3 6 13 2 25 20 13 22 23 7 9 5 9 13 13 21 23 10 27 17 25 23 11 23 27 25 23 19 27 25 20 7 9 15 22 3 13 7 25 18 17 15 22 5 8 7 25 7 10 17 18 7 16 2 15 13 17 22 12 19 23 21 27 17 7 17 13 16 27 23 1 11 22 19 7 23 19 25 18 7 9 13 8 13 25 20 22 11 3 18 18 23 15 9 21 3 27 1 5 21 25 17 19 8 1 11 3 15 22 18 27 10 27 13 9 8 13 13 18 9 16 20 23 16 18 3 9 15 7 12 19 22 13 10 6 3 2 13 22 3 22 15 15 27 16 10 2 17 1 7 2 6 5 1 7 7 10 17 3 10 6 8 6 13 7 20 2 7 11 25 7 16 11 16 20 23 19 18 27 25 5 13 7 11 17 1 11 5 1 12 6 3 7 17 17 16 8 10 19 15 20 12 17 8 2 10 7 9 8 7 3 13 8 20 10 1 17 17 3 3 23 12 8 17 8 8 20 10 10 20 23 11 6 13 18 5 25 22 7 5 11 6 19 9 17 13 2 13 12 7 5 23 27 3 25 6 7 15 17 7 16 23 19 8 11 12 27 2 15 7 12 18 8 12 16 8 11 7 1 15 10 9 8 10 1 13 21 1 10 5 22 3 17 20 10 17 25 25 19 18 12 2 8 17 12 6 15 11 22 7 9 1 8 23 21 7 10 7 10 11 10 1 25 2 5 7 19 13 16 17 9 17 16 10 19 25 22 12 7 17 16 17 12 2 22 8 6 20 9 21 11 16 1 7 17 22 6 8 23 19 5 2 17 6 21 9 25 19 1 1 25 11 25 10 18 23 9 7 23 11 7 22 8 27 10 16 12 6 13 20 11 3 8 7 10 2 9 20 11 23 2 13 25 17 23 17 7 11 11 3 23 1 20 16 16 16 13 7 7 13 16 2 6 10 17 11 20 16 19 12 8 17 3 6 13 27 10 17 20 17 10 10 12 23 10 22 8 7 11 15 6 7 12 15 22 1 8 18 13 21 12 25 6 20 20 27 2 16 27 5 27 7 10 18 22 13 3 23 27 22 6 17 13 13 21 22 17 22 7 20 17 3 8 1 21 16 12 5 18 17 5 18 22 19 19 25 13 13 7 9 15 25 25 10 7 17 16 9 22 16 25 8 8 11 21 5 2 1 27 22 13 8 2 13 9 19 5 11 2 17 3 17 19 10 11 1 16 8 15 17 11 7 22 23 8 7 8 23 20 19 1 27 12 13 20 7 6 11 18 1 16 8 15 17 3 17 16 5 16 25 9 16 11 21 17 10 17 15 7 1 13 12 27 7 23 10 5 16 6 18 2 22 1 19 15 3 17 17 13 21 18 16 6 2 13 8 10 25 17 9 6 12 2 7 19 16 6 12 11 3 15 9 9 11 3 7 25 16 13 7 3 20 20 1 25 21 7 27 22 12 9 6 16 15 22 3 7 1 18 8 12 10 10 8 3 16 20 16 9 27 2 18 22 16 25 8 21 27 5 18 21 5 17 25 16 22 17 15 17 12 27 20 11 10 11 9 19 3 25 16 3 19 9 12 22 6 15 20 9 20 13 10 7 17 15 19 2 7 8 25 16 3 12 18 20 1 17 11 9 27 22 2 11 9 27 7 23 23 16 22 25 3 11 9 10 11 7 27 12 16 20 12 10 8 9 15 16 11 17 17 13 25 3 21 23 12 16 13 5 21 1 7 23 21 7 21 22 17 20 19 16 20 2 12 17 5 8 17 9 16 19 10 17 11 8 15 23 13 25 13 2 8 10 3 9 2 7 22 18 22 18 1 8 9 27 6 1 5 1 8 7 18 8 8 9 21 27 9 9 21 17 7 23 8 3 13 25 9 23 27 6 6 6 15 7 3 13 17 19 11 20 15 7 10 10 3 15 25 23 15 17 8 7 22 25 17 7 9 16 19 27 19 15 7 6 8 7 23 15 18 9 25 27 21 6 18 19 23 9 18 25 11 25 18 17 15 10 15 17 21 27 22 20 5 2 16 12 22 17 2 17 10 12 16 5 3 2 20 9 22 6 27 2 12 21 16 6 12 25 13 7 7 5 10 12 17 7 17 23 13 17 25 19 6 17 19 11 17 23 3 12 12 1 18 27 8 7 13 27 1 12 5 16 13 19 11 17 20 21 7 23 23 3 10 8 1 22 12 22 7 18 6 7 10 5 12 17 18 17 11 20 15 22 21 22 23 20 12 2 15 7 23 11 11 22 17 12 1 6 12 27 8 18 7 12 16 21 20 1 25 7 22 8 27 20 25 20 17 15 12 17 16 8 18 11 15 17 11 12 18 8 15 17 9 7 10 20 17 8 23 5 12 3 12 17 23 6 8 15 16 12 12 12 25 15 21 10 10 22 17 2 17 27 19 7 22 11 10 19 27 7 5 18 3 21 1 8 3 25 15 5 7 6 19 21 12 23 11 17 8 15 22 21 8 11 19 20 7 11 1 11 16 9 6 21 18 12 9 2 1 18 23 7 12 11 17 3 17 19 8 8 6 23 17 6 15 27 18 20 25 23 10 13 23 17 21 6 23 8 23 6 7 3 25 21 11 1 7 7 23 25 8 9 16 5 16 3 5 2 27 10 25 19 5 13 25 1 6 17 13 1 17 10 1 1 18 20 27 1 10 23 3 25 10 2 9 17 18 17 25 9 9 9 9 6 17 16 27 1 22 6 9 2 27 10 16 2 5 10 7 17 21 10 8 16 18 22 23 22 13 18 27 27 17 23 3 25 27 3 3 23 17 6 1 18 7 23 7 9 27 8 13 9 25 15 3 2 9 19 11 17 8 19 18 17 12 8 25 12 6 11 27 7 25 1 3 17 5 6 12 16 9 2 7 7 2 6 17 1 19 25 7 2 21 6 19 6 1 7 1 2 7 2 10 23 19 7 21 17 10 1 3 23 12 25 15 6 19 21 6 1 11 7 5 22 9 25 13 25 7 8 25 1 11 27 23 8 25 13 17 17 17 16 18 6 13 25 18 23 5 7 20 17 7 11 11 19 7 25 18 19 25 12 16 11 8 9 8 7 17 23 3 20 19 3 13 2 9 10 23 23 12 5 5 2 5 15 21 21 23 17 7 11 16 17 7 20 23 17 11 10 19 8 27 25 15 5 25 15 15 12 18 10 7 2 20 11 17 6 15 5 16 1 21 8 9 20 25 17 12 9 21 7 13 8 17 27 27 7 17 27 21 10 7 20 13 7 22 17 7 15 1 12 17 25 19 17 7 20 23 1 27 1 12 13 25 11 18 22 7 5 25 16 3 19 5 15 10 19 7 2 3 7 8 10 15 21 23 23 8 8 7 17 27 8 17 3 22 12 19 9 20 1 7 6 27 18 6 20 6 13 7 16 21 9 1 20 2 9 8 7 11 27 27 7 10 11 27 25 16 3 1 22 1 2 12 2 17 27 19 16 3 25 22 17 2 27 18 13 7 15 27 2 13 1 3 15 19 17 7 10 18 25 6 11 8 11 11 15 13 16 7 25 25 7 11 22 6 3 11 1 23 7 3 11 17 20 10 3 22 27 7 2 12 6 7 17 19 16 22 17 3 5 19 10 9 19 13 20 11 19 9 21 15 10 20 9 27 17 11 22 27 10 11 5 6 12 8 27 16 7 19 17 22 2 5 2 9 10 18 6 9 3 18 12 12 12 1 17 17 10 9 5 9 5 1 16 2 17 3 19 25 16 27 23 15 15 9 7 11 20 5 6 6 20 25 19 19 20 12 20 8 9 7 27 11 13 8 9 27 6 7 21 1 17 17 18 9 2 17 21 11 20 2 10 7 8 17 21 18 13 13 2 21 17 3 1 17 13 7 16 19 21 22 10 17 7 13 13 27 6 9 5 12 17 3 1 16 6 18 13 23 6 16 21 7 9 17 20 9 13 23 7 1 10 8 27 17 16 13 11 21 20 25 17 9 11 21 3 22 11 7 6 13 12 7 23 7 21 20 25 11 22 20 1 23 2 23 25 17 20 20 2 16 27 15 27 27 21 11 13 8 10 20 13 17 5 22 6 17 17 18 27 8 13 22 3 3 13 23 1 17 17 16 12 19 3 27 3 7 19 7 12 3 9 9 7 23 23 1 23 10 16 20 18 13 25 13 1 17 18 9 10 6 2 23 7 13 16 7 22 11 3 10 5 7 22 18 6 16 1 2 17 2 23 12 8 5 10 11 7 15 18 5 17 15 23 12 17 17 22 10 16 17 15 17 3 23 17 27 17 25 15 12 18 11 5 5 11 7 6 25 19 5 9 19 20 19 19 21 15 21 6 19 27 18 13 22 20 18 10 12 9 7 20 17 5 17 17 20 5 22 13 16 3 17 13 20 11 21 19 21 19 6 1 21 10 18 9 6 18 27 12 12 17 1 7 16 23 12 22 17 21 23 25 9 8 2 8 19 20 5 17 11 20 11 12 25 7 21 20 19 15 27 7 10 9 13 1 5 21 17 19 18 27 16 7 10 7 22 7 25 22 25 1 17 13 2 3 13 23 16 17 27 3 25 13 18 7 21 21 15 3 9 18 3 12 27 5 10 13 25 27 10 25 1 10 23 1 17 22 10 7 23 12 3 1 12 17 10 17 23 17 17 27 3 7 25 27 1 18 8 12 2 7 5 27 21 15 8 20 15 16 16 10 7 16 16 15 27 11 20 27 3 5 18 22 1 12 9 13 16 6 21 19 7 17 17 1 21 16 27 1 23 21 12 5 15 13 1 23 15 13 7 21 12 19 10 17 7 7 3 1 11 7 21 1 1 7 11 16 22 1 8 7 3 7 21 7 19 12 11 23 23 17 3 20 7 2 17 1 2 16 8 10 17 3 10 12 20 10 23 22 23 19 2 17 7 12 3 2 5 12 21 19 20 27 20 9 3 2 7 13 13 3 11 1 27 6 12 19 8 20 22 1 2 8 6 23 9 11 2 13 13 9 20 3 15 19 5 11 7 17 23 23 20 11 27 13 20 11 21 16 16 11 5 3 23 13 18 12 17 11 13 11 2 2 27 21 11 25 7 25 7 18 1 1 20 9 21 23 3 17 6 17 1 6 15 7 27 2 10 19 20 5 19 8 20 27 11 12 7 5 25 21 16 10 16 1 15 12 7 25 9 27 15 7 21 15 11 13 19 10 13 17 11 25 17 5 18 23 10 25 25 20 7 3 5 22 21 15 12 7 7 21 23 27 5 15 17 10 6 6 21 10 19 20 15 3 6 8 10 12 19 19 15 3 21 22 15 8 5 8 1 9 20 5 1 7 9 20 19 23 18 23 17 25 22 17 27 27 17 8 22 8 22 12 17 21 11 10 8 2 21 13 12 19 8 2 15 1 27 7 17 1 10 12 7 17 5 23 12 9 18 13 7 3 9 7 15 9 27 6 17 18 15 11 19 18 15 8 5 25 20 17 1 9 1 12 25 16 16 17 21 15 23 1 5 15 12 22 19 11 3 5 7 8 3 15 22 18 16 9 12 11 17 5 12 9 6 18 7 9 2 6 1 17 5 1 25 27 10 20 12 19 23 22 13 21 15 11 3 10 16 17 19 1 17 3 3 13 2 8 3 16 1 17 17 25 17 27 25 1 17 22 19 21 7 17 12 6 21 3 7 5 21 3 1 6 12 20 6 6 1 7 20 20 12 19 6 17 19 23 6 17 5 16 9 1 12 7 18 15 7 1 10 20 15 7 6 5 15 5 13 3 7 10 13 23 17 7 7 7 19 20 6 7 1 8 5 9 20 21 17 3 27 17 6 3 5 6 21 17 27 8 12 10 10 17 11 12 20 7 17 19 12 16 8 6 13 16 12 25 1 1 17 13 16 7 12 1 7 16 15 6 8 23 25 22 13 25 7 19 18 22 23 16 5 6 20 10 1 25 8 19 6 23 5 20 7 17 25 6 22 18 12 18 25 15 3 27 9 8 17 3 27 7 8 10 6 15 18 7 3 10 19 3 13 20 17 10 15 19 6 3 11 25 15 2 15 18 18 22 23 22 7 7 13 9 11 11 12 22 1 5 10 6 25 16 17 17 1 2 22 23 10 3 21 23 18 1 7 3 27 7 13 21 17 25 10 16 25 16 27 6 25 6 17 22 7 7 8 18 16 22 3 8 16 19 27 2 22 27 12 21 13 23 23 23 13 21 11 18 3 25 22 19 23 25 9 11 10 11 5 19 8 15 13 16 3 2 15 5 15 19 20 17 9 6 11 17 16 27 7 15 23 16 20 25 8 7 23 3 22 15 21 3 1 23 15 10 27 27 15 27 3 25 5 10 13 22 25 15 7 22 15 21 8 1 17 7 11 12 27 22 20 10 7 2 7 2 12 25 12 8 20 7 16 5 23 5 6 17 25 15 20 16 15 7 25 12 2 16 21 7 16 21 25 17 18 8 23 17 9 8 10 27 20 11 9 7 12 25 15 1 12 21 25 5 5 17 19 19 7 19 11 12 19 21 23 23 21 21 8 6 20 20 3 22 3 18 13 23 19 13 17 17 13 3 2 13 18 9 22 22 6 19 18 6 17 22 17 8 18 16 18 19 10 17 23 19 27 20 9 5 21 12 18 17 6 1 13 7 17 2 3 25 10 27 20 25 2 1 1 16 5 21 25 5 23 2 23 20 10 22 21 7 13 10 16 9 1 23 13 11 7 21 13 20 25 13 13 6 17 7 17 27 7 8 17 18 15 17 10 13 23 27 17 25 17 5 21 7 7 7 17 23 9 1 23 18 18 20 3 21 8 17 2 6 23 27 7 1 18 18 23 8 16 23 15 10 17 1 6 1 6 18 23 2 17 12 9 2 18 10 11 16 17 19 25 22 27 13 15 12 13 2 6 22 27 21 16 20 17 27 11 17 8 15 3 8 5 7 9 21 11 17 23 21 23 1 13 20 11 17 2 5 6 16 22 13 2 17 22 18 23 7 20 1 3 1 7 25 18 6 6 11 21 5 17 3 17 5 27 18 2 15 7 25 7 16 7 25 13 15 10 5 17 11 2 9 6 11 2 8 27 15 3 3 17 12 8 19 5 6 27 13 8 12 2 6 25 23 17 22 18 6 16 8 6 23 12 15 18 21 1 5 18 18 1 3 6 15 27 10 27 12 25 13 11 6 11 19 17 22 23 22 3 17 8 10 9 7 17 17 9 6 20 18 15 7 2 7 18 19 8 7 8 16 2 7 15 25 13 13 22 23 10 20 13 11 16 11 20 7 21 1 12 17 25 6 20 8 10 10 21 15 9 7 2 7 16 13 17 22 20 20 11 7 19 21 9 20 6 15 21 6 6 7 17 12 7 23 7 2 27 16 7 12 21 17 23 20 9 8 3 20 12 25 27 10 23 23 21 3 5 22 9 8 16 10 7 1 25 21 13 19 1 21 6 23 7 10 11 16 7 5 17 1 27 12 17 16 21 8 27 9 23 1 1 16 10 10 20 9 3 20 17 12 23 11 16 5 3 8 8 3 7 1 27 12 1 16 1 5 7 7 17 11 8 8 17 11 7 15 7 1 21 15 1 12 13 16 10 15 17 27 23 19 20 7 7 17 20 18 12 27 6 21 15 1 20 17 17 3 9 3 27 20 12 7 23 16 7 5 23 7 6 23 18 3 22 22 11 18 20 27 2 18 11 25 12 3 13 17 11 3 5 5 12 3 8 22 2 23 9 23 16 17 12 17 2 18 7 15 25 19 13 7 22 23 16 2 21 13 1 25 9 19 9 6 7 27 5 1 27 10 25 17 8 17 5 21 23 13 18 19 10 3 15 27 9 5 23 3 15 20 1 17 3 7 9 19 27 18 15 7 15 1 7 7 11 5 23 16 20 23 5 7 1 8 13 10 21 22 5 5 17 21 15 5 7 16 13 18 17 17 6 17 18 21 22 23 15 19 13 22 9 12 7 23 1 23 27 21 25 21 20 19 17 3 16 19 3 6 15 7 9 19 5 11 2 5 7 3 7 25 5 11 7 18 7 22 10 20 1 1 22 5 15 22 16 10 21 3 3 6 6 9 16 15 19 10 20 25 21 7 22 27 9 9 5 17 23 12 5 18 11 6 15 19 17 19 10 2 15 1 27 5 5 9 3 11 16 12 17 17 23 11 18 9 13 23 12 16 6 17 23 6 2 6 17 6 7 3 20 21 7 11 3 8 19 13 2 8 2 27 6 16 2 17 25 15 6 12 17 8 11 19 2 11 7 9 9 18 2 6 17 8 5 25 17 22 22 15 16 16 17 13 27 11 6 18 7 10 12 3 12 22 23 27 12 22 13 3 7 16 27 11 7 17 2 12 11 18 7 9 19 9 7 22 15 8 17 5 16 17 17 23 22 13 1 11 7 21 19 18 17 5 23 6 7 5 1 17 6 19 23 1 7 7 1 17 7 27 11 3 11 7 1 3 2 27 22 16 3 20 17 2 20 9 10 7 22 16 7 3 20 17 2 16 8 17 11 16 8 10 7 22 10 7 2 7 23 17 12 7 11 7 8 2 8 10 19 18 7 21 8 15 9 8 7 23 20 17 1 22 10 10 1 11 9 19 12 22 6 13 21 11 19 27 3 20 23 25 12 7 16 20 1 11 6 18 7 11 5 13 16 9 10 25 20 17 11 3 22 7 25 17 6 25 11 12 9 2 15 17 7 15 13 17 22 17 23 17 21 17 5 16 17 16 5 17 15 8 12 10 22 17 17 13 17 7 6 3 16 20 16 16 7 27 3 8 17 5 17 15 25 3 22 21 17 12 7 16 22 17 7 25 1 27 8 3 11 16 7 7 8 1 21 7 2 3 7 13 1 17 17 1 6 12 5 6 23 6 7 10 20 9 18 9 25 15 1 15 22 20 9 7 22 20 9 1 25 9 9 5 27 5 13 21 17 19 25 17 3 21 13 17 9 9 7 27 17 3 22 13 16 19 6 11 12 15 6 3 16 8 1 12 12 1 23 22 7 27 27 8 20 11 25 7 21 1 19 23 27 18 17 3 17 3 17 7 2 13 21 13 1 3 11 20 6 2 16 22 3 9 16 20 25 15 1 23 5 18 6 19 1 11 17 6 19 23 15 9 17 13 25 7 21 11 7 8 10 27 1 15 12 20 9 13 5 19 7 10 18 10 15 2 17 1 18 13 21 12 8 1 20 19 22 23 8 22 11 15 18 11 23 11 13 7 27 10 12 7 6 5 3 25 18 13 5 7 27 13 17 23 10 17 18 27 3 8 18 3 23 3 16 25 22 6 3 21 3 13 22 6 11 8 15 25 3 13 15 17 2 7 2 19 10 3 12 9 11 7 16 2 20 12 19 8 19 12 6 25 23 7 12 7 25 10 23 9 21 25 27 12 16 16 8 10 11 9 17 22 17 25 9 12 23 5 23 20 21 19 15 5 1 17 11 7 25 23 15 6 9 3 8 13 22 17 9 9 10 17 12 8 10 17 13 6 19 22 3 27 13 2 6 2 17 10 11 8 17 13 23 8 6 13 2 6 22 21 22 19 17 3 9 18 25 22 5 16 6 5 16 3 23 13 15 13 19 9 6 17 23 21 21 10 18 17 1 8 6 21 23 11 13 2 9 9 5 17 17 13 20 19 7 3 8 1 9 13 21 1 16 17 18 19 9 13 19 7 17 8 23 20 10 9 5 23 13 21 3 18 3 2 13 13 7 11 27 7 10 6 11 2 1 3 22 20 17 5 22 11 21 23 7 20 15 9 1 1 10 9 13 19 13 25 17 8 12 2 2 9 2 1 7 22 6 9 22 9 18 5 18 7 6 25 15 17 25 23 18 6 1 3 3 19 25 10 23 6 16 9 27 12 22 18 16 21 11 6 16 2 10 5 16 17 19 20 17 15 10 19 21 3 17 22 22 21 21 6 22 10 23 5 18 2 22 8 17 23 23 13 3 7 11 11 12 22 21 5 10 13 10 1 7 3 17 10 22 6 9 9 19 25 25 22 2 16 25 22 7 21 8 9 27 5 11 13 2 5 19 20 19 10 8 22 6 15 7 16 12 13 2 18 21 21 10 25 19 3 21 18 22 15 8 13 17 7 7 7 27 5 2 2 16 7 3 17 2 21 27 5 17 21 21 1 2 12 17 15 25 16 3 13 23 1 1 6 23 1 17 17 20 16 13 25 27 15 1 10 21 20 7 7 17 7 27 7 17 3 11 1 18 18 18 15 7 1 19 2 10 25 27 7 8 11 22 13 2 9 23 13 11 16 17 25 17 27 5 18 27 8 2 7 16 3 23 2 11 8 6 12 6 27 3 10 9 9 1 12 9 10 21 8 19 2 12 7 6 18 3 16 17 9 19 7 17 16 27 20 16 19 19 1 19 1 10 21 25 17 8 23 9 5 13 11 8 11 7 2 25 18 17 7 23 1 7 3 16 7 3

[出力例]

610372398

■参照サイト
AtCoder Beginner Contest 149

C++の練習を兼ねて, AtCoder Beginner Contest 150 の 問題F (Xor Shift) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 006 の 問題B (あみだくじ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 138 の 問題A (Larger Score) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 150 の 問題D (Semi Common Multiple) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 165 の 問題F (LIS on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 153 の 問題E (Crested Ibis vs Monster) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 135 の 問題D (Digits Parade) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 149 の 問題F (Surrounded Nodes) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 152 の 問題D (Handstand 2) ～ 問題E (Flatten) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 150 の問題F (Xor Shift) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 006 の問題B (あみだくじ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題A (Larger Score) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 150 の問題D (Semi Common Multiple) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 165 の問題F (LIS on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 153 の問題E (Crested Ibis vs Monster) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 135 の問題D (Digits Parade) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 149 の問題F (Surrounded Nodes) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 152 の問題D (Handstand 2) ～問題E (Flatten) を解いてみた.

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