2018-12-28

Codeforces AIM Tech Round 5 F: Make symmetrical

Codeforces 数学

問題概要

以下のクエリを処理せよ。なお、以下で考慮する座標はすべて自然数座標である。

点集合に $(x, y)$ を追加する
点集合から $(x, y)$ を削除する
点 $(x, y)$ が与えられる。その時点の点集合について、原点 $(0, 0)$ と $(x, y)$ を結んでできる直線に対して線対称になるために追加すべき点の個数を求める

解説

まず重要な考察として、ある点 $p$ について考慮する際に $p$ と原点を通るような円周上で $p$ を管理するということが必要です。これは、ある 2 点 $p$ と $q$ が原点を通るような直線を軸に対象であることと、 $p$ と $q$ が同一円周上に存在することが必要十分であることによります。

以下の説明では、クエリで扱われる点の座標が $(s, t)$ であるとし、直線 $l$ に対して対称な点のペアがいくつあるかを管理する $\mathrm{cnt}(l)$ と、直線 $l$ 上に点がいくつあるかを管理する $\mathrm{onseg}(l)$ を使用しています。

クエリ 1

追加される点は、円 $x^{2} + y^{2} = C (C = s^{2} + t^{2})$ の周上に位置します。原点と $(s, t)$ を通る直線 $l'$ に対して $\mathrm{onseg}(l')$ をインクリメントし、また同一円周上に存在する他の点 $(u, v)$ それぞれに対して、原点と $(s+u, t+v)$ を通る直線 $l''$ に対して $\mathrm{cnt}(l'')$ をインクリメントすればよいです。

クエリ 2

