4月, 2020 | 個人用メモ帳

2020年4月21日

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

C++の練習を兼ねて, AtCoder Regular Contest 023 の問題C (C – タコヤ木) を解いてみた.

■感想.
1. 組み合わせの復習が出来たので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■C++版プログラム(問題C／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 = 2020;
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版).
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    LL ret = 1, i = 0;
    while(i < k){
        ret *= (n - i);
        ret %= MOD;
        ret *= INV[i + 1];
        ret %= MOD;
        i++;
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    repx(i, 1, LIMIT) INV[i] = mPow((LL)i, MOD - 2);
    
    // 2. 記録のパターンをカウント.
    LL bef = 0, cur, one = 0, ans = 1;
    rep(i, N){
        scanf("%lld", &cur);
        
        // -1 の 個数 を カウント.
        if(cur == -1) one++;
        
        // -1 でない.
        if(cur != -1){
            if(bef != 0){
                // 右方向: one個, 上方向: (cur - bef)個 から 進路選択するイメージ.
                ans *= combination(cur - bef + one, one);
                ans %= MOD;
            }
            // 初期化.
            one = 0;
            bef = cur;
        }
    }
    
    // 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 = 2020;

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版).

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

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

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

LL combination(LL n, LL k){

LL ret = 1, i = 0;

while(i < k){

ret *= (n - i);

ret %= MOD;

ret *= INV[i + 1];

ret %= MOD;

i++;

}

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

repx(i, 1, LIMIT) INV[i] = mPow((LL)i, MOD - 2);

// 2. 記録のパターンをカウント.

LL bef = 0, cur, one = 0, ans = 1;

rep(i, N){

scanf("%lld", &cur);

// -1 の個数をカウント.

if(cur == -1) one++;

// -1 でない.

if(cur != -1){

if(bef != 0){

// 右方向: one個, 上方向: (cur - bef)個から進路選択するイメージ.

ans *= combination(cur - bef + one, one);

ans %= MOD;

}

// 初期化.

one = 0;

bef = cur;

}

// 3. 出力.

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

return 0;

}

[入力例]
3
1 -1 3

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

[入力例]
6
2 -1 -1 9 -1 9

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

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

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

[入力例]
15
1 -1 -1 -1 -1 7 -1 -1 10 -1 -1 13 -1 15 16

[出力例]
63000

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

[出力例]
5040

[入力例]
27
1 -1 10 -1 -1 2020 -1 -1 -1 -1 303030 -1 -1 -1 -1 -1 -1 40404040 -1 -1 -1 -1 -1 -1 -1 -1 50505050

[出力例]
297905265

[入力例]

1 -1 3

[出力例]

※AtCoderのテストケースより

[入力例]

2 -1 -1 9 -1 9

[出力例]

※AtCoderのテストケースより

[入力例]

1 -1 -1 -1 1000000000

[出力例]

999999972

※AtCoderのテストケースより

[入力例]

1 -1 -1 -1 -1 7 -1 -1 10 -1 -1 13 -1 15 16

[出力例]

63000

[入力例]

1 -1 2 -1 -1 3 -1 -1 -1 4 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 7

[出力例]

5040

[入力例]

1 -1 10 -1 -1 2020 -1 -1 -1 -1 303030 -1 -1 -1 -1 -1 -1 40404040 -1 -1 -1 -1 -1 -1 -1 -1 50505050

[出力例]

297905265

■参照サイト
AtCoder Regular Contest 023

2020年4月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 163 の問題D (D – Sum of Large Numbers) を解いてみた.

■感想.
1. 1グーゴルが巨大な数なので, もともと無かったものとして計算したが, AC版となったので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 0 ～ N から, K個以上選択した場合の最小値, 最大値 を 見ていく.
    LL ans = 0;
    repx(k, K, N + 2){
        LL minS = (LL)(k - 1) * (LL)k / 2 % MOD;
        LL maxS = (LL)(2 * N - k + 1) * (LL)k / 2 % MOD;
        LL dx = (MOD + maxS - minS + 1) % MOD;
        ans += dx;
        ans %= MOD;
        // printf("minS=%lld maxS=%lld\n", minS, maxS);
    }
    
    // 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;

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 0 ～ N から, K個以上選択した場合の最小値, 最大値を見ていく.

LL ans = 0;

repx(k, K, N + 2){

LL minS = (LL)(k - 1) * (LL)k / 2 % MOD;

LL maxS = (LL)(2 * N - k + 1) * (LL)k / 2 % MOD;

LL dx = (MOD + maxS - minS + 1) % MOD;

ans += dx;

ans %= MOD;

// printf("minS=%lld maxS=%lld\n", minS, maxS);

}

// 3. 出力.

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

return 0;

}

[入力例]
3 2

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

[入力例]
200000 200001

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

[入力例]
141421 35623

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

[入力例]
223606 173205

[出力例]
913363004

[入力例]

3 2

[出力例]

※AtCoderテストケースより

[入力例]

200000 200001

[出力例]

※AtCoderテストケースより

[入力例]

141421 35623

[出力例]

220280457

※AtCoderテストケースより

[入力例]

223606 173205

[出力例]

913363004

■参照サイト
AtCoder Beginner Contest 163

2020年4月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 022 の問題C (C – ロミオとジュリエット) を解いてみた.

■感想.
1. 木の直径を求める方針で実装したところ, AC版となった.
2. 幅優先探索(BFS) を復習出来たので, 良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define pb push_back
int d0[101010], df[101010]; // 距離を保存

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    bfs(G, 0, d0);
    
    // 3. 頂点 1 から, もっとも遠い頂点 f を, 1つ取得.
    int maxD = 0;
    int f = -1;
    rep(i, N) maxD = max(maxD, d0[i]);
    rep(i, N){
        if(d0[i] == maxD){
            f = i;
            break;
        }
    }
    
    // 4. 頂点 f から, 各頂点までの距離を計算.
    bfs(G, f, df);
    // rep(i, N) printf("%d ", df[i]);
    // puts("");
    
    // 5. 頂点 f から, もっとも遠い頂点 g を, 1つ取得.
    maxD = 0;
    int g = -1;
    rep(i, N) maxD = max(maxD, df[i]);
    rep(i, N){
        if(df[i] == maxD){
            g = i;
            break;
        }
    }
    
    // 6. 出力.
    assert(f != -1 && g != -1);
    printf("%d %d\n", f + 1, g + 1);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<int>>;

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

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

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

#define pb push_back

int d0[101010], df[101010]; // 距離を保存

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

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

// ※bfsの動作確認用.

// @param G: グラフ.

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

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

// @return: 特に無し.

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

// 1. 空のキュー.

queue<int> q;

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

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

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(d[e] > 0) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

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

bfs(G, 0, d0);

// 3. 頂点 1 から, もっとも遠い頂点 f を, 1つ取得.

int maxD = 0;

int f = -1;

rep(i, N) maxD = max(maxD, d0[i]);

rep(i, N){

if(d0[i] == maxD){

f = i;

break;

}

// 4. 頂点 f から, 各頂点までの距離を計算.

bfs(G, f, df);

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

// puts("");

// 5. 頂点 f から, もっとも遠い頂点 g を, 1つ取得.

maxD = 0;

int g = -1;

rep(i, N) maxD = max(maxD, df[i]);

rep(i, N){

if(df[i] == maxD){

g = i;

break;

}

// 6. 出力.

assert(f != -1 && g != -1);

printf("%d %d\n", f + 1, g + 1);

return 0;

}

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

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

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

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

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

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

[出力例]
19 13

[入力例]

7 6

3 2

2 4

4 5

8 9

1 8

1 6

1 2

9 10

[出力例]

5 10

※AtCoderのテストケースより

[入力例]

1 2

1 3

1 4

[出力例]

4 3

※AtCoderのテストケースより

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

2 3

[入力例]

13 7

7 4

4 2

6 2

11 6

18 10

10 3

19 15

15 10

20 17

17 5

12 5

5 3

3 2

14 8

8 2

16 9

9 1

2 1

[出力例]

19 13

■参照サイト
AtCoder Regular Contest 022

2020年4月18日

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

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

■感想.
1. 方針が全く見えなかったので, 解説を参考に実装したところ, AC版となった.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 記述をスリム化して, 再提出.
// 解き直し.
// https://img.atcoder.jp/abc162/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], dp[4][101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 解説通り(dp更新).
    dp[1][1] = a[0];
    dp[2][1] = max(a[0], a[1]);
    if(N >= 3){
        dp[3][1] = max({a[0], a[1], a[2]});
        dp[3][2] = a[0] + a[2];
    }
    repx(i, 4, N + 1){
        // i に ついて, s個以上, e個以下 を 選択.
        int s = i / 2 - 1, e = (i + 1) / 2;
        int c = (i % 3 == 0) ? 3 : (i % 3); // 現在.
        int o = (c - 1 == 0) ? 3 : c - 1;   // 一つ前.
        int t = (o - 1 == 0) ? 3 : o - 1;   // 二つ前.
        dp[c][s]     = max(dp[t][s - 1] + a[i - 1], dp[o][s]);
        dp[c][s + 1] = max(dp[t][s] + a[i - 1],     dp[o][s + 1]);
        if(s + 2 == e) dp[c][s + 2] = dp[t][s + 1] + a[i - 1];
    }
    // rep(i, 4){
    //     rep(j, N + 1) printf("%lld ", dp[i][j]);
    //     puts("");
    // }
    
    // 3. 出力.
    int index = (N % 3 == 0) ? 3 : (N % 3);
    printf("%lld\n", dp[index][N / 2]);
    return 0;
    
}

// 記述をスリム化して, 再提出.

// 解き直し.

// https://img.atcoder.jp/abc162/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], dp[4][101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 解説通り(dp更新).

dp[1][1] = a[0];

dp[2][1] = max(a[0], a[1]);

if(N >= 3){

dp[3][1] = max({a[0], a[1], a[2]});

dp[3][2] = a[0] + a[2];

}

repx(i, 4, N + 1){

// i について, s個以上, e個以下を選択.

int s = i / 2 - 1, e = (i + 1) / 2;

int c = (i % 3 == 0) ? 3 : (i % 3); // 現在.

int o = (c - 1 == 0) ? 3 : c - 1; // 一つ前.

int t = (o - 1 == 0) ? 3 : o - 1; // 二つ前.

dp[c][s] = max(dp[t][s - 1] + a[i - 1], dp[o][s]);

dp[c][s + 1] = max(dp[t][s] + a[i - 1], dp[o][s + 1]);

if(s + 2 == e) dp[c][s + 2] = dp[t][s + 1] + a[i - 1];

}

// rep(i, 4){

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

// puts("");

// }

// 3. 出力.

int index = (N % 3 == 0) ? 3 : (N % 3);

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

return 0;

}

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

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

[入力例]
5
-1000 -100 -10 0 10

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

[入力例]
10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

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

[入力例]
27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

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

[入力例]
100
47240 -39363 -15701 -23939 -45577 3929 -41290 -35889 -9506 -19878 -18735 30932 10740 2739 -25649 37201 11434 -41930 7599 45871 -21658 -30611 -15826 -13619 19279 8259 1972 687 -9279 29234 20531 19267 -48605 34290 -17852 23276 26173 43725 -34914 -31461 12506 7062 22704 13943 -8100 38020 -1553 -31218 -44575 29367 46361 10310 -8495 -29421 7817 -15540 38805 -5340 45146 37279 -8636 8402 49643 -45836 15237 -8316 -28988 -30021 -6704 -28912 -28618 -38613 10492 -36930 20235 -49077 29657 31555 -47830 -23913 -2961 44153 35312 -42699 49417 20533 40188 -18281 12769 -45193 43552 -33629 47574 42424 34204 14345 -10986 18208 -37707 -628

[出力例]
233115

[入力例]

1 2 3 4 5 6

[出力例]

※AtCoderテストケースより

[入力例]

-1000 -100 -10 0 10

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

[出力例]

5000000000

※AtCoderテストケースより

[入力例]

18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

[出力例]

295

※AtCoderテストケースより

[入力例]

100

47240 -39363 -15701 -23939 -45577 3929 -41290 -35889 -9506 -19878 -18735 30932 10740 2739 -25649 37201 11434 -41930 7599 45871 -21658 -30611 -15826 -13619 19279 8259 1972 687 -9279 29234 20531 19267 -48605 34290 -17852 23276 26173 43725 -34914 -31461 12506 7062 22704 13943 -8100 38020 -1553 -31218 -44575 29367 46361 10310 -8495 -29421 7817 -15540 38805 -5340 45146 37279 -8636 8402 49643 -45836 15237 -8316 -28988 -30021 -6704 -28912 -28618 -38613 10492 -36930 20235 -49077 29657 31555 -47830 -23913 -2961 44153 35312 -42699 49417 20533 40188 -18281 12769 -45193 43552 -33629 47574 42424 34204 14345 -10986 18208 -37707 -628

[出力例]

233115

■参照サイト
AtCoder Beginner Contest 162

2020年4月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 162 の問題E (E – Sum of gcd of Tuples (Hard)) を解いてみた.

■感想.
1. 解答方針が決まるまでに時間かかったが, 何とかAC版となった.
2. 解説を見たところ, 同じ方針だったので, 苦労したものの良かったと思った.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
const int LIMIT = 101010;
LL cMultiple[LIMIT], cDivisor[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;
}

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 倍数の個数を集計.
    repx(i, 1, K + 1) cMultiple[i] = mPow((LL)(K / i), (LL)N);
    // repx(i, 1, K + 1) printf("%lld ", cMultiple[i]);
    // puts("");
    
    // 3. i の 倍数であって, i * 2, i * 3, ..., i * n の 倍数でないものは？
    repr(i, K, 1){
        cDivisor[i] = cMultiple[i];
        repx(j, 2, K + 1){
            int ij = i * j;
            if(ij > K) break;
            cDivisor[i] -= cDivisor[ij];
        }
    }
    // repx(i, 1, K + 1) printf("%lld ", cDivisor[i]);
    // puts("");
    
    // 4. 最大公約数ごとに集計.
    // ex.
    // 3 6
    // -> 267 と 予想.
    // GCD = 1: 181通り.
    // GCD = 2: 222, 224, 242, 244, 422, 424, 442, 
    //               226, 262, 266, 622, 626, 662, 
    //               446, 464, 466, 644, 646, 664, 
    //               246, 264, 426, 462, 624, 642 の 25通り.
    // GCD = 3: 333, 336, 363, 366, 633, 636, 663 の 7通り
    // GCD = 4: 444
    // GCD = 5: 555
    // GCD = 6: 666
    // 1 * 181 + 2 * 25 + 3 * 7 + 4 * 1 + 5 * 1 + 6 * 1 = 267
    LL ans = 0;
    repx(k, 1, K + 1){
        ans += (LL)k * cDivisor[k];
        ans %= MOD;
    }
    
    // 5. 出力.
    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 = 101010;

LL cMultiple[LIMIT], cDivisor[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;

}

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 倍数の個数を集計.

repx(i, 1, K + 1) cMultiple[i] = mPow((LL)(K / i), (LL)N);

// repx(i, 1, K + 1) printf("%lld ", cMultiple[i]);

// puts("");

// 3. i の倍数であって, i * 2, i * 3, ..., i * n の倍数でないものは？

repr(i, K, 1){

cDivisor[i] = cMultiple[i];

repx(j, 2, K + 1){

int ij = i * j;

if(ij > K) break;

cDivisor[i] -= cDivisor[ij];

}

// repx(i, 1, K + 1) printf("%lld ", cDivisor[i]);

// puts("");

// 4. 最大公約数ごとに集計.

// ex.

// 3 6

// -> 267 と予想.

// GCD = 1: 181通り.

// GCD = 2: 222, 224, 242, 244, 422, 424, 442,

// 226, 262, 266, 622, 626, 662,

// 446, 464, 466, 644, 646, 664,

// 246, 264, 426, 462, 624, 642 の 25通り.

// GCD = 3: 333, 336, 363, 366, 633, 636, 663 の 7通り

// GCD = 4: 444

// GCD = 5: 555

// GCD = 6: 666

// 1 * 181 + 2 * 25 + 3 * 7 + 4 * 1 + 5 * 1 + 6 * 1 = 267

LL ans = 0;

repx(k, 1, K + 1){

ans += (LL)k * cDivisor[k];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
3 2

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

[入力例]
3 200

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

[入力例]
100000 100000

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

[入力例]
3 4

[出力例]
76

[入力例]
1 6

[出力例]
21

[入力例]
3 6

[出力例]
267

[入力例]
98765 43210

[出力例]
132859312

[入力例]

3 2

[出力例]

※AtCoderテストケースより

[入力例]

3 200

[出力例]

10813692

※AtCoderテストケースより

[入力例]

100000 100000

[出力例]

742202979

※AtCoderテストケースより

[入力例]

3 4

[出力例]

[入力例]

1 6

[出力例]

[入力例]

3 6

[出力例]

267

[入力例]

98765 43210

[出力例]

132859312

■参照サイト
AtCoder Beginner Contest 162

2020年4月16日

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

C++の練習を兼ねて, AtCoder Regular Contest 023 の問題A (A – 経過日数) ～問題B (B – 謎の人物X) を解いてみた.

■感想.
1. 問題A は, 問題文に指定されている経過日数に関する公式が面白いと感じた.
2. 問題B は, 累積和の復習が出来たので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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. 入力情報.
    int y, m, d;
    scanf("%d %d %d", &y, &m, &d);
    
    // 2. 13月, 14月 を 考慮.
    if(m == 1 || m == 2) y--, m += 12;
    
    // 3. 経過日数を計算.
    int ans = 0;
    ans += 365 * y;
    ans += y / 4;
    ans -= y / 100;
    ans += y / 400;
    ans += 306 * (m + 1) / 10;
    ans += d;
    ans -= 429;
    ans = 735369 - ans;
    
    // 4. 出力.
    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. 入力情報.

int y, m, d;

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

// 2. 13月, 14月を考慮.

if(m == 1 || m == 2) y--, m += 12;

// 3. 経過日数を計算.

int ans = 0;

ans += 365 * y;

ans += y / 4;

ans -= y / 100;

ans += y / 400;

ans += 306 * (m + 1) / 10;

ans += d;

ans -= 429;

ans = 735369 - ans;

// 4. 出力.

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

return 0;

}

[入力例]
1988
7
3

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

[入力例]
1
1
1

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

[入力例]
2014
5
16

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

[入力例]
2012
2
29

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

[入力例]
2011
2
2

[出力例]
1200

[入力例]
2008
11
24

[出力例]
2000

[入力例]

1988

[出力例]

9449

※AtCoderのテストケースより

[入力例]

[出力例]

735369

※AtCoderのテストケースより

[入力例]

2014

[出力例]

※AtCoderのテストケースより

[入力例]

2012

[出力例]

808

※AtCoderのテストケースより

[入力例]

2011

[出力例]

1200

[入力例]

2008

[出力例]

2000

■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--)
int a[1010][1010], aMax[2020], aMaxCum[2020];

