日々drdrする人のメモ

今日も明日もdrdr

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

コンテスト時間中に解いた。解法メモ。

atcoder.jp

問題概要

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

この時、以下を満たすような区間 {[L, R]}を選ぶことにした。

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

この区間 {[L, R]}の幅が最小となり、選べる同じ幅の中でも {L}が最小となる {L, R}を求めよ。

制約

  •  {2 \le N \le 10^5}
  •  {1 \le M \le \min(2 \cdot 10^5, \frac{N(N-1)}{2})}

解法

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


ある区間 {[L, R]}が選べなくなる原因は、キャラ {j \in [L, R]}全てのキャラが不利となるキャラ {i}が存在することである。
(この時、 {j = i}となる場合、そのキャラ {j}を選択することはできないため、キャラ {j (= i)}はキャラ {i}に不利と考える)


ここで各 {L}について、区間 {[L, L+k]}の中で選べる最小区間を求めることを考える。この {k}の値は、同じ {L}に対し各キャラ {i}が選べる最小区間 {[L, L + k_i]} {k_i}を求め、 {\displaystyle k = \max_i k_i}を求めることで計算する。

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


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

f:id:smijake3:20190311002538p:plain
計算例
以上の図は以下の入力に対する例である。

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を取った値で赤い数字は、選択できる区間が右にはみ出すため選択できないものを表している。
このケースでは、区間が最小(図中の緑の数字)で最も小さい {L}を選ぶので  {L = 2, R = L + 2 = 4} が解となる。


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

そのため、全体の計算量は  {O(N + M \log N)} になる。

実装

提出コード(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))