手始めに、\(X\) 単位時間ちょうどにする設定で解きましょう。

チケットを \(i\) 枚買った人のうち選ばれる人数を \(t_i\) とします。問題は以下のように言い換えられます。

• 整数組 \((t_1,t_2,t_3,t_4)\) を、以下の制約を満たすように選ぶ通り数を求めよ。
  • \(0\leq t_1\leq T_1;\) \(0\leq t_2\leq T_2;\) \(0\leq t_3\leq T_3;\) \(0\leq t_4\leq T_4\)
  • \(t_1+t_2+t_3+t_4=N\)
  • \(t_1+2t_2+3t_3+4t_4=X\)

\(t_i\) の上限制約を外して解いて良いです。上限に違反している場合を包除原理で排除すれば正しくなるためです。

すこし変形すると、まず以下の問題になって、

• \(t_2+t_3+t_4\leq N\)
• \(t_2+2t_3+3t_4=X-N\)

\(x_1=t_4,x_2=t_3+t_4,x_3=t_2+t_3+t_4\) とおくと、以下の問題になります。

• \(x_1\leq x_2\leq x_3\)
• \(x_3\leq N\)
• \(x_1+x_2+x_3=X-N\)

\(x_3\leq N\) の代わりに \(\max(x_1,x_2,x_3)\leq N\) を考えて、\(x\) の大小関係の制約をいったん外します。あとでsortedであるもののみ数えられればよいです。

これは包除原理と二項係数で求めることができて、基本的には \(6\) で割ればよいです。ただ、\(x\) の複数の要素が同じ場合だけずれるので、その分は個別に足す必要があります。とはいえ \(O(1)\) で求めるべき値は計算できています。

ところで、元の問題は \(X\) 時間以下の代わりに変な条件がついているのでした。ここで、\(t_1\ne T_1\) とすると、ちょうど \(X\) 時間でないといけないことがわかります。なので、\(X-1\) 時間以下になるなら \(t_1=T_1\) としてよく、そうして残りので問題を解けばよいです。

これは \(t_2\) 以降についても同じことが言えるので、結局 \(4\) 個の \(X\) について問題を解けばよいです。全員選べるかつ全員選ぶ場合、\(X-3\) 時間未満でもよいことに注意してください。

ところで、はじめの想定は \(O(N)\) の解法でした。なんとなくAIに投げたら解かれて、解法が正しいことを私とhighlighterが確かめたのでこれで出題しました。私は、弱い…