問題一覧 > 通常問題

No.1906 Twinkle Town

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : 👑 hitonanodehitonanode / テスター : SumitacchanSumitacchan
6 ProblemId : 7731 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 01:16:51

問題文

ある街に $10^9$ 本の街灯と,これらの街灯を点灯・消灯させるための $N$ 本の魔法のステッキがあります.はじめ,全ての街灯は消灯した状態です.また,各ステッキ $i$ ($1 \le i \le N$) にはパワーと呼ばれる値 $A_i$ が定まっています.

電飾太郎さんと節電次郎さんの二人がこれらのステッキを使ってゲームをします.二人は交互に一本ずつステッキを選び,選んだ本人が直ちにこれを振っていきます.なお,電飾太郎さんが先手です.ステッキを二人のいずれかが振ると,それぞれ以下の効果があります.

  • 電飾太郎さんがパワー $A$ のステッキを振ると,街灯 $1, \dots, A$ が(それ以前の状態に関わらず)点灯した状態に変化する.
  • 節電次郎さんがパワー $A$ のステッキを振ると,街灯 $1, \dots, A$ が(それ以前の状態に関わらず)消灯した状態に変化する.
ただし,全てのステッキは一度振ると消滅してしまうため,同じステッキを複数回選ぶことはできません.$N$ 本のステッキを振り終えた時点で点灯した状態の街灯の数をゲームのスコアと呼びます.

電飾太郎さんはスコアの最大化を,また節電次郎さんはスコアの最小化を目標として常に最適な戦略を取ります(また,お互いの目標など全ての情報は両者とも既知であるものとします).二人で全てのステッキを振り終えた時点でのスコアを求めてください.$T$ 個のテストケースが与えられるので,それぞれについて解答してください.

入力

1 行目に,入力に含まれるテストケース数が与えられます.

$T$

その後 $2T$ 行にわたって各テストケースが与えられます.各テストケースは以下の形式で 2 行にわたって与えられます.

$N$
$A_1 \ A_2 \ \dots A_N$

  • $1 \le T \le 2 \times 10^4$
  • $1 \le N \le 2 \times 10^5$
  • $1 \le A_i \le 10^9$ $(1 \le i \le N)$
  • 一つの入力データに含まれる $T$ 個の $N$ の総和は $2 \times 10^5$ 以下
  • 入力は全て整数

出力

$T$ 行にわたって出力してください.$i$ 行目 $(1 \le i \le T)$ には $i$ 個目のテストケースの答えとなる整数を出力してください.$T$ 行目の最後でも改行してください.

サンプル

サンプル1
入力
1
3
3 4 6
出力
5

電飾太郎さんが最初にパワー $6$ のステッキを振ると,街灯 $1, 2, 3, 4, 5, 6$ が点灯した状態になります.二手目で節電次郎さんがパワー $4$ のステッキを振ると,街灯 $5, 6$ のみが点灯した状態に変化します.最後に電飾太郎さんがパワー $3$ のステッキを振ると,街灯 $1, 2, 3, 5, 6$ の $5$ 本 が点灯した状態になります.

一方が上記と異なるゲーム進行をとろうとした場合,(相手が最適な手を選ぶことで)必ず上記の結果より不利なゲーム結果になることが確かめられます.よって両者が最適な行動をとった場合の結果として $5$ を出力します.

サンプル2
入力
1
3
3 5 6
出力
5

サンプル3
入力
4
1
8
2
10 4
4
3 5 1 7
5
6 7 8 3 9
出力
8
6
4
7

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