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

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

■感想.
1. k番目のボールを取り除く前と取り除いた後の差分に着目できたので, AC版になったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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--)
int a[202020];
LL ball[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a[i]);
        // a[i] が 書かれているボールの数.
        ball[a[i]]++;
    }
    
    // 2. N個のボールで, 条件を満たす2個のボールの選び方は？
    LL total = 0;
    repx(i, 1, N + 1) total += ball[i] * (ball[i] - 1) / 2;
    
    // 3. k番目のボールを除いた場合, 条件を満たす2個のボールの選び方は？
    rep(k, N){
        LL b = ball[a[k]], ans = total;
        // ans = ans - b * (b - 1) / 2 + (b - 1) * (b - 2) / 2
        // => ans = ans - b + 1
        if(b) ++ans -= b;
        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--)

int a[202020];

LL ball[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

// a[i] が書かれているボールの数.

ball[a[i]]++;

}

// 2. N個のボールで, 条件を満たす2個のボールの選び方は？

LL total = 0;

repx(i, 1, N + 1) total += ball[i] * (ball[i] - 1) / 2;

// 3. k番目のボールを除いた場合, 条件を満たす2個のボールの選び方は？

rep(k, N){

LL b = ball[a[k]], ans = total;

// ans = ans - b * (b - 1) / 2 + (b - 1) * (b - 2) / 2

// => ans = ans - b + 1

if(b) ++ans -= b;

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

}

return 0;

}

[入力例]
5
1 1 2 1 2

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

[入力例]
4
1 2 3 4

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

[入力例]
5
3 3 3 3 3

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

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

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

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

[出力例]
3
3
3
3
4
3
3
3
3

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

[出力例]
2
2
3
2
2
3
3
3
2
2

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

[出力例]
30
30
30
31
31
31
32
33
33
34
35
34
33
32
32
32
31
31
30
30
30

100

101

102

103

104

105

106

107

[入力例]

1 1 2 1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

3 3 3 3 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2 1 4 2 1 4 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 5 4 3 2 1

[出力例]

[入力例]

3 1 4 1 5 9 2 6 5 3

[出力例]

[入力例]

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

[出力例]

■参照サイト
AtCoder Beginner Contest 159

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

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

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

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