3月, 2020 | 個人用メモ帳

2020年3月17日2020年3月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 013 の問題C (C – 節制) ～問題D (D – 阿弥陀) を解いてみた.

■感想.
1. 問題C は, 着眼点が見えなかったので, 解説どおりに実装したところ, AC版となった.
※ 質素な食事の最低回数を評価するときに, 0回以上とする点に注意が必要だった(01_010.txtなどでWAとなった).
2. 問題D は, ゴリゴリ実装する羽目になったものの, 解説見る前に, 何とかAC版となった.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/abc013
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){

    // 1. 入力情報.
    LL N, H, A, B, C, D, E;
    scanf("%lld %lld %lld %lld %lld %lld %lld", &N, &H, &A, &B, &C, &D, &E);
    
    // 2. 解説どおり.
    // 普通の食事 … X回.
    // 簡素な食事 … Y回.
    // 各(X, Y) について, H + B * X + D * Y - (N - X - Y) * E > 0 を チェック.
    // -> Y > ((N - X) * E - H - B * X) / (D + E) とすると, 
    // 質素な食事を, 最低何回取れば良いか分かるとのこと.
    LL ans = 2020202020202020;
    rep(i, N + 1){
        // 普通の食事.
        LL X = (LL)i;
        
        // 簡素な食事.
        LL Y = ((N - X) * E - H - B * X) / (D + E);
        Y = (Y < 0) ? 0 : Y; // 01_010.txt などの WA回避.
        if(H + B * X + D * Y - (N - X - Y) * E <= 0) Y++;
        
        // 必要な食費.
        ans = min(ans, A * X + C * Y);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;

}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL N, H, A, B, C, D, E;

scanf("%lld %lld %lld %lld %lld %lld %lld", &N, &H, &A, &B, &C, &D, &E);

// 2. 解説どおり.

// 普通の食事 … X回.

// 簡素な食事 … Y回.

// 各(X, Y) について, H + B * X + D * Y - (N - X - Y) * E > 0 をチェック.

// -> Y > ((N - X) * E - H - B * X) / (D + E) とすると,

// 質素な食事を, 最低何回取れば良いか分かるとのこと.

LL ans = 2020202020202020;

rep(i, N + 1){

// 普通の食事.

LL X = (LL)i;

// 簡素な食事.

LL Y = ((N - X) * E - H - B * X) / (D + E);

Y = (Y < 0) ? 0 : Y; // 01_010.txt などの WA回避.

if(H + B * X + D * Y - (N - X - Y) * E <= 0) Y++;

// 必要な食費.

ans = min(ans, A * X + C * Y);

}

// 3. 出力.

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

return 0;

}

[入力例]
4 5
100 4 60 1 4

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

[入力例]
10 1
5000 2 2000 1 300

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

[入力例]
9 23
170 8 120 5 12

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

[入力例]
653 314159
6728 123456 5141 41928 222222

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

[入力例]

4 5

100 4 60 1 4

[出力例]

160

※AtCoderテストケースより

[入力例]

10 1

5000 2 2000 1 300

[出力例]

20000

※AtCoderテストケースより

[入力例]

9 23

170 8 120 5 12

[出力例]

650

※AtCoderテストケースより

[入力例]

653 314159

6728 123456 5141 41928 222222

[出力例]

2818162

※AtCoderテストケースより

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

#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 101010;
int io[MAX], oi[MAX];
vector<vector<int>> group; // 全グループ情報.
int gRank[MAX]; // グループ内出現順位.
int at[MAX]; // i本目は, どのグループに属するか.

int main(){

    // 1. 入力情報.
    int N, M, D;
    scanf("%d %d %d", &N, &M, &D);
    
    // 2. あみだくじ作成(1段階分).
    rep(i, 101010) io[i + 1] = i + 1;
    rep(i, M){
        int x;
        scanf("%d", &x);
        swap(io[x], io[x + 1]);
    }
    // rep(i, N + 1) printf("%d ", io[i]);
    // puts("");
    
    // 3. i本目 -> XX本目 を 作成.
    repx(i, 1, N + 1) oi[io[i]] = i;
    
    // 4. 各縦線が所属するグループなどの事前計算.
    int gCount = 0;
    repx(i, 1, N + 1){
        int x = i, r = 0;
        vector<int> g;
        
        // 4-1. グループ番号を, インクリメント.
        if(gRank[x] == 0) gCount++;
        
        // 4-2. 同一グループの把握.
        while(gRank[x] == 0){
            // グループ番号を設定.
            at[x] = gCount;
            
            // グループ内の順位を設定.
            gRank[x] = ++r;
            
            // グループに要素を追加.
            g.pb(x);
            
            // 次の要素.
            x = oi[x];
        }
        
        // 4-3. 空で無ければ追加.
        if(g.size() > 0) group.pb(g);
    }
    
    // 5. 巨大あみだくじをシュミレート.
    repx(k, 1, N + 1){
        // 5-1. k番目の縦線が所属するグループ.
        int kG = at[k];
        
        // 5-2. D個繋げた場合のオフセット.
        int gSize = group[kG - 1].size();
        int kO = D % gSize;
        
        // 5-3. グループ内の順位は.
        int kR = gRank[k];
        
        // 5-4. 上記の結果から, D個繋げた場合の遷移先は.
        int ans = group[kG - 1][(kR + kO - 1) % gSize];
        
        // 5-5. 出力.
        printf("%d\n", ans);
    }
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

const int MAX = 101010;

int io[MAX], oi[MAX];

vector<vector<int>> group; // 全グループ情報.

int gRank[MAX]; // グループ内出現順位.

int at[MAX]; // i本目は, どのグループに属するか.

int main(){

// 1. 入力情報.

int N, M, D;

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

// 2. あみだくじ作成(1段階分).

rep(i, 101010) io[i + 1] = i + 1;

rep(i, M){

int x;

scanf("%d", &x);

swap(io[x], io[x + 1]);

}

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

// puts("");

// 3. i本目 -> XX本目を作成.

repx(i, 1, N + 1) oi[io[i]] = i;

// 4. 各縦線が所属するグループなどの事前計算.

int gCount = 0;

repx(i, 1, N + 1){

int x = i, r = 0;

vector<int> g;

// 4-1. グループ番号を, インクリメント.

if(gRank[x] == 0) gCount++;

// 4-2. 同一グループの把握.

while(gRank[x] == 0){

// グループ番号を設定.

at[x] = gCount;

// グループ内の順位を設定.

gRank[x] = ++r;

// グループに要素を追加.

g.pb(x);

// 次の要素.

x = oi[x];

}

// 4-3. 空で無ければ追加.

if(g.size() > 0) group.pb(g);

}

// 5. 巨大あみだくじをシュミレート.

repx(k, 1, N + 1){

// 5-1. k番目の縦線が所属するグループ.

int kG = at[k];

// 5-2. D個繋げた場合のオフセット.

int gSize = group[kG - 1].size();

int kO = D % gSize;

// 5-3. グループ内の順位は.

int kR = gRank[k];

// 5-4. 上記の結果から, D個繋げた場合の遷移先は.

int ans = group[kG - 1][(kR + kO - 1) % gSize];

// 5-5. 出力.

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

}

return 0;

}

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

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

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

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

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

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

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

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

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

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

[入力例]

5 7 1

1 4 3 4 2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

5 7 2

1 4 3 4 2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

10 20 300

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

[出力例]

※AtCoderテストケースより

[入力例]

7 11 321

1 3 4 2 3 5 1 6 4 2 5

[出力例]

[入力例]

33 100 314159265

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

[出力例]

■参照サイト
AtCoder Beginner Contest 013

2020年3月16日2020年3月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 024 の問題D (D – 動的計画法) を解いてみた.

■感想.
1. 着眼点が見えなかったので, 解説どおりに実装したところ, AC版となった.
2. 数式変形を駆使する解法に, 目から鱗だった.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/abc024
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t % MOD;
}

