らくがき入門

機械学習を始めとしたコンピュータサイエンスを主に扱っています。

ABC141の解法

本日開催されたABC141のD問題までの解法について書きます。

A: Weather Prediction

特に工夫はなく、if文を連打してAC

S = input()

if S == 'Sunny':
    print('Cloudy')
elif S == 'Cloudy':
    print('Rainy')
elif S == 'Rainy':
    print('Sunny')

B: Tap Dance

問題文から奇数のときはL以外、偶数のときはR以外を出さないとYesにならないことがわかる。 これらを判定し、もしNoが出た場合はexitするように書くことでAC。

from sys import exit


S = input()

for i in range(len(S)):
    num = i+1
    if num % 2 == 1 and S[i] == 'L':
        print('No')
        exit()
    if num % 2 == 0 and S[i] == 'R':
        print('No')
        exit()
print('Yes')

C: Attack Survival

参加者それぞれの正解数をカウントして、(全体正解数Q-参加者の正解数V)を計算することで、 参加者それぞれの不正解数がわかる(今回の問題では不正解数分だけ最初にもっていたKポイントから減算されるという問題設定)。 よって、Q-V がKを超えるかどうかを判定し、AC。

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]

victory_cnt = [0] * N 

for i in range(Q):
    victory_cnt[A[i]-1] += 1

for v in victory_cnt:
    if (Q-v) >= K:
        print('No')
    else:
        print('Yes')

D: Powerful Discount Tickets

コンテスト中に方針を立てることはできたが、TLEを解消できなかった。 コンテスト終了後、プライオリティキューを用いてsubmitすることでTLEを出さずにACできた。 方針としては、最大値に対して割引の回数だけ割引し続けるという方針でいくとうまくいく。 このとき、割引前の最大値と、その最大値に対して割引を適用したあとでは最大値が入れ替わる可能性があることが今回のポイントとなる。 それを踏まえて、プライオリティキューで最大値を取り出して、(最大値//2)をプライオリティキューに加えて、それに対してまた最大値を取り出すという処理を繰り返すことで対処する。

import heapq


N, M = map(int, input().split())
A = list(map(int, input().split()))
A_inv = [-a for a in A]
heapq.heapify(A_inv)
for _ in range(M):
    max_inv = heapq.heappop(A_inv)
    heapq.heappush(A_inv, -(-max_inv//2))

print(sum([-a for a in A_inv]))

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?