https://beta.atcoder.jp/contests/arc102/tasks/arc102_b
整数$L$が与えられる。以下のような条件を満たす有向グラフを1つ作って出力せよ(多重辺があってもよい)。
長さが0から$L-1$までの相異なるパスというのはそのまま2進数と対応させることができて、$2^n$の長さの辺をそれぞれ高々1回だけ通れるようなグラフを作れば任意の長さのパスを作ることができる。これは、頂点を1列に並べて
ということを繰り返せば達成できる。ただし、これだけでは$L$が$2^n$となっているテストケースには正解できるが、そうでないものには正解できない(たとえば、長さ0から7のパスが作れるグラフを構築することはできるが、長さ8のパスを作れるグラフを作ろうとすると長さ15までのパスも同時に作れるようになってしまう)。これは簡単に解決できて、たとえば長さ7までのパスを作れるグラフを(頂点数4)構築したあとに頂点1から頂点4に長さ8の辺をつければ長さ8のパスが作れるようになる。その代わりに頂点2から伸ばせば長さ8から9のパスが、頂点3から伸ばせば長さ8から11のパスが作れるようになる。このように途中の点から終点までの間に適切な長さのバイパスを構築することで、任意の長さまでのパスが作れるようなグラフに作り替えられる。実装方法としては、現在のグラフで作れるパスの最大の長さを$M$として、頂点を終点から順に見て、そこまでで作れる長さ+$M$が$L$より小さいならその点から終点に長さ$M+1$のパスを引く、ということを繰り返せばよい。
この問題には別解が存在する。前提条件として
ということを利用する。ここで、あるグラフについて「$L$を+1する」「$L$を2倍する」という操作ができれば、それらの操作を適切に行うことで$L=2$のグラフから任意$L$についてグラフを作れる。+1の操作だけでも任意のグラフが作れるのだが、2倍の操作を加えることで計算量が$O(\log{L})$に落ちる。
$L$を+1する操作は、頂点1から最も番号の大きい頂点に長さ$L$の辺を引く操作である。$L$を2倍する操作は、今ある辺の長さをすべて2倍したあと最も番号の大きい頂点から新しい頂点に長さ0,1の辺を引く操作である。繰り返し二乗法の要領でこれらの操作をする順番を決めることができる。
解法はコンテスト中にわかっていて、実装もほとんど終わっていたが微妙なバグを埋め込んでしまい間に合わなかった。別解については全く思いつかなかったが任意の整数を$n$倍と+1で構成するテクニックはARC084-Dを彷彿とさせる。どうやら典型らしいので覚えておきたい。