Atcoder ABC233 振り返り
最近はデータ分析コンペに注力しててABCはやってなかったけど久しぶりに参加.
diff1000未満の問題コツコツやって緑は行きたい.
A - 10yen Stamp 【AC】
既に一枚貼られてるX円切手がY円を超えていたら一枚もある必要が無い.そうで無かった場合足りないY-X円を10円切手を使う.Y-Xが10で割り切れた場合そのまま(Y-X)//10を出力する.10で割り切れない場合+1枚必要なので(Y-X)//10+1を出力する.
a,b = map(int, input().split()) if a >=b: print(0) elif (b-a) % 10 == 0: print((b-a)//10) else: print((b-a)//10 + 1)
B - A Reverse 【AC】
pythonで文字列の反転はスライスを使う.
a,b = map(int, input().split()) l = input() ll = l[a-1:b] l = l[:a-1] + ll[::-1] + l[b:] print(l)
C - Product【AC】
全探索する.
N, X = map(int, input().split()) L = [] for i in range(N): L.append([int(i) for i in input().split()]) ans = 0 num = L[0][1:] for l in L[1:]: newnum = [] for ll in l[1:]: for n in num: if n*ll<=X: newnum.append(n*ll) num = newnum for i in num: if i == X: ans += 1 print(ans)
D - Count Interval【解説AC】
連続部分列でググって,K=0の場合である過去問Zero sum rangesを見つけたが解くことが出来なかった… S[l−1]=S[r]−Kとなるlを探せば良いと言うことは思い付きset型を使ったりしたが,lの個数をカウントしなければいけないことに気づけなかった.辞書型を使ってS[r]-Kが存在すればその個数+する.S[r]を+1することによってlのカウントを増やす.
import collections N, K = map(int, input().split()) A = [int(i) for i in input().split()] a = [0] for i in A: a.append(a[-1]+i) ans = 0 cc = {} for i in a: cc.setdefault(i - K, 0) cc.setdefault(i, 0) ans += cc[i - K] cc[i] += 1 print(ans)
E - Σ[k=0..10^100]floor(X/10^k)【解説AC】
Dをずっと考えていてEには触れなかった.始め文字列のまま扱っていたがTLEしたためdequeを使った.解説にある筆算の形を思い付くこと,次の桁に移るにはXの桁和からその桁の値を引くことを思い付く事が出来れば解けたかなという感じがする.
from collections import deque X = input() s = 0 for x in X: s += int(x) ans = deque() c = 0 i = 1 while c != 0 or i <= len(X): c += s ans.appendleft(str(c)[-1]) c //= 10 try: s -= int(X[-i]) except: pass i += 1 print("".join(ans))