【AtCoder】PythonでABC323を解く

はじめに

abc323のA,B,C,D問題をPython3で解きます。

A問題: Weak Beats

atcoder.jp

問題の概要

16bitの数値が与えられる。MSB(最上位ビット)から見た2bit目、4bit目、…、16bit目といった偶数目のビット全てが0かを答えよ。

問題の考察

偶数目のビットを1とした0b0101010101010101とのビット演算子の論理積を取ることで判定します。

コード

def main():
    S = int(input(), 2)
    ans = "No" if S & 0b0101010101010101 else "Yes"
    print(ans)


if __name__ == "__main__":
    main()

B問題: Round-Robin Tournament

atcoder.jp

問題の概要

からまでの番号が付いたプレイヤー人での総当たり戦の結果が与えられる。勝利数が多い方が順位は上になり、勝利数が同じ場合はプレイヤー番号が小さい方が順位は上になる。順位が高い順にプレイヤー番号を答えよ。

問題の考察

勝利数とプレイヤー番号のタプルを作ってソートします。

コード

def solve(N, Ss):
    wins = [0] * N
    for i, S in enumerate(Ss):
        for s in S:
            if s == "o":
                wins[i] += 1

    X = [(-w, i) for i, w in enumerate(wins, 1)]
    X = sorted(X)

    ans = [i for _, i in X]

    return ans


def main():
    N = int(input())
    Ss = [input() for _ in range(N)]
    ans = solve(N, Ss)
    print(*ans)


if __name__ == "__main__":
    main()

C問題: World Tour Finals

atcoder.jp

問題の概要

人のプレイヤーそれぞれについて、点数な問の問題をある時刻に解いた結果が与えられる。各プレイヤーについて、その時刻の最高点を上回るのに必要な解くべき問題数の最小値を求めよ。

問題の考察

点数の高い順に問題をソートしておき、まだ解いていない問題から加算していくことで、最高点を超えるのに必要な問題数を計算します。

コード

def solve(N, M, A, Ss):
    scores = [
        i + sum(A[j] for j, s in enumerate(S) if s == "o") for i, S in enumerate(Ss, 1)
    ]
    target = max(scores)

    X = [(a, i) for i, a in enumerate(A)]
    X = sorted(X, reverse=True)

    ans = []
    for i, (S, score) in enumerate(zip(Ss, scores)):
        if score == target:
            ans.append(0)
        else:
            n = 0
            for a, j in X:
                if S[j] == "x":
                    score += a
                    n += 1
                    if score > target:
                        ans.append(n)
                        break

    return ans


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    S = [input() for _ in range(N)]
    ans = solve(N, M, A, S)
    print(*ans)


if __name__ == "__main__":
    main()

D問題: Merge Slimes

atcoder.jp

問題の概要

種類のサイズのスライムがおり、サイズのスライムは匹いる。同じサイズのスライムが2匹いるとき、合成することでその2匹は消滅して代わりに倍のサイズのスライム1匹になる。最小でスライムは何匹になるか。

問題の考察

小さいサイズから順に合成していけばよさそうです。ヒープに初期値として種類のサイズを入れておき、小さいサイズから取り出しつつ合成したら倍のサイズをヒープに入れます。

コード

from collections import Counter
from heapq import heappop, heappush


def solve(N, S, C):
    cnts = Counter()
    for s, c in zip(S, C):
        cnts[s] += c

    heap = []
    for s in S:
        heappush(heap, s)

    while heap:
        s = heappop(heap)
        if cnts[s] > 1:
            cnts[2 * s] += cnts[s] // 2
            cnts[s] %= 2
            heappush(heap, 2 * s)

    return sum(cnts.values())


def main():
    N = int(input())
    S, C = list(zip(*[list(map(int, input().split())) for _ in range(N)]))
    ans = solve(N, S, C)
    print(ans)


if __name__ == "__main__":
    main()