int main(){
    
    // 1. 入力情報.
    LL A, B, C;
    scanf("%lld %lld %lld", &A, &B, &C);
    
    // 2. 解説通り.
    // 2-1. c を 計算.
    // c = (B * C - A * B) / (C * A - B * C + A * B)
    LL ab = A * B % MOD, bc = B * C % MOD, ca = C * A % MOD;
    LL cMol = (bc + MOD - ab) % MOD;
    LL cDen = mPow((ca + MOD - bc + ab) % MOD, MOD - 2);
    LL c = cMol * cDen % MOD;
    
    // 2-2. r を 計算.
    // r = (B * C - C * A) / (A * B - B * C + C * A)
    LL rMol = (bc + MOD - ca) % MOD;
    LL rDen = mPow((ab + MOD - bc + ca) % MOD, MOD - 2);
    LL r = rMol * rDen % MOD;
    
    // 3. 出力.
    printf("%lld %lld\n", r, c);
    return 0;
    
}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 1e9 + 7;

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

int main(){

// 1. 入力情報.

LL A, B, C;

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

// 2. 解説通り.

// 2-1. c を計算.

// c = (B * C - A * B) / (C * A - B * C + A * B)

LL ab = A * B % MOD, bc = B * C % MOD, ca = C * A % MOD;

LL cMol = (bc + MOD - ab) % MOD;

LL cDen = mPow((ca + MOD - bc + ab) % MOD, MOD - 2);

LL c = cMol * cDen % MOD;

// 2-2. r を計算.

// r = (B * C - C * A) / (A * B - B * C + C * A)

LL rMol = (bc + MOD - ca) % MOD;

LL rDen = mPow((ab + MOD - bc + ca) % MOD, MOD - 2);

LL r = rMol * rDen % MOD;

// 3. 出力.

printf("%lld %lld\n", r, c);

return 0;

}

[入力例]
15
35
21

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

[入力例]
126
252
210

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

[入力例]
144949225
545897619
393065978

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

[入力例]
999888777
666555444
333222111

[出力例]
681836797 485100218

[入力例]

[出力例]

4 2

※AtCoderテストケースより

[入力例]

126

252

210

[出力例]

5 4

※AtCoderテストケースより

[入力例]

144949225

545897619

393065978

[出力例]

314159 365358

※AtCoderテストケースより

[入力例]

999888777

666555444

333222111

[出力例]

681836797 485100218

■参照サイト
AtCoder Beginner Contest 024

2020年3月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 021 の問題D (D – 多重ループ) を解いてみた.

