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

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

■感想.
1. priority_queue を使って解こうとしたら, まったくダメだったので, 解説を参照した.
2. 解説で, 紹介されている数式などをもとに実装し, 何とか, AC版となった.
※ f(X) を計算すると, 降順に並んでいるので, lower_bound関数が使えるように, f(X) を昇順sort する処理を追加した.
3. 個人的には, マジックを観ているようで, 非常に面白い問題に感じた.

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

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

// 解き直し.
// ABC 143解説.
// https://img.atcoder.jp/abc143/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int MAX = 321123;
LL A[MAX], C[MAX], D[MAX], DCUM[MAX], KDCUM[MAX], f[MAX];

int main(){
    
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%lld", &A[i]), C[A[i]]++;
    for(int i = 1; i <= N; i++) D[C[i]]++;
    
    // 2. 解説通り(累積和).
    for(int i = 1; i <= N; i++) DCUM[i] = DCUM[i - 1] + D[i];
    for(int i = 1; i <= N; i++) KDCUM[i] = KDCUM[i - 1] + (LL)i * D[i];
    
    // 3. f(X) の 計算.
    // -> lower_bound を 使用する都合上, index を ずらした.
    for(int x = 0; x < N; x++){
        f[x] = KDCUM[x];
        f[x] += (LL)(x + 1) * (DCUM[N] - DCUM[x]);
        f[x] /= (x + 1);
    }
    // for(int i = 0; i <= N; i++) printf("%lld ", DCUM[i]);
    // printf("\n");
    // for(int i = 0; i <= N; i++) printf("%lld ", KDCUM[i]);
    // printf("\n");
    
    // 4. f(X) の sort.
    // -> lower_bound を 使用する都合上, 昇順sort した.
    sort(f, f + N);
    // for(int i = 0; i < N; i++) printf("%lld ", f[i]);
    // printf("\n");
    
    // 5. N個の整数を出力.
    for(int t = 1; t <= N; t++){
        int at = lower_bound(f, f + N, t) - f;
        printf("%d\n", N - at);
    }
    return 0;
    
}

// 解き直し.

// ABC 143解説.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int MAX = 321123;

LL A[MAX], C[MAX], D[MAX], DCUM[MAX], KDCUM[MAX], f[MAX];

int main(){

// 1. 入力情報取得.

int N;

scanf("%d", &N);

for(int i = 0; i < N; i++) scanf("%lld", &A[i]), C[A[i]]++;

for(int i = 1; i <= N; i++) D[C[i]]++;

// 2. 解説通り(累積和).

for(int i = 1; i <= N; i++) DCUM[i] = DCUM[i - 1] + D[i];

for(int i = 1; i <= N; i++) KDCUM[i] = KDCUM[i - 1] + (LL)i * D[i];

// 3. f(X) の計算.

// -> lower_bound を使用する都合上, index をずらした.

for(int x = 0; x < N; x++){

f[x] = KDCUM[x];

f[x] += (LL)(x + 1) * (DCUM[N] - DCUM[x]);

f[x] /= (x + 1);

}

// for(int i = 0; i <= N; i++) printf("%lld ", DCUM[i]);

// printf("\n");

// for(int i = 0; i <= N; i++) printf("%lld ", KDCUM[i]);

// printf("\n");

// 4. f(X) の sort.

// -> lower_bound を使用する都合上, 昇順sort した.

sort(f, f + N);

// for(int i = 0; i < N; i++) printf("%lld ", f[i]);

// printf("\n");

// 5. N個の整数を出力.

for(int t = 1; t <= N; t++){

int at = lower_bound(f, f + N, t) - f;

printf("%d\n", N - at);

}

return 0;

}

[入力例]
3
2 1 2

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

[入力例]
5
1 2 3 4 5

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

[入力例]
4
1 3 3 3

[出力例(debug版)]
1 1 1 2 
4
1
0
0

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

[出力例(debug版)]
1 1 1 1 1 2 2 3 3 4 
10
5
3
1
0
0
0
0
0
0

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

[出力例(debug版)]
1 1 1 1 1 1 1 1 1 2 2 2 3 4 5 6 8 
17
8
5
4
3
2
1
1
0
0
0
0
0
0
0
0
0

[入力例]

2 1 2

[出力例(debug版)]

1 1 2

※AtCoderテストケースより

[入力例]

1 2 3 4 5

[出力例(debug版)]

1 1 1 2 5

※AtCoderテストケースより

[入力例]

1 3 3 3

[出力例(debug版)]

1 1 1 2

[入力例]

1 1 2 1 1 2 3 2 3 4

[出力例(debug版)]

1 1 1 1 1 2 2 3 3 4

[入力例]

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

[出力例(debug版)]

1 1 1 1 1 1 1 1 1 2 2 2 3 4 5 6 8

■参照サイト
AtCoder Beginner Contest 143

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

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

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

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