5月, 2020 | 個人用メモ帳

2020年5月17日

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

C++の練習を兼ねて, AtCoder Regular Contest 039 の問題A (A – B problem) ～問題B (高橋幼稚園) を解いてみた.

■感想.
1. 問題B は, 組み合わせに関する問題で, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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 A, B;
    scanf("%d %d", &A, &B);
    
    // 2. A, B の 各桁 を 確認.
    // ※ A, B ともに, 3桁であることに注意.
    int a100 = A / 100 * 100;        // 100 の 位.
    int a010 = (A - a100) / 10 * 10; // 10 の 位.
    int a001 = (A - a100 - a010);    // 1 の 位.
    int b100 = B / 100 * 100;        // 100 の 位.
    int b010 = (B - b100) / 10 * 10; // 10 の 位.
    int b001 = (B - b100 - b010);    // 1 の 位.
    // printf("%d %d %d %d %d %d\n", a100, a010, a001, b100, b010, b001);
    
    // 3. A - B の 最大値は？
    int ans = A - B;
    ans = max(ans, 900  + a010 + a001 - B);
    ans = max(ans, a100 +   90 + a001 - B);
    ans = max(ans, a100 + a010 +    9 - B);
    ans = max(ans, A                  - (100  + b010 + b001));
    ans = max(ans, A                  - (b100 +    0 + b001));
    ans = max(ans, A                  - (b100 + b010 +    0));
    
    // 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 A, B;

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

// 2. A, B の各桁を確認.

// ※ A, B ともに, 3桁であることに注意.

int a100 = A / 100 * 100; // 100 の位.

int a010 = (A - a100) / 10 * 10; // 10 の位.

int a001 = (A - a100 - a010); // 1 の位.

int b100 = B / 100 * 100; // 100 の位.

int b010 = (B - b100) / 10 * 10; // 10 の位.

int b001 = (B - b100 - b010); // 1 の位.

// printf("%d %d %d %d %d %d\n", a100, a010, a001, b100, b010, b001);

// 3. A - B の最大値は？

int ans = A - B;

ans = max(ans, 900 + a010 + a001 - B);

ans = max(ans, a100 + 90 + a001 - B);

ans = max(ans, a100 + a010 + 9 - B);

ans = max(ans, A - (100 + b010 + b001));

ans = max(ans, A - (b100 + 0 + b001));

ans = max(ans, A - (b100 + b010 + 0));

// 4. 出力.

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

return 0;

}

[入力例]
567 234

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

[入力例]
999 100

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

[入力例]
100 999

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

[入力例]
212 567

[出力例]
345

[入力例]
915 197

[出力例]
808

[入力例]
991 109

[出力例]
891

[入力例]

567 234

[出力例]

733

※AtCoderのテストケースより

[入力例]

999 100

[出力例]

899

※AtCoderのテストケースより

[入力例]

100 999

[出力例]

-99

※AtCoderのテストケースより

[入力例]

212 567

[出力例]

345

[入力例]

915 197

[出力例]

808

[入力例]

991 109

[出力例]

891

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

