問題

$K = N - 4 \ge 0$ が与えられる。 自然数の組 $(a, b, c)$ であって $a \le b \le c$ かつ $a + b + c = K$ なものの数を数えよ。

考察過程

  • グラフは忘れてよい。数え上げの問題
  • ${} _ {K + 2} C _ 2$ ですねと思ったら違った。グラフの同型性から $a \le b \le c$ の制約が入るため
  • 次に分けてそれぞれ数えればよい
    1. $a = b = c$ なもの
    2. $a = b \ne c$ なもの
    3. $a \ne b \land b \ne c \ne a$ なもの
  • $n$ が大きいので ${} _ n C _ r$ の階乗がしんどい問題がある
    • これ嘘。$r$ が小さいため
  • (1.) は自明。$3 K$ かどうかだけ
  • (2.) は？ $c \ne K$ であって $K - c$ が偶数なものを数える
  • (3.) は一番厳しそうだな。どうするの
  • $a \lt b \lt c$ なものを数えるのと同じ。差分だけ見るのはどうか？
  • つまり $3a + 2b’ + c’ = K$ な $(a, b, c)$ を数える
  • すぐには出てこない。OEIS したさがあるが……
  • (ここまで20分)
  • $a \lt b \lt c$ なものを数えるのと $a \le b \le c$ なものを数えるのは、何か違いがありますか？
  • 順序の制約なしの場合の全体の数が出てるので、そこから (1.) と (2.) の分引いて $3!$ とかで割れば (3.) が出ますね
  • 解けたでしょ。実装します
  • (ここまで22分)
  • (2.) について確認。$K = (0, 1, 2, 3, 4, 5, \dots)$ のとき $a \le b \le c$ を仮定してその数 $(1, 1, 2, 1, 3, 3, \dots)$
  • $3$ の倍数のとき (1.) の場合を巻き込んでしまうね
  • まとめれる？ (2.) は $3$ 回数えられるけど (1.) は $1$ 回だけなのでまとめることはできません
  • バグった
  • 修正できた。(2.) の式を間違い
  • AC です
  • (ここまで32分)

解法

次の $3$ つは容易に計算できる:

  • 自然数の組 $(a, b, c)$ かつ $a + b + c = K$ なものの数
  • 自然数の組 $(a, b, c)$ かつ $a + b + c = K$ であって $a = b = c$ なものの数
  • 自然数の組 $(a, b, c)$ かつ $a + b + c = K$ であって $a = b \ne c$ なものの数

その結果から目的のものの数はすぐに出る。 $O(1)$。

メモ

リンク