ABC031 C - 数列ゲーム
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time import numpy as np # 時々使う # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) # MOD = 10 ** 9 + 7 MOD = 998244353 INF = float('inf') def solve(N, A): ret = -INF for i in range(N+1): max_a = -INF tmp_ret = -INF for j in range(N+1): if i == j: continue tmp_t, tmp_a = 0, 0 T = A[min(i, j):max(i, j)+1] for k in range(len(T)): if k % 2 == 0: tmp_t += T[k] else: tmp_a += T[k] if max_a < tmp_a: tmp_ret = tmp_t max_a = tmp_a ret = max(ret, tmp_ret) return ret def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() A = il() print(solve(N, A)) if __name__ == '__main__': main()
回答
高橋君の位置を一意に決めることで、青木君の点数を求めることが出来ます。
ケース数が少ないため、全ての位置で点数を求めて、得られる最高点を探索します。
一見複雑なゲームですが、高橋君の位置を決めると、青木君の得点を求めることが出来ます。
そのため、以下の3つを繰り返して回答を探索することが出来ます。
- 高橋君の位置
i
(0 <= i < N
)を決める - 青木君が取りうる全ての位置
j
(i != j, 0 <= j < N
)から、青木君が最も得点を得られる位置を探索する - 青木君が最も点数を得られる位置
j
の中で、高橋君が得られる最も高い得点を回答とする
以上の手順を行うと、高橋君と青木君の全ての位置を試す、全探索になります。
しかし、2 <= N <= 50
と、取りうる位置の範囲は狭いため、全探索でも十分に高速です。