No.1279 Array Battle
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 266
作問者 : 👑
platinum
/ テスター :
mfbgjscz
タグ : / 解いたユーザー数 266
作問者 : 👑
platinum
/ テスター :
mfbgjscz
問題文最終更新日: 2020-09-16 08:06:22
問題文
A君、B君はそれぞれ要素数 $N$ の正の整数列 $a,b$ を持っています。$i$ 番目の要素はそれぞれ $a_i,b_i$ です。
二人はこの整数列を使ってゲームをします。$i$ ターン目 $(i=1,2, \dots,N)$ の行動は次の通りです。
・A君は $a$ からまだ選んでいない要素を自由に一つ選ぶ。B君は $b_i$ を選ぶ。
・A君が選んだ要素の方が大きければA君はその差だけ得点を得る。そうでない場合は得点に変化はない。
A君の要素の選び方は全部で $N!$ 通りあります。この中で、A君が獲得する得点が最大となるような要素の選び方は何通りありますか。
入力
$N$ $a_1\ a_2\ \dots\ a_N$ $b_1\ b_2\ \dots\ b_N$
・入力は全て整数である。
・$1 \le N \le 9$
・$1 \le a_i, b_i \le 10^8$
出力
A君が獲得する得点が最大となるような要素の選び方の場合の数を出力してください。
サンプル
サンプル1
入力
2 3 4 1 4
出力
1
A君は $1$ ターン目に $4$ を選ぶことで $3$ 点を得ることができます。
$1$ ターン目に $3$ を選ぶと、$2$ 点しか得ることができません。
得点が最大の $3$ 点となるのは $1$ 通りなので、$1$ を出力します。
サンプル2
入力
3 5 5 5 7 5 6
出力
6
A君に成す術はなく、どんな選び方をしても得点は $0$ です。
要素の選び方は全部で $6$ 通りあるので、$6$ を出力します。
サンプル3
入力
5 6 5 5 4 4 1 3 5 7 9
出力
28
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。