int main(){
    
    // 1. 入力情報.
    int R, C, D;
    scanf("%d %d %d", &R, &C, &D);
    rep(i, R) rep(j, C) scanf("%d", &a[i][j]);
    
    // 2. 対角線方向で最大値を保存.
    rep(i, R) rep(j, C) aMax[i + j] = max(aMax[i + j], a[i][j]);
    
    // 3. 偶奇に分けて, i以下の最大値を保存.
    aMaxCum[0] = aMax[0];
    aMaxCum[1] = aMax[1];
    rep(i, 2020) aMaxCum[i + 2] = max(aMaxCum[i], aMax[i + 2]);
    
    // 4. 出力.
    printf("%d\n", aMaxCum[D]);
    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 a[1010][1010], aMax[2020], aMaxCum[2020];

int main(){

// 1. 入力情報.

int R, C, D;

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

rep(i, R) rep(j, C) scanf("%d", &a[i][j]);

// 2. 対角線方向で最大値を保存.

rep(i, R) rep(j, C) aMax[i + j] = max(aMax[i + j], a[i][j]);

// 3. 偶奇に分けて, i以下の最大値を保存.

aMaxCum[0] = aMax[0];

aMaxCum[1] = aMax[1];

rep(i, 2020) aMaxCum[i + 2] = max(aMaxCum[i], aMax[i + 2]);

// 4. 出力.

printf("%d\n", aMaxCum[D]);

return 0;

}

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

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

[入力例]
4 4 100
999 999 999 999
999 999 999 999
999 999 999 999
999 999 999 999

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

[入力例]
3 4 5
700 198 700 198
198 700 198 700
700 198 700 198

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

[入力例]
3 5 7
100 333 400 666 800
111 200 444 700 888
500 222 300 777 900

[出力例]
888

[入力例]
10 16 999
282 1151 195 1143 910 1179 834 1081 48 414 883 235 799 1164 1041 1218
34 621 898 79 1017 1058 679 1057 1229 499 347 262 1203 815 58 1169
1105 1152 548 817 743 636 239 318 601 267 642 205 1041 381 1016 439
1161 913 84 588 1151 1121 1141 513 632 1190 672 355 861 202 929 904
749 102 1032 135 751 1039 513 748 715 199 263 463 809 1187 589 524
1171 626 156 873 1021 317 1099 1122 253 977 1129 615 873 543 804 1011
163 917 353 640 84 1024 637 1054 553 426 711 185 202 127 543 591
987 586 493 157 42 164 758 181 139 152 361 645 245 661 1038 1180
489 884 558 312 661 348 990 147 489 1097 1199 145 618 654 402 718
554 446 1077 1005 326 145 1015 1148 1070 1233 839 1078 992 217 674 478

[出力例]
1229

[入力例]

3 2 1

9 5

3 1

8 9

[出力例]

※AtCoderのテストケースより

[入力例]

4 4 100

999 999 999 999

[出力例]

999

※AtCoderのテストケースより

[入力例]

3 4 5

700 198 700 198

198 700 198 700

700 198 700 198

[出力例]

198

※AtCoderのテストケースより

[入力例]

3 5 7

100 333 400 666 800

111 200 444 700 888

500 222 300 777 900

[出力例]

888

[入力例]

10 16 999

282 1151 195 1143 910 1179 834 1081 48 414 883 235 799 1164 1041 1218

34 621 898 79 1017 1058 679 1057 1229 499 347 262 1203 815 58 1169

1105 1152 548 817 743 636 239 318 601 267 642 205 1041 381 1016 439

1161 913 84 588 1151 1121 1141 513 632 1190 672 355 861 202 929 904

749 102 1032 135 751 1039 513 748 715 199 263 463 809 1187 589 524

1171 626 156 873 1021 317 1099 1122 253 977 1129 615 873 543 804 1011

163 917 353 640 84 1024 637 1054 553 426 711 185 202 127 543 591

987 586 493 157 42 164 758 181 139 152 361 645 245 661 1038 1180

489 884 558 312 661 348 990 147 489 1097 1199 145 618 654 402 718

554 446 1077 1005 326 145 1015 1148 1070 1233 839 1078 992 217 674 478

[出力例]

1229

■参照サイト
AtCoder Regular Contest 023

2020年4月15日2022年9月4日

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

C++の練習を兼ねて, AtCoder Regular Contest 022 の問題A (A – スーパーICT高校生) ～問題B (B – 細長いお菓子) を解いてみた.

■感想.
1. 問題B は, 尺取り法をイメージした実装としたが, 左端の決め方で, 非常に苦労したものの, AC版になり, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    char c[111];
    scanf("%s", c);
    
    // 2. 文字列 "ICT" が 作れるか？
    int l = strlen(c), i = -1, ict = 0;
    while(++i < l){
        if(ict == 0 && (c[i] == 'i' || c[i] == 'I')) ict++;
        if(ict == 1 && (c[i] == 'c' || c[i] == 'C')) ict++;
        if(ict == 2 && (c[i] == 't' || c[i] == 'T')) ict++;
    }
    
    // 3. 出力.
    printf("%s\n", (ict == 3) ? "YES" : "NO");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

char c[111];

scanf("%s", c);

// 2. 文字列 "ICT" が作れるか？

int l = strlen(c), i = -1, ict = 0;

while(++i < l){

if(ict == 0 && (c[i] == 'i' || c[i] == 'I')) ict++;

if(ict == 1 && (c[i] == 'c' || c[i] == 'C')) ict++;

if(ict == 2 && (c[i] == 't' || c[i] == 'T')) ict++;

}

// 3. 出力.

printf("%s\n", (ict == 3) ? "YES" : "NO");

return 0;

}

[入力例]
InformationAndCommunicationTechnology

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

[入力例]
InformationTechnology

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

[入力例]
SinCosTan

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

[入力例]
Ticket

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

[入力例]
InternetTrouble

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

[入力例]
BreadthFirstSearch

[出力例]
NO

[入力例]
TopologicalSort

[出力例]
YES

[入力例]

InformationAndCommunicationTechnology

[出力例]

YES

※AtCoderのテストケースより

[入力例]

InformationTechnology

[出力例]

※AtCoderのテストケースより

[入力例]

SinCosTan

[出力例]

YES

※AtCoderのテストケースより

[入力例]

Ticket

[出力例]

YES

※AtCoderのテストケースより

[入力例]

InternetTrouble

[出力例]

※AtCoderのテストケースより

[入力例]

BreadthFirstSearch

[出力例]

[入力例]

TopologicalSort

[出力例]

YES

■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--)
int a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 同じ味のブロックが2つ以上含まれない, ひと繋がりになった部分を確認(尺取り法っぽい？).
    int ans = 1, l = 0, r = 0;
    map<int, int> m;
    // 2-1. 左端 を 固定.
    while(l < N){
        // 2-2. 左端のブロックを追加.
        m.clear();
        m[a[l]] = l;
        
        // 2-3. r を 更新.
        r = l + 1;
        
        // 2-4. 右端 を 固定.
        while(r < N){
            // 2-5. 同じ味のブロックか存在するかを確認.
            if(m.count(a[r]) > 0) break;
            
            // 2-6. 右端ブロックを追加.
            m[a[r]] = r;
            
            // 2-7. 最大値更新.
            ans = max(ans, (int)m.size());
            
            // 2-8. r を increment.
            // printf("l=%d r=%d m.size()=%d\n", l, r, m.size());
            r++;
        }
        
        // 2-9. 終了条件.
        if(r >= N - 1) break;
        
        // 2-10. l を 更新.
        // a[r] が 重複判定された index プラス 1 を 設定.
        l = m[a[r]] + 1;
    }
    ans = max(ans, (int)m.size());
    
    // 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 a[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 同じ味のブロックが2つ以上含まれない, ひと繋がりになった部分を確認(尺取り法っぽい？).

int ans = 1, l = 0, r = 0;

map<int, int> m;

// 2-1. 左端を固定.

while(l < N){

// 2-2. 左端のブロックを追加.

m.clear();

m[a[l]] = l;

// 2-3. r を更新.

r = l + 1;

// 2-4. 右端を固定.

while(r < N){

// 2-5. 同じ味のブロックか存在するかを確認.

if(m.count(a[r]) > 0) break;

// 2-6. 右端ブロックを追加.

m[a[r]] = r;

// 2-7. 最大値更新.

ans = max(ans, (int)m.size());

// 2-8. r を increment.

// printf("l=%d r=%d m.size()=%d\n", l, r, m.size());

r++;

}

// 2-9. 終了条件.

if(r >= N - 1) break;

// 2-10. l を更新.

// a[r] が重複判定された index プラス 1 を設定.

l = m[a[r]] + 1;

}

ans = max(ans, (int)m.size());

// 3. 出力.

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

return 0;

}

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

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

[入力例]
1
100

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

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

[出力例]
9

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

[出力例]
3

[入力例]
1000
550 734 953 900 452 347 189 680 25 307 277 458 652 314 838 251 427 821 413 232 268 623 465 782 671 121 773 821 955 367 940 907 771 811 512 870 54 607 49 379 593 849 66 947 287 11 73 913 459 808 388 430 810 256 106 771 451 53 218 97 734 835 117 637 762 888 939 41 467 767 815 572 447 332 287 325 103 279 353 796 899 781 572 536 712 376 384 690 482 916 664 361 577 655 482 398 403 975 874 207 654 40 642 388 69 328 890 597 712 118 305 902 699 708 50 471 101 957 418 522 291 427 818 712 809 805 754 99 522 358 753 541 526 858 828 395 936 944 987 831 468 560 918 890 603 520 957 908 604 61 204 802 949 910 519 423 206 794 818 188 12 525 352 517 205 493 15 398 987 391 753 263 836 133 719 967 332 151 917 593 268 448 676 822 445 972 209 119 31 398 542 227 919 937 83 518 866 751 708 267 665 3 660 581 454 287 925 862 572 289 482 63 477 350 39 233 897 228 962 335 884 661 241 274 329 994 901 977 245 538 105 264 870 725 917 600 978 619 945 510 234 495 837 516 53 307 298 62 741 50 254 417 998 492 60 348 97 76 493 618 41 301 516 69 444 784 641 357 897 150 993 417 258 832 902 732 839 24 959 708 172 143 815 50 267 838 72 957 264 58 2 177 143 273 60 920 205 478 937 670 226 791 691 93 233 250 366 233 381 820 604 82 873 430 88 638 331 154 803 819 643 480 980 43 593 963 51 688 484 999 765 531 473 613 388 789 871 466 812 370 712 964 330 706 601 811 139 303 437 286 972 996 714 577 969 347 719 244 8 23 299 89 142 558 905 279 315 869 16 764 190 602 467 17 115 542 729 567 918 399 59 543 272 110 896 819 344 757 286 31 978 50 989 302 577 973 80 678 718 666 127 783 615 810 124 445 646 966 861 852 444 212 506 119 575 945 987 408 109 557 449 302 152 962 219 910 621 986 305 140 793 185 37 171 339 777 973 27 638 779 349 344 401 401 386 402 174 26 629 227 55 801 207 430 528 528 378 368 514 490 257 458 949 62 277 136 450 404 726 809 745 104 911 917 187 546 938 638 332 373 223 331 173 161 142 761 626 515 513 284 946 447 653 921 617 536 922 611 132 728 784 336 229 534 24 355 589 244 189 190 432 938 884 433 895 353 28 122 57 200 522 733 184 336 932 237 651 171 883 440 407 411 724 588 234 459 540 137 894 882 420 125 422 935 570 946 877 505 895 756 199 364 443 788 905 710 293 41 732 314 939 101 662 298 957 97 115 951 853 556 239 364 825 724 834 910 855 685 320 172 454 200 876 279 155 375 208 186 194 594 256 855 826 721 884 452 812 599 461 609 574 687 852 314 469 570 76 563 969 513 431 699 765 334 856 648 580 110 426 992 470 263 801 184 463 193 162 338 870 706 94 844 546 668 518 197 416 971 550 616 355 708 721 854 691 939 74 531 668 537 70 911 5 543 351 18 450 315 552 114 842 557 780 207 270 509 776 198 30 960 339 214 884 799 724 500 197 765 257 886 6 237 820 261 483 250 319 549 192 95 661 973 752 112 625 584 792 95 4 800 739 793 536 635 784 304 338 817 283 836 219 160 323 785 700 818 386 808 910 919 583 520 925 689 850 452 692 935 196 464 762 58 937 798 370 904 628 6 940 961 4 541 297 939 700 814 837 224 287 946 145 398 604 9 569 747 348 913 915 319 372 408 124 211 188 892 919 377 841 339 451 151 582 937 63 95 89 468 669 903 17 44 530 89 259 22 424 20 527 428 547 134 492 80 86 161 626 224 564 614 972 87 835 256 655 141 891 304 861 859 468 650 190 346 851 740 713 975 398 967 376 820 208 271 635 345 864 986 148 243 428 525 982 235 441 861 999 460 834 809 741 742 309 178 220 758 573 820 872 638 882 869 970 857 639 985 879 424 729 689 566 376 398 333 595 75 415 419 654 627 749 533 679 299 24 954 772 564 761 464 378 2 680 330 742 489 480 255 230 801 829 519 21 164 235 699 253 273 968 820 392 989 674 88 625 200 252 804 12 77 976 149 10 750 759 529 732 590 548 259 930 286 329 936 875 90 453 843 543 258 517 482 310 930 50 449 922 87 385 293 396 871 30 403 224 334 955 403 675 833 674 887 534 732 672 262 25 105 818 897 686 895 767 680 570 74 449 842 50 663 873 146 324 222 402 583 449 802 841 7 241 287 807 732 644 950 538 236 803 639 703 126 122 674 155 245 876 621 438 392

[出力例]
85

