茶色になった!(ABC141)
ABC141のネタバレあります!
富士通杯(将棋の全国大会)で主将やりながらAtCoderやってた三十三間党です.
問題はこちら→atcoder.jp
A.Weather Prediction
この町では晴れ,曇り,雨と天気が周期的に変化するらしい.雨多くて辛いね.if文使って書いた.3分くらい.
S = input() if S == "Sunny": print("Cloudy") elif S == "Cloudy": print("Rainy") else: print("Sunny")
B.Tap Dance
踊りやすさとは.for文を使って,偶数文字目にR,奇数文字目にLがあれば奇数があればbreakしてNo言ってexit,なかったらYesと言うように書きました.4分くらい.
S = input() for i in range(len(S)): if S[i] == "U" or S[i] == "D": continue if i % 2 == 0: if S[i] != "R": print("No") exit() else: if S[i] != "L": print("No") exit() print("Yes")
C.Attack Survival
一回正解すると他の皆の点が減っていくスタイル.つらいね.allとか使うわけにはいかないので,文面通りには書けないけど,他の人減点って正解者加点と一緒だよね.というわけで最初のKポイントから正解数Qを引いたリストを作ってから,for文で正解者にポイントを与えるように書きました.10分くらい.
N,K,Q = map(int,input().split()) A = [int(input()) for i in range(Q)] Li = [K-Q] * N for i in A: Li[i-1] += 1 for i in range(N): if Li[i] <= 0: print("No") else: print("Yes")
D.Powerful Discount Tickets
重ね掛け出来るタイプの半額券強すぎい.M<=105なので,O(NlogN)まで許されますね.ここで優先度付きキューの取り出しがO(logN)なのを思い出したので,for文の中で優先度付きキュー使えばO(NlogN)で済むなあと思いました.優先度付きキューで最大を取り出すために使ったマイナス×と,切り捨ての相性が悪くて思いついてから書くまで手こずりました.17分くらい.
import heapq,math N,M = map(int,input().split()) A = list(map(int,input().split())) H = [] w = 0 for i in A: heapq.heappush(H,-1*i) for i in range(M): w = (heapq.heappop(H))*-1 w //= 2 heapq.heappush(H,w*-1) print(-1*sum(H))
E.Who Says a Pun?
何も思いつかないので,Nimで愚直解一応書いておいたら意外とギリギリ通らないぐらい.Z-Algorithmというもので解けるらしい.このサイトによると以下のように書ける.
これをN回繰り返してO(N2)で解ける.と思いきや同じ文字を2回使っても良いように書いてるので題意に合わせて書き換えないといけませんでした.
F.Xor Sum 3
Xorわからんごー.階段の電気のスイッチの話聞いて便利だなーと思った.
qiita.com とりあえずこれで勉強してみた.
総評
パフォーマンスは1094でした!自己最高パフォーマンス更新しましたね.あと1問出来れば水色パフォいけそうなので頑張ります.新レートは472で,茶色になりました!初めてレート上昇で色が変わったので嬉しいですね!AtCoder過去問というよりは,蟻本を進めていこうと思います.
Nimメモはここに移動しましたー> qiita.com
Twitterアカウントはこれー> twitter.com