ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ARC102 D - All Your Paths are Different Lengths

D - All Your Paths are Different Lengths
提出コード
n進数を利用する、というところまではよかったのですがそこから歯が立ちませんでした。
結論から言うと2進数を利用します。

まずは大元となる2進数のグラフを作成します。
2^{x-1} \lt lとなるうちの最大のxを求めます。lが2~3でxは2、4~7でxは3、といった具合です。
そして、x個の頂点を用意して、iからi+1の頂点に、それぞれ0と、2^{i-1}の重みをつけた辺をつくります。
これで、0~2^{x-1}-1まではすでに網羅できています。

f:id:emtubasa:20180904174902p:plain
8 \lt l \lt 15のとき

ということで、あとは残った部分を付け加えていきます。
ここで注目するべきポイントは、

  • 頂点1から頂点iまでには、02^{i-1}-1までの数がそろっている
    ということです。上の図でいうと、頂点1から3までだと0~3、1から2だと0~1、ということです。
    連続した数字がそろっているので、これをうまく利用していきます。
    あと付け加えるべき数字は、2^{x-1}からl-1までになります。
    これらも連続している数字になります。
    ここで、i番目の頂点からxに、pという重みの辺を付けてみると、新しく作成できる数字は
    pp+2^{i-1}-1になります。
    iが大きいほど作成できる数字の個数が多いので、後ろから貪欲に作成できるならする、しないなら次へ、ということを繰り返していけばいいです。
    今残っている未作成の数字がpからl-1とし、次に見る頂点をiとします。

  • l-p、すなわちあと作るべき個数が2^{i-1}以上のとき
    頂点iから頂点xに、重みがpの辺を作成します。
    あと作るべき未作成の数字はp+2^{i-1}からl-1になります。

  • 上記の条件を満たさないとき
    スルーします。

あとは、iを後ろから動かすことにより全探索をします。