🐷
AtCoder Beginner Contest 221
A - Seismic magnitude scales
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
a,b = map(int, inputs().split())
print(pow(32, a-b))
if __name__ == '__main__':
main()
#マグニチュードは1増えると32倍なので2増えると当然1024倍!!!!!
B - typo
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
s = input()
t = input()
lst = [s]
for i in range(len(s)-1):
nx = s[:i]+s[i+1]+s[i]+s[i+2:]
lst.append(nx)
print('Yes' if t in lst else 'No')
if __name__ == '__main__':
main()
隣り合う文字を入れ替える全パターンを列挙し、文字列Tが含まれていればokです
C - Select Mul
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
n = list(input())
ans = -inf
for i in range(2**len(n)):
l1,l2 = [], []
for j in range(len(n)):
if (i>>j)&1:
l1.append(n[j])
else:
l2.append(n[j])
l1 = ''.join(sorted(l1, reverse=True))
l2 = ''.join(sorted(l2, reverse=True))
if l1 and l2:
if l1[0]!='0' and l2[0]!='0':
ans = max(ans, int(l1)*int(l2))
print(ans)
if __name__ == '__main__':
main()
Nを文字列としてみると高々10文字程度なので、全探索できそうです。
部分集合を列挙するbit全探索を用いて取得された部分文字列に対して、成立している(数字が含まれる・leading zeroが含まれない)場合にはその積を取ればよいです。
また、積をなるべく大きくするため、部分文字列のうち大きい数字を先頭に置いた方がよいことを考慮しましょう。
D - Online games
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
n = int(input())
dic = defaultdict(int)
for _ in range(n):
a,b = map(int, inputs().split())
dic[a] += 1
dic[a+b] -= 1
dic = sorted(dic.items(), key=lambda x:x[0])
ans = {i:0 for i in range(n+1)}
pre, num = 0,0
for (a,b) in dic:
ans[num] += a - pre
num += b
pre = a
ans = [ans[i] for i in range(1, n+1)]
print(*ans)
if __name__ == '__main__':
main()
人数の変化するタイミングに着目するのが定石です。
変動する人数を記録したあと、「今回人数が変動した日付」と「前回人数が変動した日付」の差分の日数を考えましょう。
Discussion