Codeforces Round #616 Div.2 C (Div.1 A) Mind Control (R1700)

codeforces.com
問題名が面白い

問題概要

長さnの配列aがある。
人がn人いて、順番に配列aの右端か左端の数を取っていく。
自分はn人のうちm番目である。
n人のうちk人まで、左右どちらを取るかを指定する事ができる。
自分が取れる数を最大化したいとき、これの最小値はいくつか？
（つまり、自分は必ずこれ以上の数が取れる、という数を求めたい）

制約

入力あたりのテストケース数t <= 1000
1 ≤ m ≤ n ≤ 3500
0 ≤ k ≤ n−1
1 <= a_j <= 10^9 (j=1,2,...n)
∑n<=3500

考察・解法

nの合計<=3500より、O(N^2)かなあとすぐ思う。
「固定できるものがないか」という定石に従い、説得できるk人を固定することを思いつく。

1. k >= mの場合（自分より前の人全員の取り方を指定できる場合）
左右の端からそれぞれm番目までの中で任意の要素を取れるので、その中の最大が答え。
（例えば左からp番目が取りたいなら、説得できるk人のうちp-1人を左から、m-(p-1)人を右から取らせればいい）

2. k < m の場合（自分より前に、取り方を指定できない人がいる場合）
指定できるk人を、
（パターン0）左から取る人が0人で右から取る人がk人
（パターン1）左から取る人が1人で右から取る人がk-1人
……
（パターンk）左から取る人がk人で右から取る人が0人
のように固定する。
左からp人、右からk-p人を説得する場合の、 残りの配列がt = a[p:n-k+p]になる。
p=0,1...kについて、説得できない人（m-k人)を動かしていき、自分が取れるもの（説得できる人&説得できない人が取り終わったあとの、左右の端うち大きいもの）をリストdに入れていき、説得できない人を動かし終わったら、dの最小値（説得できない人がどのように取ったとしても、この最小値以上の数は取れるので）をリストbに入れる。
するとリストbには、パターン0～パターンkそれぞれの、"説得できない人たちがどのように取ったとしても自分が取れる数の最小値"が入っているため、これの最大が答えとなる。

# Codeforces Round #616 Div.2 C (Div.1 A)  Mind Control
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    q = int(input())
    for _ in range(q):
        n, m, k = map(int,input().split())
        a = list(map(int,input().split()))
        b = []
        if k >= m:
            for p in range(m):
                b.append(max(a[p],a[n-p-1]))
        else:
            for p in range(k+1):
                t = a[p:n-k+p]
                d = []
                for p in range(m-k):
                    d.append(max(t[p],t[p+n-m]))
                b.append(min(d))
        print(max(b))

if __name__ == '__main__':
    main()