// C++14(GCC 5.4.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
const int LIMIT = 1010;
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 N, K;
    scanf("%lld %lld", &N, &K);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 2. キャンディを配る.
    LL q = K / N, r = K % N, ans = 0;
    // キャンディを, 1個以上配れるか否かで場合分けする.
    if(q){
        ans = combination(N, r);
    }else{
        ans = combination(N + r - 1, r);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++14(GCC 5.4.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

const int LIMIT = 1010;

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 N, K;

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

FAC[0] = 1;

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

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

// 2. キャンディを配る.

LL q = K / N, r = K % N, ans = 0;

// キャンディを, 1個以上配れるか否かで場合分けする.

if(q){

ans = combination(N, r);

}else{

ans = combination(N + r - 1, r);

}

// 3. 出力.

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

return 0;

}

[入力例]
4 10

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

[入力例]
100 450

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

[入力例]
5 2

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

[入力例]
4 3

[出力例]
20

[入力例]
23 456

[出力例]
8855

[入力例]
85 32

[出力例]
494039129

[入力例]
100 55

[出力例]
212868586

[入力例]
83 432

[出力例]
314160076

[入力例]

4 10

[出力例]

※AtCoderのテストケースより

[入力例]

100 450

[出力例]

538992043

※AtCoderのテストケースより

[入力例]

5 2

[出力例]

※AtCoderのテストケースより

[入力例]

4 3

[出力例]

[入力例]

23 456

[出力例]

8855

[入力例]

85 32

[出力例]

494039129

[入力例]

100 55

[出力例]

212868586

[入力例]

83 432

[出力例]

314160076

■参照サイト
AtCoder Regular Contest 039

2020年5月16日

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

C++の練習を兼ねて, AtCoder Regular Contest 037 の問題A (A – 全優) ～問題B (B – バウムテスト) を解いてみた.

■感想.
1. 問題B は, 木の個数を数える内容で, 個人的には, 面白いと感じた.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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 N;
    scanf("%d", &N);
    
    // 2. 最短の合計勉強時間.
    int ans = 0, m;
    rep(i, N){
        scanf("%d", &m);
        if(m < 80) ans += (80 - m);
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 最短の合計勉強時間.

int ans = 0, m;

rep(i, N){

scanf("%d", &m);

if(m < 80) ans += (80 - m);

}

// 3. 出力.

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

return 0;

}

[入力例]
5
70 90 60 80 50

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

[入力例]
6
100 100 100 100 100 100

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

[入力例]

70 90 60 80 50

[出力例]

※AtCoderのテストケースより

[入力例]

100 100 100 100 100 100

[出力例]

※AtCoderのテストケースより

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

// C++14(GCC 5.4.1)
#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 repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 111;
int connection[MAX]; // 連結成分番号.
int v[MAX];          // 頂点数.
int e[MAX];          // 辺数.
vvi G(MAX);          // グラフ.

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. バウムテストする.
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 3. 各頂点に対する連結成分番号を設定.
    int id = 0;
    rep(i, N) if(connection[i] == 0) bfs(G, i, ++id);
    // rep(i, N) printf("i=%d con=%d\n", i, connection[i]);
    
    // 4. 各連結成分の頂点数を保存.
    rep(i, N) v[connection[i]]++;
    
    // 5. 各連結成分の辺数を保存.
    rep(i, N) for(auto &p : G[i]) e[connection[p]]++;
    
    // 6. 木を抽出.
    int ans = 0;
    repx(i, 1, N + 1) if(v[i] == e[i] / 2 + 1) ans++;
    
    // 7. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++14(GCC 5.4.1)

#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 repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

const int MAX = 111;

int connection[MAX]; // 連結成分番号.

int v[MAX]; // 頂点数.

int e[MAX]; // 辺数.

vvi G(MAX); // グラフ.

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

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

// ※bfsの動作確認用.

// @param G: グラフ.

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

// @param l: 連結成分番号(※1以上).

// @return: 特に無し.

void bfs(vvi &G, int s, int l){

// 1. 空のキュー.

queue<int> q;

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

connection[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(connection[e] > 0) continue;

if(connection[e] == 0 && e != s) connection[e] = l, q.push(e);

}

return;

}

int main(){

// 1. 入力情報.

int N, M;

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

// 2. バウムテストする.

vvi G(N);

rep(i, M){

int u, v;

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

u--, v--;

G[u].pb(v);

G[v].pb(u);

}

// 3. 各頂点に対する連結成分番号を設定.

int id = 0;

rep(i, N) if(connection[i] == 0) bfs(G, i, ++id);

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

// 4. 各連結成分の頂点数を保存.

rep(i, N) v[connection[i]]++;

// 5. 各連結成分の辺数を保存.

rep(i, N) for(auto &p : G[i]) e[connection[p]]++;

// 6. 木を抽出.

int ans = 0;

repx(i, 1, N + 1) if(v[i] == e[i] / 2 + 1) ans++;

// 7. 出力.

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

return 0;

}

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

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

[入力例]
5 1
1 2

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

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

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

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

[出力例]
5

[入力例]

8 7

1 2

2 3

2 4

5 6

6 7

6 8

7 8

[出力例]

※AtCoderのテストケースより

[入力例]

5 1

1 2

[出力例]

※AtCoderのテストケースより

[入力例]

11 11

1 2

1 3

2 4

3 5

4 6

5 7

6 8

7 9

8 10

9 11

10 11

[出力例]

※AtCoderのテストケースより

[入力例]

16 11

1 2

1 3

4 5

6 7

6 8

6 9

10 11

10 12

12 13

14 15

15 16

[出力例]

■参照サイト
AtCoder Regular Contest 037

2020年5月16日2020年5月16日

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

C++の練習を兼ねて, AtCoder Regular Contest 036 の問題A (A – ぐっすり) ～問題B (B – 山のデータ) を解いてみた.

■感想.
1. 問題B は, AtCoder Grand Contest 040 の問題A (A – ><) によく似ていることを思い出せたので, AC版となったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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 N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 睡眠不足となるか判定.
    int t, cur = 0, one = 0, two = 0, ans = -1;
    rep(i, N){
        // 今回分を更新.
        scanf("%d", &t);
        cur = t;
        
        // 睡眠時間をチェック.
        if(i > 1){
            if(cur + one + two < K){
                ans = i + 1; // 睡眠不足になる最初の日.
                break;
            }
        }
        
        // 前回以前分を更新.
        two = one;
        one = cur;
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 睡眠不足となるか判定.

int t, cur = 0, one = 0, two = 0, ans = -1;

rep(i, N){

// 今回分を更新.

scanf("%d", &t);

cur = t;

// 睡眠時間をチェック.

if(i > 1){

if(cur + one + two < K){

ans = i + 1; // 睡眠不足になる最初の日.

break;

}

// 前回以前分を更新.

two = one;

one = cur;

}

// 3. 出力.

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

return 0;

}

[入力例]
5 1080
300
420
420
180
360

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

[入力例]
5 180
60
60
60
60
60

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

[入力例]
5 4230
360
360
360
360
360

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

[入力例]
10 222
66
77
88
99
88
77
66
55
66
77

[出力例]
8

[入力例]

5 1080

300

420

180

360

[出力例]

※AtCoderのテストケースより

[入力例]

5 180

[出力例]

-1

※AtCoderのテストケースより

[入力例]

5 4230

360

[出力例]

※AtCoderのテストケースより

[入力例]

10 222

[出力例]

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

// C++14(GCC 5.4.1)
// 以下を参考.
// https://atcoder.jp/contests/agc040/tasks/agc040_a
#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 h[303030], u[303030], d[303030];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &h[i]);
    
    // 2. 山の高さの増減を確認.
    rep(i, N)         if(h[i] < h[i + 1]) u[i + 1] = u[i] + 1;
    repr(i, N - 2, 0) if(h[i] > h[i + 1]) d[i] = d[i + 1] + 1;
    // rep(i, N) printf("u=%d d=%d\n", u[i], d[i]);
    
    // 3. 山の大きさの最大値を確認.
    int ans = 0;
    rep(i, N) ans = max(ans, u[i] + d[i] + 1);
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++14(GCC 5.4.1)

// 以下を参考.

// https://atcoder.jp/contests/agc040/tasks/agc040_a

#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 h[303030], u[303030], d[303030];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 山の高さの増減を確認.

rep(i, N) if(h[i] < h[i + 1]) u[i + 1] = u[i] + 1;

repr(i, N - 2, 0) if(h[i] > h[i + 1]) d[i] = d[i + 1] + 1;

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

// 3. 山の大きさの最大値を確認.

int ans = 0;

rep(i, N) ans = max(ans, u[i] + d[i] + 1);

// 4. 出力.

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

return 0;

}

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

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

[入力例]
7
90
70
50
30
20
10
5

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

[入力例]
1
1

[出力例]
1

[入力例]
10
1
2
8
9
7
5
11
18
17
15

[出力例]
6

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

■参照サイト
AtCoder Regular Contest 036
AtCoder Grand Contest 040

2020年5月14日

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

C++の練習を兼ねて, AtCoder Regular Contest 035 の問題A (A – 高橋くんと回文) ～問題B (B – アットコーダー王国のコンテスト事情) を解いてみた.

■感想.
1. 問題B は, 階乗を使う必要があることに気付けたので, AC版となったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    char c[1010];
    scanf("%s", c);
    
    // 2. 回文判定.
    int l = strlen(c);
    bool ok = true;
    rep(i, l / 2){
        // 2-1. 左右のいずれかに, '*' が 含まれる場合.
        if(c[i] == '*' || c[l - 1 - i] == '*') continue;
        
        // 2-2. 左右が異なる文字の場合.
        if(c[i] != c[l - 1 - i]){
            ok = false;
            break;
        }
    }
    // 3. 出力.
    printf("%s\n", ok ? "YES" : "NO");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

char c[1010];

scanf("%s", c);

// 2. 回文判定.

int l = strlen(c);

bool ok = true;

rep(i, l / 2){

// 2-1. 左右のいずれかに, '*' が含まれる場合.

if(c[i] == '*' || c[l - 1 - i] == '*') continue;

// 2-2. 左右が異なる文字の場合.

if(c[i] != c[l - 1 - i]){

ok = false;

break;

}

// 3. 出力.

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

return 0;

}

[入力例]
ab*

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

[入力例]
abc

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

[入力例]
a*bc*

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

[入力例]
***

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

[入力例]

ab*

[出力例]

YES

※AtCoderのテストケースより

[入力例]

abc

[出力例]

※AtCoderのテストケースより

[入力例]

a*bc*

[出力例]

YES

※AtCoderのテストケースより

[入力例]

***

[出力例]

YES

※AtCoderのテストケースより

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<LL, LL> m;
    rep(i, N){
        LL t;
        scanf("%lld", &t);
        m[t]++;
    }
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
        
    // 2. コンテストペナルティが最小となる解き方は？
    LL t = 0, p = 0, q = 1;
    for(auto &x : m){
        rep(i, x.b) t += x.a, p += t;
        q = q * FAC[x.b] % MOD;
    }
    
    // 3. 出力.
    printf("%lld\n%lld\n", p, q);
    return 0;
    
}

