POJ-1011, LiveArchive-5522, UVa-307, SPOJ-STIJ, TJU-1009 : Sticks

蟻本 PKU UVa SPOJ

問題概要

ある数aがb個ある。それぞれの数を分割する作業を繰り替えした結果が与えられる。aとして考えられる最小値を求める問題。

解法

探索で頑張る。
長い順に調べた方が枝刈りしやすそうであることは直感的に分かる。
最初は、長い順に元はどの木片であったか絞っていく探索を書いていたが、これだと枝刈りのタイミングが遅くなってしまいTLEしてしまう。
なので、ある長さの木片を順に構成することにする。
重複を防ぐように注意して枝刈りする。また、分岐係数や深さを抑えるために鳩ノ巣原理とかを使うと少し速くなる。
フォーラムにも書かれているけど、acceptされたコードでもTLEさせられるような入力が存在するので何だかなあという気分になる。最初書いていた方だと一瞬で終わるのに…。
SPOJ、TJUのは微妙に入力（というか問題）が変わっているらしくWAになってしまった。

続きを読む