[AtCoder Daily Training HARD 2024/05/14 17:30start] 参加記録

AtCoder Daily Training HARD 2024/05/14 17:30start に参加しました。
0冠です。
ひどいもんだ。

E - Robot Takahashi

もしくは こちら

考え方

体重の小さい順に並べ、順にボーダーラインをチェックして、$f(X)$ の増減を確認します。
基本的に公式解説通りです。

注意するべきは、体重が同じ場合の処理です。
体重が同じ場合、その間にボーダーを置くことができず、まとめて処理する必要があります。
if i != n - 1 and weight == sw[i + 1][0]: で体重が同じ場合を判定しています。

実装例(Python)

def solve(n: int, s: str, w: list[int]) -> int:
    sw: list[tuple[int, bool]] = []
    adult_cnt: int = 0
    child_cnt: int = 0
    for i in range(n):
        is_adult = s[i] == "1"
        sw.append((w[i], is_adult))
        if is_adult:
            adult_cnt += 1
        else:
            child_cnt += 1

    sw.sort()
    # print(sw)

    rtn: int = adult_cnt
    right: int = adult_cnt
    for i, (weight, is_adult) in enumerate(sw):
        if is_adult:
            right -= 1
        else:
            right += 1
        if i != n - 1 and weight == sw[i + 1][0]:
            # 重さが同じ場合、まとめて処理する
            continue
        rtn = max(rtn, right)
        # print(right)

    return rtn


if __name__ == "__main__":
    N: int = int(input())
    S: str = input()
    W: list[int] = list(map(int, input().split()))
    result: int = solve(N, S, W)
    print(result)

感想

時間内に解けませんでした。
やったことあるのにも関わらず、愚かですね。
最大の敗因は、体重が同じ場合の処理の判定ミスです。
後ろのものを見るべきにも関わらず、一つ前を保存して比較していたため、WA が出ました。