Overview

This is a problem where you select the top \(K\) candidates by score from the remaining candidates after excluding those who withdrew, and determine whether Takahashi (candidate \(1\)) is among them.

Analysis

The key points in this problem are as follows:

1. Excluding withdrawn candidates: First, you need to remove withdrawn candidates from consideration. Since the numbers of withdrawn candidates are given, storing them in a set allows \(O(1)\) lookup to check whether a candidate has withdrawn.

2. Tiebreaking rule: When scores are tied, “the candidate with the smaller number ranks higher.” Since Takahashi is number \(1\), he is in the most advantageous position when there are candidates with the same score.

3. Ranking by sorting: If you sort the non-withdrawn candidates by “score in descending order, then by number in ascending order for ties,” the first \(K\) candidates are the ones who pass.

Even with a straightforward approach, you only need to sort \(N\) candidates, so \(O(N \log N)\) is fast enough. No special optimization is needed.

Algorithm

1. Store the numbers of withdrawn candidates in a set withdrawn.
2. From candidates \(1\) through \(N\), extract only those who have not withdrawn.
3. Sort the extracted candidates in descending order of score. For ties, sort in ascending order of number.
   • In implementation, if you create a tuple \((-S_i, i)\) for each candidate and sort in ascending order, candidates with higher scores come first, and among those with equal scores, candidates with smaller numbers come first.
4. If number \(1\) (Takahashi) is among the first \(K\) candidates after sorting, output Yes; otherwise, output No.

Concrete Example

If there are 5 candidates with scores \([80, 90, 80, 70, 85]\), \(K=3\), and no withdrawn candidates:

Sorting the tuples in ascending order: \((-90, 2), (-85, 5), (-80, 1), (-80, 3), (-70, 4)\)

The top \(3\) are candidates \(2, 5, 1\) → Takahashi (candidate \(1\)) is included, so the answer is Yes.

The key point is that among the tied candidates \(1\) and \(3\), candidate \(1\) with the smaller number ranks higher.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting the candidates)
• Space complexity: \(O(N)\) (for storing the candidate list and the set of withdrawn candidates)

Implementation Notes

• Fast lookup of withdrawn candidates: By storing the withdrawn candidate numbers in a set, you can check whether each candidate has withdrawn in \(O(1)\).

• Sorting key trick: Since Python tuples are compared lexicographically from the first element, using \((-S_i, \text{number})\) achieves “descending score, ascending number” ordering with a single sort() call. The technique of negating the score is commonly used in competitive programming.

• Case \(M = 0\): When there are no withdrawn candidates, the third line does not exist. If you read all input at once using sys.stdin.read().split(), no special handling is needed for this case.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    withdrawn = set()
    for i in range(M):
        withdrawn.add(int(input_data[idx + i]))
    
    # Build list of (score, number) for non-withdrawn candidates
    # Sort by (-score, number) so higher score first, then smaller number first
    candidates = []
    for i in range(N):
        num = i + 1
        if num not in withdrawn:
            candidates.append((-S[i], num))
    
    candidates.sort()
    
    # Top K candidates pass
    for i in range(K):
        if candidates[i][1] == 1:
            print("Yes")
            return
    
    print("No")

main()

This editorial was generated by claude4.6opus-thinking.