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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題G (Isosceles Trapezium) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 垂直二等分線を考えて分類していくという方針が, 面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 220 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc220/editorial/2684
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<LL, LL, LL>;
#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 all(x) x.begin(), x.end()
LL x[1010], y[1010], c[1010];

struct info{
    LL x, y, c; // 二点 x, y 座標 の 合計(中点比較用), 重みの和.
    bool operator < (const info& rhs) const{
        return (c > rhs.c);
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &c[i]);
    
    // 2. 二点について, 垂直二等分線などを集計.
    map<T3, int> m;
    int idx = -1;
    vector<vector<info>> v(N * N);
    rep(i, N){
        repx(j, i + 1, N){
            // i -> j の ベクトル.
            LL dx = x[j] - x[i];
            LL dy = y[j] - y[i];
            
            // 最大公約数で割る.
            LL g  = __gcd(abs(dx), abs(dy));
            dx /= g;
            dy /= g;
            
            // 垂直二等分線(傾き).
            // -> ベクトル(a, b) の 形で, a >= 0 となるように保存.
            LL a = -dy;
            LL b = dx;
            if(a < 0){
                a = -a;
                b = -b;
            }
            
            // a が 0 の ケース を 考慮.
            // -> 013.txt などのテストケースで, WA版となった原因と推測.
            // -> b の 符号は, 負にならないように修正.
            if(a == 0) b = abs(b);
            
            // 垂直二等分線(切片).
            // -> 直線 b * x - a * y + a * k = 0 を 保存するイメージ.
            //    但し, 切片は, 整数で保存したいので, 二点 x, y 座標 の 合計
            //    をベースに計算した値を保存.
            LL tx = x[i] + x[j];
            LL ty = y[i] + y[j];
            LL tc = c[i] + c[j];
            LL k = a * ty - b * tx;
            
            // 垂直二等分線が一致するグループごとに分類.
            T3 t = {a, b, k};
            if(!m.count(t)) m[t] = ++idx;
            info cur;
            cur.c = tc;
            cur.x = tx;
            cur.y = ty;
            v[m[t]].pb(cur);
        }
    }
    
    // 3. 選んだ４点の重みの和の最大値.
    LL ans = -1;
    rep(i, idx){
        // sort.
        sort(all(v[i]));
        
        // 先頭要素.
        info s = v[i][0];
        
        // 最大値更新.
        repx(j, 1, v[i].size()){
            // その他の要素.
            info g = v[i][j];
            
            // 中点が一致するか？
            bool ok = (s.x == g.x) && (s.y == g.y);
            
            // 中点が一致しなければ, 最大値更新.
            if(!ok) ans = max(ans, s.c + g.c);
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

// 解き直し.

// https://atcoder.jp/contests/abc220/editorial/2684

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using T3 = tuple<LL, LL, LL>;

#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 all(x) x.begin(), x.end()

LL x[1010], y[1010], c[1010];

struct info{

LL x, y, c; // 二点 x, y 座標の合計(中点比較用), 重みの和.

bool operator < (const info& rhs) const{

return (c > rhs.c);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 二点について, 垂直二等分線などを集計.

map<T3, int> m;

int idx = -1;

vector<vector<info>> v(N * N);

rep(i, N){

repx(j, i + 1, N){

// i -> j のベクトル.

LL dx = x[j] - x[i];

LL dy = y[j] - y[i];

// 最大公約数で割る.

LL g = __gcd(abs(dx), abs(dy));

dx /= g;

dy /= g;

// 垂直二等分線(傾き).

// -> ベクトル(a, b) の形で, a >= 0 となるように保存.

LL a = -dy;

LL b = dx;

if(a < 0){

a = -a;

b = -b;

}

// a が 0 のケースを考慮.

// -> 013.txt などのテストケースで, WA版となった原因と推測.

// -> b の符号は, 負にならないように修正.

if(a == 0) b = abs(b);

// 垂直二等分線(切片).

// -> 直線 b * x - a * y + a * k = 0 を保存するイメージ.

// 但し, 切片は, 整数で保存したいので, 二点 x, y 座標の合計

// をベースに計算した値を保存.

LL tx = x[i] + x[j];

LL ty = y[i] + y[j];

LL tc = c[i] + c[j];

LL k = a * ty - b * tx;

// 垂直二等分線が一致するグループごとに分類.

T3 t = {a, b, k};

if(!m.count(t)) m[t] = ++idx;

info cur;

cur.c = tc;

cur.x = tx;

cur.y = ty;

v[m[t]].pb(cur);

}

// 3. 選んだ４点の重みの和の最大値.

LL ans = -1;

rep(i, idx){

// sort.

sort(all(v[i]));

// 先頭要素.

info s = v[i][0];

// 最大値更新.

repx(j, 1, v[i].size()){

// その他の要素.

info g = v[i][j];

// 中点が一致するか？

bool ok = (s.x == g.x) && (s.y == g.y);

// 中点が一致しなければ, 最大値更新.

if(!ok) ans = max(ans, s.c + g.c);

}

// 4. 出力.

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

return 0;

}

[入力例]
5
0 3 10
3 3 10
-1 0 10
2 0 10000
4 0 10

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

[入力例]
6
0 1 1
1 4 20
2 7 300
5 6 4000
4 3 50000
3 0 600000

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

[入力例]
7
-3 0 1
-2 0 1
-1 0 1
0 0 1
1 0 1
2 0 1
3 0 1

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

[入力例]
12
0 0 5
5 0 7
2 0 6
3 0 5
-1 1 7
6 1 4
-2 3 20
7 3 1
-2 0 13
7 0 3
-6 5 11
11 5 3

[出力例]
37

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

[出力例]
25

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

[出力例]
17

[入力例]

0 3 10

3 3 10

-1 0 10

2 0 10000

4 0 10

[出力例]

※AtCoderのテストケースより

[入力例]

0 1 1

1 4 20

2 7 300

5 6 4000

4 3 50000

3 0 600000

[出力例]

650021

※AtCoderのテストケースより

[入力例]

-3 0 1

-2 0 1

-1 0 1

0 0 1

1 0 1

2 0 1

3 0 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

0 0 5

5 0 7

2 0 6

3 0 5

-1 1 7

6 1 4

-2 3 20

7 3 1

-2 0 13

7 0 3

-6 5 11

11 5 3

[出力例]

[入力例]

1 0 5

0 3 7

3 -1 2

1 5 6

6 0 3

4 6 4

-10 8 11

-4 10 7

[出力例]

[入力例]

0 1 5

0 3 7

-1 -1 3

-1 5 2

[出力例]

■参照サイト
AtCoder Beginner Contest 220

C++の練習を兼ねて, AtCoder Beginner Contest 220 の 問題G (Isosceles Trapezium) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題G (Isosceles Trapezium) を解いてみた.

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