// C++14(GCC 5.4.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

#define b second

const LL MOD = 1e9 + 7;

const int LIMIT = 10101;

LL FAC[LIMIT];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<LL, LL> m;

rep(i, N){

LL t;

scanf("%lld", &t);

m[t]++;

}

FAC[0] = 1;

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

// 2. コンテストペナルティが最小となる解き方は？

LL t = 0, p = 0, q = 1;

for(auto &x : m){

rep(i, x.b) t += x.a, p += t;

q = q * FAC[x.b] % MOD;

}

// 3. 出力.

printf("%lld\n%lld\n", p, q);

return 0;

}

[入力例]
2
20
10

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

[入力例]
5
2
1
2
1
2

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

[入力例]
13
1
1
1
1
1
1
1
1
1
1
1
1
1

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

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

[出力例]
252
435456000

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

227020758

※AtCoderのテストケースより

[入力例]

[出力例]

252

435456000

■参照サイト
AtCoder Regular Contest 035

2020年5月13日2020年5月13日

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

C++の練習を兼ねて, AtCoder Regular Contest 034 の問題A (A – 首席) ～問題C (C – 約数かつ倍数) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 最終得点が高い受験生の最終得点は？
    int maxScore = 0;
    while(N){
        // 得点を集計.
        int a, b, c, d, e, score;
        scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
        score = 900 * (a + b + c + d) + 110 * e;
        
        // 最大値を更新.
        maxScore = max(maxScore, score);
        
        // decrement.
        N--;
    }
    
    // 3. 出力.
    double ans = (double)maxScore / 900.0;
    printf("%.12f\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 最終得点が高い受験生の最終得点は？

int maxScore = 0;

while(N){

// 得点を集計.

int a, b, c, d, e, score;

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

score = 900 * (a + b + c + d) + 110 * e;

// 最大値を更新.

maxScore = max(maxScore, score);

// decrement.

N--;

}

// 3. 出力.

double ans = (double)maxScore / 900.0;

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

return 0;

}

[入力例]
2
37 54 68 66 802
58 108 106 103 871

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

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

[入力例]
2
80 120 120 120 900
0 0 0 0 731

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

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

[入力例]

37 54 68 66 802

58 108 106 103 871

[出力例]

481.4555555555555555

※AtCoderのテストケースより

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

481.455555555556

[入力例]

80 120 120 120 900

0 0 0 0 731

[出力例]

550

※AtCoderのテストケースより

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

550.000000000000

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define pb push_back

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 条件を満たす正整数 x を 求める.
    vector<LL> v;
    LL x = max(N - 162LL, 1LL);
    while(x <= N){
        // f(x) を 計算.
        LL f = 0, a = x;
        while(a) f += (a % 10), a /= 10;
        
        // x + f(x) = N か？
        if(x + f == N) v.pb(x);
        
        // increment.
        x++;
    }
    
    // 3. 出力.
    printf("%d\n", v.size());
    for(auto &p : v) printf("%lld\n", p);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define pb push_back

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 条件を満たす正整数 x を求める.

vector<LL> v;

LL x = max(N - 162LL, 1LL);

while(x <= N){

// f(x) を計算.

LL f = 0, a = x;

while(a) f += (a % 10), a /= 10;

// x + f(x) = N か？

if(x + f == N) v.pb(x);

// increment.

x++;

}

// 3. 出力.

printf("%d\n", v.size());

for(auto &p : v) printf("%lld\n", p);

return 0;

}

[入力例]
8

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

[入力例]
101

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

[入力例]
108

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

[入力例]
2019

[出力例]
2
1995
2013

[入力例]
2020

[出力例]
1
2009

[入力例]
2021

[出力例]
2
1996
2014

[入力例]
1000000007

[出力例]
2
999999940
1000000003

[入力例]
10000000000007

[出力例]
3
9999999999895
9999999999904
10000000000003

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

101

[出力例]

100

※AtCoderのテストケースより

[入力例]

108

[出力例]

※AtCoderのテストケースより

[入力例]

2019

[出力例]

1995

2013

[入力例]

2020

[出力例]

2009

[入力例]

2021

[出力例]

1996

2014

[入力例]

1000000007

[出力例]

999999940

1000000003

[入力例]

10000000000007

[出力例]

9999999999895

9999999999904

10000000000003

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

// C++(GCC 9.2.1)
// 解き直し.
// https://www.slideshare.net/chokudai/arc034
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
const LL MOD = 1e9 + 7;
map<LL, LL> divisors;

// Efficient program to print all prime factors of a given number
// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
// 与えられた正整数についての素因数分解を計算.
// @param X: 素因数分解を行う整数.
// @return: 特に無し.
void div(LL X){
    
    // 1. X を 2で割り切れなくなるまで割っていく.
    while(X % 2 == 0) divisors[2]++, X >>= 1;
    
    // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    int c = 3;
    while(c <= sqrt(X)){
        while(X % c == 0){
            divisors[c]++;
            X /= c;
        }
        c += 2;
    }
    
    // 3. X が 2 より 大きな素数であれば, 追加.
    if(X > 2) divisors[X]++;
    
    // 4. 終了.
    return;
}

int main(){
    
    // 1. 入力情報.
    LL A, B;
    scanf("%lld %lld", &A, &B);
    
    // 2. 解説通り.
    // -> A! / B! を 考え, (B + 1) ～ A までの正整数について, 素因数分解する.
    int N = (int)(A - B);
    repx(i, 1, N + 1) div(B + (LL)i);
    
    // 3. 数え上げる.
    LL ans = 1;
    for(auto &p : divisors) ans *= (p.b + 1), ans %= MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

#define b second

const LL MOD = 1e9 + 7;

map<LL, LL> divisors;

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

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

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

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

// @return: 特に無し.

void div(LL X){

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

while(X % 2 == 0) divisors[2]++, X >>= 1;

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

int c = 3;

while(c <= sqrt(X)){

while(X % c == 0){

divisors[c]++;

X /= c;

}

c += 2;

}

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

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

// 4. 終了.

return;

}

int main(){

// 1. 入力情報.

LL A, B;

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

// 2. 解説通り.

// -> A! / B! を考え, (B + 1) ～ A までの正整数について, 素因数分解する.

int N = (int)(A - B);

repx(i, 1, N + 1) div(B + (LL)i);

// 3. 数え上げる.

LL ans = 1;

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

// 4. 出力.

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

return 0;

}

[入力例]
3 2

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

[入力例]
15 4

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

[入力例]
1000000 999900

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

[入力例]
1000000000 999999900

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

[入力例]
314159265 314159200

[出力例]
291734010

[入力例]

3 2

[出力例]

※AtCoderのテストケースより

[入力例]

15 4

[出力例]

2592

※AtCoderのテストケースより

[入力例]

1000000 999900

[出力例]

21398499

※AtCoderのテストケースより

[入力例]

1000000000 999999900

[出力例]

745508745

※AtCoderのテストケースより

[入力例]

314159265 314159200

[出力例]

291734010

■参照サイト
AtCoder Regular Contest 034

2020年5月12日

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

C++の練習を兼ねて, AtCoder Regular Contest 033 の問題A (A – 隠れた言葉) ～問題C (C – データ構造) を解いてみた.

■感想.
1. 問題C は, 遅延評価セグメント木と二分探索の組み合わせで, 解けるのでは？と気付けたので, AC版となったと思う.
2. 遅延評価セグメント木が必要なため, 下記のライブラリを拝借させて頂いた.
3. 遅延評価セグメント木と二分探索を同時に復習できたので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 出力.
    printf("%d\n", N * (N + 1) / 2);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 出力.

printf("%d\n", N * (N + 1) / 2);

return 0;

}

