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

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

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

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

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

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

int main(){

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

}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

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

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

// 2. 解説どおり.

// 普通の食事 … X回.

// 簡素な食事 … Y回.

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

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

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

LL ans = 2020202020202020;

rep(i, N + 1){

// 普通の食事.

LL X = (LL)i;

// 簡素な食事.

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

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

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

// 必要な食費.

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

}

// 3. 出力.

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

return 0;

}

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

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

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

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

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

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

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

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

[入力例]

4 5

100 4 60 1 4

[出力例]

160

※AtCoderテストケースより

[入力例]

10 1

5000 2 2000 1 300

[出力例]

20000

※AtCoderテストケースより

[入力例]

9 23

170 8 120 5 12

[出力例]

650

※AtCoderテストケースより

[入力例]

653 314159

6728 123456 5141 41928 222222

[出力例]

2818162

※AtCoderテストケースより

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

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

int main(){

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

}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

const int MAX = 101010;

int io[MAX], oi[MAX];

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

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

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

int main(){

// 1. 入力情報.

int N, M, D;

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

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

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

rep(i, M){

int x;

scanf("%d", &x);

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

}

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

// puts("");

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

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

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

int gCount = 0;

repx(i, 1, N + 1){

int x = i, r = 0;

vector<int> g;

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

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

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

while(gRank[x] == 0){

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

at[x] = gCount;

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

gRank[x] = ++r;

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

g.pb(x);

// 次の要素.

x = oi[x];

}

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

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

}

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

repx(k, 1, N + 1){

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

int kG = at[k];

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

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

int kO = D % gSize;

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

int kR = gRank[k];

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

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

// 5-5. 出力.

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

}

return 0;

}

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

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

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

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

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

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

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

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

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

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

[入力例]

5 7 1

1 4 3 4 2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

5 7 2

1 4 3 4 2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

10 20 300

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

[出力例]

※AtCoderテストケースより

[入力例]

7 11 321

1 3 4 2 3 5 1 6 4 2 5

[出力例]

[入力例]

33 100 314159265

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

[出力例]

■参照サイト
AtCoder Beginner Contest 013

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

コメントを残す コメントをキャンセル

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

コメントを残すコメントをキャンセル