問題一覧 > 通常問題

No.3049 Contest Coordinator

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 79
作問者 : suisen / テスター : ochiaigawa 👑 rin204
8 ProblemId : 11848 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-08 13:48:25

ストーリー

コンテストを開くにあたっては、難易度の逆転や崖が少なくなるように問題セットを作成したいです。

問題文

長さ NN の正整数列 D=(D1,D2,…,DN)D = (D _ 1, D _ 2, \ldots, D _ N) と非負整数 TT および正整数 X,YX, Y が与えられます。

T,X,YT,X,Y に対して、長さ kk の数列 A=(A1,A2,…,Ak)A = (A _ 1, A _ 2, \ldots, A _ k) の 不満度 f(A)f(A) を次で定義します。

f(A)f(A) の定義

整数 i∈{1,2,…,k−1}i\in\lbrace 1,2,\ldots,k-1\rbrace のうち Ai+1−Ai>TA _ {i + 1} - A _ i \gt T を満たすものの個数を pp、Ai+1−Ai<0A _ {i + 1} - A _ i \lt 0 を満たすものの個数を qq として、f(A)≔pX+qYf(A) \coloneqq pX + qY と定める。

全ての k=1,2,…,Nk = 1,2,\ldots, N に対して次の (問題 kk) を解いてください。

(問題 kk)

DD から kk 個の要素を取り出して任意に並べ替えて出来る長さ kk の数列の 不満度 の最小値を求めてください。

より形式的には、min⁡I∈IN,kf(D[I])\displaystyle \min _ {I \in \mathcal{I} _ {N, k}} f(D\lbrack I\rbrack) を求めてください。ここで、IN,k\mathcal{I} _ {N, k} は次の条件を全て満たす長さ kk の整数列 I=(I1,I2,…,Ik)I = (I _ 1, I _ 2, \ldots, I _ k) 全体の集合であり、また D[I]≔(DI1,DI2,…,DIk)D\lbrack I\rbrack \coloneqq (D _ {I _ 1}, D _ {I _ 2}, \ldots, D _ {I _ k}) です。

  • 任意の i∈{1,2,…,k}i \in \lbrace 1,2,\ldots,k\rbrace について、Ii∈{1,2,…,N}I _ i\in\lbrace 1,2,\ldots,N\rbrace
  • 任意の i,j∈{1,2,…,k}i, j\in \lbrace 1,2,\ldots,k\rbrace について、i≠ji \neq j ならば Ii≠IjI _ i \neq I _ j

入力

入力は以下の形式で標準入力から与えられます。

NN TT XX YY
D1 D2 ⋯ DND _ 1\ D _ 2 \ \cdots \ D _ N
  • 入力は全て整数で与えられる。
  • 1≤N≤5×1051\leq N\leq 5\times 10 ^ 5
  • 0≤T≤1090\leq T\leq 10 ^ 9
  • 1≤X,Y≤1091\leq X,Y \leq 10 ^ 9
  • 1≤Di≤1091\leq D _ i \leq 10 ^ 9

出力

(問題 kk) に対する答えを SkS _ k として、S1,S2,…,SnS _ 1, S _ 2, \ldots, S _ n をこの順に空白区切りで出力して改行してください。

S1 S2 ⋯ SnS _ 1\ S _ 2 \ \cdots \ S _ n

サンプル

サンプル1
入力
3 2 1 2
1 7 5
出力
0 0 1

この入力は N=3, T=2, X=1, Y=2, D=(1,7,5)N = 3,\ T = 2,\ X = 1,\ Y = 2,\ D = (1,7,5) を表します。

  • k=1k = 1 のとき、考えられる数列は (1), (7), (5)(1),\ (7),\ (5) の 33 つですが、そのいずれも不満度は 00 です。従って、k=1k=1 に対する答えは 00 です。
  • k=2k = 2 のとき、考えられる数列は (1,7), (7,1), (1,5), (5,1), (7,5), (5,7)(1,7),\ (7,1),\ (1,5),\ (5,1),\ (7,5),\ (5,7) の 66 つです。それぞれの不満度は以下のようになるので、k=2k=2 に対する答えは 00 です。
    • (1,7), (1,5)(1,7),\ (1,5) は p=1, q=0p=1,\ q=0 なので不満度は 11 です。
    • (7,1), (5,1), (7,5)(7,1),\ (5,1),\ (7,5) は p=0, q=1p=0,\ q=1 なので不満度は 22 です。
    • (5,7)(5,7) は p=0, q=0p=0,\ q=0 なので不満度は 00 です。
  • k=3k = 3 のとき、考えられる数列は (1,7,5), (7,1,5), (1,5,7), (5,1,7), (7,5,1), (5,7,1)(1,7,5),\ (7,1,5),\ (1,5,7),\ (5,1,7),\ (7,5,1),\ (5,7,1) の 66 つです。それぞれの不満度は以下のようになるので、k=3k=3 に対する答えは 11 です。
    • (1,7,5), (7,1,5), (5,1,7)(1,7,5),\ (7,1,5),\ (5,1,7) は p=1, q=1p=1,\ q=1 なので不満度は 33 です。
    • (1,5,7)(1,5,7) は p=1, q=0p=1,\ q=0 なので不満度は 11 です。
    • (5,7,1)(5,7,1) は p=0, q=1p=0,\ q=1 なので不満度は 22 です。
    • (7,5,1)(7,5,1) は p=0, q=2p=0,\ q=2 なので不満度は 44 です。
サンプル2
入力
5 4 3 2
1 1 1 1 1
出力
0 0 0 0 0

どのように選んでも常に不満度は 00 です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。