[入力例]
1

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

[入力例]
2

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

[入力例]
3

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

[入力例]
4

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

[入力例]
1000

[出力例]
500500

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

1000

[出力例]

500500

■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--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N, M, a, b;
    scanf("%d %d", &N, &M);
    set<int> A, B;
    rep(i, N){
        scanf("%d", &a);
        A.insert(a);
    }
    rep(i, M){
        scanf("%d", &b);
        B.insert(b);
    }
    
    // 2. 両方に現れる個数は？
    int AND = 0;
    for(auto &p : A) if(B.count(p) > 0) AND++;
    
    // 3. どちらかに現れる個数は？
    int OR = A.size() + B.size() - AND;
    
    // 4. Jaccard係数は？
    double ans = (double)AND / (double)OR;
    
    // 5. 出力.
    printf("%.12f\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, M, a, b;

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

set<int> A, B;

rep(i, N){

scanf("%d", &a);

A.insert(a);

}

rep(i, M){

scanf("%d", &b);

B.insert(b);

}

// 2. 両方に現れる個数は？

int AND = 0;

for(auto &p : A) if(B.count(p) > 0) AND++;

// 3. どちらかに現れる個数は？

int OR = A.size() + B.size() - AND;

// 4. Jaccard係数は？

double ans = (double)AND / (double)OR;

// 5. 出力.

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

return 0;

}

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

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

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

[入力例]
9 10
11 2 33 4 55 6 77 8 99
10 11 14 19 55 1000000000 4 5 7 8

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

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

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

[出力例]
0.655172413793

[入力例]

3 2

1 3 5

1 2

[出力例]

0.2500000000

※AtCoderのテストケースより

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

0.250000000000

[入力例]

9 10

11 2 33 4 55 6 77 8 99

10 11 14 19 55 1000000000 4 5 7 8

[出力例]

0.2666666667

※AtCoderのテストケースより

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

0.266666666667

[入力例]

50 75

17 16 1 10 26 26 21 15 16 30 3 10 21 12 3 6 15 11 15 14 14 23 16 20 8 17 13 30 12 9 2 5 8 26 17 11 1 6 15 9 6 28 26 13 21 14 3 13 25 28

18 30 12 15 24 24 19 6 17 25 27 18 18 5 17 24 1 25 8 28 18 23 2 24 27 11 15 11 14 20 12 14 6 26 15 11 23 24 12 11 6 24 13 12 21 15 5 11 29 12 7 20 8 14 14 28 22 11 10 24 2 15 7 26 13 17 23 15 15 26 18 30 8 23 13

[出力例]

0.655172413793

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

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

// ※※※ 以下のライブラリを使用(一部改変) ※※※.
// 遅延評価セグメント木をソラで書きたいあなたに.
// http://tsutaj.hatenablog.com/entry/2017/03/30/224339
// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726
struct LazySegmentTree{
private:
    int n;
    vector<int> node, lazy;
public:
    LazySegmentTree(vector<int> v){
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);
        // 元配列 の 値 を, セグメント木のノード に 保存.
        rep(i, sz) node[i + n - 1] = v[i];
        repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }
    void eval(int k, int l, int r){
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void update(int a, int b, int x, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }else{
            update(a, b, x, 2 * k + 1,           l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2,           r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }
    int query(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        int vl = query(a, b, 2 * k + 1,           l, (l + r) / 2);
        int vr = query(a, b, 2 * k + 2, (l + r) / 2,           r);
        return vl + vr;
    }

};

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリに回答.
    LazySegmentTree seg(vector<int>(MAX, 0));
    int T, X;
    rep(i, Q){
        scanf("%d %d", &T, &X);
        // S に 数X を 追加.
        if(T == 1){
            seg.update(X, MAX, 1);
        }
        
        // S に含まれる数で, X番目に小さい数Y を答え, その数を, S から削除.
        if(T == 2){
            int l = 0, h = MAX, m, Y;
            int debug = 0;
            while(l < h - 1 && debug < 100){
                // 中央を決める.
                m = (l + h) / 2;
                
                // m番目は？
                Y = seg.query(m, m + 1);
                
                if(Y < X) l = m;
                else      h = m;
                
                // 無限ループ防止用.
                debug++;
            }
            
            // X番目に小さい数.
            printf("%d\n", h);
            
            // S から 削除.
            seg.update(h, MAX, -1);
        }
    }
    return 0;
    
}

100

101

102

103

104

105

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

const int MAX = 202020;

// ※※※ 以下のライブラリを使用(一部改変) ※※※.

// 遅延評価セグメント木をソラで書きたいあなたに.

// http://tsutaj.hatenablog.com/entry/2017/03/30/224339

// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726

struct LazySegmentTree{

private:

int n;

vector<int> node, lazy;

public:

LazySegmentTree(vector<int> v){

int sz = (int)v.size();

n = 1; while(n < sz) n *= 2;

node.resize(2 * n - 1);

lazy.resize(2 * n - 1, 0);

// 元配列の値を, セグメント木のノードに保存.

rep(i, sz) node[i + n - 1] = v[i];

repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];

}

void eval(int k, int l, int r){

if(lazy[k] != 0) {

node[k] += lazy[k];

if(r - l > 1) {

lazy[2 * k + 1] += lazy[k] / 2;

lazy[2 * k + 2] += lazy[k] / 2;

}

lazy[k] = 0;

}

void update(int a, int b, int x, int k = 0, int l = 0, int r = -1){

if(r < 0) r = n;

eval(k, l, r);

if(b <= l || r <= a) return;

if(a <= l && r <= b){

lazy[k] += (r - l) * x;

eval(k, l, r);

}else{

update(a, b, x, 2 * k + 1, l, (l + r) / 2);

update(a, b, x, 2 * k + 2, (l + r) / 2, r);

node[k] = node[2 * k + 1] + node[2 * k + 2];

}

int query(int a, int b, int k = 0, int l = 0, int r = -1){

if(r < 0) r = n;

eval(k, l, r);

if(b <= l || r <= a) return 0;

if(a <= l && r <= b) return node[k];

int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);

int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);

return vl + vr;

}

};