■感想.
1. 重複組み合わせで出てくる計算結果に等しいことに気付けたので, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
const int LIMIT = 202020;
LL FAC[LIMIT];
LL INV[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t % MOD;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL n, k;
    scanf("%lld %lld", &n, &k);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    
    // 2. 重複組み合わせ nHk = (n - 1 + k)C(n - 1) を 計算.
    LL ans = combination(n - 1 + k, n - 1);
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

const int LIMIT = 202020;

LL FAC[LIMIT];

LL INV[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

LL n, k;

scanf("%lld %lld", &n, &k);

FAC[0] = 1;

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

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

// 2. 重複組み合わせ nHk = (n - 1 + k)C(n - 1) を計算.

LL ans = combination(n - 1 + k, n - 1);

// 3. 出力.

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

return 0;

}

[入力例]
10
2

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

[入力例]
10
3

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

[入力例]
10
4

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

[入力例]
400
296

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

[入力例]
100000
100000

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

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

220

※AtCoderテストケースより

[入力例]

[出力例]

715

※AtCoderテストケースより

[入力例]

400

296

[出力例]

546898535

※AtCoderテストケースより

[入力例]

100000

[出力例]

939733670

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 021

2020年3月14日2020年3月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 021 の問題C (C – 正直者の高橋くん) を解いてみた.

■感想.
1. 最短距離を計算後(bfs)に, 経路をカウントする部分の方針が見えず, 解説を見て実装した.
2. 幅優先探索の復習が出来たので, 良かった思う.
3. DAG(Directed Acyclic Graph)という新しい知識に触れることが出来たので, 非常に良かったと思う.
4. 訪問済みフラグを, 頂点ベースで実装しても上手く行かなかったので, 辺ベースに変更したところ, AC版となった.
5. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/abc021
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
const int MAX = 111;
const int MOD = 1e9 + 7;
int dist[MAX], dp[MAX];
int memo[MAX][MAX]; // 辺に関する訪問済みフラグ.

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

// DAG上の最短経路数をカウント(bfsっぽい実装).
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @return: 特に無し.
void countRouteOnDAG(vvi &G, int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. スタート地点は, 1通りとする.
    dp[s] = 1;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            
            // 6. 訪問済であれば, 処理をスキップ.
            if(memo[u][e] > 0)  continue;
            if(memo[u][e] == 0) dp[e] += dp[u], dp[e] %= MOD, q.push(e), memo[u][e] = 1;
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, a, b, M;
    scanf("%d %d %d %d", &N, &a, &b, &M);
    a--, b--;
    
    vvi G(MAX);
    vector<P> stock;
    int x, y;
    rep(i, M){
        scanf("%d %d", &x, &y);
        x--, y--;
        G[x].pb(y);
        G[y].pb(x);
        stock.pb({x, y});  // DAG構築で使う予定.
    }
    
    // 2. スタート地点 の 頂点 a からの 最短経路 を 探索.
    bfs(G, a);
    // rep(i, N) printf("%d ", dist[i]);
    // puts("");
    
    // 3. DAG作成.
    // DAG(Directed Acyclic Graph): 閉路がない有効グラフ(解説通り).
    vvi DAG(MAX);
    for(auto &p : stock){
        int u = p.a, v = p.b;
        if(dist[p.b] == dist[p.a] + 1) DAG[p.a].pb(p.b); // 頂点 u -> 頂点 v.
        if(dist[p.a] == dist[p.b] + 1) DAG[p.b].pb(p.a); // 頂点 v -> 頂点 u.
    }
    
    // 4. DAG から 最短経路 の 本数 を カウント(解説通り).
    countRouteOnDAG(DAG, a);
    // rep(i, N) printf("%d ", dp[i]);
    // puts("");
    
    // 5. 出力.
    printf("%d\n", dp[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

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<int>>;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

const int MAX = 111;

const int MOD = 1e9 + 7;

int dist[MAX], dp[MAX];

int memo[MAX][MAX]; // 辺に関する訪問済みフラグ.

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

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

// ※bfsの動作確認用.

// @param G: グラフ.

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

// @return: 特に無し.

void bfs(vvi &G, int s){

// 1. 空のキュー.

queue<int> q;

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

// -> スタート地点は, 距離ゼロと見る.

dist[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(dist[e] > 0) continue;

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

}

return;

}

// DAG上の最短経路数をカウント(bfsっぽい実装).

// @param G: グラフ.

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

// @return: 特に無し.

void countRouteOnDAG(vvi &G, int s){

// 1. 空のキュー.

queue<int> q;

// 2. スタート地点は, 1通りとする.

dp[s] = 1;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(memo[u][e] > 0) continue;

if(memo[u][e] == 0) dp[e] += dp[u], dp[e] %= MOD, q.push(e), memo[u][e] = 1;

}

return;

}

int main(){

// 1. 入力情報.

int N, a, b, M;

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

a--, b--;

vvi G(MAX);

vector<P> stock;

int x, y;

rep(i, M){

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

x--, y--;

G[x].pb(y);

G[y].pb(x);

stock.pb({x, y}); // DAG構築で使う予定.

}

// 2. スタート地点の頂点 a からの最短経路を探索.

bfs(G, a);

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

// puts("");

// 3. DAG作成.

// DAG(Directed Acyclic Graph): 閉路がない有効グラフ(解説通り).

vvi DAG(MAX);

for(auto &p : stock){

int u = p.a, v = p.b;

if(dist[p.b] == dist[p.a] + 1) DAG[p.a].pb(p.b); // 頂点 u -> 頂点 v.

if(dist[p.a] == dist[p.b] + 1) DAG[p.b].pb(p.a); // 頂点 v -> 頂点 u.

}

// 4. DAG から最短経路の本数をカウント(解説通り).

countRouteOnDAG(DAG, a);

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

// puts("");

// 5. 出力.

printf("%d\n", dp[b]);

return 0;

}

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

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

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

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

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

[出力例]
10

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

[出力例]
8

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

[出力例]
6

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

[出力例]
11

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

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

[入力例]

1 7

1 2

1 3

4 2

4 3

4 5

4 6

7 5

7 6

[出力例]

※AtCoderテストケースより

[入力例]

1 7

1 2

1 3

4 2

4 3

4 5

4 6

7 5

7 6

4 7

[出力例]

※AtCoderテストケースより

[入力例]

3 10

3 2

3 1

3 4

3 5

2 6

2 7

1 7

4 8

5 8

5 13

5 9

8 15

13 15

9 15

7 11

7 14

7 12

11 10

14 10

12 10

15 10

[出力例]

[入力例]

5 11

5 2

5 3

5 4

5 1

5 6

6 14

6 15

14 16

16 15

1 12

13 1

10 4

9 3

8 2

7 2

20 19

19 7

7 17

8 17

17 9

10 24

12 24

12 18

13 18

24 17

16 18

22 18

21 17

23 17

11 23

11 21

11 22

[出力例]

[入力例]

1 16

1 2

1 3

1 4

2 3

3 4

2 5

3 5

4 5

4 7

2 6

5 6

5 7

7 8

7 15

6 8

6 14

8 11

8 9

8 10

10 11

10 9

14 9

9 12

15 11

11 13

13 16

12 16

[出力例]

[入力例]

18 17

18 1

18 2

2 3

18 3

1 4

1 5

5 6

1 6

2 7

2 8

2 9

3 10

3 11

4 12

5 12

6 12

7 13

7 8

8 13

9 13

10 14

14 11

10 11

12 15

13 15

13 16

14 16

15 17

15 16

16 17

[出力例]

■参照サイト
AtCoder Beginner Contest 021

2020年3月14日2020年3月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 022 の問題C (C – Blue Bird) を解いてみた.

■感想.
1. 方針が全く見えず, 解説を見て実装した.
2. Warshall–Floyd法の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/abc022
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 333;
const int INF = 123456789;
int d[MAX][MAX];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, MAX) rep(j, MAX) if(i != j) d[i][j] = INF;
    vector<int> z;
    rep(i, M){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        d[a][b] = c;
        d[b][a] = c;
        // 頂点0 に 隣接する頂点を保存.
        if(a == 0) z.pb(b);
        if(b == 0) z.pb(a);
    }
    
    // 2. Warshall–Floyd法(※各頂点間の最短距離を保存).
    // 但し, 頂点0 に 隣接する辺を除いたグラフで計算する(解説通り).
    repx(k, 1, N){
        repx(i, 1, N){
            repx(j, 1, N){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    
    // 3. 頂点0 に隣接する 頂点x, y を 選んだとして, 閉路の最短距離を計算(解説通り).
    int ans = INF;
    rep(i, z.size()){
        rep(j, z.size()){
            if(i != j) ans = min(ans, d[0][z[i]] + d[0][z[j]] + d[z[i]][z[j]]);
        }
    }
    
    // 4. 出力.
    printf("%d\n", (ans == INF) ? -1 : ans);
    return 0;
    
}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

const int MAX = 333;

const int INF = 123456789;

int d[MAX][MAX];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, MAX) rep(j, MAX) if(i != j) d[i][j] = INF;

vector<int> z;

rep(i, M){

int a, b, c;

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

a--, b--;

d[a][b] = c;

d[b][a] = c;

// 頂点0 に隣接する頂点を保存.

if(a == 0) z.pb(b);

if(b == 0) z.pb(a);

}

// 2. Warshall–Floyd法(※各頂点間の最短距離を保存).

// 但し, 頂点0 に隣接する辺を除いたグラフで計算する(解説通り).

repx(k, 1, N){

repx(i, 1, N){

repx(j, 1, N){

d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

}

// 3. 頂点0 に隣接する頂点x, y を選んだとして, 閉路の最短距離を計算(解説通り).

int ans = INF;

rep(i, z.size()){

rep(j, z.size()){

if(i != j) ans = min(ans, d[0][z[i]] + d[0][z[j]] + d[z[i]][z[j]]);

}

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]

5 7

1 2 2

1 4 1

2 3 7

1 5 12

3 5 2

2 5 3

3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2 1

1 3 1

1 4 1

1 5 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

10 12

1 4 3

1 9 1

2 5 4

2 6 1

3 7 5

3 10 9

4 7 2

5 6 6

5 8 5

6 8 3

7 9 5

8 10 8

[出力例]

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 022

2020年3月13日

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

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

■感想.
1. 重心から, 最も近い点を考慮して, 拡大率を求める方針で実装したが, AC版を取れなかった.
※ 解説を見たところ, 距離が, 0 になる場合があって, 場合分けが必要との指摘があった.
※ 途中, redeclared as different kind of symbol の error も出てきて, 実装に手こずってしまった.
2. 解説にある方法の中で, 重心から, 最も遠い点を考慮する方針に変更したら, AC版となった.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/abc022
#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 double INF = 202020202020.0;
const int MAX = 101010;
// ./Main.cpp:10:14: error: ‘double y1 [101010]’ redeclared as different kind of symbol
double ax1[MAX], ay1[MAX], ax2[MAX], ay2[MAX];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 1回目の観測.
    double gx1 = 0.0, gy1 = 0.0, gx2 = 0.0, gy2 = 0.0;
    rep(i, N){
        scanf("%lf %lf", &ax1[i], &ay1[i]);
        gx1 += ax1[i];
        gy1 += ay1[i];
    }
    
    // 3. 2回目の観測.
    rep(i, N){
        scanf("%lf %lf", &ax2[i], &ay2[i]);
        gx2 += ax2[i];
        gy2 += ay2[i];
    }
    
    // 4. 重心を計算.
    gx1 /= (double)N, gy1 /= (double)N;
    gx2 /= (double)N, gy2 /= (double)N;
    
    // 5. 重心から一番遠い点の距離を計算.
    double d1 = 0.0, d2 = 0.0;
    rep(i, N) d1 = max(d1, hypot(ax1[i] - gx1, ay1[i] - gy1));
    rep(i, N) d2 = max(d2, hypot(ax2[i] - gx2, ay2[i] - gy2));
    
    // 6. 拡大率を計算.
    double ans = d2 / d1;
    
    // 7. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

// 解き直し.

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

#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 double INF = 202020202020.0;

const int MAX = 101010;

// ./Main.cpp:10:14: error: ‘double y1 [101010]’ redeclared as different kind of symbol

double ax1[MAX], ay1[MAX], ax2[MAX], ay2[MAX];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 1回目の観測.

double gx1 = 0.0, gy1 = 0.0, gx2 = 0.0, gy2 = 0.0;

rep(i, N){

scanf("%lf %lf", &ax1[i], &ay1[i]);

gx1 += ax1[i];

gy1 += ay1[i];

}

// 3. 2回目の観測.

rep(i, N){

scanf("%lf %lf", &ax2[i], &ay2[i]);

gx2 += ax2[i];

gy2 += ay2[i];

}

// 4. 重心を計算.

gx1 /= (double)N, gy1 /= (double)N;

gx2 /= (double)N, gy2 /= (double)N;

// 5. 重心から一番遠い点の距離を計算.

double d1 = 0.0, d2 = 0.0;

rep(i, N) d1 = max(d1, hypot(ax1[i] - gx1, ay1[i] - gy1));

rep(i, N) d2 = max(d2, hypot(ax2[i] - gx2, ay2[i] - gy2));

// 6. 拡大率を計算.

double ans = d2 / d1;

// 7. 出力.

printf("%.12lf\n", ans);

return 0;

}

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

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

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

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

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

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

[入力例]

0 0

0 1

1 0

1 1

0 2

2 0

-2 0

0 -2

[出力例]

2.8284271247

※AtCoderテストケースより

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

2.828427124746

[入力例]

3 4

1 3

4 3

2 2

0 1

2 0

5 5

-1 2

-1 -3

2 1

2 6

4 -3

[出力例]

2.2360679775

※AtCoderテストケースより

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

2.236067977500

■参照サイト
AtCoder Beginner Contest 022

2020年3月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 026 の問題D (D – 高橋君ボール1号) を解いてみた.

■感想.
1. とりあえず, 解説見る前に, AC版となったので良かったと思う.
2. 誤差を小さくするために, 試行錯誤した気がする, あと, 検算も行って, 誤差も確認してみた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
const double INF = 123456789.0;
const double PI = acos(-1);

// 近似値計算を行う.
// @param A: 与えられた定数.
// @param B: 与えられた定数.
// @param C: 与えられた定数.
// @param v: x1 - x2 の絶対値 が 最小となる差分を抽出するときの初期値.
// @param t0: x1 - x2 の絶対値 が 最小となる時刻を抽出するときの初期値.
// @param t1: チェック開始の時刻.
// @param t2: チェック終了の時刻.
// @param dt: 時刻の増分.
// @param ret: f(t) = 100 の候補となる時刻 t を 返却.
double approximation(double A, double B, double C, double v, double t0, double t1, double t2, double dt){
    double mValue = v;
    double ret = t0;
    for(double t = t1; t <= t2; t += dt){
        double x1 = (100.0 - A * t) / B;
        double x2 = sin(C * t * PI);
        double dx = abs(x1 - x2);
        if(mValue > dx) mValue = dx, ret = t;
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    double A, B, C;
    scanf("%lf %lf %lf", &A, &B, &C);
    
    // 2. t の 範囲.
    // sin が -1.0 ～ 1.0 を取り得るので, 
    // (100.0 - B) / A ～ t ～ (100.0 + B) / A にあると見る.
    // (100.0 - A * t) / B と sin(C * t * PI) を 比較していく.
    double minT = (100.0 - B) / A - 1.0;
    double maxT = (100.0 + B) / A + 1.0;
    
    // 3. 求めたいタイミング t を 計算.
    // 3-1. 0.0001 刻みでチェック.
    double ans = approximation(A, B, C, INF, INF, minT, maxT, 0.0001);
    
    // 3-2. 0.0000001 刻みでチェック.
    ans = approximation(A, B, C, INF, INF, ans - 0.00005, ans + 0.00005, 0.0000001);
    
    // 3-3. 0.0000000001 刻みでチェック.
    ans = approximation(A, B, C, INF, INF, ans - 0.00000005, ans + 0.00000005, 0.0000000001);
    
    // 4. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

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

const double INF = 123456789.0;

const double PI = acos(-1);

// 近似値計算を行う.

// @param A: 与えられた定数.

// @param B: 与えられた定数.

// @param C: 与えられた定数.

// @param v: x1 - x2 の絶対値が最小となる差分を抽出するときの初期値.

// @param t0: x1 - x2 の絶対値が最小となる時刻を抽出するときの初期値.

// @param t1: チェック開始の時刻.

// @param t2: チェック終了の時刻.

// @param dt: 時刻の増分.

// @param ret: f(t) = 100 の候補となる時刻 t を返却.

double approximation(double A, double B, double C, double v, double t0, double t1, double t2, double dt){

double mValue = v;

double ret = t0;

for(double t = t1; t <= t2; t += dt){

double x1 = (100.0 - A * t) / B;

double x2 = sin(C * t * PI);

double dx = abs(x1 - x2);

if(mValue > dx) mValue = dx, ret = t;

}

return ret;

}

int main(){

// 1. 入力情報.

double A, B, C;

scanf("%lf %lf %lf", &A, &B, &C);

// 2. t の範囲.

// sin が -1.0 ～ 1.0 を取り得るので,

// (100.0 - B) / A ～ t ～ (100.0 + B) / A にあると見る.

// (100.0 - A * t) / B と sin(C * t * PI) を比較していく.

double minT = (100.0 - B) / A - 1.0;

double maxT = (100.0 + B) / A + 1.0;

// 3. 求めたいタイミング t を計算.

// 3-1. 0.0001 刻みでチェック.

double ans = approximation(A, B, C, INF, INF, minT, maxT, 0.0001);

// 3-2. 0.0000001 刻みでチェック.

ans = approximation(A, B, C, INF, INF, ans - 0.00005, ans + 0.00005, 0.0000001);

// 3-3. 0.0000000001 刻みでチェック.

ans = approximation(A, B, C, INF, INF, ans - 0.00000005, ans + 0.00000005, 0.0000000001);

// 4. 出力.

printf("%.12lf\n", ans);

return 0;

}

[入力例]
1 1 1

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

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

[入力例]
53 82 49

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

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

[検算]
f(t) = A * t + B * sin(C * t * π)
= 53 * 3.339022245712 + 82 * sin(49 * 3.339022245712 * pi)
= 99.999999846272120472542354537431751869090678235828794219312798

[入力例]
2 5 11

[出力例]
47.500000000035

[検算]
f(t) = A * t + B * sin(C * t * π)
= 2 * 47.500000000035 + 5 * sin(11 * 47.500000000035 * pi)
= 100.00000000006999999634269471912132454725400665944316198321531

[入力例]
73 97 53

[出力例]
2.409696528411

[検算]
f(t) = A * t + B * sin(C * t * π)
= 73 * 2.409696528411 + 97 * sin(53 * 2.409696528411 * pi)
= 99.999999755111031414900657374160299818922779168874946453733136

[入力例]
83 93 62

[出力例]
0.950437075697

[検算]
f(t) = A * t + B * sin(C * t * π)
= 83 * 0.950437075697 + 93 * sin(62 * 0.950437075697 * pi)
= 99.999999284483012827002351221307941250368079227798607124455658

[入力例]
3 5 7

[出力例]
34.166666666637

[検算]
f(t) = A * t + B * sin(C * t * π)
= 3 * 34.166666666637 + 5 * sin(7 * 34.166666666637 * pi)
= 100.00000000273599251032683314745965551798528853209778735756501

[入力例]
97 86 75

[出力例]
0.356330212207

[検算]
f(t) = A * t + B * sin(C * t * π)
= 97 * 0.356330212207 + 86 * sin(75 * 0.356330212207 * pi)
= 99.999999783042160771603891862182801369863813784100760331134612

[入力例]
37 91 58

[出力例]
0.320343316043

[検算]
f(t) = A * t + B * sin(C * t * π)
= 37 * 0.320343316043 + 91 * sin(58 * 0.320343316043 * pi)
= 100.00000002495890247903533712021585220833944974624376986519264

[入力例]

1 1 1

[出力例]

100

※AtCoderテストケースより

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

99.999999999964

[入力例]

53 82 49

[出力例]

1.63372043395339

※AtCoderテストケースより

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

3.339022245712

[検算]

f(t) = A * t + B * sin(C * t * π)

= 53 * 3.339022245712 + 82 * sin(49 * 3.339022245712 * pi)

= 99.999999846272120472542354537431751869090678235828794219312798

[入力例]

2 5 11

[出力例]

47.500000000035

[検算]

f(t) = A * t + B * sin(C * t * π)

= 2 * 47.500000000035 + 5 * sin(11 * 47.500000000035 * pi)

= 100.00000000006999999634269471912132454725400665944316198321531

[入力例]

73 97 53

[出力例]

2.409696528411

[検算]

f(t) = A * t + B * sin(C * t * π)

= 73 * 2.409696528411 + 97 * sin(53 * 2.409696528411 * pi)

= 99.999999755111031414900657374160299818922779168874946453733136

[入力例]

83 93 62

[出力例]

0.950437075697

[検算]

f(t) = A * t + B * sin(C * t * π)

= 83 * 0.950437075697 + 93 * sin(62 * 0.950437075697 * pi)

= 99.999999284483012827002351221307941250368079227798607124455658

[入力例]

3 5 7

[出力例]

34.166666666637

[検算]

f(t) = A * t + B * sin(C * t * π)

= 3 * 34.166666666637 + 5 * sin(7 * 34.166666666637 * pi)

= 100.00000000273599251032683314745965551798528853209778735756501

[入力例]

97 86 75

[出力例]

0.356330212207

[検算]

f(t) = A * t + B * sin(C * t * π)

= 97 * 0.356330212207 + 86 * sin(75 * 0.356330212207 * pi)

= 99.999999783042160771603891862182801369863813784100760331134612

[入力例]

37 91 58

[出力例]

0.320343316043

[検算]

f(t) = A * t + B * sin(C * t * π)

= 37 * 0.320343316043 + 91 * sin(58 * 0.320343316043 * pi)

= 100.00000002495890247903533712021585220833944974624376986519264

■参照サイト
AtCoder Beginner Contest 026
フリー計算

2020年3月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 026 の問題C (C – 高橋君の給料) を解いてみた.

■感想.
1. とりあえず, 解説見る前に, AC版となったので良かったと思う.
2. 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int INF = 123456789;
vector<int> B[33];
int C[33];

int main(){
    
    // 1. 入力情報.
    int N, b;
    scanf("%d", &N);
    rep(i, N - 1){
        scanf("%d", &b);
        B[b].pb(i + 2);
    }
    
    // 2. 部下のいない社員の給料を設定.
    rep(i, 33) C[i] = -INF;
    repx(i, 1, N + 1) if(B[i].size() == 0) C[i] = 1;
    
    // 3. 部下のいる社員の給料を設定.
    bool ok = false;
    while(1){
        // 計算済みフラグを設定.
        ok = true;
        
        // 給料の金額を更新.
        repx(i, 1, N + 1){
            // 直属の部下の給料をチェック.
            int minC = INF, maxC = -INF;
            for(auto &p : B[i]){
                minC = min(minC, C[p]);
                maxC = max(maxC, C[p]);
            }
            // 直属の部下で, -INF が いない場合は, 更新できる.
            if(minC > -INF) C[i] = maxC + minC + 1;
        }
        
        // 計算済みフラグを更新.
        repx(i, 1, N + 1) if(C[i] == -INF) ok = false;
        
        // 計算済みの場合は, 終了.
        if(ok) break;
    }
    // repx(i, 1, N + 1) printf("%d ", C[i]);
    // puts("");
    
    // 4. 出力.
    printf("%d\n", C[1]);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

const int INF = 123456789;

vector<int> B[33];

int C[33];

int main(){

// 1. 入力情報.

int N, b;

scanf("%d", &N);

rep(i, N - 1){

scanf("%d", &b);

B[b].pb(i + 2);

}

// 2. 部下のいない社員の給料を設定.

rep(i, 33) C[i] = -INF;

repx(i, 1, N + 1) if(B[i].size() == 0) C[i] = 1;

// 3. 部下のいる社員の給料を設定.

bool ok = false;

while(1){

// 計算済みフラグを設定.

ok = true;

// 給料の金額を更新.

repx(i, 1, N + 1){

// 直属の部下の給料をチェック.

int minC = INF, maxC = -INF;

for(auto &p : B[i]){

minC = min(minC, C[p]);

maxC = max(maxC, C[p]);

}

// 直属の部下で, -INF がいない場合は, 更新できる.

if(minC > -INF) C[i] = maxC + minC + 1;

}

// 計算済みフラグを更新.

repx(i, 1, N + 1) if(C[i] == -INF) ok = false;

// 計算済みの場合は, 終了.

if(ok) break;

}

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

// puts("");

// 4. 出力.

printf("%d\n", C[1]);

return 0;

}

[入力例]
5
1
1
1
1

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

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

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

[入力例]
6
1
2
3
3
2

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

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

[出力例(debug版)]
1023 511 255 127 63 31 15 7 3 1 
1023
※AtCoderテストケースより

[入力例]
6
1
1
1
2
2

[出力例(debug版)]
5 3 1 1 1 1 
5

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

[出力例(debug版)]
15 7 3 3 1 1 1 1 1 1 1 
15

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

[出力例(debug版)]
1048575 524287 262143 131071 65535 32767 16383 8191 4095 2047 1023 511 255 127 63 31 15 7 3 1 
1048575

100

101

102

103

104

105

106

107

108

109

110

[入力例]

[出力例(debug版)]

3 1 1 1 1

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

7 3 3 1 1 1 1

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

11 5 3 1 1 1

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

1023 511 255 127 63 31 15 7 3 1

1023

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

5 3 1 1 1 1

[入力例]

[出力例(debug版)]

15 7 3 3 1 1 1 1 1 1 1

[入力例]

[出力例(debug版)]

1048575 524287 262143 131071 65535 32767 16383 8191 4095 2047 1023 511 255 127 63 31 15 7 3 1

1048575

■参照サイト
AtCoder Beginner Contest 026

2020年3月8日

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

C++の練習を兼ねて, AtCoder Beginner Contest 027 の問題D (D – ロボット) を解いてみた.

■感想.
1. 方針が全く見えなかったので, 解説を確認して, 実装した.
2. 個人的には, 非常に摩訶不思議な解法に見えたとともに, アルゴリズムの奥深さに驚いた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/abc027
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
LL p[101010]; // i番目より右側にある '+' の 個数.
LL m[101010]; // i番目より右側にある '-' の 個数.

int main(){
    
    // 1. 入力情報.
    char c[101010];
    scanf("%s", c);
    
    // 2. i番目よりも右側にある '+', '-' を 集計(解説通り).
    int l = strlen(c);
    rep(i, l){
        p[i + 1] = p[i];
        m[i + 1] = m[i];
        if(c[i] == '+') p[i + 1]++;
        if(c[i] == '-') m[i + 1]++;
    }
    // rep(i, l + 1) printf("p[%d]=%lld m[%d]=%lld\n", i, p[i], i, m[i]);
    
    // 3. 幸福度の変化量(解説通り).
    vector<LL> dx; // (i番目より右側の '+' の個数) - (i番目より右側の '-' の個数)
    int mCount = 0;
    rep(i, l) if(c[i] == 'M') dx.pb({p[i + 1] - m[i + 1]}), mCount++;
    
    // 4. sort(解説通り).
    sort(all(dx));
    
    // 5. 後半 - 前半 を 計算(解説通り).
    LL ans = 0;
    rep(i, mCount / 2)          ans -= dx[i]; // 前半.
    repx(i, mCount / 2, mCount) ans += dx[i]; // 後半.
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

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

LL p[101010]; // i番目より右側にある '+' の個数.

LL m[101010]; // i番目より右側にある '-' の個数.

int main(){

// 1. 入力情報.

char c[101010];

scanf("%s", c);

// 2. i番目よりも右側にある '+', '-' を集計(解説通り).

int l = strlen(c);

rep(i, l){

p[i + 1] = p[i];

m[i + 1] = m[i];

if(c[i] == '+') p[i + 1]++;

if(c[i] == '-') m[i + 1]++;

}

// rep(i, l + 1) printf("p[%d]=%lld m[%d]=%lld\n", i, p[i], i, m[i]);

// 3. 幸福度の変化量(解説通り).

vector<LL> dx; // (i番目より右側の '+' の個数) - (i番目より右側の '-' の個数)

int mCount = 0;

rep(i, l) if(c[i] == 'M') dx.pb({p[i + 1] - m[i + 1]}), mCount++;

// 4. sort(解説通り).

sort(all(dx));

// 5. 後半 - 前半を計算(解説通り).

LL ans = 0;

rep(i, mCount / 2) ans -= dx[i]; // 前半.

repx(i, mCount / 2, mCount) ans += dx[i]; // 後半.

// 6. 出力.

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

return 0;

}

[入力例]
M+MM-M

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

[入力例]
MMM+M

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

[入力例]
MMM+--MMM

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

[入力例]
+

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

[入力例]
M--M-M+M+

[出力例]
3
※AtCoder解説例より

[入力例]
M--M-+M++-MM+++-M---M+--M-+---M++---M+--MM---M-M-MMM+M-M---+--M-M----M---M-MMM+-M+++-M-+MMMM-+--M+M++-M--+MM-+-++-+-M---M-M+++M-+--++-M------+M-MM++M-MM-++-M-M+-MM-+-+--M-M-+M---+-++-M++--+---+++MMMM-

[出力例]
555

[入力例]
M+MMMM++MM-++-+MMM+-M--M+M-+-MMM+-MM---++M-+MMMM+--+MMMM+-M+M-M-+-+M+MMM---+M+MMMM+++MMM-++M-M-M+-MM+M-MM+MMM-+M+M-MMMMMMMMMMM+M+-+MM+M++++M+M+M++MM-++M-MM-M+MMM+-MMM-MMMMMMMMM+MMM-MMM--MM-M+-MMM++M-MMM-MMMMM-+M-MM++MM-M+--+MM+-MM--+-+++M-MMMMMMMMM+M-M-+MM+MM--MMMMMMMM---MM+-++-MM+MMMMMM+MMMM-+MM++--M+++MM-M---MMMMMMMM-+-M-MMM++M+-+-MM+M-M-M+MMM+M+M-+-MM-M-M++M-+---+-MMMMMM++-MM-M-+MMM-+M-M-+-M++M-+MMMM--MM-MM-+M+MM-++MM++--+MMM----++MMM+++M-MMMM-MMM--M-MM-M+++MM-M+-MM-MMMMMMMM+MM+MM+-MMMM+M+M-+MMMM-MMMM+MMMM-M+--M++M+MMM-++-MM+M-+M-+M-++M+MM++-M-+-M--M+MM-MMM-++-M-M+M--MM++--MM-MM-MM++-+M+-+MM-M-+M+MM++M-MMMMM-MMMM+M+-MM+-+M-M+-M-M++M++-+MMMMM-MMM+--MMM-MM-+M+++M-M-MM+-M-MM-MM++M+M-+-MMMMMMMMMM+M+M++-MM-MMMM-+MMMM+MMM+MM--+M+M--++MMM+MM+MM+MM--M+-+-MM+M-M-+M--MMM++M-MMM+-M++MM-MMM+-++-M--M+M++MM++-M+M+MM--+-+MMMMMMM+-MMMM+-M++-++MM+MM+-M----M-MMMM--M+-MM--+-M---MMMM+MMMM+M+M--M++M++M---+-M-MMMMMM+--M+MMMMM+-M+M++M+-MM++--MMMM+M+MMMMM-MMMMM-++MM+M+MMM-+-+-+M-MMM---++M-M+M--MMM+M-++-+M+

[出力例]
2015

[入力例]

M+MM-M

[出力例]

※AtCoderテストケースより

[入力例]

MMM+M

[出力例]

※AtCoderテストケースより

[入力例]

MMM+--MMM

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

M--M-M+M+

[出力例]

※AtCoder解説例より

[入力例]

M--M-+M++-MM+++-M---M+--M-+---M++---M+--MM---M-M-MMM+M-M---+--M-M----M---M-MMM+-M+++-M-+MMMM-+--M+M++-M--+MM-+-++-+-M---M-M+++M-+--++-M------+M-MM++M-MM-++-M-M+-MM-+-+--M-M-+M---+-++-M++--+---+++MMMM-

[出力例]

555

[入力例]

M+MMMM++MM-++-+MMM+-M--M+M-+-MMM+-MM---++M-+MMMM+--+MMMM+-M+M-M-+-+M+MMM---+M+MMMM+++MMM-++M-M-M+-MM+M-MM+MMM-+M+M-MMMMMMMMMMM+M+-+MM+M++++M+M+M++MM-++M-MM-M+MMM+-MMM-MMMMMMMMM+MMM-MMM--MM-M+-MMM++M-MMM-MMMMM-+M-MM++MM-M+--+MM+-MM--+-+++M-MMMMMMMMM+M-M-+MM+MM--MMMMMMMM---MM+-++-MM+MMMMMM+MMMM-+MM++--M+++MM-M---MMMMMMMM-+-M-MMM++M+-+-MM+M-M-M+MMM+M+M-+-MM-M-M++M-+---+-MMMMMM++-MM-M-+MMM-+M-M-+-M++M-+MMMM--MM-MM-+M+MM-++MM++--+MMM----++MMM+++M-MMMM-MMM--M-MM-M+++MM-M+-MM-MMMMMMMM+MM+MM+-MMMM+M+M-+MMMM-MMMM+MMMM-M+--M++M+MMM-++-MM+M-+M-+M-++M+MM++-M-+-M--M+MM-MMM-++-M-M+M--MM++--MM-MM-MM++-+M+-+MM-M-+M+MM++M-MMMMM-MMMM+M+-MM+-+M-M+-M-M++M++-+MMMMM-MMM+--MMM-MM-+M+++M-M-MM+-M-MM-MM++M+M-+-MMMMMMMMMM+M+M++-MM-MMMM-+MMMM+MMM+MM--+M+M--++MMM+MM+MM+MM--M+-+-MM+M-M-+M--MMM++M-MMM+-M++MM-MMM+-++-M--M+M++MM++-M+M+MM--+-+MMMMMMM+-MMMM+-M++-++MM+MM+-M----M-MMMM--M+-MM--+-M---MMMM+MMMM+M+M--M++M++M---+-M-MMMMMM+--M+MMMMM+-M+M++M+-MM++--MMMM+M+MMMMM-MMMMM-++MM+M+MMM-+-+-+M-MMM---++M-M+M--MMM+M-++-+M+

[出力例]

2015

■参照サイト
AtCoder Beginner Contest 027

2020年3月8日

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

C++の練習を兼ねて, AtCoder Beginner Contest 158 の問題D (D – String Formation) を解いてみた(二回目).

■感想.
1. 前回版から, 実行時間を短縮できたので良かったと思う(1224[ms] ⇒ 42[ms]).
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    char o[101010];
    int Q;
    scanf("%s %d", o, &Q);
    
    // 2. 文字列を, Q回操作.
    int t, f;
    string p = "", s = ""; // prefix, suffix
    char c[11];
    bool flip = false;
    rep(i, Q){
        scanf("%d", &t);
        // 2-1. 文字列 S の前後を反転.
        if(t == 1) flip = !flip;
        
        // 2-2. 文字列 S の先頭, 末尾を操作.
        if(t == 2){
            scanf("%d %s", &f, c);
            
            // 2-3. 文字列 S の先頭に C を追加.
            if(f == 1){
                if(flip) s.pb(c[0]);
                else     p.pb(c[0]);
            }
            
            // 2-4. 文字列 S の末尾に C を追加.
            if(f == 2){
                if(flip) p.pb(c[0]);
                else     s.pb(c[0]);
            }
        }
    }
    
    // 3. 出力.
    int ol = strlen(o);
    int pl = p.size();
    int sl = s.size();
    if(flip){
        repr(i, sl - 1, 0) printf("%c", s[i]);
        repr(i, ol - 1, 0) printf("%c", o[i]);
        rep(i, pl)         printf("%c", p[i]);
    }else{
        repr(i, pl - 1, 0) printf("%c", p[i]);
        rep(i, ol)         printf("%c", o[i]);
        rep(i, sl)         printf("%c", s[i]);
    }
    return 0;
    
}

// 高速化.

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

char o[101010];

int Q;

scanf("%s %d", o, &Q);

// 2. 文字列を, Q回操作.

int t, f;

string p = "", s = ""; // prefix, suffix

char c[11];

bool flip = false;

rep(i, Q){

scanf("%d", &t);

// 2-1. 文字列 S の前後を反転.

if(t == 1) flip = !flip;

// 2-2. 文字列 S の先頭, 末尾を操作.

if(t == 2){

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

// 2-3. 文字列 S の先頭に C を追加.

if(f == 1){

if(flip) s.pb(c[0]);

else p.pb(c[0]);

}

// 2-4. 文字列 S の末尾に C を追加.

if(f == 2){

if(flip) p.pb(c[0]);

else s.pb(c[0]);

}

// 3. 出力.

int ol = strlen(o);

int pl = p.size();

int sl = s.size();

if(flip){

repr(i, sl - 1, 0) printf("%c", s[i]);

repr(i, ol - 1, 0) printf("%c", o[i]);

rep(i, pl) printf("%c", p[i]);

}else{

repr(i, pl - 1, 0) printf("%c", p[i]);

rep(i, ol) printf("%c", o[i]);

rep(i, sl) printf("%c", s[i]);

}

return 0;

}

[入力例]
a
4
2 1 p
1
2 2 c
1

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

[入力例]
a
6
2 2 a
2 1 b
1
2 2 c
1
1

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

[入力例]
y
1
2 1 x

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

[入力例]
abcba
15
2 2 d
2 1 e
1
2 2 f
1
2 1 g
1
2 1 i
1
1
2 1 j
2 2 k
1
2 2 l
2 1 m

[出力例]
mkgfeabcbadijl

[入力例]
formation
150
2 2 d
1
2 2 q
1
2 2 f
1
2 2 q
2 2 w
2 2 p
2 2 v
2 2 f
1
1
2 1 d
2 1 t
1
2 1 i
2 1 w
1
2 1 z
2 1 w
1
1
2 2 l
2 1 q
1
2 1 m
1
1
2 1 j
2 2 a
1
2 1 j
2 2 r
1
2 2 m
2 2 z
2 1 j
1
1
2 1 i
2 1 b
1
2 2 g
2 1 z
1
2 1 r
1
1
2 2 k
1
2 1 i
2 2 j
2 1 q
2 2 e
1
2 2 j
1
2 1 o
2 2 h
1
2 2 j
2 2 y
1
2 2 j
2 2 k
1
2 1 r
1
2 2 f
2 1 r
1
2 2 x
1
2 2 r
1
2 2 m
1
2 2 h
2 1 l
1
2 2 d
2 2 s
2 2 j
1
2 2 w
2 2 x
1
2 2 a
2 2 p
2 2 s
1
2 2 a
2 2 k
1
2 2 c
2 2 d
2 1 u
2 2 s
1
2 2 t
2 2 x
1
2 2 u
1
2 2 r
2 1 a
2 2 u
1
2 2 v
2 2 v
2 2 y
1
2 2 s
2 1 k
2 2 t
1
2 2 u
2 2 x
2 1 h
2 1 n
1
2 2 x
2 2 h
1
2 1 j
2 1 e
1
2 2 q
2 2 s
2 2 s
1
2 1 o
2 2 w
1
2 2 d
2 2 v
2 2 m
2 1 c
2 2 j
1
2 1 p
2 2 h
1
2 2 f
1
2 2 x
1
2 1 b
2 2 e

[出力例]
bxhcwxukyvvausdcspajsdlmxryjojqikzzmjaqwztdfdnoitamrofqqwpvfiwlmjrjibgrjehjkrfrhwxakutxrusthnxhjeqssodvmjpfe

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

[入力例]

2 1 p

2 2 c

[出力例]

cpa

※AtCoderテストケースより

[入力例]

2 2 a

2 1 b

2 2 c

[出力例]

aabc

※AtCoderテストケースより

[入力例]

2 1 x

[出力例]

※AtCoderテストケースより

[入力例]

abcba

2 2 d

2 1 e

2 2 f

2 1 g

2 1 i

2 1 j

2 2 k

2 2 l

2 1 m

[出力例]

mkgfeabcbadijl

[入力例]

formation

150

2 2 d

2 2 q

2 2 f

2 2 q

2 2 w

2 2 p

2 2 v

2 2 f

2 1 d

2 1 t

2 1 i

2 1 w

2 1 z

2 1 w

2 2 l

2 1 q

2 1 m

2 1 j

2 2 a

2 1 j

2 2 r

2 2 m

2 2 z

2 1 j

2 1 i

2 1 b

2 2 g

2 1 z

2 1 r

2 2 k

2 1 i

2 2 j

2 1 q

2 2 e

2 2 j

2 1 o

2 2 h

2 2 j

2 2 y

2 2 j

2 2 k

2 1 r

2 2 f

2 1 r

2 2 x

2 2 r

2 2 m

2 2 h

2 1 l

2 2 d

2 2 s

2 2 j

2 2 w

2 2 x

2 2 a

2 2 p

2 2 s

2 2 a

2 2 k

2 2 c

2 2 d

2 1 u

2 2 s

2 2 t

2 2 x

2 2 u

2 2 r

2 1 a

2 2 u

2 2 v

2 2 y

2 2 s

2 1 k

2 2 t

2 2 u

2 2 x

2 1 h

2 1 n

2 2 x

2 2 h

2 1 j

2 1 e

2 2 q

2 2 s

2 1 o

2 2 w

2 2 d

2 2 v

2 2 m

2 1 c

2 2 j

2 1 p

2 2 h

2 2 f

2 2 x

2 1 b

2 2 e

[出力例]

bxhcwxukyvvausdcspajsdlmxryjojqikzzmjaqwztdfdnoitamrofqqwpvfiwlmjrjibgrjehjkrfrhwxakutxrusthnxhjeqssodvmjpfe

■参照サイト
AtCoder Beginner Contest 158

C++の練習を兼ねて, AtCoder Beginner Contest 013 の 問題C (C – 節制) ～ 問題D (D – 阿弥陀) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 024 の 問題D (D – 動的計画法) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 021 の 問題D (D – 多重ループ) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 021 の 問題C (C – 正直者の高橋くん) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 022 の 問題C (C – Blue Bird) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 026 の 問題D (D – 高橋君ボール1号) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 026 の 問題C (C – 高橋君の給料) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 027 の 問題D (D – ロボット) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 158 の 問題D (D – String Formation) を解いてみた(二回目).

C++の練習を兼ねて, AtCoder Beginner Contest 013 の問題C (C – 節制) ～問題D (D – 阿弥陀) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 024 の問題D (D – 動的計画法) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 021 の問題D (D – 多重ループ) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 021 の問題C (C – 正直者の高橋くん) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 022 の問題C (C – Blue Bird) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 026 の問題D (D – 高橋君ボール1号) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 026 の問題C (C – 高橋君の給料) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 027 の問題D (D – ロボット) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 158 の問題D (D – String Formation) を解いてみた(二回目).