問題

$N$ 個の整数が与えられます。 $i$ 個目の整数は $a_i$ です。 与えられたすべての整数を赤、緑、青の $3$ 色のいずれかで塗り、以下の条件を満たすようにする方法の個数を $998244353$ で割ったあまりを求めてください。

  • 赤、緑、青で塗られた整数の総和をそれぞれ $R, G, B$ とする。三辺の長さがそれぞれ $R, G, B$ であるような正の面積の三角形が存在する。

考察過程

思い出し:

  1. 総和 $(R, G, B)$ の条件は $R + G + B \gt 2 \max(R, G, B)$ に等しい。
  2. 補集合を数えると楽そう。
  3. $R + G + B = \sum a_i$ は固定なので最大値の側だけ考えればよい。
  4. 全体 $3^n$ から「最大の総和が $\sum a_i / 2$ を超えるものの数」を引けばよい。
  5. DP やるだけぽい。
  6. 書いた。だめ。$\sum a_i$ が偶数の場合だけ落ちる。
  7. 最大値 $C$ がよくても $A = 0$ だとだめ。
  8. $A = 0, ~ B = C = \sum a_i / 2$ のような場合がだめっぽい。
  9. (時間切れ)

解法

三角形を作れる条件は最大の辺が $\sum a_i / 2$ 以上であること。 $\sum a_i$ が奇数の場合は自然に DP やるだけ。 偶数の場合も同様だが、 $(\sum a_i / 2, \sum a_i / 2, 0)$ などの形を重複して数えてしまうのでこれを別の DP で求めて引いてやる必要がある。 計算量は $O(N \sum a_i)$。

反省

  • 方向は見えていたのに時間切れ。深く考えずに実験や係数ガチャで脳死で通そうとしたのがだめ。
  • ちゃんと考察過程を wiki にまとめていくようにすれば冷静さが得られたりしないか？
  • 「これ足しすぎてるから引けばよさそう」ではなくてきちんと「包除原理」と言葉にする必要があった気がする。後から言われて「ああこれのことね」と気付いたのはよくなさそう。
  • 1行修正したらAC。なぜなのか。

リンク