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

C++の練習を兼ねて, AtCoder Regular Contest 082 の問題E (ConvexScore) を解いてみた.

■感想.
1. 問題E は解答方針が見えなかったので, 解説を参考に実装し, AC版に到達できたので, 良かったと思う.
2. 但し, 傾きに紐づく頂点情報を管理するなどで, 実装に非常に苦労した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Regular Contest 082 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/arc082/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<int, 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 a first
#define b second
const LL MOD = 998244353;
LL mPow[202];
int x[202], y[202];
T3 tilt[202][202]; // 頂点 i, 頂点 j に 対する傾き.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d", &x[i], &y[i]);
    
    // 2. 2 の 冪乗.
    mPow[0] = 1LL;
    rep(i, N) mPow[i + 1] = mPow[i] << 1, mPow[i + 1] %= MOD;
    
    // 3. 二点間の傾きを保存(傾き b / a, 切片 c として, {a, b, c} を 保存).
    map<T3, int> m; // {傾き, index}
    rep(i, N){
        // 頂点 A を 取得.
        int iX = x[i], iY = y[i];
        repx(j, i + 1, N){
            // 頂点 B を 取得.
            int jX = x[j], jY = y[j];
            
            // 傾きを計算.
            int a = jX - iX, b = jY - iY;
            int g = __gcd(a, b);
            a /= g;
            b /= g;
            
            // 符号を調整.
            if(a < 0) a = -a, b = -b;
            if(a == 0 && b != 0) b = 1;
            if(a != 0 && b == 0) a = 1;
            
            // 切片(※a倍している状態で保存).
            int c = 0;
            if(a != 0) c = a * iY - b * iX;
            else       c = iX;
            
            // 傾きを保存.
            T3 t = {a, b, c};
            m[t] = 0;
            tilt[i][j] = t;
        }
    }
    
    // 4. index を 設定.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    // for(auto &p : m){
    //     int a = get<0>(p.a);
    //     int b = get<1>(p.a);
    //     int c = get<2>(p.a);
    //     int i = p.b;
    //     printf("a=%d b=%d c=%d i=%d\n", a, b, c, i);
    // }
    
    // 5. 二点間の傾きに紐づく頂点を保存.
    vector<set<int>> v(idx + 1);
    rep(i, N){
        repx(j, i + 1, N){
            // 頂点 i, 頂点 j に 対する傾きに対応する頂点情報を保存.
            int at = m[tilt[i][j]];
            v[at].insert(i);
            v[at].insert(j);
        }
    }
    
    // 6. 集計.
    // 6-1. 0点集合.
    LL ans = mPow[N];
    ans += (MOD - 1LL);
    ans %= MOD;
    
    // 6-2. 1点集合.
    ans += (MOD - (LL)N);
    ans %= MOD;
    
    // 6-3. 2点以上集合.
    for(auto &p : m){
        // 傾きに対応するindexから, 該当する頂点数を取得.
        T3 t = p.a;
        int at = m[t];
        int k = v[at].size();
        ans += (MOD - mPow[k]);
        ans %= MOD;
        ans += (LL)k;
        ans %= MOD;
        ans += 1LL;
        ans %= MOD;
    }
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using T3 = tuple<int, 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 a first

#define b second

const LL MOD = 998244353;

LL mPow[202];

int x[202], y[202];

T3 tilt[202][202]; // 頂点 i, 頂点 j に対する傾き.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 2 の冪乗.

mPow[0] = 1LL;

rep(i, N) mPow[i + 1] = mPow[i] << 1, mPow[i + 1] %= MOD;

// 3. 二点間の傾きを保存(傾き b / a, 切片 c として, {a, b, c} を保存).

map<T3, int> m; // {傾き, index}

rep(i, N){

// 頂点 A を取得.

int iX = x[i], iY = y[i];

repx(j, i + 1, N){

// 頂点 B を取得.

int jX = x[j], jY = y[j];

// 傾きを計算.

int a = jX - iX, b = jY - iY;

int g = __gcd(a, b);

a /= g;

b /= g;

// 符号を調整.

if(a < 0) a = -a, b = -b;

if(a == 0 && b != 0) b = 1;

if(a != 0 && b == 0) a = 1;

// 切片(※a倍している状態で保存).

int c = 0;

if(a != 0) c = a * iY - b * iX;

else c = iX;

// 傾きを保存.

T3 t = {a, b, c};

m[t] = 0;

tilt[i][j] = t;

}

// 4. index を設定.

int idx = -1;

for(auto &p : m) p.b = ++idx;

// for(auto &p : m){

// int a = get<0>(p.a);

// int b = get<1>(p.a);

// int c = get<2>(p.a);

// int i = p.b;

// printf("a=%d b=%d c=%d i=%d\n", a, b, c, i);

// }

// 5. 二点間の傾きに紐づく頂点を保存.

vector<set<int>> v(idx + 1);

rep(i, N){

repx(j, i + 1, N){

// 頂点 i, 頂点 j に対する傾きに対応する頂点情報を保存.

int at = m[tilt[i][j]];

v[at].insert(i);

v[at].insert(j);

}

// 6. 集計.

// 6-1. 0点集合.

LL ans = mPow[N];

ans += (MOD - 1LL);

ans %= MOD;

// 6-2. 1点集合.

ans += (MOD - (LL)N);

ans %= MOD;

// 6-3. 2点以上集合.

for(auto &p : m){

// 傾きに対応するindexから, 該当する頂点数を取得.

T3 t = p.a;

int at = m[t];

int k = v[at].size();

ans += (MOD - mPow[k]);

ans %= MOD;

ans += (LL)k;

ans %= MOD;

ans += 1LL;

ans %= MOD;

}

// 7. 出力.

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

return 0;

}

[入力例]
4
0 0
0 1
1 0
1 1

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

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

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

[入力例]
1
3141 2718

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

[入力例]
7
3 6
9 3
10 3
6 9
3 4
6 3
3 0

[出力例]
97

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

[出力例]
33554091

[入力例]

0 0

0 1

1 0

1 1

[出力例]

※AtCoderテストケースより

[入力例]

0 0

0 1

0 2

0 3

1 1

[出力例]

※AtCoderテストケースより

[入力例]

3141 2718

[出力例]

※AtCoderテストケースより

[入力例]

3 6

9 3

10 3

6 9

3 4

6 3

3 0

[出力例]

[入力例]

7 5

12 6

3 2

10 0

12 3

2 5

14 7

2 12

15 15

16 12

10 13

18 13

2 6

19 11

20 17

16 14

21 23

18 0

23 11

4 22

9 20

7 10

21 1

7 3

9 12

[出力例]

33554091

■参照サイト
AtCoder Regular Contest 082

C++の練習を兼ねて, AtCoder Regular Contest 082 の 問題E (ConvexScore) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 082 の問題E (ConvexScore) を解いてみた.

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