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版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る