Australia

ウォンバットのブログ

AtCoder Regular Contest 102 D - All Your Paths are Different Lengths

これは流石に解きたかった

問題

https://beta.atcoder.jp/contests/arc102/tasks/arc102_b

解法

  • 頂点 iから頂点 i+1に長さ 0の辺と長さ 2^{i-1}の辺を張る

とすると、経路長 0から 2^{N-1}-1のパスが1本ずつできます。
まずはこれでパスの最大長さを Lを超えない最大まで持って行きましょう。そこから、

  • 頂点 iから頂点 Nに長さ 現在あるパスの最大長さ+1の辺を張る

とすると、パスの最大長さが 2^{i-1}だけ更新されることがわかります。したがって、 L-2^{N-1}の二進数における各桁を取り出しながら、適切に辺を張り最大長さを更新していけばよいです。

実装

https://beta.atcoder.jp/contests/arc102/submissions/3123362

反省

解法の上2行まではすぐでしたが、そこから先の考察がお粗末すぎました。
あくまで二進数を詰める方向で行けばよかったのですが、途中でこれでは無理だと勘違いして基数を変えてみたりしていました。
最初からある程度道が開けていただけに変に焦ってしまったところはあると思います。
しかしながらやっぱり