Mister雑記

競プロやります。

ARC102-D 「All Your Paths are Different Lengths」 (700)

下手な勘違いは、やめようね!

問題リンク

概要

整数 Lについて、以下を満たす有向グラフを1つ構築せよ。

  • 頂点数は20以下、各頂点には 1 \sim Nの相異なる番号が振られている。
  • 辺数は60以下、各辺には 0 \sim 10^6の長さが付いている。
  • 辺は全て番号の小さい頂点から大きい頂点へと張られている。
  • 頂点1から頂点 Nへの異なるパスはちょうど L個あり、それらの長さは 0 \sim L - 1の相異なる整数。

制約

  •  2 \leq L \leq 10^6

解説

こういう「 0 \sim Xまでの整数を全部作れ」っていう問題は大抵「 p進法を使う」と相場が決まっている。今回の場合は p = 2が一番やりやすい。本番中に p = 3でやって沼にハマったのが私。 本記事ではもちろん p = 2で解説していく。

本問の構築過程は主に

  1. 大まかに引く
  2. バイパスで調整

の2段階に分けられる。

大まかに引く

まず頂点数は調整が面倒なので常に20個とする。そして、以下のように辺を張る。

f:id:misteer:20180920202200p:plain

これで K本の辺を張ったとき、 [0, 2^K)の任意の整数を作ることができる。

辺を張れる数は最大19本なので、 2^{19} - 1 = 524,287まで作ることができる。制約に2倍弱足りないが、それは次の過程で補える。

バイパスで調整

実際に L = 334 (ん?)で考えてみよう。

上のように8本の辺を張ることで [0, 256)までは作れる。一方で9本張ってしまうと [0, 512)まで作れてしまいパスが多すぎとなる。

ではどうやって [256, 334)を作るか?そこで256を後から加えることにして [0, 78)を作ることを考える。 これは上と同様の方法で6本の辺によって [0, 64)までなら作れる。 ということで、6本の辺の先、つまり頂点7から20に向けて長さ 256バイパスを張ることで [256, 320)のパスが新たに増える。

では次は320を引いて [0, 14)を作って......と考えることで最終的に [0, 334)のパスが全部できる。

f:id:misteer:20180920202131p:plain

ちなみに一番下にあるように、バイパスの始点は Lのbitと一致している。プロはこの性質から巧みにパスを張ったりできるんだろうか。

実装例

正直この問題で真に難しいのは考察より実装である。実装が上手い人は何を意識しているのかとても気になる。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct edge {
    int from;
    int to;
    int cost;
    edge(int _from, int _to, int _cost) : from(_from), to(_to), cost(_cost){};
};

vector<edge> ans;

// [add, add + L)のバイパスを作る
void bypass(int add, int L) {
    if (L <= 0) return;
    for (int k = 19; k >= 0; --k) {
        if (L >= (1 << k)) {
            // [add, add + 2^k)を作る
            // k本の辺の後、つまり頂点k+1から20に辺を張る
            ans.push_back(edge(k + 1, 20, add));

            // [add + 2^k, add + L)を作る
            bypass(add + (1 << k), L - (1 << k));
            break;
        }
    }
    return;
}

int main() {
    int L;
    cin >> L;

    // 0の辺を全部張る
    for (int i = 1; i < 20; ++i) {
        ans.push_back(edge(i, i + 1, 0));
    }

    // 大まかにグラフを作る
    for (int k = 19; k >= 1; --k) {
        if (L >= (1 << k)) {
            // k本辺を張って[0, 2^k)を作る
            for (int i = 1; i <= k; ++i) {
                ans.push_back(edge(i, i + 1, 1 << (i - 1)));
            }

            // [2^k, L)を作る
            bypass(1 << k, L - (1 << k));
            break;
        }
    }

    cout << 20 << " " << ans.size() << endl;
    for (auto e : ans) {
        cout << e.from << " " << e.to << " " << e.cost << endl;
    }
    return 0;
}

個人的に本問で得られた実装テクが1つある。 本問の様に「 L \geq 2^iを満たす iを知りたい」というケースは珍しくないのだが、このとき「超過するまで iをインクリメントして iを1引く」とするとまずバグる。 こういうときは、上のように「上から iをデクリメントする」方が自然だしかなりバグりにくい。

感想

  • 本番の私は時間切れとはいえよく3進法で通したなぁとつくづく思う
    • ちなみに3進法のコードがこちら
  • 実装のテクも1つ学んだし、時間かけて記事用に実装しただけの成果はあったと思いたい。