[入力例]
5000
783 692 655 647 704 737 109 819 326 153 288 974 274 353 595 148 845 144 273 541 572 749 553 630 325 289 857 404 479 499 665 856 53 777 507 205 345 54 123 153 1 257 517 193 92 596 984 778 143 627 321 241 154 509 771 438 128 976 720 1 785 595 614 729 326 586 727 224 222 52 627 724 797 171 825 300 1 77 156 558 66 225 167 241 918 386 826 201 40 869 138 197 144 98 691 405 856 14 691 548 865 628 706 101 71 402 70 667 349 780 781 89 720 675 899 648 911 401 739 301 402 129 687 715 265 703 175 25 717 404 481 791 212 318 715 241 688 500 805 855 692 330 491 490 106 315 493 733 708 424 139 222 826 289 81 679 977 847 926 358 846 161 469 766 718 789 895 419 389 420 932 97 535 871 90 449 312 267 352 839 31 729 322 583 827 777 688 432 6 493 884 568 391 917 147 651 688 109 690 678 151 735 902 776 408 833 775 502 862 977 599 759 202 450 753 758 898 314 584 370 194 227 288 557 431 963 180 182 466 81 875 348 584 950 362 707 59 387 258 573 357 291 367 785 990 349 351 527 54 309 419 943 229 209 585 793 799 160 87 524 380 985 208 176 403 554 306 551 472 515 915 714 457 747 109 498 312 591 193 174 320 975 703 205 808 269 114 334 224 94 350 346 166 466 804 753 686 116 142 564 683 211 667 248 352 677 766 509 162 823 431 617 541 347 298 571 56 640 893 826 665 953 223 231 793 516 2 186 194 353 418 935 660 229 446 625 774 586 894 438 450 301 160 308 753 754 219 352 345 967 523 251 983 890 550 252 58 604 543 903 468 170 975 640 930 587 469 271 621 392 670 725 738 552 155 741 310 83 372 570 499 604 166 661 385 234 339 120 979 428 276 962 726 251 329 897 476 5 630 795 186 712 115 569 85 487 130 834 99 734 269 165 222 304 534 954 233 115 320 649 522 243 434 191 424 472 152 156 2 215 581 632 813 946 266 635 378 481 496 419 72 379 712 107 305 86 240 493 409 179 849 605 649 897 520 999 845 307 796 923 405 40 334 455 28 585 903 982 39 818 599 32 763 472 585 50 814 665 36 279 808 10 222 657 181 642 835 327 3 891 563 787 686 898 54 445 657 515 444 60 236 556 82 226 612 724 182 199 626 383 873 193 155 953 235 431 440 800 375 775 468 59 456 393 805 734 255 169 731 60 462 494 816 198 510 600 442 340 330 525 901 417 106 578 932 423 698 252 880 906 573 727 896 295 94 662 773 110 620 3 760 98 716 617 544 11 837 842 490 979 851 830 512 161 851 832 367 281 433 513 767 726 403 847 128 857 200 495 121 638 720 175 855 832 345 132 295 671 153 957 828 166 204 942 50 413 609 209 71 873 871 833 186 72 405 857 986 399 413 201 304 118 413 254 670 925 644 869 438 582 858 749 689 939 391 153 428 408 722 893 715 522 827 273 198 391 303 677 865 451 31 644 716 585 396 513 350 457 689 307 901 332 141 554 183 135 919 4 393 558 391 865 357 797 244 334 927 615 285 526 305 57 180 594 510 399 810 434 136 992 694 20 34 811 414 49 463 945 687 781 941 919 446 614 270 613 120 162 606 80 400 295 152 196 689 678 445 404 153 819 411 623 91 835 512 162 29 214 538 980 953 931 626 576 102 800 395 194 566 397 263 936 851 191 703 653 626 592 348 845 828 208 5 253 257 642 289 442 362 837 976 465 653 971 821 461 839 474 968 81 642 757 749 92 816 69 223 842 662 423 726 677 647 909 3 787 37 807 48 739 275 934 139 925 495 223 795 916 837 347 533 382 122 48 221 654 389 811 761 462 389 14 937 998 267 912 730 495 792 949 240 184 817 474 399 413 801 190 708 962 385 512 566 501 568 143 682 413 854 549 514 742 662 355 483 239 509 749 970 724 271 16 522 891 140 37 395 144 723 463 139 65 860 377 122 986 741 620 595 907 319 612 950 157 336 738 397 472 43 165 622 816 107 98 558 611 174 931 783 871 677 782 616 6 626 288 444 540 672 752 643 504 26 790 194 151 538 151 165 728 938 791 353 345 20 641 145 50 816 137 629 430 444 392 883 548 732 883 961 642 502 182 635 919 910 824 536 491 314 131 986 333 62 64 597 361 269 169 772 239 500 243 39 497 981 393 167 27 78 270 154 226 477 604 136 66 941 352 279 328 493 474 43 464 571 459 195 892 728 822 469 915 895 874 324 36 533 312 906 838 935 638 692 975 952 928 714 457 31 543 497 648 831 784 507 355 229 173 13 42 851 18 793 734 95 318 238 883 561 157 408 845 680 739 69 458 922 865 848 201 641 386 426 4 108 932 910 71 7 28 929 461 107 848 777 276 528 144 213 630 540 60 136 598 255 442 644 69 206 46 673 257 576 23 897 323 795 526 670 338 178 151 172 869 107 625 884 598 994 351 842 235 753 6 38 707 453 154 615 284 475 792 713 40 275 124 465 642 364 322 872 801 455 21 799 647 336 28 153 465 721 595 230 149 145 284 78 98 78 219 729 157 99 25 565 187 49 638 328 352 166 790 676 860 75 529 442 136 85 255 23 459 817 80 946 797 537 888 56 308 973 236 916 707 687 259 418 796 100 668 192 80 877 561 965 85 534 136 865 471 799 979 341 246 186 167 158 28 119 936 271 83 60 273 284 138 231 757 222 981 283 884 152 260 75 159 737 541 181 765 312 974 843 455 595 190 334 153 809 274 462 775 406 141 966 73 934 142 997 676 264 279 725 98 385 976 989 897 186 229 853 25 238 489 123 360 638 670 313 561 485 178 152 714 253 522 245 759 559 450 790 684 570 155 345 148 327 310 279 275 786 993 182 187 113 526 986 920 764 197 396 444 967 791 532 877 138 235 433 893 540 680 830 931 416 756 600 327 881 419 945 592 238 462 196 522 831 671 678 121 973 378 88 31 424 117 424 371 320 309 345 111 522 367 976 58 556 972 992 719 870 421 243 666 68 536 324 392 39 834 905 323 2 331 866 310 362 360 976 96 31 72 56 491 311 921 371 786 356 685 113 855 34 286 139 425 378 292 994 307 644 150 474 268 907 125 815 454 765 950 443 317 440 132 80 344 919 56 906 834 729 574 169 534 98 979 567 753 822 721 837 835 760 64 238 554 166 524 289 830 11 174 472 321 218 184 807 359 563 848 220 944 561 142 93 19 682 693 111 315 144 503 710 953 374 633 283 493 825 363 91 612 314 948 325 99 334 658 364 739 133 282 674 959 2 628 847 926 392 577 558 181 319 661 84 511 96 446 629 358 928 921 751 92 790 665 998 678 852 192 750 373 101 807 278 225 806 945 694 415 168 967 104 533 803 133 64 624 553 358 182 743 164 322 980 339 731 317 401 634 894 633 730 910 182 513 351 520 439 421 945 298 716 458 626 52 71 219 514 803 881 854 529 828 797 640 164 571 220 321 883 128 949 896 308 551 339 653 555 218 263 122 763 7 15 560 275 862 527 783 105 760 567 593 986 426 596 800 905 734 992 474 486 666 291 800 157 762 14 934 289 730 621 438 930 277 529 99 961 747 38 823 127 962 77 699 975 563 557 176 415 630 160 54 779 227 625 385 901 424 906 665 874 253 375 399 778 152 480 986 530 713 713 30 761 671 328 500 885 607 470 440 85 33 331 785 152 869 444 656 727 272 707 755 866 482 898 636 344 676 201 871 356 759 942 143 644 448 761 653 36 244 457 200 140 775 704 102 241 637 938 695 829 485 649 537 639 679 334 117 946 663 177 566 367 427 536 389 306 311 462 122 369 109 244 482 444 913 651 377 603 819 80 199 888 746 158 187 429 885 691 196 40 209 853 990 290 12 270 581 409 134 291 590 603 285 417 967 826 856 277 247 444 351 209 191 799 547 11 122 467 126 262 395 289 483 99 352 213 18 211 603 570 369 852 479 13 465 194 102 275 604 668 18 209 880 529 687 435 283 749 969 71 811 85 159 554 570 289 770 835 232 990 423 79 237 744 60 268 512 666 620 178 575 732 785 657 450 257 460 451 667 14 696 472 855 967 641 836 152 817 71 202 878 337 449 186 868 146 516 184 347 539 672 41 188 596 562 1 161 764 434 470 102 923 149 145 113 954 298 301 205 285 439 750 901 570 973 400 366 884 702 517 790 127 381 483 349 442 135 263 719 434 771 666 302 894 266 216 302 456 10 237 333 802 957 251 446 975 289 541 403 637 936 420 529 479 665 271 606 732 748 912 730 314 918 828 88 867 770 63 30 93 408 774 313 759 732 870 311 240 57 357 527 250 680 568 612 79 532 18 487 98 32 731 345 827 772 551 929 25 285 997 408 841 278 307 737 481 725 928 948 775 365 919 298 488 643 334 329 942 102 869 564 49 454 890 159 623 749 838 930 914 206 995 66 268 290 745 467 584 955 542 625 778 142 662 330 391 728 373 140 711 184 931 174 821 479 939 354 127 965 314 183 190 413 727 728 85 585 789 450 442 719 439 950 287 872 433 616 421 49 911 941 834 960 606 138 368 185 218 431 510 544 921 282 426 103 520 163 612 948 427 452 198 874 516 412 604 199 103 728 714 39 162 283 778 465 433 7 899 296 208 111 363 786 680 841 40 54 440 790 916 104 530 762 706 609 816 139 759 685 465 776 200 555 437 367 326 733 345 36 740 893 128 374 954 561 27 156 359 315 486 154 44 247 523 131 910 540 688 64 948 39 772 702 695 995 192 292 792 917 117 629 168 522 167 320 95 271 904 78 420 990 687 476 306 820 603 464 816 185 125 380 534 526 975 380 703 766 429 472 302 726 631 310 164 455 226 347 270 996 806 667 363 867 54 591 458 163 274 68 262 864 835 545 429 821 649 303 932 822 967 324 224 712 848 926 50 226 372 850 63 169 327 796 826 396 206 198 188 450 825 746 36 976 869 824 842 261 117 867 955 542 79 584 194 15 63 464 49 668 643 46 592 937 561 507 535 58 541 109 526 653 524 808 673 445 718 394 628 332 652 449 145 702 825 50 508 409 598 669 935 132 563 22 654 664 977 335 226 470 397 73 518 471 408 295 974 650 519 610 355 412 849 869 426 551 581 416 715 821 547 642 29 384 487 565 594 936 435 657 482 385 764 746 473 847 535 674 15 498 547 620 679 911 260 154 452 580 100 946 252 355 20 697 914 341 77 914 84 954 591 771 725 209 816 600 520 829 868 923 871 171 872 892 61 621 886 67 531 885 926 935 298 926 545 489 338 449 105 889 583 4 370 764 62 286 512 266 409 297 791 237 16 238 992 936 702 881 311 796 696 280 763 120 882 605 484 543 727 638 349 945 111 445 48 976 954 940 44 917 459 518 24 97 940 42 811 868 886 774 380 272 396 760 642 691 859 804 173 996 93 705 561 942 645 249 549 595 711 869 223 934 419 337 710 249 602 548 422 964 385 506 427 486 408 865 138 925 148 364 19 2 359 489 782 783 878 946 272 963 25 890 531 849 425 517 791 52 858 733 412 713 730 65 304 488 92 705 41 350 983 404 540 914 944 358 99 33 67 644 19 837 733 292 854 621 834 617 812 494 869 782 658 287 523 326 235 751 532 269 185 689 57 354 396 646 20 336 488 139 170 483 105 921 221 606 761 184 517 412 578 637 997 476 565 153 983 227 633 683 361 911 374 358 408 816 19 949 697 406 656 917 180 783 617 82 389 481 95 873 15 858 641 557 654 849 330 643 160 759 846 810 272 213 605 837 117 805 898 686 226 152 571 297 316 112 361 465 95 523 461 886 32 68 729 994 370 640 733 436 29 900 933 643 204 203 9 489 512 55 168 210 912 731 79 100 853 465 803 702 195 39 526 585 338 270 585 756 893 34 295 695 845 795 284 205 628 865 754 317 408 535 501 873 430 30 11 706 825 591 672 265 194 215 538 914 381 887 286 249 185 924 260 739 452 217 629 345 190 709 532 446 256 102 675 351 937 575 376 23 180 910 244 644 660 979 618 990 673 6 169 548 31 553 809 539 720 178 114 612 942 268 941 704 825 390 940 504 698 531 681 692 431 675 908 354 502 287 981 80 364 455 32 35 40 98 268 544 987 27 745 398 985 615 44 322 596 809 553 941 114 191 763 889 868 797 772 111 683 715 954 483 959 581 217 824 478 530 980 589 420 751 977 722 87 470 860 755 520 732 109 896 298 859 400 947 850 409 991 797 276 951 751 704 413 929 434 474 556 408 263 660 114 391 206 674 574 232 605 144 635 296 930 762 708 496 3 812 637 720 631 822 23 15 898 491 260 735 973 968 201 178 573 975 39 760 559 603 46 712 188 340 900 464 716 984 221 574 881 567 192 539 642 821 5 556 540 21 360 588 4 52 756 162 253 106 514 247 483 105 538 331 375 253 633 673 610 677 356 607 353 899 676 911 341 368 329 512 136 466 942 878 156 343 804 166 859 213 408 459 377 472 716 424 526 113 327 378 155 829 584 707 454 368 316 565 58 268 371 978 17 310 563 838 217 654 456 412 519 999 973 764 942 301 902 613 469 517 529 20 744 964 740 999 896 16 283 646 642 657 560 588 325 514 850 384 490 6 5 453 477 506 686 240 679 525 250 726 7 564 593 443 466 613 381 1 655 608 481 308 88 841 611 450 117 822 580 575 620 500 955 102 461 400 266 390 734 797 804 830 883 711 773 484 608 838 799 171 901 77 411 256 878 925 547 18 964 920 876 527 747 625 929 878 70 850 163 746 919 432 905 523 806 149 604 378 530 594 776 959 735 978 934 91 744 670 70 22 81 113 34 218 891 678 648 523 148 243 642 332 498 660 971 14 53 511 390 83 827 685 402 687 585 349 257 752 784 925 629 994 592 849 262 528 665 735 685 292 45 746 600 910 847 965 521 514 948 23 738 737 329 406 887 789 840 333 554 428 130 763 424 871 61 768 599 413 356 767 943 455 858 955 582 604 398 337 688 681 506 160 388 403 887 777 166 611 147 646 415 141 490 72 694 316 996 830 946 340 170 476 190 218 94 240 315 534 894 437 278 244 827 151 859 336 882 564 504 820 715 874 894 935 831 618 747 980 541 642 925 610 990 892 680 801 632 984 460 55 696 875 277 743 299 395 514 508 133 8 952 484 755 85 659 114 496 741 782 665 77 373 433 258 603 1 306 572 11 460 611 253 771 705 383 927 978 746 340 367 24 919 610 964 974 947 498 413 143 230 989 85 798 192 940 169 635 961 602 27 848 251 399 943 422 323 483 223 917 754 984 620 235 34 401 762 419 208 882 177 652 571 340 280 556 201 94 935 772 268 242 297 998 857 204 441 933 267 357 549 293 239 560 209 360 557 572 868 734 502 173 35 783 747 407 491 523 660 623 236 244 101 154 954 253 815 13 33 35 800 228 609 747 41 979 227 381 775 299 276 569 377 964 621 696 698 102 901 990 686 905 2 509 755 27 334 308 147 643 225 287 573 770 989 734 753 476 273 590 44 397 740 418 522 537 714 983 414 568 618 516 405 551 772 870 359 400 679 299 51 197 706 859 903 917 855 679 945 67 73 915 912 344 189 211 542 764 453 733 426 285 368 739 630 522 685 797 420 552 378 717 601 753 239 525 777 748 731 479 707 788 159 954 367 716 588 469 470 79 35 800 772 363 123 500 973 644 416 397 922 802 996 99 349 137 886 847 989 766 409 285 177 57 327 994 549 796 624 693 58 738 527 962 840 702 491 277 640 406 450 647 548 616 455 605 496 530 766 694 741 112 67 567 258 646 915 391 226 748 698 574 629 181 651 346 489 77 294 382 176 678 56 880 173 667 723 52 750 650 318 456 674 100 637 600 133 427 883 762 668 579 246 61 994 880 161 141 610 26 133 530 229 196 984 634 865 662 606 671 362 498 175 810 256 808 865 459 722 560 456 22 126 385 859 704 756 722 779 794 593 49 197 764 841 819 964 872 662 86 111 899 916 883 665 68 65 692 680 357 697 359 17 892 317 946 513 896 998 724 160 642 337 541 463 202 863 525 861 376 500 778 811 895 404 980 664 957 783 676 362 35 647 178 249 84 910 912 256 837 923 455 52 938 417 95 646 682 316 558 953 602 295 592 533 497 244 831 1 487 811 685 850 633 598 313 390 90 760 177 905 718 569 848 287 114 113 82 811 623 159 715 222 744 267 328 508 37 238 394 627 593 816 816 879 695 128 581 471 325 402 985 20 630 642 688 123 959 355 624 786 241 811 202 214 756 122 814 186 638 32 791 66 458 814 75 141 452 95 649 767 899 23 963 16 866 149 123 395 208 111 384 683 729 689 575 194 37 107 186 709 378 110 864 889 144 869 54 450 192 854 601 301 459 430 554 251 689 159 823 387 194 262 703 111 614 308 429 902 763 180 131 125 119 182 469 33 513 205 688 28 403 539 28 356 312 948 578 425 891 383 321 556 675 66 894 354 913 701 762 385 157 778 99 763 649 407 113 863 613 469 143 450 34 523 960 482 701 407 994 905 408 650 338 551 999 373 272 326 152 29 912 935 787 881 326 153 197 507 765 224 453 740 135 290 667 482 249 581 703 814 514 507 992 946 963 72 427 261 295 425 988 346 210 916 644 266 572 923 740 319 264 264 34 711 735 82 471 554 216 136 388 837 305 276 605 440 465 985 49 582 649 505 771 425 560 337 85 739 261 595 218 761 304 623 885 844 944 917 549 792 876 506 725 420 832 466 836 922 485 482 575 516 52 4 739 538 222 777 228 137 17 838 341 153 832 249 644 125 64 477 261 588 573 454 1 64 285 976 854 386 324 333 282 758 996 15 200 853 631 483 3 293 508 391 358 879 39 484 815 393 411 197 572 652 202 970 623 471 507 288 7 842 481 488 112 80 269 280 543 959 67 195 745 113 481 464 988 391 990 300 131 854 512 176 787 893 922 645 264 386 664 429 994 239 880 30 946 521 196 957 903 903 94 195 511 702 933 614 20 561 796 120 480 873 990 256 308 382 5 45 637 907 496 137 209 798 95 168 394 159 218 258 540 840 325 238 383 124 322 290 431 873 424 685 793 533 212 702 39 960 323 543 306 239 342 128 688 428 869 842 56 713 629 182 950 49 972 473 887 391 314 825 577 198 292 837 268 306 975 785 468 4 569 286 43 133 372 125 346 573 311 603 179 98 286 743 689 490 663 683 107 640 858 801 289 639 290 44 883 768 392 665 975 516 396 306 227 999 533 801 836 759 124 731 906 214 608 91 829 498 519 724 539 617 358 202 825 729 498 444 414 880 991 177 495 828 217 524 180 537 483 131 156 630 590 90 213 174 349 9 931 683 701 260 705 223 505 71 645 952 107 551 222 777 668 617 760 81 680 129 918 143 590 29 352 976 640 434 993 160 438 773 500 214 242 967 155 812 474 953 809 67 644 419 44 292 2 627 597 905 941 823 868 703 120 897 672 78 520 543 120 604 29 290 374 201 137 367 200 139 42 185 672 589 22 657 259 781 620 882 636 164 378 469 236 953 615 390 722 256 821 205 895 79 521 955 999 546 413 686 584 208 485 239 567 810 292 874 70 268 808 27 638 547 356 199 461 759 391 38 519 981 740 76 286 115 824 651 439 478 611 339 979 847 442 903 504 845 393 979 513 659 1 673 524 500 725 466 805 243 779 822 557 823 320 806 255 206 579 339 443 711 326 44 876 904 472 739 702 179 917 969 707 650 338 804 32 797 284 468 930 580 414 38 732 786 922 340 164 17 523 595 63 5 499 117 981 351 519 738 568 767 378 143 812 172 813 725 312 933 22 709 531 735 875 473 76 655 406 226 325 727 480 304 712 945 901 565 345 77 991 563 594 399 290 933 620 767 630 141 810 146 992 245 740 46 786 352 659 409 84 754 728 734 792 899 757 673 730 736 166 529 864 560 905 91 65 545 261 626 11 306 818 668 789 470 435 147 260 278 633 294 494 512 319 512 117 935 63 116 815 91 93 670 859 941 893 331 520 248 229 60 812 335 38 203 305 441 311 290 283 532 913 345 452 410 57 569 634 188 403 340 908 189 360 500 920 30 615 306 721 957 545 165 116 494 532 57 883 90 624 305 522 602 862 177 870 4 73 664 684 989 185 703 517 497 858 721 473 699 813 701 567 59 162 406 197 54 82 11 57 323 221 134 190 602 776 511 464 182 486 375 301 725 468 50 263 152 499 155 605 955 98 136 620 157 41 94 217 616 941 555 435 923 596 39 768 897 512 182 487 573 282 566 238 783 934 782 284 66 391 87 842 485 332 224 912 976 348 541 898 185 977 189 419 599 915 808 333 562 176 598 710 507 915 593 414 497 124 261 381 420 261 386 38 185 537 894 991 677 393 351 191 170 842 515 548 933 609 563 924 192 40 164 180 27 863 596 308 380 344 658 345 272 319 535 721 475 895 833 590 740 631 783 381 307 834 575 673 794 463 794 191 988 793 85 792 817 602 62 376 864 230 615 101 696 788 691 463 140 541 361 227 16 966 932 719 613 612 314 82 176 71 737 472 177 834 863 179 21 968 318 911 938 315 494 712 319 475 518 610 367 635 696 963 754 933 702 579 112 820 174 174 722 17 26 702 361 410 437 314 780 993 11 793 245 882 858 94 407 605 569 224 64 305 768 658 559 785 893 500 188 349 254 206 73 122 519 309 555 893 151 397 989 616 363 411 468 574 422 513 196 956 303 566 35 473 458 641 419 697 248 837 553 48 69 95 418 64 879 439 221 286 589 254 860 399 718 677 581 111 98 939 745 244 866 739 518 262 781 697 627 541 187 449 403 679 399 488 1 733 575 310 104 884 392 768 25 679 573 807 220 310 112 190 998 433 286 692 265 917 70 819 130 533 916 187 461 962 694 212 40 109 840 384 373 511 769 558 329 343 1 647 516 583 665 711 503 322 761 799 675 582 935 233 948 993 887 208 931 325 328 229 350 737 455 876 956 255 190 723 968 839 30 860 11 503 597 909 578 406 954 354 402 746 287 923 124 833 60 355 207 812 41 862 122 639 573 377 92 448 597 162 160 355 629 732 909 833 803 860 908 777 195 902 365 585 970 263 295 31 917 419 913 1 784 312 617 27 319 243 975 635 492 658 985 922 397 455 324 767 690 443 480 619 646 230 322 356 211 82 983 647 432 476 241 769 58 497 943 519 209 348 856 141 277 16 46 222 409 821 571 166 488 716 150 548 143 528 271 80 530 378 554 889 741 641 139 364 478 197 158 673 36 319 320 781 534 398 859 429 949 793 152 932 825 503 742 131 57

