Sticks(2)

基本アルゴリズム

前回のような簡単なInputであれば、少々無駄な探索アルゴリズムでも解を求めることが出来る。しかし、PKU1011のテストケースはそこそこ厳しいので、下手なアルゴリズムだとTLE(Time Limit Exceed)要するにタイムオーバーとなる。

とりあえずプログラムを作ってみるのも良いかもしれないが、この手の探索にはDFS(Depth First Search)というものがある。inputの各値を頂点と考えて、最初の点から順番につなぎ木(リスト)を作っていく。

前回までの例は簡単すぎて説明にならないので、次のようなinputを用意する。

8 3 8 15 2 11 4 8 1

この9つの値の合計(sum)は60。最大値(max)は15だから、60の約数から15未満の数を省いた、15,20,30,60(=length)について順に調べればよい。

まず、lengthが15になるような木を考える。9つの値を降順にソートすると、

15 11 8 8 8 4 3 2 1

このリストを先頭から順に、足して15になるところで区切っていく。

①15

②11-4

③8-...

15はそのまま。次は11+4でok。しかし次の値8は、8を足すと16で超えてしまうし3,2,1をすべて加えても14。15にはならないので、長さ15でそろえることは不可能だと分かる。では、次のようにしてはどうか

①15

②11-3-1

③8-...

これもダメ。結局上記と同じような理由で長さ15にそろえることは出来ない。

20にすることは出来るだろうか。

①15-4-1

②11-8..

最初に15-4-1と選んでしまうと、2本目でいきなり詰まる。それでは20でも無理なのかと言えば、そうではない。

①15-3-2

②11-8-1

③8-8-4

最初で15-3-2とすれば、後はうまくいく。よって答えは20。

あとは、このような探索をプログラムで表現してやればよい。