クエリ 1 とほぼ同様の方針で処理します。対応する $\mathrm{onseg}(l')$ と $\mathrm{cnt}(l'')$ に対してデクリメントすれば良いです。

クエリ 3

直線 $l$ に対してクエリに答えるものとし、クエリが呼び出された時点で点が $N$ 個存在するとします。すでにペアになっている点対が $\mathrm{cnt}(l)$ ペアあり、直線状に位置する点が $\mathrm{onseg}(l)$ 個あるため、答えは $N - 2 \mathrm{cnt}(l) - \mathrm{onseg}(l)$ になります。

最後に、計算量を確認します。クエリ 1 及び 2 で同一円周上に位置する点全てについて操作が必要ですが、実は同一円周上に位置する点の数は十分小さいです。詳しくは Pi hiding in prime regularities - YouTube などをご覧ください (この資料は hsjoihs さんから教えていただきました。ありがとうございます)。円周ごとに独立に管理することで十分高速に処理できます。

ソースコード

直線を管理するために座標を適宜正規化して管理します。クエリで与えられる点は第一象限に属することが保証されているので、比較的容易に記述できます。

pair<int, int> normalize(int x, int y) {
    int g = __gcd(x, y);
    return make_pair(x/g, y/g);
}

signed main() {
    int Q; scanf("%lld", &Q);
    map< int, set< pair<int, int> > > points;
    map< pair<int, int>, int > cnt, on_seg;
    int whole_points = 0;
    while(Q--) {
        int t, x, y; scanf("%lld%lld%lld", &t, &x, &y);
        int sum = x*x + y*y;
        if(t == 1) {
            if(points.count(sum)) {
                for(auto p : points[sum]) {
                    int px = p.first + x;
                    int py = p.second + y;
                    cnt[normalize(px, py)]++;
                }
            }
            on_seg[normalize(x, y)]++;
            points[sum].emplace(x, y);
            whole_points++;
        }
        if(t == 2) {
            on_seg[normalize(x, y)]--;
            points[sum].erase(make_pair(x, y));
            whole_points--;
            for(auto p : points[sum]) {
                int px = p.first + x;
                int py = p.second + y;
                cnt[normalize(px, py)]--;
            }
        }
        if(t == 3) {
            auto line = normalize(x, y);
            int ans = whole_points - 2 * cnt[line] - on_seg[line];
            printf("%lld\n", ans);
        }
    }
    return 0;
}

2018-12-28

Codeforces Round #527 Div.3 E: Minimal Diameter Forest

Codeforces グラフ

問題概要

原文 → Problem - E - Codeforces

$N$ 頂点からなる森が与えられる。このグラフに対して辺を追加して木を作りたい。木の直径が最小になるように辺を追加した時の、その直径の値と追加すべき辺を列挙せよ。

解説

森を木に分割して、木同士をマージすることを考えます。木 $T_1$ と $T_2$ をマージする際にどの頂点を選択するかが問題ですが、これは木 $T_1$ の中心 $c_1$ と木 $T_2$ の中心 $c_2$ の間を接続するのが最適です。木 $T_1$ の直径を $D_1$ と、中心からの距離最大値 (つまり半径) を $d_1$ とします。 $T_2$ についても同様に $D_2, d_2$ を定義します。このように接続することで、マージされた後の木の直径は $\max \left( D_1, D_2, d_1 + d_2 + 1 \right)$ となります。

中心同士を順に接続していくことになりますが、中心の頂点のみからなるグラフはどのような形をしていればよいでしょうか？直径を最小化するには、スターグラフにように接続することが最適です。また、元の木において直径が最大になるものをスターグラフ中の次数が多くなる頂点に割り当てることで、最適なマージが可能になります。

ソースコード

vector<int> G[1010];
int N, M, used[1010];

void dfs(int cur, vector<int> &dist) {
    for(auto to : G[cur]) {
        if(dist[to] >= 0) continue;
        dist[to] = dist[cur] + 1;
        dfs(to, dist);
    }
}

pair<int, int> get_graph_info(int id) {
    vector<int> d0(N, -1), d1(N, -1), d2(N, -1);
    d0[id] = 0; dfs(id, d0);

    // 直径は p1 と p2 をつなぐパスになる
    int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
    d1[p1] = 0; dfs(p1, d1); // d1 は p1 からの距離を記憶したもの
    int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
    d2[p2] = 0; dfs(p2, d2); // d2 は p2 からの距離を記憶したもの
    int diam = d2[p1];

    int mi = INF, res = -1;
    for(int i=0; i<N; i++) {
        if(d1[i] < 0 or d2[i] < 0) continue;
        used[i] = true;
        int tmp = max(d1[i], d2[i]);
        if(mi > tmp) mi = tmp, res = i;
    }
    return make_pair(diam, res);
}

signed main() {
    scanf("%lld%lld", &N, &M);
    
    for(int i=0; i<M; i++) {
        int u, v; scanf("%lld%lld", &u, &v);
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // (直径, 中心となる頂点)
    vector< pair<int, int> > cand;
    for(int i=0; i<N; i++) {
        if(used[i]) continue;
        pair<int, int> info = get_graph_info(i);
        cand.push_back(info);
    }

    sort(cand.rbegin(), cand.rend());
    vector< pair<int, int> > edges;
    for(int i=1; i<cand.size(); i++) {
        int u = cand[0].second, v = cand[i].second;
        edges.emplace_back(u+1, v+1);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    pair<int, int> whole = get_graph_info(0);
    printf("%lld\n", whole.first);
    for(auto e : edges) {
        printf("%lld %lld\n", e.first, e.second);
    }
    return 0;
}

本番ではスターグラフにする発想が思い浮かばず。冷静に考えれば自然な発想なので、もっと絵をかいてやるべきでした。

2018-12-28

Codeforces Round #527 Div.3 D1 / D2: Great Vova Wall

Codeforces 要考察

問題概要

原文 (D1) → Problem - D1 - Codeforces
原文 (D2) → Problem - D2 - Codeforces

長さ $N$ の数列が与えられる。以下の操作を繰り返し行うことによって、全要素の値を等しくしたい。

D1 で認められる操作
- 値が同じである隣り合う要素を選び、その両方に対し 1 加算
- ある要素を選び、それに対し 2 加算
D2 で認められる操作
- 値が同じである隣り合う要素を選び、その両方に対し 1 加算

解説

D1

単一要素に対して 2 加算できることから、値の偶奇が等しいものは値も等しいとみなしてよいです。つまり、与えられた数列を 0 と 1 のみからなる数列に直すことができます。

このように直した数列に対し、全要素の値を等しくできるかを考えましょう。これは stack を利用することで効率的に処理できます。括弧の対応を取るときと同じように、stack の top にある値と追加したい値が等しい場合は pop し、そうでなければ push することを繰り返し、最終的に得られた stack の size が 1 以下であれば条件を満たせます。

この正当性を簡単に述べます。まず 0 と 1 のみからなる数列に対して「単一要素に 2 加算」の操作は必要ありません。つまり「値が等しい隣り合う要素両方に 1 加算」のみを考えれば良いです。この操作を考える際、同じ parity を持つ区間の長さの偶奇*1が重要になります。この区間長が偶数である場合、うまく操作することで区間全体の parity を変えることもできますし、変えないこともできます。つまり、他の区間の状況に応じて parity を自由に変えることができるので、この区間は元からなかったかのように無視しても構いません。区間長が奇数である場合も、1 つを残して他は全て 0 または 1 に変更可能です。つまり、区間長 $\bmod 2$ を考えれば良いことになります。全体の偶奇を揃えることが目的なので、最終的に何も区間が残らないか、区間がただ 1 つ残る場合に元々の条件を満たせます。この操作は、上で書いたように stack に対する操作で簡潔に表現できます。

D2

D1 とは異なり、単一要素に対して 2 加算することが許されていません。つまり、D1 のように偶奇の戦略を使うことができなくなります。

しかし、この場合でも stack を使うことで効率的に処理できます。stack の top にある値と追加したい値が等しい場合は pop し、そうでない場合について top にある値未満である場合に push、そうでなければその時点で条件を満たしません。

top と値が等しい場合についての操作の正当性は先ほどと同様です。では top と値が異なる場合はなぜこれでうまく動くのでしょうか？

top にある値未満である場合
- stack に残っている要素は、括弧の対応で言うところの開き括弧の状態に対応します。stack に残っている要素を閉じる前に、それよりも小さい要素が来てしまったという状況です。この場合新たに追加した値を閉じることができれば、それに対して一様に加算することで元々 stack にあった要素も閉じられる可能性があります。よって stack に値を追加して操作を続ければ良いです。
top にある値を超える場合
- stack に残っている要素を閉じる前に、それよりも大きい要素が来てしまったという状況です。全要素の値を揃えるためには stack に残る要素に対して操作を行う必要があるのですが、閉じられていないため操作を行うことができません。よって、この時点で条件を満たせなくなります。

最終的に判定する際も若干の注意が必要です。数列に対して繰り返し操作をし終えた際に、各要素の値がいくつになっているか考えます。これは明らかに元の数列の最大値 $M$ になります。このことを考慮すると、最後に得られる stack の状態として許容されるものは、中身が空であるか、 $M$ だけが残っている状態のみです。

ソースコード

D1

signed main() {
    int N; scanf("%lld", &N);

    stack<int> st;
    for(int i=0; i<N; i++) {
        int val; scanf("%lld", &val);
        val %= 2;

        if(st.size()) {
            int t = st.top();
            if(t == val) st.pop();
            else st.push(val);
        }
        else st.push(val);
    }

    cout << (st.size() > 1 ? "NO" : "YES") << endl;
    return 0;
}

D2

signed main() {
    int N; scanf("%lld", &N);

    stack<int> st;
    int ma = -INF;
    for(int i=0; i<N; i++) {
        int val; scanf("%lld", &val);
        ma = max(ma, val);

        if(st.size() and st.top() == val) st.pop();
        else if(st.empty() or st.top() > val) st.push(val);
        else {
            puts("NO");
            return 0;
        }
    }

    bool ok = st.empty() or st.top() == ma;
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}

*1:数列が [0, 0, 1, 1, 1, 0] であった場合、[偶数長の '0', 奇数長の '1', 奇数長の '0'] というように、parity が等しいものが連続する数の偶奇を考える、ということです

hogecoder

tsutaj 競技プログラミングの記録

Codeforces AIM Tech Round 5 F: Make symmetrical

問題概要

解説

クエリ 1

クエリ 2

クエリ 3

ソースコード

Codeforces Round #527 Div.3 E: Minimal Diameter Forest

問題概要

解説

ソースコード

Codeforces Round #527 Div.3 D1 / D2: Great Vova Wall

問題概要

解説

D1

D2

ソースコード

D1

D2