TCO2016Round2C Easy BearBall

TCO2016Round2C Easy BearBallの解き方

問題

N個の点がある。
N個の点から始点と終点を選ぶ方法はN*(N-1)通り。
この全ての始点と終点の組み合わせについて、始点から終点に向かってボールを飛ばしたい。
ただし、点1と点2の間に点が存在しなければコスト1で点1から点2に到達できる。
点1と点2の間に点3が存在する場合、点1から点2に直接到達することは出来ないので別の点を経由する必要がある。

全ての始点と終点の組み合わせについて、始点から終点にボールを飛ばすのにかかるコストの合計の最小値はいくつか?

解法

始点を1つ選びその始点からコスト1で到達できる点の個数を求める。コスト1で到達出来ない点はコスト2となる。
これは直線状にいくつ点があろうとも直線状に無いコスト1で到達できる点を経由することでコスト2で終点に到達できるからである。

コスト1で到達できる点はベクトルを用いて、ベクトルが同じ方向ならば同一直線状にあると見なせる。(ベクトルの方向はベクトルのx,y方向の大きさをそれぞれの大きさの最大公約数で割れば異なるベクトルは区別、同じベクトルは同一視できる)

ただし、全ての点が一直線上にある場合は上の図の赤い点が経由出来ないので別に解く必要がある。

この場合、左からi番目の点が始点で始点より左にX個、始点より右にY個だった場合、自分より左の点に達するコストの合計は
自分より左側には

右側には

となるのでこれを直線上の全ての点に対して計算して合計すればよい。

コード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <string>
#include <climits>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int gcd(int a,int  b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    else return gcd(b,a%b);
}

class BearBall {
    public:
    int countThrows(vector <int> x, vector <int> y) {
        int N = x.size();
        ll ans = 0;
        for(int i=0;i<N;i++){
            set<pii> st;
            for(int j=0;j<N;j++){
                if(i==j) continue;
                int vx = x[j]-x[i];
                int vy = y[j]-y[i];
                int m=gcd(abs(vx),abs(vy));
                vx /= m;
                vy /= m;
                st.insert(make_pair(vx,vy));
            }
            int n = st.size();
            if(n==1){
                ans=0;
                for(int i=0;i<N;i++){
                    int j=N-1-i;
                    ans += i*(i+1)/2;
                    ans += j*(j+1)/2;
                }
                return ans;
            }
            ans += n + (N-1-n)*2;
        }
        return ans;
    }
};

感想

これを時間内に解けなかったのでRound2を通過することが出来なかった。悔しい。
コンテスト中にバグらせてしまい無限に時間が溶けてしまった。このくらいは解けるようになりたい。