AtCoderProblemsのTrainingをPython3でやる Easy編
↑これの21-30のやつです。
21.ABC149-C Next Prime
全てのi(2<=i<=$\sqrt{x}$)に対してx%iが0になったらx=x+1して、ならなかったらwhileループから抜けてxを出せば良いですね。
x=int(input())
while True:
for i in range(2,int(x**0.5)+1):
if x%i==0:
break
else:
break
x+=1
print(x)
22.AGC027-A Candy Distribution Again
sum(a)==xのときはnが答えなのは自明です。
それ以外のときはaをソートして$\sum_{i=1}^ka_i≦x$を満たすkの最大値が答えです。
n,x=map(int,input().split())
a=sorted([int(i)for i in input().split()])
res=0
if sum(a)==x:
res=n
else:
for i in range(n):
if sum(a[:i])<=x:res=i
print(res)
23.ABC092-B Chocolate
1<=j<=D+1の範囲で$(j-1)\%A_i=0$となるjがいくつあるかを各iに対して探せば良いです。
$(i,j)$はせいぜい$(100,100)$にしかならないので二重ループでいけますね。
n=int(input())
d,x=map(int,input().split())
a=[int(input())for i in range(n)]
res=x
for i in range(n):
for j in range(d):
if j%a[i]==0:
res+=1
print(res)
と、ここまで書いてて気づいたのですが1、各iに対するjの個数って(d-1)/a[i]+1じゃないですかーやだー。
解説もこっちしか書いてませんね。全探索とは……宇宙とは……。
n=int(input())
d,x=map(int,input().split())
a=[int(input())for i in range(n)]
res=x+n
for i in range(n):
res+=(d-1)//a[i]
print(res)
24.日立製作所 社会システム事業部 プログラミングコンテスト2020-B Nice Shopping
入力例3を見るまで割引券を使わないパターンを考えてなかったので優しいなあと思いました。
答えの初期値をmin(a)+min(b)でやった後、$a_{x_i}+b_{y_i}-C_i$と現在保持している答えを比べて、小さいほうを答えに代入していけばよいですね。
A,B,M=map(int,input().split())
a=[int(i)for i in input().split()]
b=[int(i)for i in input().split()]
xyc=[[int(i)for i in input().split()]for j in range(M)]
res=min(a)+min(b)
for x,y,c in xyc:
tmp=a[x-1]+b[y-1]-c
res=min(res,tmp)
print(res)
25.ABC150-C Count Order
Pより小さい順列の個数を$a$、Qより小さい順列の個数を$b$としても$|a-b|$
は変わらないことに気づければ、あとは順列を生成するだけです。
from itertools import permutations
n=int(input())
p=tuple(int(i)for i in input().split())
q=tuple(int(i)for i in input().split())
permutation_n=list(permutations(range(1,n+1)))
a=b=0
for i in permutation_n:
if i<p:a+=1
if i<q:b+=1
print(abs(a-b))
26.ABC153-D Caracal vs Monster
雑に再帰したら例3が再帰深すぎてエラーを吐いた。それはそう。
def attack():
global res
if h[0]!=1:
tmp=h.pop(0)
h.append(tmp//2)
h.append(tmp//2)
res+=1
return attack()
else:
return None
h=[int(input())]
res=0
attack()
res+=len(h)
print(res)
ところで、体力H(H>1)のモンスターを倒すのに必要な攻撃回数は2*(H/2のモンスターを倒すのに必要な攻撃回数)+1回です。
こっちで再帰したらいけました。
def attack(x):
if x==1:
return 1
else:
return 2*attack(x//2)+1
h=int(input())
res=attack(h)
print(res)
27.ABC158-B Count Balls
「どう見ても合ってるなのになんで通らないんだ？？？？？」と思ったら掛け算の順番の問題でした。
res=a*n//(a+b)だとダメなんですね。言われてみればその通り。
n,a,b=map(int,input().split())
res=n//(a+b)*a
if n%(a+b)>=a:
res+=a
else:
res+=n%(a+b)
print(res)
28.ABC081-B Shift only
リスト内に奇数が出るまで要素を割り続けるゲームですな。
def notExistOdd(lst):
for i in lst:
if i%2==1:
return False
return True
n=int(input())
a=[int(i)for i in input().split()]
res=0
div=lambda x:x/2
while notExistOdd(a):
res+=1
a=list(map(div,a))
print(res)
29.ABC114-B 754
スライスを使うと連続部分を切り出しやすいのでオススメです。
s=input()
res=[]
for i in range(len(s)-2):
tmp=s[i:i+3]
if len(tmp)<3:
continue
res.append(abs(753-int(tmp)))
print(min(res))
30.ABC108-B Ruined Square
平面図形はゲロを吐くほど苦手なので例を使ってガチャガチャやったり画面とにらめっこしてたら$x_2-x_1$と$y_2-y_1$っぽい数字が出てきたのでなんとかなった。
やめろ、数学の問題を出すんじゃない！
x1,y1,x2,y2=map(int,input().split())
a=x2-x1
b=y2-y1
print(x2-b,y2+a,x1-b,y1+a)
おわりに
数学の問題が出てくるとオアアーッアーッてなるのでやめて欲しいのですが、プログラミングが計算機科学である以上は無理ですね。
-
実は1問ずつ解いた直後に書いてます。 ↩