個人用メモ帳

2020年10月12日2020年10月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 052 の問題C (Factors of Factorial) を解いてみた.

■感想.
1. 塩漬けになっていた問題が, ようやくAC版となったので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 1 ～ N までの 約数 を 保存.
    map<int, LL> m;
    repx(i, 1, N + 1) a[i] = i;
    repx(i, 2, N + 1){
        if(a[i] > 1){
            int b = a[i];
            repex(j, i, N + 1, i){
                while(a[j] % b == 0){
                    a[j] /= b;
                    m[b]++;
                }
            }
        }
    }
    
    // 3. N! の 正の約数 の 個数は？
    LL ans = 1;
    for(auto &p : m) ans *= (p.b + 1), ans %= MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

#define b second

const LL MOD = 1e9 + 7;

int a[1010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 1 ～ N までの約数を保存.

map<int, LL> m;

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

repx(i, 2, N + 1){

if(a[i] > 1){

int b = a[i];

repex(j, i, N + 1, i){

while(a[j] % b == 0){

a[j] /= b;

m[b]++;

}

// 3. N! の正の約数の個数は？

LL ans = 1;

for(auto &p : m) ans *= (p.b + 1), ans %= MOD;

// 4. 出力.

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

return 0;

}

[入力例]
3

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

[入力例]
6

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

[入力例]
1000

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

[入力例]
777

[出力例]
435717873

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

1000

[出力例]

972926972

※AtCoderテストケースより

[入力例]

777

[出力例]

435717873

■参照サイト
AtCoder Beginner Contest 052

2020年10月11日2020年10月11日

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

C++の練習を兼ねて, AtCoder Beginner Contest 067 の問題C (Splitting Pile) ～問題D (Fennec VS. Snuke) を解いてみた.

■感想.
1. 問題C, D ともに, 解説を確認して, ようやくAC版となった.
※問題C は, 問題文を誤読(カードの配分についての区切りが, 複数ありうると誤認)していたことも判明した(汗).
2. 問題D で, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc078/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 a[202020], x[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL X = 0;
    rep(i, N){
        scanf("%lld", &a[i]);
        x[i + 1] = x[i] + a[i];
        X += a[i];
    }
    
    // 2. |X - 2 * x[i]| を 評価.
    LL ans = 202020202020202020;
    rep(i, N - 1) ans = min(ans, abs(X - 2 * x[i + 1]));
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/arc078/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 a[202020], x[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL X = 0;

rep(i, N){

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

x[i + 1] = x[i] + a[i];

X += a[i];

}

// 2. |X - 2 * x[i]| を評価.

LL ans = 202020202020202020;

rep(i, N - 1) ans = min(ans, abs(X - 2 * x[i + 1]));

// 3. 出力.

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

return 0;

}

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

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

[入力例]
2
10 -10

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

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

[出力例]
2

[入力例]
20
3 14 15 9 26 53 58 97 9 32 3 84 62 6 43 38 32 79 50 2

[出力例]
77

[入力例]

1 2 3 4 5 6

[出力例]

※AtCoderテストケースより

[入力例]

10 -10

[出力例]

※AtCoderテストケースより

[入力例]

1 3 4 7 8 9

[出力例]

[入力例]

3 14 15 9 26 53 58 97 9 32 3 84 62 6 43 38 32 79 50 2

[出力例]

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

// コメント修正して, 再提出.
// 解き直し.
// https://img.atcoder.jp/arc078/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
int d1[101010]; // 頂点 1 から各頂点への最短距離を保存.
int dn[202020]; // 頂点 N から各頂点への最短距離を保存.

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

int main(){
    
    // 1. 入力情報.
    int N, a, b;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 頂点 1, N から 各頂点への距離を保存.
    bfs(G, 0, d1);
    bfs(G, N - 1, dn);
    
    // 3. 黒, 白のマスの個数を評価.
    int black = 0;
    rep(i, N) if(d1[i] <= dn[i]) black++;
    
    // 4. 出力.
    printf("%s\n", (black > N / 2) ? "Fennec" : "Snuke");
    return 0;
    
}

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

// 解き直し.

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

int d1[101010]; // 頂点 1 から各頂点への最短距離を保存.

int dn[202020]; // 頂点 N から各頂点への最短距離を保存.

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

// ※bfsの動作確認用.

// @param G: グラフ.

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

// @param d: 探索開始地点からの距離.

// @return: 特に無し.

void bfs(vvi &G, int s, int* d){

// 1. 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(d[e]) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int N, a, b;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 頂点 1, N から各頂点への距離を保存.

bfs(G, 0, d1);

bfs(G, N - 1, dn);

// 3. 黒, 白のマスの個数を評価.

int black = 0;

rep(i, N) if(d1[i] <= dn[i]) black++;

// 4. 出力.

printf("%s\n", (black > N / 2) ? "Fennec" : "Snuke");

return 0;

}

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

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

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

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

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

[出力例]
Fennec

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

[出力例]
Snuke

[入力例]

3 6

1 2

3 1

7 4

5 7

1 4

[出力例]

Fennec

※AtCoderテストケースより

[入力例]

1 4

4 2

2 3

[出力例]

Snuke

※AtCoderテストケースより

[入力例]

1 2

7 3

3 2

5 1

8 1

4 6

6 9

6 1

[出力例]

Fennec

[入力例]

9 10

10 8

1 10

2 1

3 2

2 4

8 7

7 6

7 5

[出力例]

Snuke

■参照サイト
AtCoder Beginner Contest 067

2020年10月9日2020年10月9日

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

C++の練習を兼ねて, AtCoder Regular Contest 029 の問題A (高橋君とお肉) ～問題B (高橋君と禁断の書) を解いてみた.

■感想.
1. 問題B は, 計算式に辿り着くまで時間かかったものの, 何とかAC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■C++版プログラム(問題A／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--)
int t[4];

int main(){
    
    // 1. 入力情報.
    int N, sum = 0;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &t[i]);
        sum += t[i];
    }
    
    // 2. お肉を配置し, 出力.
    // 2-1. N = 1 の 場合.
    if(N == 1) printf("%d\n", t[0]);
    
    // 2-2. N = 2 の 場合.
    if(N == 2) printf("%d\n", max(t[0], t[1]));
    
    // 2-3. N = 3 の 場合.
    if(N == 3){
        int t0 = max(t[0], sum - t[0]);
        int t1 = max(t[1], sum - t[1]);
        int t2 = max(t[2], sum - t[2]);
        printf("%d\n", min({t0, t1, t2}));
    }
    
    // 2-4. N = 4 の 場合.
    if(N == 4){
        int t0 = max(t[0], sum - t[0]);
        int t1 = max(t[1], sum - t[1]);
        int t2 = max(t[2], sum - t[2]);
        int t3 = max(t[3], sum - t[3]);
        int t4 = max(t[0] + t[1], sum - t[0] - t[1]);
        int t5 = max(t[0] + t[2], sum - t[0] - t[2]);
        int t6 = max(t[0] + t[3], sum - t[0] - t[3]);
        printf("%d\n", min({t0, t1, t2, t3, t4, t5, t6}));
    }
    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--)

int t[4];

int main(){

// 1. 入力情報.

int N, sum = 0;

scanf("%d", &N);

rep(i, N){

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

sum += t[i];

}

// 2. お肉を配置し, 出力.

// 2-1. N = 1 の場合.

if(N == 1) printf("%d\n", t[0]);

// 2-2. N = 2 の場合.

if(N == 2) printf("%d\n", max(t[0], t[1]));

// 2-3. N = 3 の場合.

if(N == 3){

int t0 = max(t[0], sum - t[0]);

int t1 = max(t[1], sum - t[1]);

int t2 = max(t[2], sum - t[2]);

printf("%d\n", min({t0, t1, t2}));

}

// 2-4. N = 4 の場合.

if(N == 4){

int t0 = max(t[0], sum - t[0]);

int t1 = max(t[1], sum - t[1]);

int t2 = max(t[2], sum - t[2]);

int t3 = max(t[3], sum - t[3]);

int t4 = max(t[0] + t[1], sum - t[0] - t[1]);

int t5 = max(t[0] + t[2], sum - t[0] - t[2]);

int t6 = max(t[0] + t[3], sum - t[0] - t[3]);

printf("%d\n", min({t0, t1, t2, t3, t4, t5, t6}));

}

return 0;

}

[入力例]
4
4
6
7
10

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

[入力例]
3
1
2
4

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

[入力例]
1
29

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

[入力例]
3
5
2
3

[出力例]
5

[入力例]
4
31
41
59
26

[出力例]
85

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

■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 main(){
    
    // 1. 入力情報.
    int N;
    double A, B, C, D;
    scanf("%lf %lf %d", &A, &B, &N);
    if(A < B) swap(A, B);
    
    // 2. クエリ回答.
    rep(i, N){
        scanf("%lf %lf", &C, &D);
        if(C < D) swap(C, D);
        
        // A <= C, B <= D の ときは, YES.
        if(A <= C && B <= D){
            puts("YES");
            continue;
        }
        
        // 箱に, 高さ x の地点で, 傾けて格納できるか確認.
        // B * B = x * x + (D - A * x / B) + (D - A * x / B)
        // B * B = B2 などと略記すると,  
        // -> x = {(A * B * D) - (A2 * B2 + B4 - B2 * D2) の 平方根 * B } / (A2 + B2)
        // x >= 0 かつ 2 * x + (A2 + B2 - D2) の 平方根 <= C であることを確認.
        double x = 0.0;
        x += A * B * D;
        x -= sqrt(A * A * B * B + B * B * B * B - B * B * D * D) * B;
        x /= (A * A + B * B);
        double y = 2.0 * x + sqrt(A * A + B * B - D * D);
        bool ok = (x >= 0.0);
        ok &= (y <= C);
        printf("%s\n", ok ? "YES" : "NO");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

double A, B, C, D;

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

if(A < B) swap(A, B);

// 2. クエリ回答.

rep(i, N){

scanf("%lf %lf", &C, &D);

if(C < D) swap(C, D);

// A <= C, B <= D のときは, YES.

if(A <= C && B <= D){

puts("YES");

continue;

}

// 箱に, 高さ x の地点で, 傾けて格納できるか確認.

// B * B = x * x + (D - A * x / B) + (D - A * x / B)

// B * B = B2 などと略記すると,

// -> x = {(A * B * D) - (A2 * B2 + B4 - B2 * D2) の平方根 * B } / (A2 + B2)

// x >= 0 かつ 2 * x + (A2 + B2 - D2) の平方根 <= C であることを確認.

double x = 0.0;

x += A * B * D;

x -= sqrt(A * A * B * B + B * B * B * B - B * B * D * D) * B;

x /= (A * A + B * B);

double y = 2.0 * x + sqrt(A * A + B * B - D * D);

bool ok = (x >= 0.0);

ok &= (y <= C);

printf("%s\n", ok ? "YES" : "NO");

}

return 0;

}

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

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

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

[出力例]
NO
YES
YES
YES
NO

[入力例]
2014 29
100 
1308 1432
1531 1352
1554 1300
1346 1492
1347 1551
1551 1417
1582 1571
1425 1554
1471 1350
1325 1352
1507 1353
1358 1414
1534 1398
1441 1569
1562 1540
1567 1344
1480 1406
1376 1325
1455 1543
1588 1495
1345 1584
1519 1317
1382 1584
1473 1351
1468 1532
1488 1574
1433 1489
1351 1354
1378 1406
1532 1342
1595 1354
1450 1473
1556 1572
1327 1354
1365 1389
1390 1396
1425 1350
1350 1314
1514 1404
1427 1441
1303 1458
1368 1482
1565 1387
1581 1370
1546 1475
1479 1434
1309 1307
1572 1443
1460 1475
1491 1509
1415 1383
1459 1536
1380 1504
1339 1441
1483 1562
1541 1371
1350 1380
1375 1520
1453 1397
1533 1501
1346 1525
1588 1550
1538 1511
1455 1429
1537 1525
1544 1377
1418 1496
1543 1401
1592 1580
1329 1588
1446 1535
1549 1552
1436 1328
1478 1457
1534 1512
1549 1359
1554 1510
1532 1585
1401 1314
1518 1461
1319 1439
1461 1570
1435 1467
1481 1399
1316 1553
1327 1513
1382 1468
1385 1577
1384 1328
1514 1327
1535 1307
1391 1598
1348 1375
1402 1530
1545 1334
1462 1538
1446 1308
1455 1397
1551 1452
1546 1455

[出力例]
NO
NO
NO
NO
YES
YES
YES
YES
NO
NO
NO
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
NO
YES
NO
NO
YES
YES

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

[入力例]

1 6

8 3

4 4

5 5

[出力例]

YES

※AtCoderのテストケースより

[入力例]

3 5

4 4

3 5

6 6

7 7

9 2

[出力例]

YES

[入力例]

2014 29

100

1308 1432

1531 1352

1554 1300

1346 1492

1347 1551

1551 1417

1582 1571

1425 1554

1471 1350

1325 1352

1507 1353

1358 1414

1534 1398

1441 1569

1562 1540

1567 1344

1480 1406

1376 1325

1455 1543

1588 1495

1345 1584

1519 1317

1382 1584

1473 1351

1468 1532

1488 1574

1433 1489

1351 1354

1378 1406

1532 1342

1595 1354

1450 1473

1556 1572

1327 1354

1365 1389

1390 1396

1425 1350

1350 1314

1514 1404

1427 1441

1303 1458

1368 1482

1565 1387

1581 1370

1546 1475

1479 1434

1309 1307

1572 1443

1460 1475

1491 1509

1415 1383

1459 1536

1380 1504

1339 1441

1483 1562

1541 1371

1350 1380

1375 1520

1453 1397

1533 1501

1346 1525

1588 1550

1538 1511

1455 1429

1537 1525

1544 1377

1418 1496

1543 1401

1592 1580

1329 1588

1446 1535

1549 1552

1436 1328

1478 1457

1534 1512

1549 1359

1554 1510

1532 1585

1401 1314

1518 1461

1319 1439

1461 1570

1435 1467

1481 1399

1316 1553

1327 1513

1382 1468

1385 1577

1384 1328

1514 1327

1535 1307

1391 1598

1348 1375

1402 1530

1545 1334

1462 1538

1446 1308

1455 1397

1551 1452

1546 1455

[出力例]

YES

■参照サイト
AtCoder Regular Contest 029

2020年10月8日2020年10月9日

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

C++の練習を兼ねて, AtCoder Regular Contest 052 の問題A (何期生？) ～問題B (円錐) を解いてみた.

■感想.
1. 問題B は, 累積和で処理できたので, 何とかAC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■C++版プログラム(問題A／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--)

int main(){
    
    // 1. 入力情報.
    char S[22];
    scanf("%s", S);
    int l = strlen(S);
    
    // 2. 何期生か？
    int ans = 0;
    rep(i, l) if(S[i] >= '0' && S[i] <= '9') ans = 10 * ans + (S[i] - '0');
    
    // 3. 出力.
    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--)

int main(){

// 1. 入力情報.

char S[22];

scanf("%s", S);

int l = strlen(S);

// 2. 何期生か？

int ans = 0;

rep(i, l) if(S[i] >= '0' && S[i] <= '9') ans = 10 * ans + (S[i] - '0');

// 3. 出力.

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

return 0;

}

[入力例]
chokudai55

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

[入力例]
cho9dai

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

[入力例]
atcoder52

[出力例]
52

[入力例]

chokudai55

[出力例]

※AtCoderのテストケースより

[入力例]

cho9dai

[出力例]

※AtCoderのテストケースより

[入力例]

atcoder52

[出力例]

■C++版プログラム(問題B／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--)
const double PI = acos(-1.0);
double cone[20202][111], cones[20202];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    
    // 2. 円錐の体積を集計.
    rep(i, N){
        double x, r, h;
        scanf("%lf %lf %lf", &x, &r, &h);
        
        // 円錐全体の体積.
        double tVol = r * r * PI * h / 3.0;
        
        // 円錐を輪切りにして体積を保存.
        repx(j, (int)x, 20202){
            if(j > (int)(x + h)){
                cone[j][i] = tVol;
            }else{
                double cr = r * (double)(x + h - j) / h; // 半径.
                cone[j][i] = tVol * (1.0 - (cr * cr * cr) / (r * r * r));
            }
        }
    }
    
    // 3. 累積和を計算.
    rep(i, N) rep(j, 20202) cones[j] += cone[j][i];
    
    // 4. クエリに回答.
    rep(i, Q){
        int A, B;
        scanf("%d %d", &A, &B);
        printf("%.6lf\n", cones[B] - cones[A]);
    }
    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--)

const double PI = acos(-1.0);

double cone[20202][111], cones[20202];

int main(){

// 1. 入力情報.

int N, Q;

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

// 2. 円錐の体積を集計.

rep(i, N){

double x, r, h;

scanf("%lf %lf %lf", &x, &r, &h);

// 円錐全体の体積.

double tVol = r * r * PI * h / 3.0;

// 円錐を輪切りにして体積を保存.

repx(j, (int)x, 20202){

if(j > (int)(x + h)){

cone[j][i] = tVol;

}else{

double cr = r * (double)(x + h - j) / h; // 半径.

cone[j][i] = tVol * (1.0 - (cr * cr * cr) / (r * r * r));

}

// 3. 累積和を計算.

rep(i, N) rep(j, 20202) cones[j] += cone[j][i];

// 4. クエリに回答.

rep(i, Q){

int A, B;

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

printf("%.6lf\n", cones[B] - cones[A]);

}

return 0;

}

[入力例]
10 10
3 3 3
2 1 1
5 2 3
1 5 6
2 9 3
4 6 12
11 18 5
4 15 25
0 2 3
1 1 7
0 1
0 2
0 10
3 10
0 100
3 8
1 5
2 9
3 4
6 9

[出力例]
8.843002
80.992182
4173.878112
3865.997282
8512.668894
2882.971997
1227.377293
3629.490541
114.081013
1747.545749
※AtCoderのテストケースより

[入力例]
5 5
5 10 10
4 100 100
3 1000 1000
2 1000 1000
1 1000 1000
0 3
2 1000
4 314
3 217
5 432

[出力例]
9409079.422279
3139502408.531295
2100737789.465234
1613523459.243475
2532621914.444282
※AtCoderのテストケースより

[入力例]

10 10

3 3 3

2 1 1

5 2 3

1 5 6

2 9 3

4 6 12

11 18 5

4 15 25

0 2 3

1 1 7

0 1

0 2

0 10

3 10

0 100

3 8

1 5

2 9

3 4

6 9

[出力例]

8.843002

80.992182

4173.878112

3865.997282

8512.668894

2882.971997

1227.377293

3629.490541

114.081013

1747.545749

※AtCoderのテストケースより

[入力例]

5 5

5 10 10

4 100 100

3 1000 1000

2 1000 1000

1 1000 1000

0 3

2 1000

4 314

3 217

5 432

[出力例]

9409079.422279

3139502408.531295

2100737789.465234

1613523459.243475

2532621914.444282

※AtCoderのテストケースより

■参照サイト
AtCoder Regular Contest 052

2020年10月7日

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

C++の練習を兼ねて, AtCoder Regular Contest 054 の問題A (動く歩道) ～問題B (ムーアの法則) を解いてみた.

■感想.
1. 問題B は久しぶりに指数関数の微分を行ったので, 手こずったものの, 何とかAC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    double L, X, Y, S, D;
    scanf("%lf %lf %lf %lf %lf", &L, &X, &Y, &S, &D);
    
    // 2. 出口に辿り着く時間は？
    // 2-1. 時計回り.
    double d1 = D - S;
    if(d1 < 0.0) d1 += L;
    double t1 = d1 / (X + Y);
    
    // 2-2. 反時計回り.
    // ※ Y > X のみ計算.
    double d2 = S - D;
    if(d2 < 0.0) d2 += L;
    double t2 = 202020202020202020.0;
    if(Y > X) t2 = min(t2, d2 / (Y - X));
    
    // 3. 出力.
    printf("%.10lf\n", min(t1, t2));
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

double L, X, Y, S, D;

scanf("%lf %lf %lf %lf %lf", &L, &X, &Y, &S, &D);

// 2. 出口に辿り着く時間は？

// 2-1. 時計回り.

double d1 = D - S;

if(d1 < 0.0) d1 += L;

double t1 = d1 / (X + Y);

// 2-2. 反時計回り.

// ※ Y > X のみ計算.

double d2 = S - D;

if(d2 < 0.0) d2 += L;

double t2 = 202020202020202020.0;

if(Y > X) t2 = min(t2, d2 / (Y - X));

// 3. 出力.

printf("%.10lf\n", min(t1, t2));

return 0;

}

[入力例]
6 2 3 1 5

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

[入力例]
6 2 10 1 5

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

[入力例]
6 3 1 5 3

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

[入力例]
10 7 7 6 0

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

[入力例]
100 20 25 20 10

[出力例]
2.0000000000

[入力例]

6 2 3 1 5

[出力例]

0.8000000000

※AtCoderのテストケースより

[入力例]

6 2 10 1 5

[出力例]

0.2500000000

※AtCoderのテストケースより

[入力例]

6 3 1 5 3

[出力例]

1.0000000000

※AtCoderのテストケースより

[入力例]

10 7 7 6 0

[出力例]

0.2857142857

※AtCoderのテストケースより

[入力例]

100 20 25 20 10

[出力例]

2.0000000000

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

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

int main(){
    
    // 1. 入力情報.
    double P;
    scanf("%lf", &P);
    
    // 2. 計算が終わるまでの最短の時間は？
    // -> 計算開始が, x年だったとすると, 
    // -> f(x) = x + P / {2 の (x / 1.5)乗}
    // -> f'(x) = 1 - (log2 / 1.5) * P / {2 の (x / 1.5)乗}
    // -> f'(x) = 0 となる x は, x = (1.5 / log2) * log(P * (log2 / 1.5))
    double x = (1.5 / log(2.0)) * log(P / 1.5 * log(2.0));
    bool ok = (P / 1.5 * log(2.0) < 1.0);
    double ans = ok ? P : x + P / pow(2.0, x / 1.5);
    
    // 3. 出力.
    printf("%.10lf\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

double P;

scanf("%lf", &P);

// 2. 計算が終わるまでの最短の時間は？

// -> 計算開始が, x年だったとすると,

// -> f(x) = x + P / {2 の (x / 1.5)乗}

// -> f'(x) = 1 - (log2 / 1.5) * P / {2 の (x / 1.5)乗}

// -> f'(x) = 0 となる x は, x = (1.5 / log2) * log(P * (log2 / 1.5))

double x = (1.5 / log(2.0)) * log(P / 1.5 * log(2.0));

bool ok = (P / 1.5 * log(2.0) < 1.0);

double ans = ok ? P : x + P / pow(2.0, x / 1.5);

// 3. 出力.

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

return 0;

}

[入力例]
3.0000

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

[入力例]
0.0400

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

[入力例]
1000000000000000000.0000

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

[入力例]
1.0397

[出力例]
1.0397000000

[入力例]
1.0398

[出力例]
1.0398000000

[入力例]
2020.1007

[出力例]
16.9637664953

[入力例]

3.0000

[出力例]

2.8708930019

※AtCoderのテストケースより

[入力例]

0.0400

[出力例]

0.0400000000

※AtCoderのテストケースより

[入力例]

1000000000000000000.0000

[出力例]

90.1855078128

※AtCoderのテストケースより

[入力例]

1.0397

[出力例]

1.0397000000

[入力例]

1.0398

[出力例]

1.0398000000

[入力例]

2020.1007

[出力例]

16.9637664953

■参照サイト
AtCoder Regular Contest 054

2020年10月4日

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

C++の練習を兼ねて, AtCoder Regular Contest 053 の問題C (魔法使い高橋君) を解いてみた.

■感想.
1. 方針が見えない部分があったので, 解説を参照したところ, AC版に到達できた.
2. sort対象が, a – b の正負に応じて, 切り替わる点が, 非常に不思議な感じがして面白く感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/053/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<LL, LL, LL>;
#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 main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vector<T3> vPos, vNeg;
    rep(i, N){
        LL a, b, c;
        scanf("%lld %lld", &a, &b);
        c = a - b;
        if(c < 0) vNeg.emplace_back(a, b, c);
        else      vPos.emplace_back(a, b, c);
    }
    
    // 2. sort.
    // https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/
    sort(all(vNeg), [](const T3 &a, const T3 &b){
        return get<0>(a) < get<0>(b);
    });
    // for(auto &p : vNeg) printf("a=%lld b=%lld c=%lld\n", get<0>(p), get<1>(p), get<2>(p));
    
    // 3. sort.
    // https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/
    sort(all(vPos), [](const T3 &a, const T3 &b){
        // return get<0>(a) > get<0>(b);
        // ロジック修正: 解説にある通り, b[i] を 降順sortするのが正しいとのこと.
        return get<1>(a) > get<1>(b);
    });
    // for(auto &p : vPos) printf("a=%lld b=%lld c=%lld\n", get<0>(p), get<1>(p), get<2>(p));
    
    // 4. 気温の最大値 X を 計算.
    LL ans = -202020202020202020, X = 0;
    for(auto &p : vNeg){
        X += get<0>(p);
        ans = max(ans, X);
        X -= get<1>(p);
    }
    for(auto &p : vPos){
        X += get<0>(p);
        ans = max(ans, X);
        X -= get<1>(p);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/data/arc/053/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using T3 = tuple<LL, LL, LL>;

#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 main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vector<T3> vPos, vNeg;

rep(i, N){

LL a, b, c;

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

c = a - b;

if(c < 0) vNeg.emplace_back(a, b, c);

else vPos.emplace_back(a, b, c);

}

// 2. sort.

// https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/

sort(all(vNeg), [](const T3 &a, const T3 &b){

return get<0>(a) < get<0>(b);

});

// for(auto &p : vNeg) printf("a=%lld b=%lld c=%lld\n", get<0>(p), get<1>(p), get<2>(p));

// 3. sort.

// https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/

sort(all(vPos), [](const T3 &a, const T3 &b){

// return get<0>(a) > get<0>(b);

// ロジック修正: 解説にある通り, b[i] を降順sortするのが正しいとのこと.

return get<1>(a) > get<1>(b);

});

// for(auto &p : vPos) printf("a=%lld b=%lld c=%lld\n", get<0>(p), get<1>(p), get<2>(p));

// 4. 気温の最大値 X を計算.

LL ans = -202020202020202020, X = 0;

for(auto &p : vNeg){

X += get<0>(p);

ans = max(ans, X);

X -= get<1>(p);

}

for(auto &p : vPos){

X += get<0>(p);

ans = max(ans, X);

X -= get<1>(p);

}

// 5. 出力.

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

return 0;

}

[入力例]
1
10 20

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

[入力例]
2
30 20
10 20

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

[入力例]
5
5 10
10 5
10 15
15 10
20 20

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

[入力例]
30
2584211 79319034
105682679 99008547
68923866 64072311
39878833 55875856
22572957 97659203
74863460 24009217
77342946 112684425
14569588 113202108
69907472 67983910
17973818 46844364
66203426 106604582
52903263 57134512
76502220 38251023
15216113 68464096
81635075 6610403
1713679 44027673
36711629 105648520
45643081 36038269
1552992 97196163
9193532 48890284
73582182 101788895
45479724 59781571
33041379 89752152
69425663 15899300
71234115 14814156
113313584 109246472
13384228 7504136
94026442 83782407
22447954 37623640
17225387 38244889

[出力例]
1552992

[入力例]
50
160737 49748
42120 17095
145272 175669
153418 50326
126005 1654
145687 27952
119759 137408
191582 159810
36503 22055
20355 61699
123365 125865
89014 198800
21813 145531
44036 52132
82786 36771
110913 170470
122156 52045
18645 45641
152861 130410
84812 8416
194509 147692
64731 157011
48181 3142
104403 29766
29213 57918
21680 118313
168747 12149
92425 23006
44400 122727
23350 28895
128981 81384
27103 134077
145262 96753
8340 102961
133400 65416
152296 33888
83930 55995
28090 141822
62781 16863
51095 201406
163808 15904
15413 47524
159988 159048
157146 173681
162013 31737
117703 166679
191059 54743
81178 165991
76343 81148
51474 128303

[出力例]
457096

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

[入力例]

10 20

[出力例]

※AtCoderのテストケースより

[入力例]

30 20

10 20

[出力例]

※AtCoderのテストケースより

[入力例]

5 10

10 5

10 15

15 10

20 20

[出力例]

※AtCoderのテストケースより

[入力例]

2584211 79319034

105682679 99008547

68923866 64072311

39878833 55875856

22572957 97659203

74863460 24009217

77342946 112684425

14569588 113202108

69907472 67983910

17973818 46844364

66203426 106604582

52903263 57134512

76502220 38251023

15216113 68464096

81635075 6610403

1713679 44027673

36711629 105648520

45643081 36038269

1552992 97196163

9193532 48890284

73582182 101788895

45479724 59781571

33041379 89752152

69425663 15899300

71234115 14814156

113313584 109246472

13384228 7504136

94026442 83782407

22447954 37623640

17225387 38244889

[出力例]

1552992

[入力例]

160737 49748

42120 17095

145272 175669

153418 50326

126005 1654

145687 27952

119759 137408

191582 159810

36503 22055

20355 61699

123365 125865

89014 198800

21813 145531

44036 52132

82786 36771

110913 170470

122156 52045

18645 45641

152861 130410

84812 8416

194509 147692

64731 157011

48181 3142

104403 29766

29213 57918

21680 118313

168747 12149

92425 23006

44400 122727

23350 28895

128981 81384

27103 134077

145262 96753

8340 102961

133400 65416

152296 33888

83930 55995

28090 141822

62781 16863

51095 201406

163808 15904

15413 47524

159988 159048

157146 173681

162013 31737

117703 166679

191059 54743

81178 165991

76343 81148

51474 128303

[出力例]

457096

■参照サイト
AtCoder Regular Contest 053

2020年10月4日

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

C++の練習を兼ねて, AtCoder Regular Contest 104 の問題B (DNA Sequence) を解いてみた.

■感想.
1. 累積和を使えることに気付けたので, AC版に到達できたと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトB – DNA Sequence 解説をご覧下さい.

■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 DNA[5050][4]; // i文字目までの(A, T, C, G の)出現数

int main(){
    
    // 1. 入力情報.
    int N;
    char S[5050];
    scanf("%d %s", &N, S);
    
    // 2. 各文字の出現数をカウント.
    rep(i, N){
        rep(j, 4) DNA[i + 1][j] = DNA[i][j];
        if(S[i] == 'A') DNA[i + 1][0]++;
        if(S[i] == 'T') DNA[i + 1][1]++;
        if(S[i] == 'C') DNA[i + 1][2]++;
        if(S[i] == 'G') DNA[i + 1][3]++;
    }
    
    // 3. 区間[l, r] について, 出現数をチェック.
    int ans = 0;
    rep(l, N){
        repx(r, l + 1, N){
            // 以下の二条件を満たすものをカウント.
            // A の 出現数 と T の 出現数 が 等しい.
            // C の 出現数 と G の 出現数 が 等しい.
            bool ok = (DNA[r + 1][0] - DNA[l][0] == DNA[r + 1][1] - DNA[l][1]);
            ok &= (DNA[r + 1][2] - DNA[l][2] == DNA[r + 1][3] - DNA[l][3]);
            if(ok) ans++;
        }
    }
    
    // 4. 出力.
    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 DNA[5050][4]; // i文字目までの(A, T, C, G の)出現数

int main(){

// 1. 入力情報.

int N;

char S[5050];

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

// 2. 各文字の出現数をカウント.

rep(i, N){

rep(j, 4) DNA[i + 1][j] = DNA[i][j];

if(S[i] == 'A') DNA[i + 1][0]++;

if(S[i] == 'T') DNA[i + 1][1]++;

if(S[i] == 'C') DNA[i + 1][2]++;

if(S[i] == 'G') DNA[i + 1][3]++;

}

// 3. 区間[l, r] について, 出現数をチェック.

int ans = 0;

rep(l, N){

repx(r, l + 1, N){

// 以下の二条件を満たすものをカウント.

// A の出現数と T の出現数が等しい.

// C の出現数と G の出現数が等しい.

bool ok = (DNA[r + 1][0] - DNA[l][0] == DNA[r + 1][1] - DNA[l][1]);

ok &= (DNA[r + 1][2] - DNA[l][2] == DNA[r + 1][3] - DNA[l][3]);

if(ok) ans++;

}

// 4. 出力.

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

return 0;

}

[入力例]
4 AGCT

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

[入力例]
4 ATAT

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

[入力例]
10 AAATACCGCG

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

[入力例]
100 ACGCCTCTACGGTCAGGCGAGAGGCTCAATCTGTGGGTTGATCGTATACTACGTGCAATAGTGTCCGGACCTCATTTTCCGACCGCTATGCTAATCTTCA

[出力例]
131

[入力例]
1000 GCCACCTCCCGCTCTTTATGCCGAGCGGGCGCTGGCTGTAGCCGATTTTGTTCACGTGAATGTAACCTACATGCGATGTTAGAGGTGTTTATAGCGAGTCCACTCATCGGTCGGATTGGCGGGGTACCTTAGGAGCGCACGAGGCAAGTATCCATCATTGGGACCCCCCCTTTGGCTTGAAAAGTATAGCGCATATGTTCTAGTAACGTGTCTTGTTTGTTTCTGACTGGTCTTAGGTAGCCACGGTCTCATGTAAATAAGCTGCTAACAGCCTTTCTGTTTGATACCCGCTCGGAGGCCGGTTAGTCCGCTTGACCTAAGGACTCAGCGCCTGGGCAGAATCTGAGCGCTCCGCGCATACCGGACATAAAATATTAGGCTAATGTATGTCATGTTGTAAGATGTAATGCCATCCAAAATAGTCTAGGCCGTCGCAGGTGTTAGAAATTCAACCGAGGTAGACGATACCCCGGGGGTCCGGCTATTTGATAAAGAAATGCGGAACACGTCGTCGAAAGCCATGCGTAGTCCACCTGAGCTTTTTAGACCCCGACCCTATAATATGTGACTCTTCGCGTAATCCAAAGGATACTGCCCCTTACCATTCATGAGTTGCTTGGGAGTGCTAGTCAGCCTGATAGTCTGGAACGCTAGTTTATAAGCGGCGAGCTGATCGTCGAAAAACGTCCACTGAGATACATTTTTACTTTATAGGATCTCGGAATGCCTCATTTCTTTTCGTTGGCGTGGCTCACGATGGAAGTCAAAAGTTGGATTACAGCCGCTATCCTCGGTCCCAGATCTGCATGGGGCTTTCACGTCGTGGTACAGTAGGCGACTTCGCGCAGGCTCACTTGAGAGGGGTATCTTGATAATAGCTCCCTGTTATGTCTCCTGATTGGAAGATCGACAATCTTGATAATATTCGACCCAACATATTCGATTGCTATCAGACCCTATAAATCTGCATGATTTTCGGCCTCTATTTGCTACCTTAGTC

[出力例]
1756

[入力例]
5000 TAGTAATCTACAGCACCTTTCGCGATACCGACCAGGCTCCGGTCGTAAGATCGGCCAAAGTCCTTCTAATGACGGGACTACTATACGGCTTACTATGAAATTAGTATACCGCTGGAGCATTGAACAAGCGTTCGGGGTATTTATCTAGGAGATGCGTGGTCAGTGCTGCTGGGCGGGGGCGGTGGAGAGGAGGTGGTATTACGCATTTTCCCCGCGGAACTAGGACTGATACTGGGGCGTACACAGGTAGGAAACTGGCTTCTAGTCGACTAGGGCAACGAATTTGATTTGCGGCTAGCTTAGGGCTCACGACCCTTGGACTTCCGCAGATGCACCATCTCAACGGTAATGCTTCACGGCAATAGCCACCCTGCCAGCTCGATAATTGGTTCGTCGCGGATCCTAGCATGATCTGCCTCGCCATCCCTACCTACTCCGTCAACCTCATTGTTAGCCAGGCTCGAAAGCTTGTGAGGGCAAAGCTAACCGTCCGGGAAATGACGCACTGGCATAGCCCCCGCTTCTTAATTAGCGACCTGTATCGACATGACTTCGATTTAGACTTGACTGACTATCACAAACACCTGCCCTCACATTTGAAACGTGCCCTAGTCGATGGCTGGGTTCTGCATGACCAGCCTAGATCTTAGGGACTGACGTTGCAGCCATCGCACATATTCACGGCACACAACATTCAAGACAAAGTACGCAGACCAGTTACGGAGCGGCGCTGTCAGCCTGCCCCGAGGGCACCTTTAGGGCCTCGCTTCAACTTTGAGAATATCGGCCTATGGACAGTAATGTTCGAGCTTCTGTACGATAATCTCAGCTTCGGTACACCGCGCCTTCACAGACACCAAAGCCACTGAAAAATTGGACGCTCGTAAGATGTCCGTTCCTTGGATCCGCTTTACCCTCATTTTACTAGTACGATCTTCAATGTCGACGTTCTCATTGCAGCGGAGATAACTATTAGTGCATGCAATGTTTTGCGACTGAGGTGCGTTGTGTAGTACTCTCAGGGCGGAGTAAATCTCCGGAAAGAGTCCAAGTGACTGATCTCCAAAGGTAAATGAGTCACAGCGCAACATATGGTGTCTCGCGGAACCTGTGAGACCTATCCAGCTCGCCCGGCGAAGGTAACACCACCATACTACGGTCCCAGATGAGAACCATCAGCGGACTAGGCGGGGCAGAACGGCGAGGCTCTCTAGACAGCATTGACCATACCGCTAATGCGTAGATGCCAACCGAAGAACGATGATAATCGACTTGTAAGACGATGGACCGGGGGTCACGATAATCCCAGCTCGTGACTAATGTAGTAAATGAGGAATGATCAGCCGCCTGTCCAGCATGTAGGACTGATTTGGCTTGGGCGACGAACGTATCCGACGGTGCGCCTCTTGGAACCTGTCATGTCTAATGGAATCTCACCTGTTTTTGGGTAGAGGCAGCACCACTTGTGTTCTCCTTCTAGGTGGTGAGGAGCGGTGTATCTGTAAGCATATGTTTCTAGTCGGCGCTTCACTATACTAGTAGAGTCAAGGGTGAGAGTTGTGAAAGCTCATCAAAGTGCTCCCCTCGTCCCAACTTCTACTGCGCAAATGGCCGGGAAGGGGATTTATCTAATGAACCTGCCTGGAATGGAAAATTGCTCTGCAGGCAAGTGCCGAATCGTTTTACCGAATTCAACGCCGGTCCTCGCAGCTGACTAGGTATATTCGCCACGGGTGGTAGACGACTTGAGCGGCTATCATGCCTAGTGTCCATTAGTCTTTCCGTCTCGTATGGTCACACACTAGCAGCTTTTCCGGTCTCTAAAATCAAGAGTCATACAATCTCCGCAGTCAGTGCTAGATTGTTACGCAAGCTCACTCCGTATTCGATCGGAGTAGTCTGCACACGGGTCAGGGAATCGGACATCGGTAAATAACAAAGGAGTACGACGCGGAGCGGTTTCGTGAATTGGTGGGTGTATCGCAGTTGAAGTATCGCCCTGGAGCTTGTACTCGGCCTAAGACAGTAAGTGTTAGAAGCAAAAGAACTAGCTGCGACTAAAATCCAAATTGTGTCAAGTACCCTGGCTTTCCGTACAACAGAGCCTTATGCGGGACACTAGAAAGCGCAGGGCGACCTCGACGATGTCATTGCGTCTAAAGTACGCAATACAACCACGTTACGTTAACTTGTCGGAAGCACCGTAGCCCGGTATCCGCCCCTGTGTGTCATACTTACACTATGCGGAGACACGACGGTTGCGCGCGCAGGCATGCGCCCTTAGCCTATGAACCTAAAATATGAGAGTTTGGTCCCGCTGAGCTGCCCAAGTGCGGCCCGCTCCCTTACCACACGTATGACATGTAAGAGTTTGCGTCGTGCCTGCCTCTTTGTTCACAGTCACTATGATAATCGCCTGCCGGCATGCTACGCCCAACACTAACTCCGTGCAGCGGTGATTTTCTTTTTTGTAGCCTTGAGATACGCCAAGGCGCGTCCAGCCGGGGTCGCTATGTTAGCCTGTTGCACCGAGATGTTCACCACTAGTCGTGTCCAAGAGCAGTGCAGCCTGGATACAGTCACAGAGGTTTTCTCGTGTACCGCATGAAGCCCCTGACAAGGGTCAGTGGTCGCGAGCTCTGAGCGCAGTCACGCAGTTTGATACATTATCTTGATTTTCCGTTAGTGCGGGTAGGGAGATGACAACATGCGTAAAGCTGTTTCCTTTATGGACGTTTTTGCAGGCAATTTTCACGGGACAGCGTGAGTGGCAGCGTAGATCGAGTTCAGATCGGCTTAATATAAGGACCAATCCACCCAGTAAAACGCGTGCATTTTAGAGTTAGCTTCGCATTGCGTCTCCATACGCTGGCGATACTTAGACGCGGACTAAGTCTGCAGTGATCAGGCTTTAGAGGGAGAACCGTAGACATGCGGAAGACTCTGGCATACCCATTTGCGTACATCTGCGATATAGGGGAGCTGTCTATACCGGAACATCGTGTGCTGTTAGTCATTGCATATTTGATAGCCGACTATAAGCGGAGACGGCTAGCTCTTAGCAACAGCCGCTTTTAGCCCGCGGCCTTCCAGATTCGTTACATGAACGTTGCACTCGCGAATCTCTTTTCGGTATCGGGGGGCCGGGCATGAGGCTTGGTTAACCCTTTAATCGGGCCTAACTGGCGCTATTTGTCCTGGTCTCTGTGTTATTTCCATGCTAGGACTCCACCCCGCTGCCCAGGTGACGCCTCCAGTCTCACAAAAGATCCATTGGTATGCGCTATCGGCAGCTGATTGTATAAACTCATACGTCGAACGATCCAATACCTAACTGTAACGAGCCCCAAAGAACGTGTGGTATGATTCACGGCCTGACTACATTGGTCTGCGCAAAATCCGAAAGAGAGAAACCACTTAGCAGCGAGGGCAGCTGGGGTGGGTGTCCGTGCTTGGGATCCATGTTTGAACACCGTTGGGATGCGGCTGCGTGTTACCTTCCGTCATTGAGTTGTTGTGCTTTCGCTTTCGGAGGCGCAACGAACATTCCGGGTGCAAGAGGGCGGCTCCCTGGATACTCGCCCCGTACGACGCGTGCAGAGGCGTGCGAGAGACACTGGCTGATCGCCTGTGGAGCCGCTAGGCGGCCCCTGGTGACTGTCTGCACCGCAGATGCCGCCAGCCGCTCGTTTACGAACTCGATCTTACAGGTAAGATATGGCCTTTGTTGTCTTTTAAAATTCTCCGGCGCGACCTAACTGCTCTACCTTGACTAATGGGTACGTGCGAATCCGTTTGAGTAGTCCTCACGGCTGGTTCGTTGGGCAGTAAGACGAGCAGAGCGTTGCCTACGAATTAGGTCAATACCCTACGAAGGAGATCGCATGCTGGCCTGGGTGCGCCCCGAGCCGCGCTCCACGCATGAAGGATCAGACCGCATTTCTGTTGATAAAGAAATTGCAACGACAAGCGGTAGCTGCCACTCTTCTTATTTCGGCACATATTTGAACACTGTGAGTACGAGGCATACCTATCCGACGAATGGTCCGCTCAGCTCTCCCCACGGAGGGTTCCAGGTGCCTACAACTGATGACAGAACCAATATTACCCCATCTTGGTAAACTACGGTACAAGCGACGCGCTTGGAACTACGCCCTACTAACAGCACATATCACGCCAGTGAGTAGGGATATTGCTGGCCCGGGAATATAAGATTGCTAATCCTGTATGGCTTCATAAGCGGTTAGCCCGTGCGGCCAGAATAAGCTGAATTATAAGACGAGCGTGGCGCATCTTGGAGTTGAAAAAGTTATCATCCGACGAATAGGGGTAGCTCGTAGTTTACCTTAATACGAAGGAATAGATCCAAGTAACGCTTTCGTATTATTTGGCTTTATATTAGAGACCTCAGAGTATCGTACCAGAGGCCGGAGGGCCTTGCCTCTATGGACTCAGACGAGGTACGTACCGGAGTGCCACCTTACGCATATGTTATCACGCGTCGCGTGATGTTCTCGTCTAGACAATTGTAGCGTAGATTGTGGCCTCCGTAACCGGCCGGCACACGAGGGCCCAATAGCTAGGTACCAAAGACTCATGACGGTATCTCTGAATCTAACGGTAACGAAAGATGTCGACCAAAACATCCGCCATTTTATGACTAGGATTATTCGATGACCGTGTTCGCCTGTAACAACTACGTTCTAAAATGTGGTTTCGTGGGAGGTGAGTGACATTGACGGTGAAAAAGACGGGCTCCCTCTCTCTGTCACCCCGGTAAATAATCAAATACGTAGAAGGTCATTGAGATCTTTTTCCAGAGAACCAAAATGATTGTGCCTGATTCCAGCTATAACACGCGCGCAGGTAAGTCATAACCCATCATCCGCCGTGCGCAAATACCCTACCTGCGAGCATTCCAGAGGGCTAACTCTTCTTGGTAGTTATACCTACCGAGCGTAGTGATGTATCAGTCGTCAGCCCTTTTTCGAACGCGACAC

[出力例]
10120

[入力例]

4 AGCT

[出力例]

※AtCoderのテストケースより

[入力例]

4 ATAT

[出力例]

※AtCoderのテストケースより

[入力例]

10 AAATACCGCG

[出力例]

※AtCoderのテストケースより

[入力例]

100 ACGCCTCTACGGTCAGGCGAGAGGCTCAATCTGTGGGTTGATCGTATACTACGTGCAATAGTGTCCGGACCTCATTTTCCGACCGCTATGCTAATCTTCA

[出力例]

131

[入力例]

1000 GCCACCTCCCGCTCTTTATGCCGAGCGGGCGCTGGCTGTAGCCGATTTTGTTCACGTGAATGTAACCTACATGCGATGTTAGAGGTGTTTATAGCGAGTCCACTCATCGGTCGGATTGGCGGGGTACCTTAGGAGCGCACGAGGCAAGTATCCATCATTGGGACCCCCCCTTTGGCTTGAAAAGTATAGCGCATATGTTCTAGTAACGTGTCTTGTTTGTTTCTGACTGGTCTTAGGTAGCCACGGTCTCATGTAAATAAGCTGCTAACAGCCTTTCTGTTTGATACCCGCTCGGAGGCCGGTTAGTCCGCTTGACCTAAGGACTCAGCGCCTGGGCAGAATCTGAGCGCTCCGCGCATACCGGACATAAAATATTAGGCTAATGTATGTCATGTTGTAAGATGTAATGCCATCCAAAATAGTCTAGGCCGTCGCAGGTGTTAGAAATTCAACCGAGGTAGACGATACCCCGGGGGTCCGGCTATTTGATAAAGAAATGCGGAACACGTCGTCGAAAGCCATGCGTAGTCCACCTGAGCTTTTTAGACCCCGACCCTATAATATGTGACTCTTCGCGTAATCCAAAGGATACTGCCCCTTACCATTCATGAGTTGCTTGGGAGTGCTAGTCAGCCTGATAGTCTGGAACGCTAGTTTATAAGCGGCGAGCTGATCGTCGAAAAACGTCCACTGAGATACATTTTTACTTTATAGGATCTCGGAATGCCTCATTTCTTTTCGTTGGCGTGGCTCACGATGGAAGTCAAAAGTTGGATTACAGCCGCTATCCTCGGTCCCAGATCTGCATGGGGCTTTCACGTCGTGGTACAGTAGGCGACTTCGCGCAGGCTCACTTGAGAGGGGTATCTTGATAATAGCTCCCTGTTATGTCTCCTGATTGGAAGATCGACAATCTTGATAATATTCGACCCAACATATTCGATTGCTATCAGACCCTATAAATCTGCATGATTTTCGGCCTCTATTTGCTACCTTAGTC

[出力例]

1756

[入力例]

5000 TAGTAATCTACAGCACCTTTCGCGATACCGACCAGGCTCCGGTCGTAAGATCGGCCAAAGTCCTTCTAATGACGGGACTACTATACGGCTTACTATGAAATTAGTATACCGCTGGAGCATTGAACAAGCGTTCGGGGTATTTATCTAGGAGATGCGTGGTCAGTGCTGCTGGGCGGGGGCGGTGGAGAGGAGGTGGTATTACGCATTTTCCCCGCGGAACTAGGACTGATACTGGGGCGTACACAGGTAGGAAACTGGCTTCTAGTCGACTAGGGCAACGAATTTGATTTGCGGCTAGCTTAGGGCTCACGACCCTTGGACTTCCGCAGATGCACCATCTCAACGGTAATGCTTCACGGCAATAGCCACCCTGCCAGCTCGATAATTGGTTCGTCGCGGATCCTAGCATGATCTGCCTCGCCATCCCTACCTACTCCGTCAACCTCATTGTTAGCCAGGCTCGAAAGCTTGTGAGGGCAAAGCTAACCGTCCGGGAAATGACGCACTGGCATAGCCCCCGCTTCTTAATTAGCGACCTGTATCGACATGACTTCGATTTAGACTTGACTGACTATCACAAACACCTGCCCTCACATTTGAAACGTGCCCTAGTCGATGGCTGGGTTCTGCATGACCAGCCTAGATCTTAGGGACTGACGTTGCAGCCATCGCACATATTCACGGCACACAACATTCAAGACAAAGTACGCAGACCAGTTACGGAGCGGCGCTGTCAGCCTGCCCCGAGGGCACCTTTAGGGCCTCGCTTCAACTTTGAGAATATCGGCCTATGGACAGTAATGTTCGAGCTTCTGTACGATAATCTCAGCTTCGGTACACCGCGCCTTCACAGACACCAAAGCCACTGAAAAATTGGACGCTCGTAAGATGTCCGTTCCTTGGATCCGCTTTACCCTCATTTTACTAGTACGATCTTCAATGTCGACGTTCTCATTGCAGCGGAGATAACTATTAGTGCATGCAATGTTTTGCGACTGAGGTGCGTTGTGTAGTACTCTCAGGGCGGAGTAAATCTCCGGAAAGAGTCCAAGTGACTGATCTCCAAAGGTAAATGAGTCACAGCGCAACATATGGTGTCTCGCGGAACCTGTGAGACCTATCCAGCTCGCCCGGCGAAGGTAACACCACCATACTACGGTCCCAGATGAGAACCATCAGCGGACTAGGCGGGGCAGAACGGCGAGGCTCTCTAGACAGCATTGACCATACCGCTAATGCGTAGATGCCAACCGAAGAACGATGATAATCGACTTGTAAGACGATGGACCGGGGGTCACGATAATCCCAGCTCGTGACTAATGTAGTAAATGAGGAATGATCAGCCGCCTGTCCAGCATGTAGGACTGATTTGGCTTGGGCGACGAACGTATCCGACGGTGCGCCTCTTGGAACCTGTCATGTCTAATGGAATCTCACCTGTTTTTGGGTAGAGGCAGCACCACTTGTGTTCTCCTTCTAGGTGGTGAGGAGCGGTGTATCTGTAAGCATATGTTTCTAGTCGGCGCTTCACTATACTAGTAGAGTCAAGGGTGAGAGTTGTGAAAGCTCATCAAAGTGCTCCCCTCGTCCCAACTTCTACTGCGCAAATGGCCGGGAAGGGGATTTATCTAATGAACCTGCCTGGAATGGAAAATTGCTCTGCAGGCAAGTGCCGAATCGTTTTACCGAATTCAACGCCGGTCCTCGCAGCTGACTAGGTATATTCGCCACGGGTGGTAGACGACTTGAGCGGCTATCATGCCTAGTGTCCATTAGTCTTTCCGTCTCGTATGGTCACACACTAGCAGCTTTTCCGGTCTCTAAAATCAAGAGTCATACAATCTCCGCAGTCAGTGCTAGATTGTTACGCAAGCTCACTCCGTATTCGATCGGAGTAGTCTGCACACGGGTCAGGGAATCGGACATCGGTAAATAACAAAGGAGTACGACGCGGAGCGGTTTCGTGAATTGGTGGGTGTATCGCAGTTGAAGTATCGCCCTGGAGCTTGTACTCGGCCTAAGACAGTAAGTGTTAGAAGCAAAAGAACTAGCTGCGACTAAAATCCAAATTGTGTCAAGTACCCTGGCTTTCCGTACAACAGAGCCTTATGCGGGACACTAGAAAGCGCAGGGCGACCTCGACGATGTCATTGCGTCTAAAGTACGCAATACAACCACGTTACGTTAACTTGTCGGAAGCACCGTAGCCCGGTATCCGCCCCTGTGTGTCATACTTACACTATGCGGAGACACGACGGTTGCGCGCGCAGGCATGCGCCCTTAGCCTATGAACCTAAAATATGAGAGTTTGGTCCCGCTGAGCTGCCCAAGTGCGGCCCGCTCCCTTACCACACGTATGACATGTAAGAGTTTGCGTCGTGCCTGCCTCTTTGTTCACAGTCACTATGATAATCGCCTGCCGGCATGCTACGCCCAACACTAACTCCGTGCAGCGGTGATTTTCTTTTTTGTAGCCTTGAGATACGCCAAGGCGCGTCCAGCCGGGGTCGCTATGTTAGCCTGTTGCACCGAGATGTTCACCACTAGTCGTGTCCAAGAGCAGTGCAGCCTGGATACAGTCACAGAGGTTTTCTCGTGTACCGCATGAAGCCCCTGACAAGGGTCAGTGGTCGCGAGCTCTGAGCGCAGTCACGCAGTTTGATACATTATCTTGATTTTCCGTTAGTGCGGGTAGGGAGATGACAACATGCGTAAAGCTGTTTCCTTTATGGACGTTTTTGCAGGCAATTTTCACGGGACAGCGTGAGTGGCAGCGTAGATCGAGTTCAGATCGGCTTAATATAAGGACCAATCCACCCAGTAAAACGCGTGCATTTTAGAGTTAGCTTCGCATTGCGTCTCCATACGCTGGCGATACTTAGACGCGGACTAAGTCTGCAGTGATCAGGCTTTAGAGGGAGAACCGTAGACATGCGGAAGACTCTGGCATACCCATTTGCGTACATCTGCGATATAGGGGAGCTGTCTATACCGGAACATCGTGTGCTGTTAGTCATTGCATATTTGATAGCCGACTATAAGCGGAGACGGCTAGCTCTTAGCAACAGCCGCTTTTAGCCCGCGGCCTTCCAGATTCGTTACATGAACGTTGCACTCGCGAATCTCTTTTCGGTATCGGGGGGCCGGGCATGAGGCTTGGTTAACCCTTTAATCGGGCCTAACTGGCGCTATTTGTCCTGGTCTCTGTGTTATTTCCATGCTAGGACTCCACCCCGCTGCCCAGGTGACGCCTCCAGTCTCACAAAAGATCCATTGGTATGCGCTATCGGCAGCTGATTGTATAAACTCATACGTCGAACGATCCAATACCTAACTGTAACGAGCCCCAAAGAACGTGTGGTATGATTCACGGCCTGACTACATTGGTCTGCGCAAAATCCGAAAGAGAGAAACCACTTAGCAGCGAGGGCAGCTGGGGTGGGTGTCCGTGCTTGGGATCCATGTTTGAACACCGTTGGGATGCGGCTGCGTGTTACCTTCCGTCATTGAGTTGTTGTGCTTTCGCTTTCGGAGGCGCAACGAACATTCCGGGTGCAAGAGGGCGGCTCCCTGGATACTCGCCCCGTACGACGCGTGCAGAGGCGTGCGAGAGACACTGGCTGATCGCCTGTGGAGCCGCTAGGCGGCCCCTGGTGACTGTCTGCACCGCAGATGCCGCCAGCCGCTCGTTTACGAACTCGATCTTACAGGTAAGATATGGCCTTTGTTGTCTTTTAAAATTCTCCGGCGCGACCTAACTGCTCTACCTTGACTAATGGGTACGTGCGAATCCGTTTGAGTAGTCCTCACGGCTGGTTCGTTGGGCAGTAAGACGAGCAGAGCGTTGCCTACGAATTAGGTCAATACCCTACGAAGGAGATCGCATGCTGGCCTGGGTGCGCCCCGAGCCGCGCTCCACGCATGAAGGATCAGACCGCATTTCTGTTGATAAAGAAATTGCAACGACAAGCGGTAGCTGCCACTCTTCTTATTTCGGCACATATTTGAACACTGTGAGTACGAGGCATACCTATCCGACGAATGGTCCGCTCAGCTCTCCCCACGGAGGGTTCCAGGTGCCTACAACTGATGACAGAACCAATATTACCCCATCTTGGTAAACTACGGTACAAGCGACGCGCTTGGAACTACGCCCTACTAACAGCACATATCACGCCAGTGAGTAGGGATATTGCTGGCCCGGGAATATAAGATTGCTAATCCTGTATGGCTTCATAAGCGGTTAGCCCGTGCGGCCAGAATAAGCTGAATTATAAGACGAGCGTGGCGCATCTTGGAGTTGAAAAAGTTATCATCCGACGAATAGGGGTAGCTCGTAGTTTACCTTAATACGAAGGAATAGATCCAAGTAACGCTTTCGTATTATTTGGCTTTATATTAGAGACCTCAGAGTATCGTACCAGAGGCCGGAGGGCCTTGCCTCTATGGACTCAGACGAGGTACGTACCGGAGTGCCACCTTACGCATATGTTATCACGCGTCGCGTGATGTTCTCGTCTAGACAATTGTAGCGTAGATTGTGGCCTCCGTAACCGGCCGGCACACGAGGGCCCAATAGCTAGGTACCAAAGACTCATGACGGTATCTCTGAATCTAACGGTAACGAAAGATGTCGACCAAAACATCCGCCATTTTATGACTAGGATTATTCGATGACCGTGTTCGCCTGTAACAACTACGTTCTAAAATGTGGTTTCGTGGGAGGTGAGTGACATTGACGGTGAAAAAGACGGGCTCCCTCTCTCTGTCACCCCGGTAAATAATCAAATACGTAGAAGGTCATTGAGATCTTTTTCCAGAGAACCAAAATGATTGTGCCTGATTCCAGCTATAACACGCGCGCAGGTAAGTCATAACCCATCATCCGCCGTGCGCAAATACCCTACCTGCGAGCATTCCAGAGGGCTAACTCTTCTTGGTAGTTATACCTACCGAGCGTAGTGATGTATCAGTCGTCAGCCCTTTTTCGAACGCGACAC

[出力例]

10120

■参照サイト
AtCoder Regular Contest 104

2020年9月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 079 の問題E (E – Decrease (Judge ver.)) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参照して実装して, AC版に到達できた.
2. 個人的には, 一定のルールを繰り返すことで計算可能であることについて, 非常に面白く感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc079/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[55];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 操作回数をカウント.
    LL ans = 0;
    function<void()> f = [&](){
        // 終了条件.
        bool ok = true;
        rep(i, N){
            if(a[i] >= N){
                ok = false;
                break;
            }
        }
        if(ok) return;
        
        // 今回の操作回数を計算.
        LL cur = 0;
        rep(i, N) cur += a[i] / (LL)N;
        
        // 数列の各要素を更新.
        rep(i, N){
            LL b = a[i] / (LL)N;
            a[i] -= b * (LL)N;
            a[i] += cur - b;
        }
        
        // 今回の操作回数を加算.
        ans += cur;
        
        // 次回の操作.
        f();
    };
    f();
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/arc079/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[55];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 操作回数をカウント.

LL ans = 0;

function<void()> f = [&](){

// 終了条件.

bool ok = true;

rep(i, N){

if(a[i] >= N){

ok = false;

break;

}

if(ok) return;

// 今回の操作回数を計算.

LL cur = 0;

rep(i, N) cur += a[i] / (LL)N;

// 数列の各要素を更新.

rep(i, N){

LL b = a[i] / (LL)N;

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

a[i] += cur - b;

}

// 今回の操作回数を加算.

ans += cur;

// 次回の操作.

f();

};

f();

// 3. 出力.

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

return 0;

}

[入力例]
4
3 3 3 3

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

[入力例]
3
1 0 3

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

[入力例]
2
2 2

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

[入力例]
7
27 0 0 0 0 0 0

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

[入力例]
10
1000 193 256 777 0 1 1192 1234567891011 48 425

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

[入力例]
18
314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]
9345

[入力例]

3 3 3 3

[出力例]

※AtCoderのテストケースより

[入力例]

1 0 3

[出力例]

※AtCoderのテストケースより

[入力例]

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

27 0 0 0 0 0 0

[出力例]

※AtCoderのテストケースより

[入力例]

1000 193 256 777 0 1 1192 1234567891011 48 425

[出力例]

1234567894848

※AtCoderのテストケースより

[入力例]

314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]

9345

■参照サイト
AtCoder Regular Contest 079

2020年9月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 076 の問題E (Connected?) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参照して実装して, AC版に到達できた.
2. 個人的には, 不思議なアルゴリズム(※長方形の周上以外の整数を考慮しなくて良い)に見えて, 非常に面白く感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int R, C, N;
    scanf("%d %d %d", &R, &C, &N);
    priority_queue<P, vector<P>, greater<P>> lPQ, uPQ;
    priority_queue<P> rPQ, dPQ;
    rep(i, N){
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        bool b1 = (x1 > 0 && x1 < R && y1 > 0 && y1 < C);
        bool b2 = (x2 > 0 && x2 < R && y2 > 0 && y2 < C);
        if(b1 || b2) continue;
        int n = i + 1;
        if(x1 == 0 && y1 > 0) lPQ.push({y1, n}); // 左辺.
        if(y1 == C && x1 > 0) uPQ.push({x1, n}); // 上辺.
        if(x1 == R && y1 < C) rPQ.push({y1, n}); // 右辺.
        if(y1 == 0 && x1 < R) dPQ.push({x1, n}); // 下辺.
        if(x2 == 0 && y2 > 0) lPQ.push({y2, n}); // 左辺.
        if(y2 == C && x2 > 0) uPQ.push({x2, n}); // 上辺.
        if(x2 == R && y2 < C) rPQ.push({y2, n}); // 右辺.
        if(y2 == 0 && x2 < R) dPQ.push({x2, n}); // 下辺.
    }
    
    // 2. 長方形(4辺)を, 時計回りに見ていく.
    // 2-1. 左辺.
    stack<int> st;
    while(!lPQ.empty()){
        P p = lPQ.top();
        lPQ.pop();
        if(!st.empty()){
            // 前回出現した整数と同じ場合は, stackの要素を減らす.
            if(st.top() == p.b) st.pop();
            else                st.push(p.b);
        }else{
            st.push(p.b);
        }
    }
    
    // 2-2. 上辺.
    while(!uPQ.empty()){
        P p = uPQ.top();
        uPQ.pop();
        if(!st.empty()){
            // 前回出現した整数と同じ場合は, stackの要素を減らす.
            if(st.top() == p.b) st.pop();
            else                st.push(p.b);
        }else{
            st.push(p.b);
        }
    }
    
    // 2-3. 右辺.
    while(!rPQ.empty()){
        P p = rPQ.top();
        rPQ.pop();
        if(!st.empty()){
            // 前回出現した整数と同じ場合は, stackの要素を減らす.
            if(st.top() == p.b) st.pop();
            else                st.push(p.b);
        }else{
            st.push(p.b);
        }
    }
    
    // 2-4. 下辺.
    while(!dPQ.empty()){
        P p = dPQ.top();
        dPQ.pop();
        if(!st.empty()){
            // 前回出現した整数と同じ場合は, stackの要素を減らす.
            if(st.top() == p.b) st.pop();
            else                st.push(p.b);
        }else{
            st.push(p.b);
        }
    }
    
    // 3. 出力.
    bool ok = (st.size() == 0);
    printf("%s\n", ok ? "YES" : "NO");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int R, C, N;

scanf("%d %d %d", &R, &C, &N);

priority_queue<P, vector<P>, greater<P>> lPQ, uPQ;

priority_queue<P> rPQ, dPQ;

rep(i, N){

int x1, y1, x2, y2;

scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

bool b1 = (x1 > 0 && x1 < R && y1 > 0 && y1 < C);

bool b2 = (x2 > 0 && x2 < R && y2 > 0 && y2 < C);

if(b1 || b2) continue;

int n = i + 1;

if(x1 == 0 && y1 > 0) lPQ.push({y1, n}); // 左辺.

if(y1 == C && x1 > 0) uPQ.push({x1, n}); // 上辺.

if(x1 == R && y1 < C) rPQ.push({y1, n}); // 右辺.

if(y1 == 0 && x1 < R) dPQ.push({x1, n}); // 下辺.

if(x2 == 0 && y2 > 0) lPQ.push({y2, n}); // 左辺.

if(y2 == C && x2 > 0) uPQ.push({x2, n}); // 上辺.

if(x2 == R && y2 < C) rPQ.push({y2, n}); // 右辺.

if(y2 == 0 && x2 < R) dPQ.push({x2, n}); // 下辺.

}

// 2. 長方形(4辺)を, 時計回りに見ていく.

// 2-1. 左辺.

stack<int> st;

while(!lPQ.empty()){

P p = lPQ.top();

lPQ.pop();

if(!st.empty()){

// 前回出現した整数と同じ場合は, stackの要素を減らす.

if(st.top() == p.b) st.pop();

else st.push(p.b);

}else{

st.push(p.b);

}

// 2-2. 上辺.

while(!uPQ.empty()){

P p = uPQ.top();

uPQ.pop();

if(!st.empty()){

// 前回出現した整数と同じ場合は, stackの要素を減らす.

if(st.top() == p.b) st.pop();

else st.push(p.b);

}else{

st.push(p.b);

}

// 2-3. 右辺.

while(!rPQ.empty()){

P p = rPQ.top();

rPQ.pop();

if(!st.empty()){

// 前回出現した整数と同じ場合は, stackの要素を減らす.

if(st.top() == p.b) st.pop();

else st.push(p.b);

}else{

st.push(p.b);

}

// 2-4. 下辺.

while(!dPQ.empty()){

P p = dPQ.top();

dPQ.pop();

if(!st.empty()){

// 前回出現した整数と同じ場合は, stackの要素を減らす.

if(st.top() == p.b) st.pop();

else st.push(p.b);

}else{

st.push(p.b);

}

// 3. 出力.

bool ok = (st.size() == 0);

printf("%s\n", ok ? "YES" : "NO");

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
YES

[入力例]

4 2 3

0 1 3 1

1 1 4 1

2 0 2 2

[出力例]

YES

※AtCoderのテストケースより

[入力例]

2 2 4

0 0 2 2

2 0 0 1

0 2 1 2

1 1 2 1

[出力例]

※AtCoderのテストケースより

[入力例]

5 5 7

0 0 2 4

2 3 4 5

3 5 5 2

5 5 5 4

0 3 5 1

2 2 4 4

0 5 4 1

[出力例]

YES

※AtCoderのテストケースより

[入力例]

1 1 2

0 0 1 1

1 0 0 1

[出力例]

※AtCoderのテストケースより

[入力例]

11 15 7

11 5 11 12

7 0 5 0

3 4 7 8

1 0 3 0

5 8 9 10

0 5 0 13

3 15 7 15

[出力例]

YES

■参照サイト
AtCoder Regular Contest 076

2020年9月20日

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

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

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参照して実装して, AC版に到達できた.
※ 余談として, 問題D は, 全く理解が追い付かず, 解説の実装(方針)を, ほぼ丸暗記することにして, 深入りしない(汗).
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト
AtCoder Beginner Contest 179 (E – Sequence Sum 解説)
をご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc179/editorial/115
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
LL a[101010]; // 数列を保存.

int main(){
    
    // 1. 入力情報.
    LL N, X, M;
    scanf("%lld %lld %lld", &N, &X, &M);
    
    // 2. 数列を計算(繰り返しを確認するまで).
    set<LL> s;
    LL cur = X;
    int idx = 0;
    rep(i, 101010){
        // 繰り返しかを判定.
        if(!s.count(cur)){
            a[i] = cur;
            s.insert(cur);
            idx = i;
        }else{
            break;
        }
        
        // 次項計算.
        cur *= cur;
        cur %= M;
    }
    
    // 3. 数列を分割.
    LL bSum = 0, cSum = 0; // 合計.
    vector<LL> b; // 繰り返し始まるまで.
    vector<LL> c; // 繰り返し部分.
    bool f = false; // 繰り返し部分開始フラグ.
    rep(i, idx + 1){
        if(cur == a[i]) f = true;
        if(f) c.pb(a[i]), cSum += a[i];
        else  b.pb(a[i]), bSum += a[i];
    }
    
    // 4. N項目までの和を計算.
    LL ans = 0, bl = (LL)b.size(), cl = (LL)c.size();
    if(N <= bl + cl){
        rep(i, (int)N) ans += a[i];
    }else{
        LL q = (N - bl) / cl, r = (N - bl) % cl;
        ans += bSum;
        ans += cSum * q;
        rep(i, (int)r) ans += c[i];
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc179/editorial/115

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

LL a[101010]; // 数列を保存.

int main(){

// 1. 入力情報.

LL N, X, M;

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

// 2. 数列を計算(繰り返しを確認するまで).

set<LL> s;

LL cur = X;

int idx = 0;

rep(i, 101010){

// 繰り返しかを判定.

if(!s.count(cur)){

a[i] = cur;

s.insert(cur);

idx = i;

}else{

break;

}

// 次項計算.

cur *= cur;

cur %= M;

}

// 3. 数列を分割.

LL bSum = 0, cSum = 0; // 合計.

vector<LL> b; // 繰り返し始まるまで.

vector<LL> c; // 繰り返し部分.

bool f = false; // 繰り返し部分開始フラグ.

rep(i, idx + 1){

if(cur == a[i]) f = true;

if(f) c.pb(a[i]), cSum += a[i];

else b.pb(a[i]), bSum += a[i];

}

// 4. N項目までの和を計算.

LL ans = 0, bl = (LL)b.size(), cl = (LL)c.size();

if(N <= bl + cl){

rep(i, (int)N) ans += a[i];

}else{

LL q = (N - bl) / cl, r = (N - bl) % cl;

ans += bSum;

ans += cSum * q;

rep(i, (int)r) ans += c[i];

}

// 5. 出力.

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

return 0;

}

[入力例]
6 2 1001

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

[入力例]
1000 2 16

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

[入力例]
10000000000 10 99959

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

[入力例]
10 1 7

[出力例]
10

[入力例]
3 2 1024

[出力例]
22

[入力例]
2020202020 3030 5050

[出力例]
3030

[入力例]
2020202020 3030 50505

[出力例]
56808080744550

[入力例]
3141592653 5897 93238

[出力例]
140770895521631

[入力例]

6 2 1001

[出力例]

1369

※AtCoderテストケースより

[入力例]

1000 2 16

[出力例]

※AtCoderテストケースより

[入力例]

10000000000 10 99959

[出力例]

492443256176507

※AtCoderテストケースより

[入力例]

10 1 7

[出力例]

[入力例]

3 2 1024

[出力例]

[入力例]

2020202020 3030 5050

[出力例]

3030

[入力例]

2020202020 3030 50505

[出力例]

56808080744550

[入力例]

3141592653 5897 93238

[出力例]

140770895521631

■参照サイト
AtCoder Beginner Contest 179

C++の練習を兼ねて, AtCoder Beginner Contest 052 の 問題C (Factors of Factorial) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 067 の 問題C (Splitting Pile) ～ 問題D (Fennec VS. Snuke) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 029 の 問題A (高橋君とお肉) ～ 問題B (高橋君と禁断の書) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 052 の 問題A (何期生？) ～ 問題B (円錐) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 054 の 問題A (動く歩道) ～ 問題B (ムーアの法則) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 053 の 問題C (魔法使い高橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 104 の 問題B (DNA Sequence) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 079 の 問題E (E – Decrease (Judge ver.)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 076 の 問題E (Connected?) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 052 の問題C (Factors of Factorial) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 067 の問題C (Splitting Pile) ～問題D (Fennec VS. Snuke) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 029 の問題A (高橋君とお肉) ～問題B (高橋君と禁断の書) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 052 の問題A (何期生？) ～問題B (円錐) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 054 の問題A (動く歩道) ～問題B (ムーアの法則) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 053 の問題C (魔法使い高橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 104 の問題B (DNA Sequence) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 079 の問題E (E – Decrease (Judge ver.)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 076 の問題E (Connected?) を解いてみた.

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