ABC141にチャレンジ

AtCoder初参加。結果はA, B, Cは解けて、Dはアルゴリズムは良かったけれど実行速度が基準を満たせず、残念な結果に。個人的には、ようやく時間前に椅子に座ることができたのが、良かった。

A

Sunny, Cloudy, Rainyという単語に対して、適切な単語を答えるもの。連想配列そのものだったので、そのまんま実装してみました。

heather.py

S = input()

dict = {"Sunny": "Cloudy", "Cloudy": "Rainy", "Rainy": "Sunny"}
print(dict[S])

B

文字列の偶数インデックスと奇数インデックスのそれぞれに、使ってはいけない文字のルールが定義されている。愚直にループで回しても良かったけれど、偶数インデックスだけからなる文字列と奇数インデックスだけからなる文字列を、Pythonのスライス機能を作って実装してみました。

tap.py

S = input()

S_odd = S[::2]
S_even = S[1::2]
if 'L' in S_odd or 'R' in S_even:
  print("No")
else:
  print("Yes")

C

多人数で行うクイズ。成果した人以外の点数が１点ずつ減っていき、最後に残った人を抽出する問題。「正当者以外の点数が1点引かれる」とあるが排他的論理和を取って「正当者の点数が1点上がる」という風に考えてみた。最後の点数を確認するロジックを少しだけ考えました。

attack.py

N, K, Q = list(map(int,input().split()))
A = [int(input()) for i in range(Q)]
score = [0] * N
for i in range(Q):
  score[A[i] - 1] += 1
for i in range(N):
  result = K - Q + score[i]
  if result > 0:
    print("Yes")
  else:
    print("No")

D

「一番高い商品に割引券（半額券）を適用する」という作業を商品券の枚数分繰り返せばいい。ただAtCoderでは「繰り返すだけ」が時間切れの要因になるので、それを解決するのが大変。初めは愚直にソートして会えなく時間切れ、次に、一回の操作で値が変わる要素はたかだか１個であることに気づき、最後の値が小さくなったらbisectを使って再挿入する実装を思いついた。しかし改善はしたけど、まだだめ。今日はここで時間切れでした。
ちなみに解説見たら、優先度付きキューを使うと良いと書いてあったので、そうしてみたら制限時間内に終わるようになった。

powerful.py

import math
import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda a: -int(a), input().split()))
A.sort()
heapq.heapify(A)

for i in range(M):
  a = heapq.heappop(A)
  a /= 2.0
  heapq.heappush(A, a)

amount = 0
for a in A:
  amount += math.floor(-a)
print(amount)