Sticks(4)

探索イメージ

探索方法がイマイチ掴み難いという人もいるかもしれないので、ちょっと図を描いてみた。

ポイントを整理しておくと、

(1)データを降順にソートしておく。
(2)値の大きい順(=配列の前から順)に、stickの長さ(=length)から0になるまで値を引いていく。同時に、使用した値にはラベリングしておく。
(3)長さ0になったら、lengthを元の長さにセットしなおして(2)を再実行
(4)失敗したらバックトラック
(5)長さがlengthのstickがsum/length本できれば成功。

DFSの肝は、

最も新しくラベリングされた点に隣接する点を探索する

というところだ。つまり図の中では、探索を左側から順に行うことになる。一旦15-4-...と探索を始めたら、「どうやってもムリ！」というところまで探索してからバックトラックしていく。今回の解は15-3-2-...なので、図の①〜③は無駄な作業になるわけだが、早い段階で見つかればそこから右(図の⑤以降)は調べる必要がなくなる。

また、今回はstickの長さを揃えるという目的があるので、各値の組み合わせを網羅的に行う必要がない。大きい順に引いていくということは、図中の15や11が出てくる部分は最初から確定しているのだ。計算量もO(辺の数+点の数)程度に見積もることができる。