Atcoder ABC221, 220 振り返り
A - Seismic magnitude scales【AC】
そのまま実装します.
a, b = map(int, input().split()) print(32**(a-b))
B - typo【AC】
a, b = b, aと書くことで簡単に値を入れ替えることができます.
S = list(input()) T = list(input()) if S == T: print("Yes") else: for i in range(len(S)-1): TT = T.copy() TT[i], TT[i+1] = TT[i+1], TT[i] if S == TT: print("Yes") break else: print("No")
C - Select Mul【AC】
Nは制約から最大9桁なのでその文字を入れ替えたパターンの数は9!=3.6*10^5個.二つに分ける時取るパターンは9桁の時8個.よって走パターン数は8*3.6*10^5となり全探索しても十分間に合います.先頭が0の時は適切でないことに気をつけます。
import itertools N = list(input()) ans = 0 for i in itertools.permutations(N): for j in range(len(i)-2): a = i[:j+1] b = i[j+1:] if a[0] == "0" or b[0] == "0": continue ans = max(ans, int("".join(a))*int("".join(b))) if len(N) == 2: ans = int(N[0])*int(N[1]) print(ans)
D - Online games【AC】
何人ログインしていたかを知るには,ある人がログインした日とログインしなくなった日を結びつける必要が無いことに気をつけます.よって日にちでソートしても構いません.
ログインし始めた日に+1し,ログインしなくなった日に-1します.1日目から順に値を確認し,累積和のようにログインしている人数を管理することによって解くことが出来ます.
N = int(input()) login = {} for _ in range(N): a, b = map(int, input().split()) login.setdefault(a, 0) login.setdefault(a+b, 0) login[a] += 1 login[a+b] -= 1 login = sorted(list(login.items())) ans = 0 ans_list = [0]*N for i in range(len(login)): if ans != 0: ans_list[ans-1] += login[i][0]-login[i-1][0] ans += login[i][1] print(" ".join(map(str, ans_list)))
A - Find Multiple【AC】
O(1)でも求められますが,簡単に書けるO(N)で書きました.
A, B, C = map(int, input().split()) for i in range(A, B+1): if i % C == 0: print(i) break else: print(-1)
B - Base K【AC】
int("数字", n)とするとn進数としたときの"数字"の値を返してくれます(初めて知りました).この機能を使うと簡単に書けます.
K = int(input()) A, B = input().split() print(int(A, K)*int(B, K))
C - Long Sequence【AC】
順に足していってXを超えたら表示という方式が思い付きますが,A=(1, 1, ...)の時,1ずつしか足されないのでXを超えるまで10^18回計算することになり間に合いません.
数列Bは数列Aが繰り返されることから,数列Bは(sum(A), sum(A), ...)という数列であると言えます.
X = sum(A)*α + βという式が成り立ち,αβはX//sum(A), X%sum(A)とO(1)で求まります.最後に数列Aの和がβを超える最小値点を取れば応えになります.βは余りになるので計算回数は最大でもN-1回になります.
N = int(input()) A = [int(i) for i in input().split()] X = int(input()) B_i = 0 for i in range(N): B_i += A[i] if X < B_i: print(i+1) break else: mod = X % B_i exc = X // B_i B_i *= exc for i in range(N): B_i += A[i] if X< B_i: print(N*exc + i+1) break
D - FG operation【AC】
(解説はDPを使って解いてるけど,自分はDPのつもりで解いてないDPっぽい解法というのが最近多いです.)解説は2次元配列を使っていますが,この解法は一次元配列でループごとに配列を更新して解いています.i-2以前の情報は使わないためこの方法でも解くことが出来ます.
N = int(input()) A = [int(i) for i in input().split()] ans = [0]*10 ans[A[0]] = 1 MOD = 998244353 for i in range(N-1): anss = [0]*10 for j in range(10): if ans[j] != 0: anss[(j + A[i+1])%10] += ans[j] % MOD anss[(j * A[i+1])%10] += ans[j] % MOD ans = anss for i in ans: print(i % MOD)