int main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. クエリに回答.

LazySegmentTree seg(vector<int>(MAX, 0));

int T, X;

rep(i, Q){

scanf("%d %d", &T, &X);

// S に数X を追加.

if(T == 1){

seg.update(X, MAX, 1);

}

// S に含まれる数で, X番目に小さい数Y を答え, その数を, S から削除.

if(T == 2){

int l = 0, h = MAX, m, Y;

int debug = 0;

while(l < h - 1 && debug < 100){

// 中央を決める.

m = (l + h) / 2;

// m番目は？

Y = seg.query(m, m + 1);

if(Y < X) l = m;

else h = m;

// 無限ループ防止用.

debug++;

}

// X番目に小さい数.

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

// S から削除.

seg.update(h, MAX, -1);

}

return 0;

}

[入力例]
5
1 11
1 29
1 89
2 2
2 2

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

[入力例]
12
1 8932
1 183450
1 34323
1 81486
1 127874
1 114850
1 55277
1 112706
2 3
1 39456
1 52403
2 4

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

[入力例]
50
1 8171
1 1995
1 11779
1 12307
1 6114
2 2
1 468
1 1963
2 5
1 2668
2 3
2 4
1 5042
1 8031
2 6
1 5725
1 8941
2 5
1 6052
1 1749
1 2179
2 1
1 8839
1 6924
2 7
1 7645
1 9064
1 753
1 10576
2 13
1 5743
1 4350
1 12240
1 4611
2 3
1 6262
1 6092
1 8246
1 3480
1 8442
2 20
1 8730
1 2417
1 694
1 4985
2 15
1 10754
1 8794
1 2448
1 7851

[出力例]
6114
11779
1995
8171
12307
5725
468
6924
10576
1963
12240
6262

[入力例]

1 11

1 29

1 89

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

1 8932

1 183450

1 34323

1 81486

1 127874

1 114850

1 55277

1 112706

2 3

1 39456

1 52403

2 4

[出力例]

55277

52403

※AtCoderのテストケースより

[入力例]

1 8171

1 1995

1 11779

1 12307

1 6114

2 2

1 468

1 1963

2 5

1 2668

2 3

2 4

1 5042

1 8031

2 6

1 5725

1 8941

2 5

1 6052

1 1749

1 2179

2 1

1 8839

1 6924

2 7

1 7645

1 9064

1 753

1 10576

2 13

1 5743

1 4350

1 12240

1 4611

2 3

1 6262

1 6092

1 8246

1 3480

1 8442

2 20

1 8730

1 2417

1 694

1 4985

2 15

1 10754

1 8794

1 2448

1 7851

[出力例]

6114

11779

1995

8171

12307

5725

468

6924

10576

1963

12240

6262

■参照サイト
AtCoder Regular Contest 033
遅延評価セグメント木をソラで書きたいあなたに

2020年5月12日

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

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

■感想.
1. 1回だけ訪問する町と, 2回以上訪問する町を分離出来たので, AC版に到達できたと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 167 解説(動画)をご覧下さい.

■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--)
#define pb push_back
int a[202020], memo[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N) scanf("%d", &a[i + 1]);
    
    // 2. 周期を求める.
    int cur = 1;        // 町1 が スタート.
    vector<int> v1, v2; // 訪問した町を記録.
    while(memo[cur] < 2){
        // 訪問したことを記録.
        memo[cur]++;
        
        // テレポートした町を保存.
        if(memo[cur] == 1) v1.pb(cur); // 1回目訪問.
        if(memo[cur] == 2) v2.pb(cur); // 2回目訪問.
        
        // 次の町へ.
        cur = a[cur];
    }
    
    // 3. 1回訪問した町 と 2回訪問した町を分ける.
    LL one = (LL)(v1.size() - v2.size());
    LL two = (LL)v2.size();
    
    // 4. K回テレポートした場合は？
    int ans = 0;
    if(one >= K){
        ans = v1[(int)K];
    }else{
        LL res = (K - one) % two;
        ans = v2[(int)res];
    }
    
    // 5. 出力.
    printf("%d\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--)

#define pb push_back

int a[202020], memo[202020];

int main(){

// 1. 入力情報.

int N;

LL K;

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

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

// 2. 周期を求める.

int cur = 1; // 町1 がスタート.

vector<int> v1, v2; // 訪問した町を記録.

while(memo[cur] < 2){

// 訪問したことを記録.

memo[cur]++;

// テレポートした町を保存.

if(memo[cur] == 1) v1.pb(cur); // 1回目訪問.

if(memo[cur] == 2) v2.pb(cur); // 2回目訪問.

// 次の町へ.

cur = a[cur];

}

// 3. 1回訪問した町と 2回訪問した町を分ける.

LL one = (LL)(v1.size() - v2.size());

LL two = (LL)v2.size();

// 4. K回テレポートした場合は？

int ans = 0;

if(one >= K){

ans = v1[(int)K];

}else{

LL res = (K - one) % two;

ans = v2[(int)res];

}

// 5. 出力.

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

return 0;

}

[入力例]
4 5
3 2 4 1

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

[入力例]
6 727202214173249351
6 5 2 5 3 2

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

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

[出力例]
7

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

[出力例]
10

[入力例]
100 123456789987654321
33 50 67 56 84 89 96 83 95 68 8 86 36 89 27 29 88 88 25 78 3 74 33 46 84 51 68 81 53 83 1 44 48 9 94 8 64 28 37 4 44 25 96 95 82 91 10 40 45 17 56 27 43 6 84 4 87 79 94 15 83 52 95 50 19 91 64 47 27 97 40 58 30 14 37 11 94 64 75 54 49 96 2 98 4 10 16 56 71 88 41 88 1 70 75 23 77 51 35 98

[出力例]
56

[入力例]

4 5

3 2 4 1

[出力例]

※AtCoderテストケースより

[入力例]

6 727202214173249351

6 5 2 5 3 2

[出力例]

※AtCoderテストケースより

[入力例]

7 6

3 7 5 2 6 4 1

[出力例]

[入力例]

10 314159265358979323

8 9 2 6 10 4 3 7 5 2

[出力例]

[入力例]

100 123456789987654321

33 50 67 56 84 89 96 83 95 68 8 86 36 89 27 29 88 88 25 78 3 74 33 46 84 51 68 81 53 83 1 44 48 9 94 8 64 28 37 4 44 25 96 95 82 91 10 40 45 17 56 27 43 6 84 4 87 79 94 15 83 52 95 50 19 91 64 47 27 97 40 58 30 14 37 11 94 64 75 54 49 96 2 98 4 10 16 56 71 88 41 88 1 70 75 23 77 51 35 98

[出力例]

■参照サイト
AtCoder Beginner Contest 167

2020年5月11日

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

C++の練習を兼ねて, AtCoder Beginner Contest 166 の問題F (F – Three Variables Game) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc166/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--)
#define pb push_back
const string ABC[] = {"AB", "BC", "CA"};

