AtCoder: 早稲田大学プログラミングコンテスト2019 - D問題: Choose Your Characters

問題概要

とあるアクションゲームにおいて、の番号が振られた種類のキャラがいる。
これらのキャラには、対戦する際の有利不利、もしくは五分の関係がある。
(キャラがキャラに対し有利である場合は、必ずキャラはキャラに不利)
この有利不利の関係は個与えられ、それ以外のキャラ同士の関係は五分となっている。

この時、以下を満たすような区間を選ぶことにした。

• 相手が任意のキャラを選んでも、そのキャラに対し五分もしくは有利になるキャラが1体以上存在する。(相手と同じキャラは除外して考える)

この区間の幅が最小となり、選べる同じ幅の中でもが最小となるを求めよ。

制約

解法

各キャラについて、各において選べる最小幅の区間を求めて、そこから全体で選べる区間の最小幅と最小のを求めた。

ある区間が選べなくなる原因は、キャラ全てのキャラが不利となるキャラが存在することである。
(この時、となる場合、そのキャラを選択することはできないため、キャラはキャラに不利と考える)

ここで各について、区間の中で選べる最小区間を求めることを考える。このの値は、同じに対し各キャラが選べる最小区間のを求め、を求めることで計算する。

各キャラにおける、各に対するは、キャラが不利になるキャラのインデックスをソートし、インデックスの大きい方から選択できない区間の長さを求めることで計算できる。

図で考えると、以下のようになる。 (行は自分が選ぶキャラ、列は相手が選ぶキャラ、表の赤い箇所は自分が不利となる関係である)

6
11
1 2
1 5
3 2
3 5
3 6
5 1
5 3
5 4
6 1
6 2
6 3

図中のmaxを取った値で赤い数字は、選択できる区間が右にはみ出すため選択できないものを表している。
このケースでは、区間が最小(図中の緑の数字)で最も小さいを選ぶので が解となる。

また、どの区間も選択できない場合(全ての箇所で区間が右にはみ出してしまう場合)は"-1"を出力すればよい。
どのくらい区間が連続しているかを求める箇所は全てのキャラ合わせて高々箇所であり、1回のソートサイズは高々であるため、各について選べない区間を計算する時の計算量はである。

そのため、全体の計算量は になる。

実装

提出コード(Python3): Submission #4537616 - 早稲田大学プログラミングコンテスト2019

import sys
readline = sys.stdin.readline
 
N = int(readline())
M = int(readline())
V = [[] for i in range(N)]
for i in range(N):
    V[i].append(i)
for i in range(M):
    a, b = map(int, readline().split())
    V[a-1].append(b-1)

# L[i] = k: 区間Lから選ぶことができる最小区間の長さk
L = [0]*N

# 各キャラiについて、各Lについて選べない区間の長さkを求める
for i in range(N):
    prv = -1; cnt = 0
    v = V[i]
    v.sort(reverse=1)
    for j in v:
        if prv == j+1:
            # 区間が連続していたら+1
            cnt += 1
        else:
            # 区間が飛んだら1に初期化
            cnt = 1
        L[j] = max(L[j], cnt)
        prv = j

# 選ぶことができる最小の区間の長さと、最小のLを求める
r = N+1
ans = None
for i in range(N):
    if L[i] < r and i+L[i] < N:
        ans = i+1
        r = L[i]
if ans is None:
    sys.stdout.write("-1\n")
else:
    sys.stdout.write("%d %d\n" % (ans, ans+r))