[出力例]
127

[入力例]

1 2 1 3 1 4 4

[出力例]

※AtCoderのテストケースより

[入力例]

100

[出力例]

※AtCoderのテストケースより

[入力例]

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

[出力例]

[入力例]

1 2 2 3 3 2 1 1 1 1

[出力例]

[入力例]

1000

550 734 953 900 452 347 189 680 25 307 277 458 652 314 838 251 427 821 413 232 268 623 465 782 671 121 773 821 955 367 940 907 771 811 512 870 54 607 49 379 593 849 66 947 287 11 73 913 459 808 388 430 810 256 106 771 451 53 218 97 734 835 117 637 762 888 939 41 467 767 815 572 447 332 287 325 103 279 353 796 899 781 572 536 712 376 384 690 482 916 664 361 577 655 482 398 403 975 874 207 654 40 642 388 69 328 890 597 712 118 305 902 699 708 50 471 101 957 418 522 291 427 818 712 809 805 754 99 522 358 753 541 526 858 828 395 936 944 987 831 468 560 918 890 603 520 957 908 604 61 204 802 949 910 519 423 206 794 818 188 12 525 352 517 205 493 15 398 987 391 753 263 836 133 719 967 332 151 917 593 268 448 676 822 445 972 209 119 31 398 542 227 919 937 83 518 866 751 708 267 665 3 660 581 454 287 925 862 572 289 482 63 477 350 39 233 897 228 962 335 884 661 241 274 329 994 901 977 245 538 105 264 870 725 917 600 978 619 945 510 234 495 837 516 53 307 298 62 741 50 254 417 998 492 60 348 97 76 493 618 41 301 516 69 444 784 641 357 897 150 993 417 258 832 902 732 839 24 959 708 172 143 815 50 267 838 72 957 264 58 2 177 143 273 60 920 205 478 937 670 226 791 691 93 233 250 366 233 381 820 604 82 873 430 88 638 331 154 803 819 643 480 980 43 593 963 51 688 484 999 765 531 473 613 388 789 871 466 812 370 712 964 330 706 601 811 139 303 437 286 972 996 714 577 969 347 719 244 8 23 299 89 142 558 905 279 315 869 16 764 190 602 467 17 115 542 729 567 918 399 59 543 272 110 896 819 344 757 286 31 978 50 989 302 577 973 80 678 718 666 127 783 615 810 124 445 646 966 861 852 444 212 506 119 575 945 987 408 109 557 449 302 152 962 219 910 621 986 305 140 793 185 37 171 339 777 973 27 638 779 349 344 401 401 386 402 174 26 629 227 55 801 207 430 528 528 378 368 514 490 257 458 949 62 277 136 450 404 726 809 745 104 911 917 187 546 938 638 332 373 223 331 173 161 142 761 626 515 513 284 946 447 653 921 617 536 922 611 132 728 784 336 229 534 24 355 589 244 189 190 432 938 884 433 895 353 28 122 57 200 522 733 184 336 932 237 651 171 883 440 407 411 724 588 234 459 540 137 894 882 420 125 422 935 570 946 877 505 895 756 199 364 443 788 905 710 293 41 732 314 939 101 662 298 957 97 115 951 853 556 239 364 825 724 834 910 855 685 320 172 454 200 876 279 155 375 208 186 194 594 256 855 826 721 884 452 812 599 461 609 574 687 852 314 469 570 76 563 969 513 431 699 765 334 856 648 580 110 426 992 470 263 801 184 463 193 162 338 870 706 94 844 546 668 518 197 416 971 550 616 355 708 721 854 691 939 74 531 668 537 70 911 5 543 351 18 450 315 552 114 842 557 780 207 270 509 776 198 30 960 339 214 884 799 724 500 197 765 257 886 6 237 820 261 483 250 319 549 192 95 661 973 752 112 625 584 792 95 4 800 739 793 536 635 784 304 338 817 283 836 219 160 323 785 700 818 386 808 910 919 583 520 925 689 850 452 692 935 196 464 762 58 937 798 370 904 628 6 940 961 4 541 297 939 700 814 837 224 287 946 145 398 604 9 569 747 348 913 915 319 372 408 124 211 188 892 919 377 841 339 451 151 582 937 63 95 89 468 669 903 17 44 530 89 259 22 424 20 527 428 547 134 492 80 86 161 626 224 564 614 972 87 835 256 655 141 891 304 861 859 468 650 190 346 851 740 713 975 398 967 376 820 208 271 635 345 864 986 148 243 428 525 982 235 441 861 999 460 834 809 741 742 309 178 220 758 573 820 872 638 882 869 970 857 639 985 879 424 729 689 566 376 398 333 595 75 415 419 654 627 749 533 679 299 24 954 772 564 761 464 378 2 680 330 742 489 480 255 230 801 829 519 21 164 235 699 253 273 968 820 392 989 674 88 625 200 252 804 12 77 976 149 10 750 759 529 732 590 548 259 930 286 329 936 875 90 453 843 543 258 517 482 310 930 50 449 922 87 385 293 396 871 30 403 224 334 955 403 675 833 674 887 534 732 672 262 25 105 818 897 686 895 767 680 570 74 449 842 50 663 873 146 324 222 402 583 449 802 841 7 241 287 807 732 644 950 538 236 803 639 703 126 122 674 155 245 876 621 438 392

[出力例]

[入力例]

5000

