けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 102 D - All Your Paths are Different Lengths (700 点)

好きだけど細かいところで時間とられるやつなん

問題へのリンク

問題概要 (ARC 102 D / ABC 108 D)

整数 L が与えられる。N 頂点 M 辺の重み付き有向グラフ (頂点番号は 1, 2, ..., N) であって

  • N <= 20
  • M <= 60
  • 任意の辺 (u, v) について u < v でなければならない
  • 頂点 1 から頂点 N へのパスがちょうど L 本あって、それらの重みは 0, 1, 2, ..., L-1 である

という条件を満たすものを 1 つ構築せよ。

制約

  • 2 <= L <= 106

解法

こういうのを作った:

f:id:drken1215:20180902015526j:plain

思考過程としては、まず  L 2^{N} が近いというところから、二分累乗法的な構築方法になりそうだと思った。

で、327 といったものをどう計算していたかを思い出すと、27 を二進法展開すると  27 = 2^{0} + 2^{1} + 2^{3} + 2^{4} なので、

 3^{27} = 3^{2^{0}} × 3^{2^{1}} × 3^{2^{3}} × 3^{2^{4}}

という風にしていた。 3^{2^{n}} といったものはダブリングして求めていた。そうして求めた  3^{2^{n}} たちを最後に必要なところを取って行って計算する感じ。

これと同じようなことをしようと思った。まずは  L = 2^{n} の場合をどうやって作れるかを考えて、それを最後に組み合わせればよいと。

1 2 0
1 2 1
2 3 0
2 3 2
3 4 0
3 4 4
4 5 0
4 5 8
5 6 0
5 6 16
...

という風にすれば、まずはダブリングっぽいことはできる。あとはそれを組み合わせるための遷移を追加して行けば OK。

#include <iostream>
using namespace std;

int main() {
    int L;
    cin >> L;
    int N = 0;
    int pow = 1;
    while (pow <= L) pow *= 2, ++N;
    int M = (N-1)*2 + __builtin_popcount(L) - 1;
        
    cout << N << " " << M << endl;
    for (int i = 0; i < N-1; ++i) {
        cout << i+1 << " " << i+2 << " " << 0 << endl;
        cout << i+1 << " " << i+2 << " " << (1<<i) << endl;
    }
    int cur = 1<<(N-1);
    for (int i = N-2; i >= 0; --i) {
        if (L & (1<<i)) {
            cout << i+1 << " " << N << " " << cur << endl;
            cur += (1<<(i));
        }
    }
}