int main(){
    
    // 1. 入力情報.
    int N;
    LL A, B, C;
    map<char, LL> m;
    vector<string> v;
    scanf("%d %lld %lld %lld", &N, &A, &B, &C);
    m['A'] = A, m['B'] = B, m['C'] = C;
    rep(i, N){
        char c[11];
        scanf("%s", c);
        string s(c);
        // 配列ABC を使いたいので, "AC" は, "CA" と 見る.
        if(s == "AC") s = "CA";
        v.pb(s);
    }
    
    // 以下, 解説通り.
    // 2. A, B, C が 負にならないように操作できるか？
    bool ok = true;
    queue<char> q;
    
    // 2-1. A + B + C = 0.
    if(A + B + C == 0) ok = false;
    
    // 2-2. A + B + C = 1.
    if(A + B + C == 1){
        rep(i, N){
            // "AB", "AC", "BC" の いずれに等しいか確認.
            rep(j, 3){
                if(ABC[j] == v[i]){
                    char x = ABC[j][0], y = ABC[j][1];
                    if(m[x] > m[y]) m[x]--, m[y]++, q.push(y);
                    else            m[x]++, m[y]--, q.push(x);
                    if(m[x] < 0 || m[y] < 0) ok = false;
                    break;
                }
            }
            if(!ok) break;
        }
    }
    
    // 2-3. A + B + C >= 2.
    if(A + B + C >= 2){
        rep(i, N){
            // "AB", "AC", "BC" の いずれに等しいか確認.
            rep(j, 3){
                if(ABC[j] == v[i]){
                    char x = ABC[j][0], y = ABC[j][1];
                    if(m[x] > m[y]){
                        m[x]--, m[y]++, q.push(y);
                    }else{
                        if(m[x] == 1 && m[y] == 1){
                            if(i < N - 1 && v[i] != v[i + 1]){
                                // 次の要素.
                                char nx = v[i + 1][0], ny = v[i + 1][1];
                                if(x == nx || x == ny) m[x]++, m[y]--, q.push(x);
                                else                   m[x]--, m[y]++, q.push(y);
                            }else{
                                m[x]++, m[y]--, q.push(x);
                            }
                        }else{
                            m[x]++, m[y]--, q.push(x);
                        }
                    }
                    if(m[x] < 0 || m[y] < 0) ok = false;
                    break;
                }
            }
            if(!ok) break;
        }
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    if(ok){
        while(!q.empty()){
            char ans = q.front();
            q.pop();
            printf("%c\n", ans);
        }
    }
    return 0;
    
}

// 解き直し.

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

#define pb push_back

const string ABC[] = {"AB", "BC", "CA"};

int main(){

// 1. 入力情報.

int N;

LL A, B, C;

map<char, LL> m;

vector<string> v;

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

m['A'] = A, m['B'] = B, m['C'] = C;

rep(i, N){

char c[11];

scanf("%s", c);

string s(c);

// 配列ABC を使いたいので, "AC" は, "CA" と見る.

if(s == "AC") s = "CA";

v.pb(s);

}

// 以下, 解説通り.

// 2. A, B, C が負にならないように操作できるか？

bool ok = true;

queue<char> q;

// 2-1. A + B + C = 0.

if(A + B + C == 0) ok = false;

// 2-2. A + B + C = 1.

if(A + B + C == 1){

rep(i, N){

// "AB", "AC", "BC" のいずれに等しいか確認.

rep(j, 3){

if(ABC[j] == v[i]){

char x = ABC[j][0], y = ABC[j][1];

if(m[x] > m[y]) m[x]--, m[y]++, q.push(y);

else m[x]++, m[y]--, q.push(x);

if(m[x] < 0 || m[y] < 0) ok = false;

break;

}

if(!ok) break;

}

// 2-3. A + B + C >= 2.

if(A + B + C >= 2){

rep(i, N){

// "AB", "AC", "BC" のいずれに等しいか確認.

rep(j, 3){

if(ABC[j] == v[i]){

char x = ABC[j][0], y = ABC[j][1];

if(m[x] > m[y]){

m[x]--, m[y]++, q.push(y);

}else{

if(m[x] == 1 && m[y] == 1){

if(i < N - 1 && v[i] != v[i + 1]){

// 次の要素.

char nx = v[i + 1][0], ny = v[i + 1][1];

if(x == nx || x == ny) m[x]++, m[y]--, q.push(x);

else m[x]--, m[y]++, q.push(y);

}else{

m[x]++, m[y]--, q.push(x);

}

}else{

m[x]++, m[y]--, q.push(x);

}

if(m[x] < 0 || m[y] < 0) ok = false;

break;

}

if(!ok) break;

}

// 3. 出力.

printf("%s\n", ok ? "Yes" : "No");

if(ok){

while(!q.empty()){

char ans = q.front();

q.pop();

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

}

return 0;

}

[入力例]
2 1 3 0
AB
AC

[出力例]
Yes
A
C
※AtCoderテストケースより

[入力例]
3 1 0 0
AB
BC
AB

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

[入力例]
1 0 9 0
AC

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

[入力例]
8 6 9 1
AC
BC
AB
BC
AC
BC
AB
AB

[出力例]
Yes
C
B
B
C
C
B
A
A

※ 但し, 上記のプログラムでは, 以下の内容が出力される.
Yes
C
C
A
C
C
C
A
B
※AtCoderテストケースより

[入力例]
16 1 2 3
AC
BC
AC
BC
AB
BC
AC
AB
BC
AC
AB
AB
AC
AB
BC
AB

[出力例]
Yes
A
B
C
C
A
B
C
A
B
C
A
B
A
A
B
B

100

[入力例]

2 1 3 0

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 1 0 0

[出力例]

※AtCoderテストケースより

[入力例]

1 0 9 0

[出力例]

※AtCoderテストケースより

[入力例]

8 6 9 1

[出力例]

Yes

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

Yes

※AtCoderテストケースより

[入力例]

16 1 2 3

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 166

2020年5月10日

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

C++の練習を兼ねて, AtCoder Regular Contest 032 の問題C (C – 仕事計画) を解いてみた.

■感想.
1. 解答方針が見えなかったので, 解説を参照して実装したところ, 実装に非常に苦労したものの(※)ようやくAC版となった.
※ 同じ仕事の開始時刻が, 複数回出現する場合を考慮したところ, dp更新式が, 複雑になってしまった.
2. 苦手な, dpの訓練が出来たので, 非常に良かったと思った.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc032
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
const int MAX = 1010101;
P dp[MAX];     // {時刻i以降での最大仕事数, 次の仕事の最小番号}

struct job{
    int s, e, i; // 仕事の開始, 終了, 仕事の番号.
    bool operator < (const job& rhs) const{
        return (s != rhs.s) ? (s < rhs.s) : (e < rhs.e);
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    priority_queue<job> pq;
    vector<P> v; // 入力データ保存用.
    // map<P, int> m;
    rep(i, N){
        int s, e;
        job j;
        scanf("%d %d", &s, &e);
        j.s = s;
        j.e = e;
        j.i = i + 1;
        pq.push(j);
        v.pb({s, e});
        // m[{s, e}]++;
    }
    // while(!pq.empty()){
    //     job j = pq.top();
    //     pq.pop();
    //     printf("%d %d %d\n", j.s, j.e, j.i);
    // }
    // printf("m.size()=%d\n", m.size());
    
    // ※ 以下, 解説通り.
    // 2. dp更新.
    repr(i, MAX - 2, 0){
        while(!pq.empty()){
            // 仕事情報を一つ取ってくる.
            job j = pq.top();
            
            // 開始時刻が, 異なったら, Skip.
            if(j.s != i) break;
            
            // 仕事情報を使う場合.
            P ok = {dp[j.e].a + 1, j.i};
            
            // 仕事情報を使わない場合.
            P ng = {dp[j.s + 1].a, dp[j.s + 1].b};
            
            // 現在のdp情報.
            P cur = dp[j.s];
            
            // ok, ng, cur を 比較して, dp更新.
            if(cur.b == 0){
                if(ok.a == ng.a) dp[j.s] = (ok.b < ng.b) ? ok : ng;
                else             dp[j.s] = (ok.a > ng.a) ? ok : ng;
            }else{
                if(ok.a == ng.a){
                    if(ok.a > cur.a)  dp[j.s] = (ok.b < ng.b) ? ok : ng;
                    if(ok.a == cur.a) dp[j.s] = {ok.a, min({ok.b, ng.b, cur.b})};
                }else{
                    if(ok.a > ng.a){
                         if(ok.a > cur.a)  dp[j.s] = ok;
                         if(ok.a == cur.a) dp[j.s] = {ok.a, min(ok.b, cur.b)};
                    }
                    if(ng.a > ok.a){
                         if(ng.a > cur.a)  dp[j.s] = ng;
                         if(ng.a == cur.a) dp[j.s] = {ng.a, min(ng.b, cur.b)};
                    }
                }
            }
            
            // 仕事情報を削除して, 次処理へ.
            pq.pop();
        }
        // dp更新(※未更新の場合).
        if(dp[i].a == 0) dp[i] = dp[i + 1];
    }
    // rep(i, 20) printf("%d %d\n", dp[i].a, dp[i].b);
    
    // 3. 復元.
    vector<int> ans;
    int cur = dp[0].b;
    while(1){
        // 仕事番号を保存.
        ans.pb(cur);
        
        // 仕事情報取得.
        P p = v[cur - 1];
        
        // 仕事番号を更新.
        cur = dp[p.b].b;
        
        // 終了条件.
        if(!cur) break;
    }
    
    // 4. 出力.
    printf("%d\n", dp[0].a);
    int l = ans.size();
    rep(i, l){
        printf("%d", ans[i]);
        if(i < l - 1) printf(" ");
    }
    puts("");
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

const int MAX = 1010101;

P dp[MAX]; // {時刻i以降での最大仕事数, 次の仕事の最小番号}

struct job{

int s, e, i; // 仕事の開始, 終了, 仕事の番号.

bool operator < (const job& rhs) const{

return (s != rhs.s) ? (s < rhs.s) : (e < rhs.e);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

priority_queue<job> pq;

vector<P> v; // 入力データ保存用.

// map<P, int> m;

rep(i, N){

int s, e;

job j;

scanf("%d %d", &s, &e);

j.s = s;

j.e = e;

j.i = i + 1;

pq.push(j);

v.pb({s, e});

// m[{s, e}]++;

}

// while(!pq.empty()){

// job j = pq.top();

// pq.pop();

// printf("%d %d %d\n", j.s, j.e, j.i);

// }

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

// ※ 以下, 解説通り.

// 2. dp更新.

repr(i, MAX - 2, 0){

while(!pq.empty()){

// 仕事情報を一つ取ってくる.

job j = pq.top();

// 開始時刻が, 異なったら, Skip.

if(j.s != i) break;

// 仕事情報を使う場合.

P ok = {dp[j.e].a + 1, j.i};

// 仕事情報を使わない場合.

P ng = {dp[j.s + 1].a, dp[j.s + 1].b};

// 現在のdp情報.

P cur = dp[j.s];

// ok, ng, cur を比較して, dp更新.

if(cur.b == 0){

if(ok.a == ng.a) dp[j.s] = (ok.b < ng.b) ? ok : ng;

else dp[j.s] = (ok.a > ng.a) ? ok : ng;

}else{

if(ok.a == ng.a){

if(ok.a > cur.a) dp[j.s] = (ok.b < ng.b) ? ok : ng;

if(ok.a == cur.a) dp[j.s] = {ok.a, min({ok.b, ng.b, cur.b})};

}else{

if(ok.a > ng.a){

if(ok.a > cur.a) dp[j.s] = ok;

if(ok.a == cur.a) dp[j.s] = {ok.a, min(ok.b, cur.b)};

}

if(ng.a > ok.a){

if(ng.a > cur.a) dp[j.s] = ng;

if(ng.a == cur.a) dp[j.s] = {ng.a, min(ng.b, cur.b)};

}

// 仕事情報を削除して, 次処理へ.

pq.pop();

}

// dp更新(※未更新の場合).

if(dp[i].a == 0) dp[i] = dp[i + 1];

}

// rep(i, 20) printf("%d %d\n", dp[i].a, dp[i].b);

// 3. 復元.

vector<int> ans;

int cur = dp[0].b;

while(1){

// 仕事番号を保存.

ans.pb(cur);

// 仕事情報取得.

P p = v[cur - 1];

// 仕事番号を更新.

cur = dp[p.b].b;

// 終了条件.

if(!cur) break;

}

// 4. 出力.

printf("%d\n", dp[0].a);

int l = ans.size();

rep(i, l){

printf("%d", ans[i]);

if(i < l - 1) printf(" ");

}

puts("");

return 0;

}

[入力例]
4
0 5
0 3
3 7
5 10

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

[入力例]
5
0 5
0 3
3 7
5 10
7 12

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

[入力例]
8
1 5
3 9
2 5
1 2
8 10
9 11
7 15
10 14

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

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

[出力例]
3
2 3 1

[入力例]
8
0 2
0 5
0 3
3 7
3 9
8 10
8 12
11 15

[出力例]
4
1 4 6 8

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

[出力例]
3
19 26 4

[入力例]
100
666 3011
384 706
1140 3366
483 1655
1010 2579
439 2528
424 1299
735 2607
80 975
190 646
789 1932
844 3062
466 2043
117 1398
556 2773
90 1559
803 844
516 1882
690 1122
564 856
335 2453
600 825
1214 1773
500 2764
122 980
987 2000
997 1096
1083 1498
314 472
623 2005
1072 2768
628 1022
462 1091
1004 2769
265 1842
3 882
650 2142
873 2527
985 1101
937 2112
1093 1275
160 963
703 2274
669 1038
739 1313
342 2252
469 1466
898 1885
959 1721
76 1196
1144 1540
1166 3250
1150 1307
48 1031
1116 2138
415 587
133 309
119 2276
70 2013
828 2003
1033 3349
481 1457
1031 2804
1166 1552
170 1293
297 1521
90 741
375 2238
486 1837
446 1764
105 2045
870 2801
1051 2974
552 2231
403 556
806 2106
1058 2264
1179 2751
260 2008
588 1264
818 1882
697 1409
290 745
626 2124
745 783
1001 2328
552 2299
58 1731
936 2060
166 1317
981 1609
417 1506
435 1270
859 2658
972 1397
379 466
145 603
579 1456
140 631
700 2209

[出力例]
6
57 2 85 17 27 3

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

[入力例]

0 5

0 3

3 7

5 10

[出力例]

1 4

※AtCoderのテストケースより

[入力例]

0 5

0 3

3 7

5 10

7 12

[出力例]

2 3 5

※AtCoderのテストケースより

[入力例]

1 5

3 9

2 5

1 2

8 10

9 11

7 15

10 14

[出力例]

4 3 5 8

※AtCoderのテストケースより

[入力例]

5 6

0 1

2 3

[出力例]

2 3 1

[入力例]

0 2

0 5

0 3

3 7

3 9

8 10

8 12

11 15

[出力例]

1 4 6 8

[入力例]

4 17

1 21

10 31

13 18

12 25

8 16

6 25

2 21

4 15

5 17

10 25

2 19

4 21

10 17

5 26

10 32

14 15

13 33

4 11

5 22

2 22

12 19

3 14

10 15

13 24

11 13

2 27

2 14

2 25

4 27

[出力例]

19 26 4

[入力例]

100

666 3011

384 706

1140 3366

483 1655

1010 2579

439 2528

424 1299

735 2607

80 975

190 646

789 1932

844 3062

466 2043

117 1398

556 2773

90 1559

803 844

516 1882

690 1122

564 856

335 2453

600 825

1214 1773

500 2764

122 980

987 2000

997 1096

1083 1498

314 472

623 2005

1072 2768

628 1022

462 1091

1004 2769

265 1842

3 882

650 2142

873 2527

985 1101

937 2112

1093 1275

160 963

703 2274

669 1038

739 1313

342 2252

469 1466

898 1885

959 1721

76 1196

1144 1540

1166 3250

1150 1307

48 1031

1116 2138

415 587

133 309

119 2276

70 2013

828 2003

1033 3349

481 1457

1031 2804

1166 1552

170 1293

297 1521

90 741

375 2238

486 1837

446 1764

105 2045

870 2801

1051 2974

552 2231

403 556

806 2106

1058 2264

1179 2751

260 2008

588 1264

818 1882

697 1409

290 745

626 2124

745 783

1001 2328

552 2299

58 1731

936 2060

166 1317

981 1609

417 1506

435 1270

859 2658

972 1397

379 466

145 603

579 1456

140 631

700 2209

[出力例]

57 2 85 17 27 3

■参照サイト
AtCoder Regular Contest 032

2020年5月9日2020年8月7日

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

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

■感想.
1. 解答方針が見えなかったので, 解説を参照して実装したところ, ようやくAC版となった.
2. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc031
// C++14 (GCC 5.4.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 101010;
int ih[MAX], oh[MAX];

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &ih[i]);
        oh[ih[i]] = i;
    }
    
    // 2. 解説通り.
    BIT<LL> d(N);
    rep(i, N) d.add(i, 1);
    
    // 3. 積み木を調べる.
    // ex.
    // d.sum(0, 5) -> 区間[l + 1, r] = [1, 5] の 和と見て, 合計 5 と理解.
    LL ans = 0;
    rep(i, N - 1){
        // 左右の和を抽出.
        LL l = d.sum(0, oh[i + 1]);
        LL r = d.sum(oh[i + 1] + 1, N);
        
        // 小さい方を加算.
        ans += min(l, r);
        // printf("i=%d l=%lld r=%lld\n", i, l, r);
        
        // Binary Indexed Tree を 更新.
        d.add(oh[i + 1], -1);
        // rep(j, N) printf("%lld ", d.sum(j, j + 1));
        // puts("");
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++14 (GCC 5.4.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

const int MAX = 101010;

int ih[MAX], oh[MAX];

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] += x;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x += d[i];

return x;

}

T sum(int l, int r){

return sum(r - 1) - sum(l - 1);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

oh[ih[i]] = i;

}

// 2. 解説通り.

BIT<LL> d(N);

rep(i, N) d.add(i, 1);

// 3. 積み木を調べる.

// ex.

// d.sum(0, 5) -> 区間[l + 1, r] = [1, 5] の和と見て, 合計 5 と理解.

LL ans = 0;

rep(i, N - 1){

// 左右の和を抽出.

LL l = d.sum(0, oh[i + 1]);

LL r = d.sum(oh[i + 1] + 1, N);

// 小さい方を加算.

ans += min(l, r);

// printf("i=%d l=%lld r=%lld\n", i, l, r);

// Binary Indexed Tree を更新.

d.add(oh[i + 1], -1);

// rep(j, N) printf("%lld ", d.sum(j, j + 1));

// puts("");

}

// 4. 出力.

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

return 0;

}

[入力例]
4
2 4 1 3

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

[入力例]
5
2 4 1 3 5

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

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

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

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

[出力例]
5

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

[出力例]
15

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

[出力例]
78

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

[出力例]
130

[入力例]

2 4 1 3

[出力例]

※AtCoderのテストケースより

[入力例]

2 4 1 3 5

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 4 3 5 6

[出力例]

※AtCoderのテストケースより

[入力例]

6 5 2 1 3 4

[出力例]

[入力例]

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

[出力例]

[入力例]

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

[出力例]

[入力例]

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

[出力例]

130

■参照サイト
AtCoder Regular Contest 031
Binary Indexed Tree (Fenwick Tree)

C++の練習を兼ねて, AtCoder Regular Contest 039 の 問題A (A – B problem) ～ 問題B (高橋幼稚園) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 037 の 問題A (A – 全優) ～ 問題B (B – バウムテスト) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 036 の 問題A (A – ぐっすり) ～ 問題B (B – 山のデータ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 035 の 問題A (A – 高橋くんと回文) ～ 問題B (B – アットコーダー王国のコンテスト事情) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 034 の 問題A (A – 首席) ～ 問題C (C – 約数かつ倍数) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 033 の 問題A (A – 隠れた言葉) ～ 問題C (C – データ構造) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 166 の 問題F (F – Three Variables Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 032 の 問題C (C – 仕事計画) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 039 の問題A (A – B problem) ～問題B (高橋幼稚園) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 037 の問題A (A – 全優) ～問題B (B – バウムテスト) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 036 の問題A (A – ぐっすり) ～問題B (B – 山のデータ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 035 の問題A (A – 高橋くんと回文) ～問題B (B – アットコーダー王国のコンテスト事情) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 034 の問題A (A – 首席) ～問題C (C – 約数かつ倍数) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 033 の問題A (A – 隠れた言葉) ～問題C (C – データ構造) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 166 の問題F (F – Three Variables Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 032 の問題C (C – 仕事計画) を解いてみた.

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