783 692 655 647 704 737 109 819 326 153 288 974 274 353 595 148 845 144 273 541 572 749 553 630 325 289 857 404 479 499 665 856 53 777 507 205 345 54 123 153 1 257 517 193 92 596 984 778 143 627 321 241 154 509 771 438 128 976 720 1 785 595 614 729 326 586 727 224 222 52 627 724 797 171 825 300 1 77 156 558 66 225 167 241 918 386 826 201 40 869 138 197 144 98 691 405 856 14 691 548 865 628 706 101 71 402 70 667 349 780 781 89 720 675 899 648 911 401 739 301 402 129 687 715 265 703 175 25 717 404 481 791 212 318 715 241 688 500 805 855 692 330 491 490 106 315 493 733 708 424 139 222 826 289 81 679 977 847 926 358 846 161 469 766 718 789 895 419 389 420 932 97 535 871 90 449 312 267 352 839 31 729 322 583 827 777 688 432 6 493 884 568 391 917 147 651 688 109 690 678 151 735 902 776 408 833 775 502 862 977 599 759 202 450 753 758 898 314 584 370 194 227 288 557 431 963 180 182 466 81 875 348 584 950 362 707 59 387 258 573 357 291 367 785 990 349 351 527 54 309 419 943 229 209 585 793 799 160 87 524 380 985 208 176 403 554 306 551 472 515 915 714 457 747 109 498 312 591 193 174 320 975 703 205 808 269 114 334 224 94 350 346 166 466 804 753 686 116 142 564 683 211 667 248 352 677 766 509 162 823 431 617 541 347 298 571 56 640 893 826 665 953 223 231 793 516 2 186 194 353 418 935 660 229 446 625 774 586 894 438 450 301 160 308 753 754 219 352 345 967 523 251 983 890 550 252 58 604 543 903 468 170 975 640 930 587 469 271 621 392 670 725 738 552 155 741 310 83 372 570 499 604 166 661 385 234 339 120 979 428 276 962 726 251 329 897 476 5 630 795 186 712 115 569 85 487 130 834 99 734 269 165 222 304 534 954 233 115 320 649 522 243 434 191 424 472 152 156 2 215 581 632 813 946 266 635 378 481 496 419 72 379 712 107 305 86 240 493 409 179 849 605 649 897 520 999 845 307 796 923 405 40 334 455 28 585 903 982 39 818 599 32 763 472 585 50 814 665 36 279 808 10 222 657 181 642 835 327 3 891 563 787 686 898 54 445 657 515 444 60 236 556 82 226 612 724 182 199 626 383 873 193 155 953 235 431 440 800 375 775 468 59 456 393 805 734 255 169 731 60 462 494 816 198 510 600 442 340 330 525 901 417 106 578 932 423 698 252 880 906 573 727 896 295 94 662 773 110 620 3 760 98 716 617 544 11 837 842 490 979 851 830 512 161 851 832 367 281 433 513 767 726 403 847 128 857 200 495 121 638 720 175 855 832 345 132 295 671 153 957 828 166 204 942 50 413 609 209 71 873 871 833 186 72 405 857 986 399 413 201 304 118 413 254 670 925 644 869 438 582 858 749 689 939 391 153 428 408 722 893 715 522 827 273 198 391 303 677 865 451 31 644 716 585 396 513 350 457 689 307 901 332 141 554 183 135 919 4 393 558 391 865 357 797 244 334 927 615 285 526 305 57 180 594 510 399 810 434 136 992 694 20 34 811 414 49 463 945 687 781 941 919 446 614 270 613 120 162 606 80 400 295 152 196 689 678 445 404 153 819 411 623 91 835 512 162 29 214 538 980 953 931 626 576 102 800 395 194 566 397 263 936 851 191 703 653 626 592 348 845 828 208 5 253 257 642 289 442 362 837 976 465 653 971 821 461 839 474 968 81 642 757 749 92 816 69 223 842 662 423 726 677 647 909 3 787 37 807 48 739 275 934 139 925 495 223 795 916 837 347 533 382 122 48 221 654 389 811 761 462 389 14 937 998 267 912 730 495 792 949 240 184 817 474 399 413 801 190 708 962 385 512 566 501 568 143 682 413 854 549 514 742 662 355 483 239 509 749 970 724 271 16 522 891 140 37 395 144 723 463 139 65 860 377 122 986 741 620 595 907 319 612 950 157 336 738 397 472 43 165 622 816 107 98 558 611 174 931 783 871 677 782 616 6 626 288 444 540 672 752 643 504 26 790 194 151 538 151 165 728 938 791 353 345 20 641 145 50 816 137 629 430 444 392 883 548 732 883 961 642 502 182 635 919 910 824 536 491 314 131 986 333 62 64 597 361 269 169 772 239 500 243 39 497 981 393 167 27 78 270 154 226 477 604 136 66 941 352 279 328 493 474 43 464 571 459 195 892 728 822 469 915 895 874 324 36 533 312 906 838 935 638 692 975 952 928 714 457 31 543 497 648 831 784 507 355 229 173 13 42 851 18 793 734 95 318 238 883 561 157 408 845 680 739 69 458 922 865 848 201 641 386 426 4 108 932 910 71 7 28 929 461 107 848 777 276 528 144 213 630 540 60 136 598 255 442 644 69 206 46 673 257 576 23 897 323 795 526 670 338 178 151 172 869 107 625 884 598 994 351 842 235 753 6 38 707 453 154 615 284 475 792 713 40 275 124 465 642 364 322 872 801 455 21 799 647 336 28 153 465 721 595 230 149 145 284 78 98 78 219 729 157 99 25 565 187 49 638 328 352 166 790 676 860 75 529 442 136 85 255 23 459 817 80 946 797 537 888 56 308 973 236 916 707 687 259 418 796 100 668 192 80 877 561 965 85 534 136 865 471 799 979 341 246 186 167 158 28 119 936 271 83 60 273 284 138 231 757 222 981 283 884 152 260 75 159 737 541 181 765 312 974 843 455 595 190 334 153 809 274 462 775 406 141 966 73 934 142 997 676 264 279 725 98 385 976 989 897 186 229 853 25 238 489 123 360 638 670 313 561 485 178 152 714 253 522 245 759 559 450 790 684 570 155 345 148 327 310 279 275 786 993 182 187 113 526 986 920 764 197 396 444 967 791 532 877 138 235 433 893 540 680 830 931 416 756 600 327 881 419 945 592 238 462 196 522 831 671 678 121 973 378 88 31 424 117 424 371 320 309 345 111 522 367 976 58 556 972 992 719 870 421 243 666 68 536 324 392 39 834 905 323 2 331 866 310 362 360 976 96 31 72 56 491 311 921 371 786 356 685 113 855 34 286 139 425 378 292 994 307 644 150 474 268 907 125 815 454 765 950 443 317 440 132 80 344 919 56 906 834 729 574 169 534 98 979 567 753 822 721 837 835 760 64 238 554 166 524 289 830 11 174 472 321 218 184 807 359 563 848 220 944 561 142 93 19 682 693 111 315 144 503 710 953 374 633 283 493 825 363 91 612 314 948 325 99 334 658 364 739 133 282 674 959 2 628 847 926 392 577 558 181 319 661 84 511 96 446 629 358 928 921 751 92 790 665 998 678 852 192 750 373 101 807 278 225 806 945 694 415 168 967 104 533 803 133 64 624 553 358 182 743 164 322 980 339 731 317 401 634 894 633 730 910 182 513 351 520 439 421 945 298 716 458 626 52 71 219 514 803 881 854 529 828 797 640 164 571 220 321 883 128 949 896 308 551 339 653 555 218 263 122 763 7 15 560 275 862 527 783 105 760 567 593 986 426 596 800 905 734 992 474 486 666 291 800 157 762 14 934 289 730 621 438 930 277 529 99 961 747 38 823 127 962 77 699 975 563 557 176 415 630 160 54 779 227 625 385 901 424 906 665 874 253 375 399 778 152 480 986 530 713 713 30 761 671 328 500 885 607 470 440 85 33 331 785 152 869 444 656 727 272 707 755 866 482 898 636 344 676 201 871 356 759 942 143 644 448 761 653 36 244 457 200 140 775 704 102 241 637 938 695 829 485 649 537 639 679 334 117 946 663 177 566 367 427 536 389 306 311 462 122 369 109 244 482 444 913 651 377 603 819 80 199 888 746 158 187 429 885 691 196 40 209 853 990 290 12 270 581 409 134 291 590 603 285 417 967 826 856 277 247 444 351 209 191 799 547 11 122 467 126 262 395 289 483 99 352 213 18 211 603 570 369 852 479 13 465 194 102 275 604 668 18 209 880 529 687 435 283 749 969 71 811 85 159 554 570 289 770 835 232 990 423 79 237 744 60 268 512 666 620 178 575 732 785 657 450 257 460 451 667 14 696 472 855 967 641 836 152 817 71 202 878 337 449 186 868 146 516 184 347 539 672 41 188 596 562 1 161 764 434 470 102 923 149 145 113 954 298 301 205 285 439 750 901 570 973 400 366 884 702 517 790 127 381 483 349 442 135 263 719 434 771 666 302 894 266 216 302 456 10 237 333 802 957 251 446 975 289 541 403 637 936 420 529 479 665 271 606 732 748 912 730 314 918 828 88 867 770 63 30 93 408 774 313 759 732 870 311 240 57 357 527 250 680 568 612 79 532 18 487 98 32 731 345 827 772 551 929 25 285 997 408 841 278 307 737 481 725 928 948 775 365 919 298 488 643 334 329 942 102 869 564 49 454 890 159 623 749 838 930 914 206 995 66 268 290 745 467 584 955 542 625 778 142 662 330 391 728 373 140 711 184 931 174 821 479 939 354 127 965 314 183 190 413 727 728 85 585 789 450 442 719 439 950 287 872 433 616 421 49 911 941 834 960 606 138 368 185 218 431 510 544 921 282 426 103 520 163 612 948 427 452 198 874 516 412 604 199 103 728 714 39 162 283 778 465 433 7 899 296 208 111 363 786 680 841 40 54 440 790 916 104 530 762 706 609 816 139 759 685 465 776 200 555 437 367 326 733 345 36 740 893 128 374 954 561 27 156 359 315 486 154 44 247 523 131 910 540 688 64 948 39 772 702 695 995 192 292 792 917 117 629 168 522 167 320 95 271 904 78 420 990 687 476 306 820 603 464 816 185 125 380 534 526 975 380 703 766 429 472 302 726 631 310 164 455 226 347 270 996 806 667 363 867 54 591 458 163 274 68 262 864 835 545 429 821 649 303 932 822 967 324 224 712 848 926 50 226 372 850 63 169 327 796 826 396 206 198 188 450 825 746 36 976 869 824 842 261 117 867 955 542 79 584 194 15 63 464 49 668 643 46 592 937 561 507 535 58 541 109 526 653 524 808 673 445 718 394 628 332 652 449 145 702 825 50 508 409 598 669 935 132 563 22 654 664 977 335 226 470 397 73 518 471 408 295 974 650 519 610 355 412 849 869 426 551 581 416 715 821 547 642 29 384 487 565 594 936 435 657 482 385 764 746 473 847 535 674 15 498 547 620 679 911 260 154 452 580 100 946 252 355 20 697 914 341 77 914 84 954 591 771 725 209 816 600 520 829 868 923 871 171 872 892 61 621 886 67 531 885 926 935 298 926 545 489 338 449 105 889 583 4 370 764 62 286 512 266 409 297 791 237 16 238 992 936 702 881 311 796 696 280 763 120 882 605 484 543 727 638 349 945 111 445 48 976 954 940 44 917 459 518 24 97 940 42 811 868 886 774 380 272 396 760 642 691 859 804 173 996 93 705 561 942 645 249 549 595 711 869 223 934 419 337 710 249 602 548 422 964 385 506 427 486 408 865 138 925 148 364 19 2 359 489 782 783 878 946 272 963 25 890 531 849 425 517 791 52 858 733 412 713 730 65 304 488 92 705 41 350 983 404 540 914 944 358 99 33 67 644 19 837 733 292 854 621 834 617 812 494 869 782 658 287 523 326 235 751 532 269 185 689 57 354 396 646 20 336 488 139 170 483 105 921 221 606 761 184 517 412 578 637 997 476 565 153 983 227 633 683 361 911 374 358 408 816 19 949 697 406 656 917 180 783 617 82 389 481 95 873 15 858 641 557 654 849 330 643 160 759 846 810 272 213 605 837 117 805 898 686 226 152 571 297 316 112 361 465 95 523 461 886 32 68 729 994 370 640 733 436 29 900 933 643 204 203 9 489 512 55 168 210 912 731 79 100 853 465 803 702 195 39 526 585 338 270 585 756 893 34 295 695 845 795 284 205 628 865 754 317 408 535 501 873 430 30 11 706 825 591 672 265 194 215 538 914 381 887 286 249 185 924 260 739 452 217 629 345 190 709 532 446 256 102 675 351 937 575 376 23 180 910 244 644 660 979 618 990 673 6 169 548 31 553 809 539 720 178 114 612 942 268 941 704 825 390 940 504 698 531 681 692 431 675 908 354 502 287 981 80 364 455 32 35 40 98 268 544 987 27 745 398 985 615 44 322 596 809 553 941 114 191 763 889 868 797 772 111 683 715 954 483 959 581 217 824 478 530 980 589 420 751 977 722 87 470 860 755 520 732 109 896 298 859 400 947 850 409 991 797 276 951 751 704 413 929 434 474 556 408 263 660 114 391 206 674 574 232 605 144 635 296 930 762 708 496 3 812 637 720 631 822 23 15 898 491 260 735 973 968 201 178 573 975 39 760 559 603 46 712 188 340 900 464 716 984 221 574 881 567 192 539 642 821 5 556 540 21 360 588 4 52 756 162 253 106 514 247 483 105 538 331 375 253 633 673 610 677 356 607 353 899 676 911 341 368 329 512 136 466 942 878 156 343 804 166 859 213 408 459 377 472 716 424 526 113 327 378 155 829 584 707 454 368 316 565 58 268 371 978 17 310 563 838 217 654 456 412 519 999 973 764 942 301 902 613 469 517 529 20 744 964 740 999 896 16 283 646 642 657 560 588 325 514 850 384 490 6 5 453 477 506 686 240 679 525 250 726 7 564 593 443 466 613 381 1 655 608 481 308 88 841 611 450 117 822 580 575 620 500 955 102 461 400 266 390 734 797 804 830 883 711 773 484 608 838 799 171 901 77 411 256 878 925 547 18 964 920 876 527 747 625 929 878 70 850 163 746 919 432 905 523 806 149 604 378 530 594 776 959 735 978 934 91 744 670 70 22 81 113 34 218 891 678 648 523 148 243 642 332 498 660 971 14 53 511 390 83 827 685 402 687 585 349 257 752 784 925 629 994 592 849 262 528 665 735 685 292 45 746 600 910 847 965 521 514 948 23 738 737 329 406 887 789 840 333 554 428 130 763 424 871 61 768 599 413 356 767 943 455 858 955 582 604 398 337 688 681 506 160 388 403 887 777 166 611 147 646 415 141 490 72 694 316 996 830 946 340 170 476 190 218 94 240 315 534 894 437 278 244 827 151 859 336 882 564 504 820 715 874 894 935 831 618 747 980 541 642 925 610 990 892 680 801 632 984 460 55 696 875 277 743 299 395 514 508 133 8 952 484 755 85 659 114 496 741 782 665 77 373 433 258 603 1 306 572 11 460 611 253 771 705 383 927 978 746 340 367 24 919 610 964 974 947 498 413 143 230 989 85 798 192 940 169 635 961 602 27 848 251 399 943 422 323 483 223 917 754 984 620 235 34 401 762 419 208 882 177 652 571 340 280 556 201 94 935 772 268 242 297 998 857 204 441 933 267 357 549 293 239 560 209 360 557 572 868 734 502 173 35 783 747 407 491 523 660 623 236 244 101 154 954 253 815 13 33 35 800 228 609 747 41 979 227 381 775 299 276 569 377 964 621 696 698 102 901 990 686 905 2 509 755 27 334 308 147 643 225 287 573 770 989 734 753 476 273 590 44 397 740 418 522 537 714 983 414 568 618 516 405 551 772 870 359 400 679 299 51 197 706 859 903 917 855 679 945 67 73 915 912 344 189 211 542 764 453 733 426 285 368 739 630 522 685 797 420 552 378 717 601 753 239 525 777 748 731 479 707 788 159 954 367 716 588 469 470 79 35 800 772 363 123 500 973 644 416 397 922 802 996 99 349 137 886 847 989 766 409 285 177 57 327 994 549 796 624 693 58 738 527 962 840 702 491 277 640 406 450 647 548 616 455 605 496 530 766 694 741 112 67 567 258 646 915 391 226 748 698 574 629 181 651 346 489 77 294 382 176 678 56 880 173 667 723 52 750 650 318 456 674 100 637 600 133 427 883 762 668 579 246 61 994 880 161 141 610 26 133 530 229 196 984 634 865 662 606 671 362 498 175 810 256 808 865 459 722 560 456 22 126 385 859 704 756 722 779 794 593 49 197 764 841 819 964 872 662 86 111 899 916 883 665 68 65 692 680 357 697 359 17 892 317 946 513 896 998 724 160 642 337 541 463 202 863 525 861 376 500 778 811 895 404 980 664 957 783 676 362 35 647 178 249 84 910 912 256 837 923 455 52 938 417 95 646 682 316 558 953 602 295 592 533 497 244 831 1 487 811 685 850 633 598 313 390 90 760 177 905 718 569 848 287 114 113 82 811 623 159 715 222 744 267 328 508 37 238 394 627 593 816 816 879 695 128 581 471 325 402 985 20 630 642 688 123 959 355 624 786 241 811 202 214 756 122 814 186 638 32 791 66 458 814 75 141 452 95 649 767 899 23 963 16 866 149 123 395 208 111 384 683 729 689 575 194 37 107 186 709 378 110 864 889 144 869 54 450 192 854 601 301 459 430 554 251 689 159 823 387 194 262 703 111 614 308 429 902 763 180 131 125 119 182 469 33 513 205 688 28 403 539 28 356 312 948 578 425 891 383 321 556 675 66 894 354 913 701 762 385 157 778 99 763 649 407 113 863 613 469 143 450 34 523 960 482 701 407 994 905 408 650 338 551 999 373 272 326 152 29 912 935 787 881 326 153 197 507 765 224 453 740 135 290 667 482 249 581 703 814 514 507 992 946 963 72 427 261 295 425 988 346 210 916 644 266 572 923 740 319 264 264 34 711 735 82 471 554 216 136 388 837 305 276 605 440 465 985 49 582 649 505 771 425 560 337 85 739 261 595 218 761 304 623 885 844 944 917 549 792 876 506 725 420 832 466 836 922 485 482 575 516 52 4 739 538 222 777 228 137 17 838 341 153 832 249 644 125 64 477 261 588 573 454 1 64 285 976 854 386 324 333 282 758 996 15 200 853 631 483 3 293 508 391 358 879 39 484 815 393 411 197 572 652 202 970 623 471 507 288 7 842 481 488 112 80 269 280 543 959 67 195 745 113 481 464 988 391 990 300 131 854 512 176 787 893 922 645 264 386 664 429 994 239 880 30 946 521 196 957 903 903 94 195 511 702 933 614 20 561 796 120 480 873 990 256 308 382 5 45 637 907 496 137 209 798 95 168 394 159 218 258 540 840 325 238 383 124 322 290 431 873 424 685 793 533 212 702 39 960 323 543 306 239 342 128 688 428 869 842 56 713 629 182 950 49 972 473 887 391 314 825 577 198 292 837 268 306 975 785 468 4 569 286 43 133 372 125 346 573 311 603 179 98 286 743 689 490 663 683 107 640 858 801 289 639 290 44 883 768 392 665 975 516 396 306 227 999 533 801 836 759 124 731 906 214 608 91 829 498 519 724 539 617 358 202 825 729 498 444 414 880 991 177 495 828 217 524 180 537 483 131 156 630 590 90 213 174 349 9 931 683 701 260 705 223 505 71 645 952 107 551 222 777 668 617 760 81 680 129 918 143 590 29 352 976 640 434 993 160 438 773 500 214 242 967 155 812 474 953 809 67 644 419 44 292 2 627 597 905 941 823 868 703 120 897 672 78 520 543 120 604 29 290 374 201 137 367 200 139 42 185 672 589 22 657 259 781 620 882 636 164 378 469 236 953 615 390 722 256 821 205 895 79 521 955 999 546 413 686 584 208 485 239 567 810 292 874 70 268 808 27 638 547 356 199 461 759 391 38 519 981 740 76 286 115 824 651 439 478 611 339 979 847 442 903 504 845 393 979 513 659 1 673 524 500 725 466 805 243 779 822 557 823 320 806 255 206 579 339 443 711 326 44 876 904 472 739 702 179 917 969 707 650 338 804 32 797 284 468 930 580 414 38 732 786 922 340 164 17 523 595 63 5 499 117 981 351 519 738 568 767 378 143 812 172 813 725 312 933 22 709 531 735 875 473 76 655 406 226 325 727 480 304 712 945 901 565 345 77 991 563 594 399 290 933 620 767 630 141 810 146 992 245 740 46 786 352 659 409 84 754 728 734 792 899 757 673 730 736 166 529 864 560 905 91 65 545 261 626 11 306 818 668 789 470 435 147 260 278 633 294 494 512 319 512 117 935 63 116 815 91 93 670 859 941 893 331 520 248 229 60 812 335 38 203 305 441 311 290 283 532 913 345 452 410 57 569 634 188 403 340 908 189 360 500 920 30 615 306 721 957 545 165 116 494 532 57 883 90 624 305 522 602 862 177 870 4 73 664 684 989 185 703 517 497 858 721 473 699 813 701 567 59 162 406 197 54 82 11 57 323 221 134 190 602 776 511 464 182 486 375 301 725 468 50 263 152 499 155 605 955 98 136 620 157 41 94 217 616 941 555 435 923 596 39 768 897 512 182 487 573 282 566 238 783 934 782 284 66 391 87 842 485 332 224 912 976 348 541 898 185 977 189 419 599 915 808 333 562 176 598 710 507 915 593 414 497 124 261 381 420 261 386 38 185 537 894 991 677 393 351 191 170 842 515 548 933 609 563 924 192 40 164 180 27 863 596 308 380 344 658 345 272 319 535 721 475 895 833 590 740 631 783 381 307 834 575 673 794 463 794 191 988 793 85 792 817 602 62 376 864 230 615 101 696 788 691 463 140 541 361 227 16 966 932 719 613 612 314 82 176 71 737 472 177 834 863 179 21 968 318 911 938 315 494 712 319 475 518 610 367 635 696 963 754 933 702 579 112 820 174 174 722 17 26 702 361 410 437 314 780 993 11 793 245 882 858 94 407 605 569 224 64 305 768 658 559 785 893 500 188 349 254 206 73 122 519 309 555 893 151 397 989 616 363 411 468 574 422 513 196 956 303 566 35 473 458 641 419 697 248 837 553 48 69 95 418 64 879 439 221 286 589 254 860 399 718 677 581 111 98 939 745 244 866 739 518 262 781 697 627 541 187 449 403 679 399 488 1 733 575 310 104 884 392 768 25 679 573 807 220 310 112 190 998 433 286 692 265 917 70 819 130 533 916 187 461 962 694 212 40 109 840 384 373 511 769 558 329 343 1 647 516 583 665 711 503 322 761 799 675 582 935 233 948 993 887 208 931 325 328 229 350 737 455 876 956 255 190 723 968 839 30 860 11 503 597 909 578 406 954 354 402 746 287 923 124 833 60 355 207 812 41 862 122 639 573 377 92 448 597 162 160 355 629 732 909 833 803 860 908 777 195 902 365 585 970 263 295 31 917 419 913 1 784 312 617 27 319 243 975 635 492 658 985 922 397 455 324 767 690 443 480 619 646 230 322 356 211 82 983 647 432 476 241 769 58 497 943 519 209 348 856 141 277 16 46 222 409 821 571 166 488 716 150 548 143 528 271 80 530 378 554 889 741 641 139 364 478 197 158 673 36 319 320 781 534 398 859 429 949 793 152 932 825 503 742 131 57

[出力例]

127

■参照サイト
AtCoder Regular Contest 022

2020年4月13日

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

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

■感想.
1. 累積和を使う方針で, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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--)
LL r[4040], g[4040], b[4040]; // 'R', 'G', 'B' の 出現位置.
LL rCum[4040], gCum[4040], bCum[4040]; // 累積和.

