No.3041 非対称じゃんけん
レベル : / 実行時間制限 : 1ケース 2.200秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 70
作問者 :
Nauclhlt🪷
/ テスター :
Blue_S
eiram
naniwazu
タグ : / 解いたユーザー数 70
作問者 :


問題文最終更新日: 2025-02-09 01:32:06
ストーリー
nauclhltくんはじゃんけんをした時の指の本数の総和が何通り存在するのか気になりました。
出せる手に対称性が無いものをじゃんけんと呼んで良いのかは分かりませんが、気にしません。
問題文
手にちょうど$F$本の指を持つ$N$人がじゃんけんをします。
じゃんけんをするとは、それぞれの人が3つの手のうち1つを独立に選んで出す行為をいいます。
$i(1\leq i\leq N)$番目の人は以下の3つの手から出す手を選ぶことができます。
- 手1: $A_i$本の指を立てる
- 手2: $B_i$本の指を立てる
- 手3: $C_i$本の指を立てる
整数$n(1\leq n\leq N)$に対して、$f(n)$を次のように定義します。
- 人$1, 2, \cdots, n$の$n$人でじゃんけんをしたときに、立っている指の本数の和としてあり得る非負整数の個数
例えば、$N=2, F=5, A=(0, 0), B=(2, 2), C=(5, 5)$のとき、$f(1)=3, f(2)=6$です。
$F, A, B, C$および正整数$N$が与えられるので、$k=1, 2, \cdots, N$に対して$f(k)$を求めてください。
入力
$N\ F$ $A_1\ A_2\ \cdots\ A_N$ $B_1\ B_2\ \cdots\ B_N$ $C_1\ C_2\ \cdots\ C_N$
- $1\leq N\leq 1.5\times 10^4$
- $1\leq F\leq 60$
- $0\leq A_i, B_i, C_i\leq F$
出力
$N$行出力してください。$k(1\leq k\leq N)$行目には、$f(k)$の値を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 5 0 0 0 2 2 2 5 5 5
出力
3 6 10
一般的なじゃんけんです。
- 人1がじゃんけんをするとき、立っている指の本数としてあり得るものは$0, 2, 5$の$3$通りです。
- 人1, 2がじゃんけんをするとき、立っている指の本数としてあり得るものは$0, 2, 4, 5, 7, 10$の$6$通りです。
- 人1, 2, 3がじゃんけんをするとき、立っている指の本数としてあり得るものは$0, 2, 4, 5, 6, 7, 9, 10, 12, 15$の$10$通りです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。