AtCoder AGC 050 A - AtCoder Jumper (500 点)

これ本当にずっとわからなかった...言われてみればという感じ！！

• 問題へのリンク

問題概要

以下の条件を満たす、頂点数 の有向グラフ (頂点番号を とする) を構築せよ (自己ループも多重辺も可)。

• すべての頂点の出次数は 2 である
• 任意の頂点対 に対して、 から への最短路長が 10 以下である

制約

• 

考えたこと

本当に何もわからなかった。でも、まったく進展がなかったわけではなく

• 1-indexed で考えるよりも 0-indexed で考えた方がよさそう
• なんらかの規則によって得られた結果を mod. するのがよさそう

といったことは考えていた。ここまではよかった。僕はここからスモールワールドについて調べて

「どの頂点も次数が低いグラフでも、最初は各頂点の近隣と結んでおいて、確率 でランダムにつなぎ変えると、直径が のオーダーになる」

というのを見た。実際にやってみると、確かに直径が 20 くらいにはなるのだ (ここでは から への最短路長の最大値を直径と呼ぶことにする)。そこから焼き鈍したりしたけど、15 より下回ることはなかった。今思うと、evima さんのツイートを見て納得した。

10回しか移動できないってことは選択肢は 2^1 + 2^2 + … + 2^10 = 2047 通りしかなくて、それで 999 か所の行き先を網羅する必要があるので無駄は 1 ビットくらいしか許されないので、お絵かきして適当にうまくやる感じの方針はかなり絶望的ですね。

— えびま (@evima0) 2020年12月26日

つまり、乱択でできるほど甘くはないということだ。さらに、スモールワールドに関する知見から、 -> を固定して、他を色々試すとかもやってみた ( から を決め打ちしてそれに固執したのが敗因)。結局何をやっても決定打に至らなかった。

頂点 0 から任意頂点に行く方法

とりあえず、頂点 0 から任意頂点に行く方法を考えたりもしていた。結果的にはこの方針をもうちょっと頑張っていれば、正解にたどり着けたのかもしれない。頂点 0 から任意頂点に行く方法として、次の 2 通りがあると思っていた

1. 頂点 0 から最初の一手で遠くまでいって、徐々に範囲を絞っていく (二分探索的アプローチ)
2. 頂点 0 から最初は近く、徐々に遠くまで行けるようにしていく (ダブリング的アプローチ)

一応両方考えていたんだけど、1 をメインに考えてしまっていた。2 を頑張っていれば AC に至れたのかもしれない。2 のアプローチでは、こんな感じ。

• 0 から 1 手で 1, 2 に行けるようにする
• 1 から 3, 4、2 から 5, 6 に行けるようにすれば、0 から 2 手で 3, 4, 5, 6 に行ける
• 同様に、0 から 3 手で 7, 8, 9, 10, 11, 12, 13, 14 で行けるようにする
• ...

というふうにすれば、0 から 手で 個の頂点に行き渡らせることができる。このときの規則をちゃんと書くと、

---

頂点 からは、 () と () へリンクを張る

---

という感じだ。実はこれですべてが上手くいっている！！！

セグメント木やヒープのアナロジー

セグメント木では頂点 の子供を にする。そしてセグメント木の根を中途半端なところにとれば、次のことが容易にイメージできる

---

任意の頂点 に対して、 ステップ先の子供をとると、 個の連番になる

---

その連番の始点がどうなるかはわからないけど、いずれにしてもちゃんと連番になるのだ。よって、毎回 をとれば、任意の頂点から ステップで 個の連続する頂点に行けることになる。

よって に対しては、 で十分のようだ。

コード

checker 付き

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int check(const vector<pint> &G) {
    int N = G.size();
    int res = 0;
    for (int v = 0; v < N; ++v) {
        queue<int> que;
        vector<int> dp(N, -1);
        que.push(v);
        dp[v] = 0;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            if (dp[G[u].first] == -1) {
                dp[G[u].first] = dp[u] + 1;
                que.push(G[u].first);
            }
            if (dp[G[u].second] == -1) {
                dp[G[u].second] = dp[u] + 1;
                que.push(G[u].second);
            }
        }
        for (int u = 0; u < N; ++u) res = max(res, dp[u]);
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<pint> res(N);
    for (int i = 0; i < N; ++i) {
        res[i].first = i * 2 % N;
        res[i].second = (i * 2 + 1) % N;
    }

    for (int i = 0; i < N; ++i) {
        cout << res[i].first + 1 << " " << res[i].second + 1 << endl;
    }

    // cout << check(res) << endl;
}