ACL Contest 1 参加記

2完青パフォでした。ACLはほとんど対策できてなかったのですが、自分のレート帯なら関係ないだろうと思って考察を頑張りました。Bでコンテスト前にたまたま目にした拡張ユークリッドの互除法が使える問題が出て、運がよかったです。

jjjjjjjtgpptmjjさんのACL Contest 1での成績：332位
パフォーマンス：1835相当
レーティング：1434→1481 (+47) :)
Highestを更新しました！#AtCoder #ACLContest1 https://t.co/Q9Ypyd5ynZ

— naga@精進 (@longeqe) 2020年9月21日

A - Reachable Towns

問題へのリンク

解説

まず、座標の2変数を処理するのは困難なので、でソートし、その配列を前から見ていきます。 すると、自分より前に見た点は、必ず座標が小さいので、座標も小さいものをmergeすればよいことがわかります。mergeした後は、mergeしたうち一つだけが未来の選択肢と残っていれば十分ですが、これはy座標が最も小さいものに代表させましょう。なぜなら、最もmergeされやすいからです。

選択肢の保存には二分探索したい関係で、std::setを使います。小さい方からとれる優先度つきqueueなどでもよさそうです。

実装

struct UnionFind{
    /**/
};
int main() {
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    UnionFind Uni(N);
    vector<pair<i_i, int>> xyi;
    rep(i,N){
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
        xyi.push_back({{x[i], y[i]}, i});
    }
    sort(all(xyi));
    set<pair<int, int>> st;
    // 今入ってる座標は全てx座標が自分未満なので、y座標が自分未満のやつを探せば良い
    rep(i,N){
        auto pp = xyi[i];
        auto [p, idx] = pp;
        auto [a, b] = p;
        // stの中の{b,INF}未満のやつを全てuniteする
        int ue = b;
        int minn = b;
        while(1){
            auto itr = st.lower_bound({ue, INF});
            if(itr == st.begin())break;
            itr--;
            auto tmp = *itr;
            auto [sita, idx2] = tmp;
            Uni.unite(idx, idx2);
            st.erase(itr);
            chmin(minn, sita);
        }
        st.insert({minn, idx});
    }
    rep(i,N){
        cout << Uni.size(i) << endl;
    }
}

B - Sum is Multiple

問題へのリンク

解説

がの倍数になればよいです。連続する2つの整数は互いに素、つまりとに共通する素因数がないことから、の素因数を素数ごとに別々に押し付けることになります。ここで、の素因数となる素数は高々個しかないので、それらの割り振りをbit全探索します。そうして割り振った2数をそれぞれとすると、との倍数の差が1になるような数を探したくなります。つまり、

を満たすを求めればよいことになります。

この不定方程式は拡張ユークリッドの互除法に似ていて、ならできることがわかっていました。ここで、かつなので、なる解はありません。よって、との符号は異なることがわかります。したがって、それらの符号を反転させれば、差がの2数にすることができます。

• 参考

実装

template<typename T> 
map<T,int> factorize(T x){
    map<T,int> mp;
    for (T i = 2; i*i <= x; i++){
        while (x%i == 0) {
            x /= i;
            mp[i]++;
        }
        if (x == 1) break;
    }
    if (x != 1) mp[x]++;
    return mp;
}

ll power_pow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int main() {
    ll N;
    cin >> N;
    auto vn = factorize(2*N);
    int M = vn.size();
    vector<pair<ll,int>> vp;
    for(auto p: vn)vp.push_back(p);
    if(N == 1){
        cout << 1 << endl;
        return 0;
    }
    ll ans = N-1;
    for(int i = 0; i < bit(M); i++){
        vector<pair<ll,int>> v2[2];
        rep(j,M)v2[(i>>j)&1].push_back(vp[j]);
        ll a = 1, b = 1;
        for(auto [val, sisu]: v2[0])a *= power_pow(val, sisu);
        for(auto [val, sisu]: v2[1])b *= power_pow(val, sisu);
        ll x, y;
        extGCD(a, b, x, y);
        if(x * y >= 0)continue;
        x *= -1;
        y *= -1;
        a *= abs(x);
        b *= abs(y);
        chmin(ans, min(a, b)));
    }
    cout << ans << endl;
}