memo: ABC044

A, Bはやるだけ。CはDP。

おそらくだが解説よりも簡単かつ高速な方法で通したと思うので概要を述べる。

1枚目から $i$ 枚目までのカードだけを使ってどのような組み合わせを作れるかを順に求める。

問題設定から、平均がある値になるものだけが重要なので、「狙う平均からの差分の合計」だけを覚えておけば良い。使った枚数は不要。最終的にこの合計が $0$ となるような組み合わせを探す問題となる。

たとえば1つ目の入力例について考えると、狙う平均値は $8$ なので、

1枚目 ($7 \equiv -1$) までを使うと $\{0, -1\}$ （何も取らないと平均が0, 1枚だけ取ると平均が-1になる）
2枚目 ($9 \equiv +1$) までを使うと $\{0, -1, 1, 0\}$
3枚目 ($8 \equiv \pm0$) までを使うと $\{0, -1, 1, 0, 0, -1, 1, 0\}$
4枚目 ($9 \equiv +1$) までを使うと $\{0, -1, 1, 0, 0, -1, 1, 0, 1, 0, 2, 1, 1, 0, 2, 1\}$

となり、全て使った時点で平均が $0$ になっているのは6通り。

ただし、カードを1枚も取らないという手を含むため、その分を引いて答えは5通りとなる。

うまくカウンタのようなものを使うことで全体で $O\left(N\right)$ くらい……のはず。

Dは出来なかった。

$2 \le b \le \sqrt{n}$ は全探索し、 $\sqrt{n} \le b \le n$ は $b$ 進数であらわすと必ず2桁の数になることを使って高速に解ける。

最初解説を聞いてやってみても間に合わずずっと悩んでいたが、unsigned intをlong longに置き換えただけで早くなって通った。いっそPythonで書けばよかったかな。

memo