好きだけど細かいところで時間とられるやつなん
問題概要
整数 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
解法
こういうのを作った:
思考過程としては、まず と が近いというところから、二分累乗法的な構築方法になりそうだと思った。
で、327 といったものをどう計算していたかを思い出すと、27 を二進法展開すると なので、
という風にしていた。 といったものはダブリングして求めていた。そうして求めた たちを最後に必要なところを取って行って計算する感じ。
これと同じようなことをしようと思った。まずは の場合をどうやって作れるかを考えて、それを最後に組み合わせればよいと。
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)); } } }