TopCoder SRM 687 (Div. 1) Easy. AlmostFibonacciKnapsack

問題概要

以下の漸化式で表される数列が与えられる。

  • A[1]=2
  • A[2]=3
  • A[n]=A[n-1]+A[n-2]-1

整数 x を異なる A[i] の和で表せるだろうか。表せるなら一例を示せ。

解法

異なるフィボナッチ数の和で任意の整数が作れることを知っていれば、この数列でも同じことが成り立つことが予想でき、実際に正しい。

さらにフィボナッチ数のときと同様に、大きい方から貪欲に引いていけば答えになる。ただし引いた結果が 1 にならないように引くという条件が加わる。どうしてそれで上手くいくのか考えてみよう。

まず A[1] から A[k] までを使って作ることのできる数を調べてみる。

f:id:pekempey:20160408171952p:plain

どうやら A[1]+...+A[k]-1 を除けば A[1]+...+A[k] までの任意の整数が作れるらしい。これは帰納法で簡単に示せる。

後は A[k]≦x<A[k+1] を満たす A[k] で x を引いた値が A[1]+...+A[k-1] 以下になることを示せば終わり。

これは x-A[k]≦A[1]+...+A[k-1] 、つまり x≦A[1]+...+A[k-1]+A[k] が示せればいい。右辺にある A[k-1]+A[k] は A[k+1]-1 にでき、x<A[k+1] という前提があるので正しい。

x=A[k]+1 のときは、A[k-1]+A[k-2] を引けば 0 になるので問題ない。


貪欲に DFS すればすぐに解が見つかりそうだったので、本番中は貪欲ではなく貪欲 DFS を書いた。貪欲操作を優先してるので、すぐに解は見つかる。

TopCoder SRM 687 (Div. 1) Easy. AlmostFibonacciKna ...

割と早解きできて良かった。yukicoder 勢が有利な問題?