👨🏭
AtCoder Beginner Contest 223
A - Exact Price
def main():
x = int(input())
print('Yes' if x%100==0 and x!=0 else 'No')
if __name__ == '__main__':
main()
x>0かつ100で割り切れる場合はYes, それ以外はNoです
B - String Shifting
def main():
s = input()
lst = []
for i in range(len(s)):
t = s[i:]+s[:i]
lst.append(t)
lst = sorted(lst)
print(lst[0])
print(lst[-1])
if __name__ == '__main__':
main()
右シフトと左シフトの片方を考えればよいです。
ここでSの長さは高々1000程度なので、生成される文字列を全探索した後に辞書順でソートをしてあげれば答えが求まります。
C - Doukasen
def main():
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
time = [lst[i][0]/lst[i][1] for i in range(n)]
tar = sum(time)/2
ans, t = 0, 0
for i in range(n):
if t+time[i]<tar:
t += time[i]
ans += lst[i][0]
else:
ans += lst[i][1] * (tar - t)
break
print(ans)
if __name__ == '__main__':
main()
答えを一意に求める(条件から方程式を立てて算出する)のは難しそうなので、シミュレーションしましょう。
2つの火がぶつかるタイミングは、導火線を全て燃やすのに要する時間の半分です。
よって一つ一つの導火線を見ていき、その導火線の長さ
D - Restricted Permutation
import sys
import heapq
from collections import defaultdict, deque
inputs = sys.stdin.readline
def TopologicalSort_BFS(n, g):
outs = defaultdict(list)
ins = defaultdict(int)
for a,b in g:
outs[a].append(b)
ins[b] += 1
tank = [v for v in range(1, n+1) if ins[v]==0]
heapq.heapify(tank)
ret = []
while tank:
v = heapq.heappop(tank)
ret.append(v)
for nx in outs[v]:
ins[nx] -= 1
if ins[nx] == 0:
heapq.heappush(tank, nx)
return ret
def main():
n,m = map(int, inputs().split())
g = [list(map(int, inputs().split())) for _ in range(m)]
ret = TopologicalSort_BFS(n, g)
if set(ret)!={i for i in range(1, n+1)}:
print(-1)
else:
print(*ret)
if __name__ == '__main__':
main()
トポロジカルソートを考えますが、辞書順で最小のものを求めることに注意です。
入次数が0になる頂点をQueueに追加していく際に、最小の数字を引き出す必要があるため、これを高速に行うことができるHeapを用いましょう。
Discussion