ARC-102-D All Your Paths are Different Lengths

問題文

D - All Your Paths are Different Lengths

解けなかったので反省も込めて

 解法

上記 URL から見れる。

 感想・教訓

制約から辺を2のべき乗で重みをふっていくのはピンとくる。

そうすると 0 ~ (2^i) - 1 まで連続してできることもすぐわかる。

ここで任意の数まで連続にできるにはどうするかと考えて、2^i 個連続にできることは分かっているので、0 ~ (2^i) - 1 ,(2^i) ~ (2^i) + (2^j) - 1 てな感じにすればよい。

ここまでわかってて解けなかった（ゲジゲジ）。ほかの方の考察を聞くとトポロジカル順に 2 のべき乗の重みをふっていたけど、自分の考察ではトポロジカル逆順でふっていて分かりづらかったのが1つの原因だと思う。

考察も実装も前者のほうが楽。

１完だと気が滅入る。

 コード

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
  int L;
  cin >> L;
  int l = L;
  vector<tuple<int, int, int>> v;
  for (int i = 0; L >= (1 << i); ++i) {
    if (i) {
      v.push_back(make_tuple(i, i + 1, (1 << (i - 1))));
    }
    if (L & (1 << i)) {
      if (l -= (1 << i)) {
        v.push_back(make_tuple(i + 1, 20, l));
      }
    }
  }
  cout << 20 << " " << v.size() + 19 << endl;
  for (int i = 1; i < 20; ++i) {
    cout << i << " " << i + 1 << " " << 0 << endl;
  }
  for (auto x : v) {
    cout << get<0>(x) << " " << get<1>(x) << " " << get<2>(x) << endl;
  }
}