AtCoder ABC141
AtCoderのABCに出てるので、自分が大会中に考えていたことをアウトプットしてみる。
使用言語はPython3系で、今回はA-Cまで3完。D考えていて手も足も出ず降参した。
そのうちC++とかRustとか、速い言語に移行しないといけない日が来そう。
AtCoder ABC141
A. Weather Prediction
いつも通り、入力から分岐させるだけ。
判定に使う文字列、リスト化して要素でぶん回しでもよかったかも
#coding:utf-8 s = input() if s == 'Sunny': print('Cloudy') elif s == 'Cloudy': print('Rainy') else: print('Sunny')
B. Tap Dance
どう考えてもDDRじゃん。
入力を偶数と奇数要素ごとに分けて、その中でNGになっている文字があるか探す。
あったらフラグを変えて、最後に判定する。
ポイント
リストのスライス。list[start:stop:step]を応用する。
#coding:utf-8 s = input() #入力文字列を1文字ごとにリストの要素として格納 tap = list(s) #偶数番目、奇数番目で要素を取り出しておく e_tap = tap[1::2] o_tap = tap[0::2] #print(o_tap, e_tap) #判定フラグ。1度でも動きにくい文字が出たら1にする o = 0 e = 0 #偶数番目 for i in e_tap: if i == 'R': o = 1 break #奇数番目 for i in o_tap: if i == 'L': e = 1 break #結果判定 if o == 0 and e == 0: print('Yes') else: print('No')
C. Attack Survival
入力の範囲で105がいたことに気づかず、最初に愚直に実装したらTLE食らった。
そして意外と標準入力からリストを作る、リストに一括操作する方法忘れてる...
#coding:utf-8 #愚直に実装したらTLE n, k, q = map(int, input().split()) a = [input() for i in range(q)] point = [k] * n #print(point) #点数計算 for i in range(0, q): #全員1問につき1点減点しておく/ここが遅かった point = [j-1 for j in point] #正解者だけ点数を元に戻す point[int(a[i])-1] += 1 #print(point) #結果判定 for i in point: if i <= 0: print('No') else: print('Yes')
ポイント
愚直にやると計算量がO(NQ)になり、双方の最大値が105のため到底時間制限でアウト。
正解数(＝問題数)の分、先に減点しておいた配列を用意し、正解者の分をその後得点加算する
#coding:utf-8 n, k, q = map(int, input().split()) a = [input() for i in range(q)] #問題数分、最初から全員不正解だったとして減点しておく point = [k-q] * n #print(point) #点数計算。正解した人だけ点を元に戻していく for i in range(0, q): point[int(a[i])-1] += 1 #print(point) #結果判定 for i in point: if i <= 0: print('No') else: print('Yes')
1つループが減ってすっきりした。Cからは計算量を問われるので、良い意味で怠ける方法が必要。
D. Powerful Discount Ticket
当時さっぱり検討つかなかったけど、解説聞いて実装してみた。
割引券を1枚ずつ、その時の最高額の商品に使う考え方で最小値が出るとか。
ただ、愚直にやるとTLEになるので、優先度付きキューをおすすめされた。
ひとつ勉強になりました。
ポイント
- その時の最大値や最小値を使って繰り返し処理の際は優先度付きキューを使う
- 「配列の要素が増える」「最小値(最大値)を取り出す」が何度も出たらheapq
- Pythonではheapqライブラリを使う
- そのまま使うと最小値の取り出しになるので、
最大値を扱う時はキューにリストの負の値をとる
- そのまま使うと最小値の取り出しになるので、
heapq.heapify(a) #リストaを優先度付きキューにする heapq.heappop(a) #優先度付きキューaの最小値を取り出して削除 heapq.heappush(a, 1) #優先度付きキューaに1を追加する
#coding:utf-8 import heapq n, m = map(int, input().split()) a = list(map(int, input().split())) #heapqで最大値をとる際は一度マイナスにしてから a = [-1 * i for i in a] #その時買うものリストにある最高額に対して、割引券を1枚ずつ使う #ただし愚直にやるとTLEのため、優先度付きキューを使う #入力リストをheap化する heapq.heapify(a) #割引券の枚数分だけ、最高額を抽出し、割引券を使う for i in range(0, m): #当時の最高額をheappopで取り出して割引後の価格を出す discount = (heapq.heappop(a) * (-1)) // 2 #heappushで割引後の価格をリストに入れる heapq.heappush(a, discount * (-1)) print(-1 * sum(a))