int main(){
    
    // 1. 入力情報.
    int N;
    char c[4040];
    scanf("%d %s", &N, c);
    
    // 2. 'R', 'G', 'B' の 出現位置を保存.
    rep(i, N){
        if(c[i] == 'R') r[i]++;
        if(c[i] == 'G') g[i]++;
        if(c[i] == 'B') b[i]++;
    }
    
    // 3. 累積和.
    rep(i, N){
        rCum[i + 1] = rCum[i] + r[i];
        gCum[i + 1] = gCum[i] + g[i];
        bCum[i + 1] = bCum[i] + b[i];
    }
    
    // 4. 条件を満たす組を計算.
    // 中央の文字 を 変えながら, 集計.
    LL ans = 0;
    repx(i, 1, N - 1){
        char mc = c[i];
        // 左右の文字数.
        int l = i, r = N - 1 - i;
        // 'R' の 場合.
        if(mc == 'R'){
            // 'G' < 'R' < 'B'.
            ans += gCum[i] * (bCum[N] - bCum[i]);
            // 'B' < 'R' < 'G'.
            ans += bCum[i] * (gCum[N] - gCum[i]);
            // 中央の文字から同じ距離で, 異なる文字('G', 'B')だったら, 減算.
            repx(j, 1, min(l, r) + 1){
                if(c[i - j] == 'G' && c[i + j] == 'B') ans--;
                if(c[i - j] == 'B' && c[i + j] == 'G') ans--;
            }
        }
        
        // 'G' の 場合.
        if(mc == 'G'){
            // 'R' < 'G' < 'B'.
            ans += rCum[i] * (bCum[N] - bCum[i]);
            // 'B' < 'G' < 'R'.
            ans += bCum[i] * (rCum[N] - rCum[i]);
            // 中央の文字から同じ距離で, 異なる文字('R', 'B')だったら, 減算.
            repx(j, 1, min(l, r) + 1){
                if(c[i - j] == 'R' && c[i + j] == 'B') ans--;
                if(c[i - j] == 'B' && c[i + j] == 'R') ans--;
            }
        }
        
        // 'B' の 場合.
        if(mc == 'B'){
            // 'R' < 'B' < 'G'.
            ans += rCum[i] * (gCum[N] - gCum[i]);
            // 'G' < 'B' < 'R'.
            ans += gCum[i] * (rCum[N] - rCum[i]);
            // 中央の文字から同じ距離で, 異なる文字('R', 'G')だったら, 減算.
            repx(j, 1, min(l, r) + 1){
                if(c[i - j] == 'R' && c[i + j] == 'G') ans--;
                if(c[i - j] == 'G' && c[i + j] == 'R') ans--;
            }
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL r[4040], g[4040], b[4040]; // 'R', 'G', 'B' の出現位置.

LL rCum[4040], gCum[4040], bCum[4040]; // 累積和.

int main(){

// 1. 入力情報.

int N;

char c[4040];

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

// 2. 'R', 'G', 'B' の出現位置を保存.

rep(i, N){

if(c[i] == 'R') r[i]++;

if(c[i] == 'G') g[i]++;

if(c[i] == 'B') b[i]++;

}

// 3. 累積和.

rep(i, N){

rCum[i + 1] = rCum[i] + r[i];

gCum[i + 1] = gCum[i] + g[i];

bCum[i + 1] = bCum[i] + b[i];

}

// 4. 条件を満たす組を計算.

// 中央の文字を変えながら, 集計.

LL ans = 0;

repx(i, 1, N - 1){

char mc = c[i];

// 左右の文字数.

int l = i, r = N - 1 - i;

// 'R' の場合.

if(mc == 'R'){

// 'G' < 'R' < 'B'.

ans += gCum[i] * (bCum[N] - bCum[i]);

// 'B' < 'R' < 'G'.

ans += bCum[i] * (gCum[N] - gCum[i]);

// 中央の文字から同じ距離で, 異なる文字('G', 'B')だったら, 減算.

repx(j, 1, min(l, r) + 1){

if(c[i - j] == 'G' && c[i + j] == 'B') ans--;

if(c[i - j] == 'B' && c[i + j] == 'G') ans--;

}

// 'G' の場合.

if(mc == 'G'){

// 'R' < 'G' < 'B'.

ans += rCum[i] * (bCum[N] - bCum[i]);

// 'B' < 'G' < 'R'.

ans += bCum[i] * (rCum[N] - rCum[i]);

// 中央の文字から同じ距離で, 異なる文字('R', 'B')だったら, 減算.

repx(j, 1, min(l, r) + 1){

if(c[i - j] == 'R' && c[i + j] == 'B') ans--;

if(c[i - j] == 'B' && c[i + j] == 'R') ans--;

}

// 'B' の場合.

if(mc == 'B'){

// 'R' < 'B' < 'G'.

ans += rCum[i] * (gCum[N] - gCum[i]);

// 'G' < 'B' < 'R'.

ans += gCum[i] * (rCum[N] - rCum[i]);

// 中央の文字から同じ距離で, 異なる文字('R', 'G')だったら, 減算.

repx(j, 1, min(l, r) + 1){

if(c[i - j] == 'R' && c[i + j] == 'G') ans--;

if(c[i - j] == 'G' && c[i + j] == 'R') ans--;

}

// 5. 出力.

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

return 0;

}

[入力例]
4
RRGB

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

[入力例]
39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

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

[入力例]
3
RGB

[出力例]
0

[入力例]
1000
GGRGBRRGBGBRGBGRGBGRGBGRGRRBBRGGRRGRGBBGGGBGRGRRBRGGBRBGGRBRGBBRGGBRBGRRGGRGGGBBGBGBBBRRBBGGGGGBBBGBGGGGBBGRBRBGGGRRGRGGRBRBRGGBGGRGBRRBBGRBGRGBBRBRRBGRGRRGBGBGGRRGRRBBGGGRGRBBGBBRGGGGGBGGGRBBRBRRGBGRGRGBRRRGGGBRBGRGGBBRBGGRBGRBRBGBGRRGGRRGGGRGRGRBRGGRGBBGRGBGGGGGGBGRGBGBRGRBBRGBBRGGGRBBGGBGGGBBRGBRRRGRRBRGRBRBGBGRBBRRGRGBGGGGGRBGGBBGBRGGRRBGRGGGGGGGGGGGGGGBBGGGBRRGGBGGBGGRGGRGBRBGRRRRGRGBGBGGGRGGGRGGBRGGBGBRGBRRBGRGGRGRGBRGBBRGBBBGGGBGGGRGRGGGGBRGGGGBBGGGGGGRBGGGBRBBRGBRGBBBGRGBRGRGGGRBGGBRGRBBGBBRRGBRGBBGBGGBGGGGBRGGGGRRRGGGGGGRGRRGGGRRGGGGRBBGGGRGBBGRBBGGRGGBBGGGBGRGGBBBBGRGGGBRGGGGBGBGRGGGBBBGRRRBBBGGGBGGGGBGRRGGBGBBRGGGBRRGRGGGRBRGRRGGRRBGBGGRBGBGRGGRGBGRRRRBGGBGBGBGRBGGGBBGGGGGBBGGRBRGGRGGRGBGGRBGGRRGBGRBRRBGRGGRGGRGBGGGGGBRRGGBGRGRBGRGGRRGBGGRBRBGRRGBGGGGGGBBBGBGGBRGBGGBGGBGGRGGGBGRRGRGRGGRGGRGRGBBBGGRGBGGGBGGRGGRBRGBRGRRBBGRRGRGGBGGGRRRGGRBRGBGBBGBGGBGRGGBGBGGBRGBGGRRRGRGGRRRRGRGGGRGRGRBGGBGGGRGRRRRGBRGGGGBRBRRRBGGGGGRGRRBGGBGRBGBGGRGRBRBRGRGGGBGGGBGGGGGGGBRBRRBRGGRBGRRGGBGGGBR

[出力例]
32183632

[入力例]
2000
RBRRRGGGBRBRGBBGGBGGGRGGBGGGRGGRBBRRRGGRBGGGBGBGBBGBRBGRGBGBBRRRBRRGRGBRRBGBBBGRRGRGGRRBBGGGGRBGBGBRBRBRRRBBGBRBBRGRBGRRRBRGBRBBGBGBGGBBBRBGBBBBBGGRGRGBBRGBBBRRGBGBBRGBGRBBBRBRBGGRGGRRBRBBBBBGRRRBGRGBBBRRBRBGGRBBBRRBGBGBBBBGRRGRBBBGGGBGBGGGBRRBRGRRBBRBRBRGRRBGGBBBBBBRRRGRBRRBRGGBBGBRRGGBBBRBGBBGBGBBGBRRRRRGBRBGRBRBGGBRGRBBRRGBBGGGRRGRBRRGGRGBGRBGGGGRRBRRRGBRRGRGRBGRRGRRGRBBRBRGBRGGRRBGGRBRBGGRGBBBRRGBBRGBBGRBGRRRBRRBRRGRGRGGGGBRGBBRRGBBBRBRRBRRRGRBRGBGRGRRRRRBGRGRGBRBGRRBGGRRRBGRRGBRBGRGRBBBGRRBGRRBGGRBRGGBRBBGBGRGBRRRBRBRGBGBRGGGBGRRBRRBBBGRBBRGRBBGRBGRBBBBRBRGGRBGRGRGRGGRBBGBGGBBBGGGRRGGBRRBGRGRBBBRBBRRGRRGGBGRBBRBBGGBRRGRRBRBGRBRGRGGGGBBGRRRBBRBRGGRGRBBRBGBRRBGGBGGRBGRBGGGRGRRBBRBBRBBGBBBRBGGRRBGGBBBRRRBGBGGBBBGBBGRBRRGGGRGRGRBRRRRBGGRGRGRRGRBRBGGBRBGBGBRBBRRBRBGRBRBGRBBRGGRBGRBRBRGGBGBGGGRBBRRGBRGRBGGBBRRBBRGGRGGGGRRRGRBGRGRBGRBRGBBRRRRGBRRGGBGGRRBRGRBGBGBGRGGGBBRBGRGRBRGGGBGGBGBGRRBRBRBRGRGRGRGRGRBGRBGRGBRBRBBBBBGBRGRGBGBGBGBGBGGBRGBGBGGGRGGBRBGBGGRBBBRRGGBRBBBGBBBBRGRRRBBBRGGRRBBBBBRGGBGGGRGBGGBRRGBRGBBBRRBBBGBBGGRRRGGRRGRRRBRBBGGBGBGGGRGBRBBRGRRRRGGRGBBRRGBRRRGBGRRRBBGRRGRRRGRRRRBGRGBGRRGBRGBGGGBGGRGGRBGGBRGRBBBRRRGRRGGRBGRRRGBGBBBRGRBRRRBRBBGGRGRRBBGRGRGBBRBGGGBBRBRBRBRGGBRRRGBBGBRRGBBGRRRGBBBGGRGGBBRRGBBRBRGGBGBRRRGGBBRBBGGBGRBRBRRRGBRBRBRBGRBBRBRRBRBRRGGGBBBGRGBRRGBRGRBRGGRRBBBBBRBGBBBBGBRRRRGGRBBBRGGBGRRGBGBRRBGGRGRGGBBRGBGBGBGRGGGRGGRRGGRRGBBRBGGRBRGGBRBGGGRGBBBBBRBBBBBGGGGGBRGGRBRBGBRRGRGRRGGBGBGRGGBBBRGGBBBGGGGBGRBBBRRGBBBBBGGBGRBBBBGBBRGBGBBGGRBRRGGBRRBRRRGBGRBRBBGBGRGGRRGRRGRRBBGBBRGBRGRBBGBBRBRRGRGBBRBRGRBGGRRGBRBRBGRGRRRGRRRRRGBRBRRGGGBGBGBBRGGGGRGBGRRRRRRBBGBBBBGGBBRRGRGGGRGBGRBRBBGRRGRGGRBBGRGRBRBBGGBGGGBRRBRGGRGGGBGBGBBRBGBBBGRBRBRGGRRGGGGGGGBRRGGRRGRRGBGRBGRRGRGGGRGGRRBGGBBGBRBRRBBBGGGRRRRBGBBBRRBGRRGRBRRRBRGBRBRGBBBGGBGGBBRGRRRBBGBBBRGGGBGBRBGGGBGGGRBBBRRRRBRGGRBBRRRBBGBGRRGGRRBGGBBBBBBGRGRGRBGGRBGRGRBBGGBGGBBGGGBGRGGBBGRGRRBRBRRRRRGRBRGBRRGRGRRBRRRRRBGRBRGGBRBRRGRGRGBGRRBGRBGRGRBBBGBBRGRBRRBGRGBBGRRRRRRBGGRBBGRGRGGBBRGRRRBGRRBGRRGBGGBBRRRGBGR

[出力例]
295881790

[入力例]
4000
RGGRGBGBGRGGGBRRBRRGBGRGRRRGBRRGBBRGGRRGRBBRGGGRRBGRRRGRRBRGGBRRBBGBBBBRRRGGRRRRBGGGBGGBRRGRGGRGGRRBBRBGRBGBBBRRRGRGBGGBBRBBGGGGGBGGRRGRBGBRBGBGBGGBGRGGRGBBBGBGRBBRRBRGRBGBGBRRGBRBRGGBBRGGBBGBRBGBRBRBRGGBRBBRGRGBBBRRBBBBGGGRBBBGRBGRGRRGBGGRBGRGRGBRBRGGGGBRGRBGBRRGBBGBRGBRRGGGGGGGRRRGBBBGBBGGRBRGRBRRRBRRGGGBRBRGGGRGRGGRRGRBRRBGRGRBGGGGRGRGGBGGBGBGGRRGRRBBBRGGRRRGRBGGGGRGBGRBRRGBRBGGRBGBGGBRBGRBGGRBRGBBBGBGRBRBRGBRBRBGGBGRRGBRRRRBBRBGGBGBRRGBGGRRBRBBGBGBBBBGGGGBGGGBRRGRBBRBGRRRGRGBGBRBBGRGBGBGGGBRBBBRGGBGBGRGGRRBGRGGRBGBBGRGRGRBRGBBGGGBBBBGGRRRRRBBBGBBGRBBGBRGRRRGGBRGBBRBGBGBBBRGRRBBGGGRBBBBBRBRRGBBRGRBRRGGRBBRBGGGGGBGBRGRGGGRBRRGBGBRRRBRGGGRBGGRGGRGGGGGBRBGGGBRRBRRRRRRRBRGRRBGBRBBRBRRBGRBGBGGRGBGGRRGRGGGBGBRRGRBRBGBBRRRGGGRRBGGRBBBRBRRRGRRRBGRRRBGBRRGBBBRRRGBRGGRBRGGGRRRBBGGBBRGGRBGBGRRGBBBBGBBRBRGGGGBRRRGRRGBBBRBRBRBGRBRGBGGBRGGGGBGGBRGGRBGBGBBRBBRRBGRGRBRBRBRGRBRRBRRRRGRBGBRBBBGRRGGBGRBBBBRBBRRBRRRRBBGBRBRRGGGBRRBRRRRRRGRBRBRGRRRGBGRRRRBBRBBGGGGGBGRBBBBBGBRRBGRGRRBGGBBBRRRGRBGBGBRRBGBRRBRRRRBGGRGRGBRRBRGRGGGGGBRRGRGBGGBBBBBBBRRBRRRGBBRBGBRBRRBGBGRGGGRBBGBBGGGBBRRBBBBRBBGBRBBBGGRRRRRBRBRBBGRGGGRBRRGRBRGGBGBBRRRGRRBGGBGBGGRBRRRRRGRGGRBGRRGRGRRGGBGRRBRRBBGBRRRRGRGBRBGBRGBBBRGRBRRGGGRGBBGGGRBBRRGBGRRBGRRBGBRRGGBRRRRGBRGBRBGBGGBRRRBRRBRBBRGRBGRGGRRGGGGRGBRBGGGRBRGGGRGGRGGGGRRGRBBRBGRRRBRRGBBGGRBBBRRRBBBBBGBRGBRBRBRBRGRRGBGBRRGGRBRGBBRGBRGBRRRRRRRRGGRGRBGBGRBBRRBGGGGBBRGBRRBGGBRBBGRGRGRRRRBGBBBRBGRBBGGRGRRGBRBRRGGRGGGBGGBBBRGRBRBGBBGBRRGBGGBRGBRGRBGRGBBBGBGRGRGRBGBGRRRBGRBGRBRGRRBGBBGRGGBBGRBBGGBRBGGRRGRGBRBBBGRGGBRGBGGRRBBGBBGBGRBBBGRBBRBRGGRRRGRBGGBGGGGGRGRBBBRRBBRRBRGBGGBRBGRRGGRRGBGBGRBBBGBGGBBGBGBRBBGGBBGRBGRRBGRRRBRGGBGBRBGRGGRBBBGBGGRRGBRRBRGGBRGGBBGRBGRBBRRRBRRBGGRBGGBRGBGGRRBGGGRGBRBBRRBGBBBBBGBRGBBBBBBBRGBGRRBRBBBRBGRRRGBBRRGRBRRGRRGGBBRGRGGBBGRGRGRRRGBGBGGBGBBBGBGRRRBBRRRBGRRRRBGRRGRGRRBBBGBRRGBBRBGBBBRBBGGRGBRGRGRBRBRRRGRBGGGBBRBRRRBRBRRGGGGGBBBRBGRBGBBGGBBRGRBRGGBGBGBRGGRRGRRGGBBRGRGRBRGBBBBGRGBGBRBBGBBGRRGGBRRBGBRBGGGRGGBRBGBRBBRBRBBGBRGRGBBRRBRRBRRBRRBRGBGBRRRBBGGRBRGRRBGBGRRBGRBBGGBBBGGBRBGGGGBGRGGBGBGBRBBGGGGGGGGRGRGGRBRRRBGBBGBBRBGBBGGBRBGGBGGRGBRBBBGRGRBGGGGBGRRBBGRBBBGBBGBGRBRRBRRBGRRRGGRGRGBGBGBBBRGBBBGBGGBRGGRRGBRGRRGGGRGRBRBRBGBBBBBBRRRBGRGBGGBGGBRBRRGGRRRGRRBGBRGBRRRGGBBGBGBRBGBBRBGGRGGGGBGBGBGBBGBGBRRBRRRGGRGBGRBGGGGBRBRBRRBRGGBRBRRRRRBGGGBGRGRGGBRBBBBRGBBBRRGRGBBGGBRBBRGRBBRBRBRBRBGRRGBBGRRGRGGBGBGRBGBBRBGBGRRRGGRRRGRBRBGRBRRGBBBGGRGGRRBRRGGRBGGGBGBBRRBBRGBRRBGGRRRGBGBGBGBGBRGRGGBGRBRBBRGBGGGRBRBGBBGRBGRRBBGRRBGGGBGGBBRGRRRRRBRRBGBBRGBBBGBRBBGRGRRBRRBRGBBRGBGRGRRBGBGBRRBRGRRRGBRGRGBGBBGBRRBBRGGRGRRGBBRBBGRRBGRBRBRGBGBRBRRBGRRRGGGBRRBGRRRBRRBGRRBRRBGBGGRRRBBBGGBGGRBRGBRGGRGRBBGBRBBRGBGRGRBRGRRRGRBRRRBBBBGBBGRGBRRBRGRBRRBRRGRGGRGGGRBBRRBGGBGGRBGGGGBRBGBBBBRRRGRBRBBRGBBGGBGRGBRRBBRBRRRGRGGGRGGRRGBRBRRGGBBRBGBGGRGGBGRGBRBGRGBRRBGGRRBRRRGGGBGRGRRBGBRBRGRGBRGBRRGRGBBGGGBBRGRGBRRRRRGGGBBGBGRRBBBGGGRGRRRGBBRGRRGGBBRRRGGBGGBRBBBBBRGRBGGBGGGRGRGBBRBBGGGRGBGGGBGGBGGGGRGGBGRRGGGGRBGGRBRRBRBBBBBRGRGBBGBRBGBGRGGBBBRGBGGBGRGBGRRBRBGGRRBBRRGBGBRGBBRBGGGGBGBRBBRGGBGGBRRBBGRRRRRRBGRGBBGBBBRGGRBBBBRGRGRGBRBBGRGBGBBRGRRRGRRBRBGGRGRBBRRGGRRBGBBGBGBGGGGGBGBBRGBBBGBGRBRGGRBBGRBGGBRGBRGRBBRBBBBGRBBRGBRBBBBBGBRBGRRGGGBGBGBGGGRGGBRRGBRRRGBRGGGBGRGBGRGBBGBGBGBBBGGGRGBRBBGBRRBBBGRBBRRGRRBGBRRRRBBRGBGGRBGGGRBRRRRGRGBRBBBBGGRRRRGBRBRGRBBRRRRRRBGBRBRBBRGBGGBRBGGGRGRRGBRBRGRRRRGRRGGRBRGGGBGBGRBGRBRGBGGGBBBBRRBGGGRRBRRBBBGRGGGGGGRBGGRBGRGGBBRGRBRGGBRGBRBGGGBGRRGBBGBRGGRBBGGRGBRGGBGGRGBRBGRBBRBGGBRRGRBBRBBGRGBBGBGBGGBGGRRGGBBBRRBGRRRRBRGBRBGBBRGBGRGGGGRGGBBBGRBRBBBGBRRBGRRGRRRRGRRGRRRBGRRRRGRBGGRBGRBRRRRGBRGGGGBGBBBBRRRGBBBGBBBGBBBRGBBRGRGBRBBGBGBBGBGGRGBGGGRRBBBBRBBGBRGGBGBBRBBGRBRBRRBGBRBGRGBRRBGGRRRRRGRGRBRBBRBRGRRGBRRBGGRBRGBGBGGGRGRBBRGGBBBRBRRBGGBGBBGGRRGRRBRGRBGBGRBGRBRBRRRGGGGGBBRRRBBGBGRGBGBGGRRBBRRBRGBGBRBBRRBGGBBRGBRBRBBRBBBRBBRBRGBRRRRGRGRGBRRRGBRRRRRGGRRRGBBRGRGGBBRRBRRGGBBBRRRBGBGBBGBBBGBRRRRBBRRGBRBGGBGRBRBBGRBGBBGGBBRGBBGBRGGRRGRGGGBBRGRRRGBRRRBGBRRGBGGRGRGRRRGGRRBGRGBRRRRBBRGBRGGGRBGBGBBBGGRBBRRGBRRBRBBGBBBBGRRGGGGRRGBRRRG

[出力例]
2369278004

[入力例]

RRGB

[出力例]

※AtCoderテストケースより

[入力例]

RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

[出力例]

1800

※AtCoderテストケースより

[入力例]

RGB

[出力例]

[入力例]

1000

GGRGBRRGBGBRGBGRGBGRGBGRGRRBBRGGRRGRGBBGGGBGRGRRBRGGBRBGGRBRGBBRGGBRBGRRGGRGGGBBGBGBBBRRBBGGGGGBBBGBGGGGBBGRBRBGGGRRGRGGRBRBRGGBGGRGBRRBBGRBGRGBBRBRRBGRGRRGBGBGGRRGRRBBGGGRGRBBGBBRGGGGGBGGGRBBRBRRGBGRGRGBRRRGGGBRBGRGGBBRBGGRBGRBRBGBGRRGGRRGGGRGRGRBRGGRGBBGRGBGGGGGGBGRGBGBRGRBBRGBBRGGGRBBGGBGGGBBRGBRRRGRRBRGRBRBGBGRBBRRGRGBGGGGGRBGGBBGBRGGRRBGRGGGGGGGGGGGGGGBBGGGBRRGGBGGBGGRGGRGBRBGRRRRGRGBGBGGGRGGGRGGBRGGBGBRGBRRBGRGGRGRGBRGBBRGBBBGGGBGGGRGRGGGGBRGGGGBBGGGGGGRBGGGBRBBRGBRGBBBGRGBRGRGGGRBGGBRGRBBGBBRRGBRGBBGBGGBGGGGBRGGGGRRRGGGGGGRGRRGGGRRGGGGRBBGGGRGBBGRBBGGRGGBBGGGBGRGGBBBBGRGGGBRGGGGBGBGRGGGBBBGRRRBBBGGGBGGGGBGRRGGBGBBRGGGBRRGRGGGRBRGRRGGRRBGBGGRBGBGRGGRGBGRRRRBGGBGBGBGRBGGGBBGGGGGBBGGRBRGGRGGRGBGGRBGGRRGBGRBRRBGRGGRGGRGBGGGGGBRRGGBGRGRBGRGGRRGBGGRBRBGRRGBGGGGGGBBBGBGGBRGBGGBGGBGGRGGGBGRRGRGRGGRGGRGRGBBBGGRGBGGGBGGRGGRBRGBRGRRBBGRRGRGGBGGGRRRGGRBRGBGBBGBGGBGRGGBGBGGBRGBGGRRRGRGGRRRRGRGGGRGRGRBGGBGGGRGRRRRGBRGGGGBRBRRRBGGGGGRGRRBGGBGRBGBGGRGRBRBRGRGGGBGGGBGGGGGGGBRBRRBRGGRBGRRGGBGGGBR

[出力例]

32183632

[入力例]

2000

RBRRRGGGBRBRGBBGGBGGGRGGBGGGRGGRBBRRRGGRBGGGBGBGBBGBRBGRGBGBBRRRBRRGRGBRRBGBBBGRRGRGGRRBBGGGGRBGBGBRBRBRRRBBGBRBBRGRBGRRRBRGBRBBGBGBGGBBBRBGBBBBBGGRGRGBBRGBBBRRGBGBBRGBGRBBBRBRBGGRGGRRBRBBBBBGRRRBGRGBBBRRBRBGGRBBBRRBGBGBBBBGRRGRBBBGGGBGBGGGBRRBRGRRBBRBRBRGRRBGGBBBBBBRRRGRBRRBRGGBBGBRRGGBBBRBGBBGBGBBGBRRRRRGBRBGRBRBGGBRGRBBRRGBBGGGRRGRBRRGGRGBGRBGGGGRRBRRRGBRRGRGRBGRRGRRGRBBRBRGBRGGRRBGGRBRBGGRGBBBRRGBBRGBBGRBGRRRBRRBRRGRGRGGGGBRGBBRRGBBBRBRRBRRRGRBRGBGRGRRRRRBGRGRGBRBGRRBGGRRRBGRRGBRBGRGRBBBGRRBGRRBGGRBRGGBRBBGBGRGBRRRBRBRGBGBRGGGBGRRBRRBBBGRBBRGRBBGRBGRBBBBRBRGGRBGRGRGRGGRBBGBGGBBBGGGRRGGBRRBGRGRBBBRBBRRGRRGGBGRBBRBBGGBRRGRRBRBGRBRGRGGGGBBGRRRBBRBRGGRGRBBRBGBRRBGGBGGRBGRBGGGRGRRBBRBBRBBGBBBRBGGRRBGGBBBRRRBGBGGBBBGBBGRBRRGGGRGRGRBRRRRBGGRGRGRRGRBRBGGBRBGBGBRBBRRBRBGRBRBGRBBRGGRBGRBRBRGGBGBGGGRBBRRGBRGRBGGBBRRBBRGGRGGGGRRRGRBGRGRBGRBRGBBRRRRGBRRGGBGGRRBRGRBGBGBGRGGGBBRBGRGRBRGGGBGGBGBGRRBRBRBRGRGRGRGRGRBGRBGRGBRBRBBBBBGBRGRGBGBGBGBGBGGBRGBGBGGGRGGBRBGBGGRBBBRRGGBRBBBGBBBBRGRRRBBBRGGRRBBBBBRGGBGGGRGBGGBRRGBRGBBBRRBBBGBBGGRRRGGRRGRRRBRBBGGBGBGGGRGBRBBRGRRRRGGRGBBRRGBRRRGBGRRRBBGRRGRRRGRRRRBGRGBGRRGBRGBGGGBGGRGGRBGGBRGRBBBRRRGRRGGRBGRRRGBGBBBRGRBRRRBRBBGGRGRRBBGRGRGBBRBGGGBBRBRBRBRGGBRRRGBBGBRRGBBGRRRGBBBGGRGGBBRRGBBRBRGGBGBRRRGGBBRBBGGBGRBRBRRRGBRBRBRBGRBBRBRRBRBRRGGGBBBGRGBRRGBRGRBRGGRRBBBBBRBGBBBBGBRRRRGGRBBBRGGBGRRGBGBRRBGGRGRGGBBRGBGBGBGRGGGRGGRRGGRRGBBRBGGRBRGGBRBGGGRGBBBBBRBBBBBGGGGGBRGGRBRBGBRRGRGRRGGBGBGRGGBBBRGGBBBGGGGBGRBBBRRGBBBBBGGBGRBBBBGBBRGBGBBGGRBRRGGBRRBRRRGBGRBRBBGBGRGGRRGRRGRRBBGBBRGBRGRBBGBBRBRRGRGBBRBRGRBGGRRGBRBRBGRGRRRGRRRRRGBRBRRGGGBGBGBBRGGGGRGBGRRRRRRBBGBBBBGGBBRRGRGGGRGBGRBRBBGRRGRGGRBBGRGRBRBBGGBGGGBRRBRGGRGGGBGBGBBRBGBBBGRBRBRGGRRGGGGGGGBRRGGRRGRRGBGRBGRRGRGGGRGGRRBGGBBGBRBRRBBBGGGRRRRBGBBBRRBGRRGRBRRRBRGBRBRGBBBGGBGGBBRGRRRBBGBBBRGGGBGBRBGGGBGGGRBBBRRRRBRGGRBBRRRBBGBGRRGGRRBGGBBBBBBGRGRGRBGGRBGRGRBBGGBGGBBGGGBGRGGBBGRGRRBRBRRRRRGRBRGBRRGRGRRBRRRRRBGRBRGGBRBRRGRGRGBGRRBGRBGRGRBBBGBBRGRBRRBGRGBBGRRRRRRBGGRBBGRGRGGBBRGRRRBGRRBGRRGBGGBBRRRGBGR

[出力例]

295881790

[入力例]

4000

RGGRGBGBGRGGGBRRBRRGBGRGRRRGBRRGBBRGGRRGRBBRGGGRRBGRRRGRRBRGGBRRBBGBBBBRRRGGRRRRBGGGBGGBRRGRGGRGGRRBBRBGRBGBBBRRRGRGBGGBBRBBGGGGGBGGRRGRBGBRBGBGBGGBGRGGRGBBBGBGRBBRRBRGRBGBGBRRGBRBRGGBBRGGBBGBRBGBRBRBRGGBRBBRGRGBBBRRBBBBGGGRBBBGRBGRGRRGBGGRBGRGRGBRBRGGGGBRGRBGBRRGBBGBRGBRRGGGGGGGRRRGBBBGBBGGRBRGRBRRRBRRGGGBRBRGGGRGRGGRRGRBRRBGRGRBGGGGRGRGGBGGBGBGGRRGRRBBBRGGRRRGRBGGGGRGBGRBRRGBRBGGRBGBGGBRBGRBGGRBRGBBBGBGRBRBRGBRBRBGGBGRRGBRRRRBBRBGGBGBRRGBGGRRBRBBGBGBBBBGGGGBGGGBRRGRBBRBGRRRGRGBGBRBBGRGBGBGGGBRBBBRGGBGBGRGGRRBGRGGRBGBBGRGRGRBRGBBGGGBBBBGGRRRRRBBBGBBGRBBGBRGRRRGGBRGBBRBGBGBBBRGRRBBGGGRBBBBBRBRRGBBRGRBRRGGRBBRBGGGGGBGBRGRGGGRBRRGBGBRRRBRGGGRBGGRGGRGGGGGBRBGGGBRRBRRRRRRRBRGRRBGBRBBRBRRBGRBGBGGRGBGGRRGRGGGBGBRRGRBRBGBBRRRGGGRRBGGRBBBRBRRRGRRRBGRRRBGBRRGBBBRRRGBRGGRBRGGGRRRBBGGBBRGGRBGBGRRGBBBBGBBRBRGGGGBRRRGRRGBBBRBRBRBGRBRGBGGBRGGGGBGGBRGGRBGBGBBRBBRRBGRGRBRBRBRGRBRRBRRRRGRBGBRBBBGRRGGBGRBBBBRBBRRBRRRRBBGBRBRRGGGBRRBRRRRRRGRBRBRGRRRGBGRRRRBBRBBGGGGGBGRBBBBBGBRRBGRGRRBGGBBBRRRGRBGBGBRRBGBRRBRRRRBGGRGRGBRRBRGRGGGGGBRRGRGBGGBBBBBBBRRBRRRGBBRBGBRBRRBGBGRGGGRBBGBBGGGBBRRBBBBRBBGBRBBBGGRRRRRBRBRBBGRGGGRBRRGRBRGGBGBBRRRGRRBGGBGBGGRBRRRRRGRGGRBGRRGRGRRGGBGRRBRRBBGBRRRRGRGBRBGBRGBBBRGRBRRGGGRGBBGGGRBBRRGBGRRBGRRBGBRRGGBRRRRGBRGBRBGBGGBRRRBRRBRBBRGRBGRGGRRGGGGRGBRBGGGRBRGGGRGGRGGGGRRGRBBRBGRRRBRRGBBGGRBBBRRRBBBBBGBRGBRBRBRBRGRRGBGBRRGGRBRGBBRGBRGBRRRRRRRRGGRGRBGBGRBBRRBGGGGBBRGBRRBGGBRBBGRGRGRRRRBGBBBRBGRBBGGRGRRGBRBRRGGRGGGBGGBBBRGRBRBGBBGBRRGBGGBRGBRGRBGRGBBBGBGRGRGRBGBGRRRBGRBGRBRGRRBGBBGRGGBBGRBBGGBRBGGRRGRGBRBBBGRGGBRGBGGRRBBGBBGBGRBBBGRBBRBRGGRRRGRBGGBGGGGGRGRBBBRRBBRRBRGBGGBRBGRRGGRRGBGBGRBBBGBGGBBGBGBRBBGGBBGRBGRRBGRRRBRGGBGBRBGRGGRBBBGBGGRRGBRRBRGGBRGGBBGRBGRBBRRRBRRBGGRBGGBRGBGGRRBGGGRGBRBBRRBGBBBBBGBRGBBBBBBBRGBGRRBRBBBRBGRRRGBBRRGRBRRGRRGGBBRGRGGBBGRGRGRRRGBGBGGBGBBBGBGRRRBBRRRBGRRRRBGRRGRGRRBBBGBRRGBBRBGBBBRBBGGRGBRGRGRBRBRRRGRBGGGBBRBRRRBRBRRGGGGGBBBRBGRBGBBGGBBRGRBRGGBGBGBRGGRRGRRGGBBRGRGRBRGBBBBGRGBGBRBBGBBGRRGGBRRBGBRBGGGRGGBRBGBRBBRBRBBGBRGRGBBRRBRRBRRBRRBRGBGBRRRBBGGRBRGRRBGBGRRBGRBBGGBBBGGBRBGGGGBGRGGBGBGBRBBGGGGGGGGRGRGGRBRRRBGBBGBBRBGBBGGBRBGGBGGRGBRBBBGRGRBGGGGBGRRBBGRBBBGBBGBGRBRRBRRBGRRRGGRGRGBGBGBBBRGBBBGBGGBRGGRRGBRGRRGGGRGRBRBRBGBBBBBBRRRBGRGBGGBGGBRBRRGGRRRGRRBGBRGBRRRGGBBGBGBRBGBBRBGGRGGGGBGBGBGBBGBGBRRBRRRGGRGBGRBGGGGBRBRBRRBRGGBRBRRRRRBGGGBGRGRGGBRBBBBRGBBBRRGRGBBGGBRBBRGRBBRBRBRBRBGRRGBBGRRGRGGBGBGRBGBBRBGBGRRRGGRRRGRBRBGRBRRGBBBGGRGGRRBRRGGRBGGGBGBBRRBBRGBRRBGGRRRGBGBGBGBGBRGRGGBGRBRBBRGBGGGRBRBGBBGRBGRRBBGRRBGGGBGGBBRGRRRRRBRRBGBBRGBBBGBRBBGRGRRBRRBRGBBRGBGRGRRBGBGBRRBRGRRRGBRGRGBGBBGBRRBBRGGRGRRGBBRBBGRRBGRBRBRGBGBRBRRBGRRRGGGBRRBGRRRBRRBGRRBRRBGBGGRRRBBBGGBGGRBRGBRGGRGRBBGBRBBRGBGRGRBRGRRRGRBRRRBBBBGBBGRGBRRBRGRBRRBRRGRGGRGGGRBBRRBGGBGGRBGGGGBRBGBBBBRRRGRBRBBRGBBGGBGRGBRRBBRBRRRGRGGGRGGRRGBRBRRGGBBRBGBGGRGGBGRGBRBGRGBRRBGGRRBRRRGGGBGRGRRBGBRBRGRGBRGBRRGRGBBGGGBBRGRGBRRRRRGGGBBGBGRRBBBGGGRGRRRGBBRGRRGGBBRRRGGBGGBRBBBBBRGRBGGBGGGRGRGBBRBBGGGRGBGGGBGGBGGGGRGGBGRRGGGGRBGGRBRRBRBBBBBRGRGBBGBRBGBGRGGBBBRGBGGBGRGBGRRBRBGGRRBBRRGBGBRGBBRBGGGGBGBRBBRGGBGGBRRBBGRRRRRRBGRGBBGBBBRGGRBBBBRGRGRGBRBBGRGBGBBRGRRRGRRBRBGGRGRBBRRGGRRBGBBGBGBGGGGGBGBBRGBBBGBGRBRGGRBBGRBGGBRGBRGRBBRBBBBGRBBRGBRBBBBBGBRBGRRGGGBGBGBGGGRGGBRRGBRRRGBRGGGBGRGBGRGBBGBGBGBBBGGGRGBRBBGBRRBBBGRBBRRGRRBGBRRRRBBRGBGGRBGGGRBRRRRGRGBRBBBBGGRRRRGBRBRGRBBRRRRRRBGBRBRBBRGBGGBRBGGGRGRRGBRBRGRRRRGRRGGRBRGGGBGBGRBGRBRGBGGGBBBBRRBGGGRRBRRBBBGRGGGGGGRBGGRBGRGGBBRGRBRGGBRGBRBGGGBGRRGBBGBRGGRBBGGRGBRGGBGGRGBRBGRBBRBGGBRRGRBBRBBGRGBBGBGBGGBGGRRGGBBBRRBGRRRRBRGBRBGBBRGBGRGGGGRGGBBBGRBRBBBGBRRBGRRGRRRRGRRGRRRBGRRRRGRBGGRBGRBRRRRGBRGGGGBGBBBBRRRGBBBGBBBGBBBRGBBRGRGBRBBGBGBBGBGGRGBGGGRRBBBBRBBGBRGGBGBBRBBGRBRBRRBGBRBGRGBRRBGGRRRRRGRGRBRBBRBRGRRGBRRBGGRBRGBGBGGGRGRBBRGGBBBRBRRBGGBGBBGGRRGRRBRGRBGBGRBGRBRBRRRGGGGGBBRRRBBGBGRGBGBGGRRBBRRBRGBGBRBBRRBGGBBRGBRBRBBRBBBRBBRBRGBRRRRGRGRGBRRRGBRRRRRGGRRRGBBRGRGGBBRRBRRGGBBBRRRBGBGBBGBBBGBRRRRBBRRGBRBGGBGRBRBBGRBGBBGGBBRGBBGBRGGRRGRGGGBBRGRRRGBRRRBGBRRGBGGRGRGRRRGGRRBGRGBRRRRBBRGBRGGGRBGBGBBBGGRBBRRGBRRBRBBGBBBBGRRGGGGRRGBRRRG

[出力例]

2369278004

■参照サイト
AtCoder Beginner Contest 162

2020年4月12日2020年4月12日

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

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

■感想.
1. D + L ＜ X * Y のパターンが, 非常に難しく, 実装方針を固めるまでに苦労した.
2. 社員室の区画について, 上下左右を外した集合を考えてから, 集計したところ, AC版（101点）となったので, 良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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 = 2020;
LL FAC[LIMIT], 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 R, C, X, Y, D, L;
    scanf("%lld %lld %lld %lld %lld %lld", &R, &C, &X, &Y, &D, &L);
    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. デスクとサーバーラックの配置を検証.
    // 2-1. D + L == X * Y の 場合.
    LL ans = 0;
    if(D + L == X * Y){
        // 左上の配置を変えていく.
        rep(i, R - X + 1) rep(j, C - Y + 1) ans += combination(X * Y, D), ans %= MOD;
    }
    
    // 2-2. D + L < X * Y の 場合.
    if(D + L < X * Y){
        // 左上の配置を変えていく.
        rep(i, R - X + 1){
            rep(j, C - Y + 1){
                // 全通り.
                // (X * Y)箇所     から D個 を 選択して配置.
                // (X * Y - D)箇所 から L個 を 選択して配置.
                LL all = combination(X * Y, D) * combination(X * Y - D, L) % MOD;
                
                // 条件を満たさない配置を洗い出す.
                // デスクとサーバーラックを配置しない方向について, 
                // u: 上, d: 下, l: 左, r: 右 として,
                LL u = combination(X * Y - Y, D) * combination(X * Y - Y - D, L) % MOD;
                LL d = combination(X * Y - Y, D) * combination(X * Y - Y - D, L) % MOD;
                LL l = combination(X * Y - X, D) * combination(X * Y - X - D, L) % MOD;
                LL r = combination(X * Y - X, D) * combination(X * Y - X - D, L) % MOD;
                
                // ud: 上下, ul: 上左, ur: 上右, dl: 下左, dr: 下右, lr: 左右.
                LL ud = combination(X * Y - Y - Y,     D) * combination(X * Y - Y - Y - D,     L) % MOD;
                LL ul = combination(X * Y - Y - X + 1, D) * combination(X * Y - Y - X + 1 - D, L) % MOD;
                LL ur = combination(X * Y - Y - X + 1, D) * combination(X * Y - Y - X + 1 - D, L) % MOD;
                LL dl = combination(X * Y - Y - X + 1, D) * combination(X * Y - Y - X + 1 - D, L) % MOD;
                LL dr = combination(X * Y - Y - X + 1, D) * combination(X * Y - Y - X + 1 - D, L) % MOD;
                LL lr = combination(X * Y - X - X,     D) * combination(X * Y - X - X - D,     L) % MOD;
                
                // ulr: 上左右, udl: 上下左, udr: 上下右, dlr: 下左右.
                LL ulr = combination(X * Y - Y - X - X + 2, D) * combination(X * Y - Y - X - X + 2 - D, L) % MOD;
                LL udl = combination(X * Y - Y - Y - X + 2, D) * combination(X * Y - Y - Y - X + 2 - D, L) % MOD;
                LL udr = combination(X * Y - Y - Y - X + 2, D) * combination(X * Y - Y - Y - X + 2 - D, L) % MOD;
                LL dlr = combination(X * Y - Y - X - X + 2, D) * combination(X * Y - Y - X - X + 2 - D, L) % MOD;
                
                // udlr: 上下左右.
                LL udlr = combination(X * Y - Y - Y - X - X + 4, D) * combination(X * Y - Y - Y - X - X + 4 - D, L) % MOD;
                
                // 集計.
                LL cur = all;
                cur += MOD, cur -= u, cur %= MOD;
                cur += MOD, cur -= d, cur %= MOD;
                cur += MOD, cur -= l, cur %= MOD;
                cur += MOD, cur -= r, cur %= MOD;
                cur += ud, cur %= MOD;
                cur += ul, cur %= MOD;
                cur += ur, cur %= MOD;
                cur += dl, cur %= MOD;
                cur += dr, cur %= MOD;
                cur += lr, cur %= MOD;
                cur += MOD, cur -= ulr, cur %= MOD;
                cur += MOD, cur -= udl, cur %= MOD;
                cur += MOD, cur -= udr, cur %= MOD;
                cur += MOD, cur -= dlr, cur %= MOD;
                cur += udlr, cur %= MOD;
                
                // 加算.
                ans += cur, ans %= MOD;
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

#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 = 2020;

LL FAC[LIMIT], 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 R, C, X, Y, D, L;

scanf("%lld %lld %lld %lld %lld %lld", &R, &C, &X, &Y, &D, &L);

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. デスクとサーバーラックの配置を検証.

// 2-1. D + L == X * Y の場合.

LL ans = 0;

if(D + L == X * Y){

// 左上の配置を変えていく.

rep(i, R - X + 1) rep(j, C - Y + 1) ans += combination(X * Y, D), ans %= MOD;

}

// 2-2. D + L < X * Y の場合.

if(D + L < X * Y){

// 左上の配置を変えていく.

rep(i, R - X + 1){

rep(j, C - Y + 1){

// 全通り.

// (X * Y)箇所から D個を選択して配置.

// (X * Y - D)箇所から L個を選択して配置.

LL all = combination(X * Y, D) * combination(X * Y - D, L) % MOD;

// 条件を満たさない配置を洗い出す.

// デスクとサーバーラックを配置しない方向について,

// u: 上, d: 下, l: 左, r: 右として,

LL u = combination(X * Y - Y, D) * combination(X * Y - Y - D, L) % MOD;

LL d = combination(X * Y - Y, D) * combination(X * Y - Y - D, L) % MOD;

LL l = combination(X * Y - X, D) * combination(X * Y - X - D, L) % MOD;

LL r = combination(X * Y - X, D) * combination(X * Y - X - D, L) % MOD;

// ud: 上下, ul: 上左, ur: 上右, dl: 下左, dr: 下右, lr: 左右.

LL ud = combination(X * Y - Y - Y, D) * combination(X * Y - Y - Y - D, L) % MOD;

LL ul = combination(X * Y - Y - X + 1, D) * combination(X * Y - Y - X + 1 - D, L) % MOD;

LL ur = combination(X * Y - Y - X + 1, D) * combination(X * Y - Y - X + 1 - D, L) % MOD;

LL dl = combination(X * Y - Y - X + 1, D) * combination(X * Y - Y - X + 1 - D, L) % MOD;

LL dr = combination(X * Y - Y - X + 1, D) * combination(X * Y - Y - X + 1 - D, L) % MOD;

LL lr = combination(X * Y - X - X, D) * combination(X * Y - X - X - D, L) % MOD;

// ulr: 上左右, udl: 上下左, udr: 上下右, dlr: 下左右.

LL ulr = combination(X * Y - Y - X - X + 2, D) * combination(X * Y - Y - X - X + 2 - D, L) % MOD;

LL udl = combination(X * Y - Y - Y - X + 2, D) * combination(X * Y - Y - Y - X + 2 - D, L) % MOD;

LL udr = combination(X * Y - Y - Y - X + 2, D) * combination(X * Y - Y - Y - X + 2 - D, L) % MOD;

LL dlr = combination(X * Y - Y - X - X + 2, D) * combination(X * Y - Y - X - X + 2 - D, L) % MOD;

// udlr: 上下左右.

LL udlr = combination(X * Y - Y - Y - X - X + 4, D) * combination(X * Y - Y - Y - X - X + 4 - D, L) % MOD;

// 集計.

LL cur = all;

cur += MOD, cur -= u, cur %= MOD;

cur += MOD, cur -= d, cur %= MOD;

cur += MOD, cur -= l, cur %= MOD;

cur += MOD, cur -= r, cur %= MOD;

cur += ud, cur %= MOD;

cur += ul, cur %= MOD;

cur += ur, cur %= MOD;

cur += dl, cur %= MOD;

cur += dr, cur %= MOD;

cur += lr, cur %= MOD;

cur += MOD, cur -= ulr, cur %= MOD;

cur += MOD, cur -= udl, cur %= MOD;

cur += MOD, cur -= udr, cur %= MOD;

cur += MOD, cur -= dlr, cur %= MOD;

cur += udlr, cur %= MOD;

// 加算.

ans += cur, ans %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
3 2
2 2
2 2

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

[入力例]
4 5
3 1
3 0

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

[入力例]
23 18
15 13
100 95

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

[入力例]
30 30
24 22
145 132

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

[入力例]
1 1
1 1
1 0

[出力例]
1

[入力例]
2 1
1 1
1 0

[出力例]
2

[入力例]
7 5
2 3
1 1

[出力例]
72

[入力例]
21 23
19 17
100 123

[出力例]
844610938

[入力例]
25 28
18 20
111 222

[出力例]
945783731

[入力例]
30 30
25 27
189 202

[出力例]
638825258

[入力例]

3 2

2 2

[出力例]

※AtCoderテストケースより

[入力例]

4 5

3 1

3 0

[出力例]

※AtCoderテストケースより

[入力例]

23 18

15 13

100 95

[出力例]

364527243

※AtCoderテストケースより

[入力例]

30 30

24 22

145 132

[出力例]

976668549

※AtCoderテストケースより

[入力例]

1 1

1 0

[出力例]

[入力例]

2 1

1 1

1 0

[出力例]

[入力例]

7 5

2 3

1 1

[出力例]

[入力例]

21 23

19 17

100 123

[出力例]

844610938

[入力例]

25 28

18 20

111 222

[出力例]

945783731

[入力例]

30 30

25 27

189 202

[出力例]

638825258

■参照サイト
AtCoder Beginner Contest 003

2020年4月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 023 の問題C (C – 収集王) を解いてみた.

■感想.
1. 方針を決めるのに非常に苦戦したものの, 飴の置いてある場所を, 数え直しする方針で, AC版となったので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
LL ar[101010], ac[101010]; // 各行, 各列 の 飴の個数.
vector<P> v;

int main(){
    
    // 1. 入力情報.
    int R, C, N;
    LL K;
    scanf("%d %d %lld %d", &R, &C, &K, &N);
    rep(i, N){
        int r, c;
        scanf("%d %d", &r, &c);
        ar[r]++;
        ac[c]++;
        v.pb({r, c});
    }
    
    // 2. 各行, 各列 の 飴の個数 が, 合計K個 となるパターンは？
    LL ans = 0;
    map<LL, LL> mr, mc;
    repx(i, 1, R + 1) mr[ar[i]]++;
    repx(i, 1, C + 1) mc[ac[i]]++;
    for(auto i = mr.begin(); i != mr.end(); ++i){
        LL cKey = K - i->a, rValue = i->b;
        if(mc.count(cKey) > 0) ans += mc[cKey] * rValue;
    }
    
    // 3. 飴の置いてある場所について, 再度数え直し.
    // (ri, ci) が 合計K個       ならば, 減算.
    // (ri, ci) が 合計(K + 1)個 ならば, 加算.
    for(auto &p : v){
        int r = p.a, c = p.b;
        if(ar[r] + ac[c] == K)     ans--;
        if(ar[r] + ac[c] == K + 1) ans++;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

LL ar[101010], ac[101010]; // 各行, 各列の飴の個数.

vector<P> v;

int main(){

// 1. 入力情報.

int R, C, N;

LL K;

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

rep(i, N){

int r, c;

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

ar[r]++;

ac[c]++;

v.pb({r, c});

}

// 2. 各行, 各列の飴の個数が, 合計K個となるパターンは？

LL ans = 0;

map<LL, LL> mr, mc;

repx(i, 1, R + 1) mr[ar[i]]++;

repx(i, 1, C + 1) mc[ac[i]]++;

for(auto i = mr.begin(); i != mr.end(); ++i){

LL cKey = K - i->a, rValue = i->b;

if(mc.count(cKey) > 0) ans += mc[cKey] * rValue;

}

// 3. 飴の置いてある場所について, 再度数え直し.

// (ri, ci) が合計K個ならば, 減算.

// (ri, ci) が合計(K + 1)個ならば, 加算.

for(auto &p : v){

int r = p.a, c = p.b;

if(ar[r] + ac[c] == K) ans--;

if(ar[r] + ac[c] == K + 1) ans++;

}

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
16

[入力例]

3 5 3

1 2

2 1

2 5

3 2

3 5

[出力例]

※AtCoderテストケースより

[入力例]

7 3 1

3 2

3 3

4 2

4 3

[出力例]

※AtCoderテストケースより

[入力例]

5 5 2

1 1

2 2

3 3

4 4

5 5

[出力例]

※AtCoderテストケースより

[入力例]

16 10 5

2 2

2 4

16 10

6 2

4 9

6 4

16 4

13 1

11 6

10 6

7 9

8 9

8 4

13 6

10 3

[出力例]

■参照サイト
AtCoder Beginner Contest 023

C++の練習を兼ねて, AtCoder Regular Contest 023 の 問題C (C – タコヤ木) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 163 の 問題D (D – Sum of Large Numbers) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 022 の 問題C (C – ロミオとジュリエット) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 162 の 問題E (E – Sum of gcd of Tuples (Hard)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 023 の 問題A (A – 経過日数) ～ 問題B (B – 謎の人物X) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 022 の 問題A (A – スーパーICT高校生) ～ 問題B (B – 細長いお菓子) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 023 の 問題C (C – 収集王) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 023 の問題C (C – タコヤ木) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 163 の問題D (D – Sum of Large Numbers) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 022 の問題C (C – ロミオとジュリエット) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 162 の問題E (E – Sum of gcd of Tuples (Hard)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 023 の問題A (A – 経過日数) ～問題B (B – 謎の人物X) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 022 の問題A (A – スーパーICT高校生) ～問題B (B – 細長いお菓子) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 023 の問題C (C – 収集王) を解いてみた.