【競技プログラミング】AtCoder Beginner Contest 257_C問題

問題

要約

1. N人の人がいて、それぞれ子供か大人である。
2. 各人の体重はWiで与えられる。
3. 文字列Sで各人が子供(0)か大人(1)かが示されている。
4. ロボットの高橋君に実数Xを設定すると、体重がX未満なら子供、X以上なら大人と判定する。
5. f(X)は、高橋君がXで判定したときに正しく判定できる人数。
6. f(X)の最大値を求める。

• N: 人の総数
• Wi: i番目の人の体重
• S: 長さNの文字列。0は子供、1は大人を表す
• X: 高橋君に設定する実数（子供と大人を区別する閾値）
• f(X): Xを設定したときに正しく判定できる人数

既存投稿一覧ページへのリンク

一覧ページ

アプローチ1

1. 大人と子供を分離し、それぞれの体重をソートする。
2. 可能性のある閾値Xを特定する。
3. 各閾値について、正しく判定できる人数を計算し、最大値を更新する。
4. 最終的な最大値を出力する。

解法手順1

1. 入力を受け取り、大人の体重リストAと子供の体重リストCを作成する。
2. 閾値の候補として、子供の体重+1と大人の体重を集合optionに追加する。
3. AとCをソートする。
4. 初期の正解数として、全員を大人か子供のどちらかとして判定した場合の大きい方を設定する。
5. 各閾値候補について以下を行う：
   a. 二分探索を使用して、閾値未満の子供の数と閾値以上の大人の数を高速に計算する。
   b. その合計が現在の最大値より大きければ、最大値を更新する。
6. 最終的な最大値を出力する。

ACコード1

ac.py

from bisect import bisect_left

def io_func():
    # 人数Nを入力として受け取る
    N = int(input())
    # 大人か子供かを示すリストSを入力として受け取る
    S = list(map(int, input()))
    # 体重のリストWを入力として受け取る
    W = list(map(int, input().split()))
    return N, S, W

def solve(N, S, W):
    # 大人の体重リストAと子供の体重リストCを初期化
    A, C = [], []
    # 閾値の候補を格納するセットoptionを初期化
    option = set()

    # 大人と子供を分離し、閾値の候補を追加
    for i in range(N):
        if S[i]:
            A.append(W[i])
            option.add(W[i])
        else:
            C.append(W[i])
            option.add(W[i] + 1)
    
    # 大人と子供の体重リストをソート
    A.sort()
    C.sort()
    
    # 大人の数を記録
    M = len(A)
    
    # 初期の正解数を設定（全員を大人か子供のどちらかとして判定）
    ans = max(len(A), len(C))

    # 各閾値候補について正しく判定できる人数を計算
    for w in option:
        # 二分探索を使用して、閾値未満の子供の数と閾値以上の大人の数を計算
        res = bisect_left(C, w) + M - bisect_left(A, w)
        # 最大値を更新
        ans = max(res, ans)
    
    # 最終的な最大値を返す
    return ans

# メイン処理
N, S, W = io_func()
result = solve(N, S, W)
print(result)

###
# N: 人数
# S: 大人か子供かを示すリスト（1が大人、0が子供）
# W: 体重のリスト
# A: 大人の体重リスト
# C: 子供の体重リスト
# option: 閾値の候補を格納するセット
# M: 大人の数
# ans: 正しく判定できる最大人数
# w: 閾値候補
# res: 各閾値候補での正しく判定できる人数

# 1. io_func関数：
#    - 標準入力から必要なデータを読み込む
#    - 人数N、大人/子供を示すリストS、体重リストWを返す
# 2. solve関数：
#    - 大人と子供を分離し、それぞれの体重リストA, Cを作成
#    - 閾値候補をoptionセットに追加
#    - A, Cをソート
#    - 初期の正解数を設定
#    - 各閾値候補について：
#      - 二分探索を使用して正しく判定できる人数を計算
#      - 最大値を更新
#    - 最終的な最大値を返す
# 3. メイン処理：
#    - io_func関数を呼び出してデータを取得
#    - solve関数を呼び出して結果を計算
#    - 結果を出力

ac.py

from abc import ABC, abstractmethod
from bisect import bisect_left
from typing import List, Set, Tuple

class InputReader(ABC):
    @abstractmethod
    def read_input(self) -> Tuple[int, List[int], List[int]]:
        pass

class ConsoleInputReader(InputReader):
    def read_input(self) -> Tuple[int, List[int], List[int]]:
        N = int(input())
        S = list(map(int, input()))
        W = list(map(int, input().split()))
        return N, S, W

class Person:
    def __init__(self, is_adult: bool, weight: int):
        self.is_adult = is_adult
        self.weight = weight

class WeightClassifier:
    def __init__(self, people: List[Person]):
        self.people = people
        self.adults = [p.weight for p in people if p.is_adult]
        self.children = [p.weight for p in people if not p.is_adult]
        self.threshold_candidates = self._generate_threshold_candidates()

    def _generate_threshold_candidates(self) -> Set[int]:
        candidates = set()
        for person in self.people:
            if person.is_adult:
                candidates.add(person.weight)
            else:
                candidates.add(person.weight + 1)
        return candidates

    def find_best_threshold(self) -> int:
        self.adults.sort()
        self.children.sort()
        adult_count = len(self.adults)
        max_correct = max(adult_count, len(self.children))

        for threshold in self.threshold_candidates:
            correct_count = (
                bisect_left(self.children, threshold) +
                adult_count - bisect_left(self.adults, threshold)
            )
            max_correct = max(max_correct, correct_count)

        return max_correct

class WeightClassificationSolver:
    def __init__(self, input_reader: InputReader):
        self.input_reader = input_reader

    def solve(self) -> int:
        N, S, W = self.input_reader.read_input()
        people = [Person(bool(S[i]), W[i]) for i in range(N)]
        classifier = WeightClassifier(people)
        return classifier.find_best_threshold()

# メイン処理
if __name__ == "__main__":
    input_reader = ConsoleInputReader()
    solver = WeightClassificationSolver(input_reader)
    result = solver.solve()
    print(result)