AtCoder Beginner Contest 144
はい。
https://atcoder.jp/contests/abc144
ooox-- 878(-38)でした。ダメです。
A - 9x9
PyPy3
a,b=map(int,input().split()) print([a*b,-1][a>9 or b>9])
A,Bどちらかが9より大きければ-1、そうでなければ計算結果を。
B - 81
PyPy3
n=int(input()) for i in range(1,10): for j in range(1,10): if n==i*j: print("Yes") exit() print("No")
全部調べます。コンテスト中は適当に2重ループ書いたのですが、内側は for j in range(1,i+1):
でも良さそうな気がします。計算量減らす必要のある場面でもないので適当にしましたけど。
C - Walk on Multiplication Table
PyPy3
n=int(input()) x=int(n**0.5)+1 for i in range(x,0,-1): if n%i==0: print(-2+i+(n//i)) exit()
コンテスト中にじっくり時間かけて提出。なぜ時間をかけてしまったのだろうか。 N = i × jのマスに移動回数を少なくするなら、iとjがNの平方根に近い数の時の方が少なくなります。
例えばN=20のとき1 × 20で移動よりは、4 × 5の方が移動が少ないです。例は出せますが証明はありません。
なので平方根に近い数から1に向かってforループで割り切れる数を探します。上記では x=int(n**0.5)+1
で+1していますが、多分+1する必要はないです。 N=20の時に5から探し始めると20は5で割りきれて4が商として見つけることが出来て、4から探し始めても5が商として同じ移動回数の組合せが見つけられるはずです。証明はないです。
D - Water Bottle
PyPy3
import math pi=3.1415926535897932 chk=0.0000001 a,b,x=map(int,input().split()) t=a*b/2 s=x/a if t>s: h=[0,a] while 1: hs=(h[0]+h[1])/2 w=b*hs/2 if abs(w-s)<chk: break elif w>s: h[1]=hs elif w<s: h[0]=hs print(90-math.atan(hs/b)*180/pi) else: h=[0,b] while 1: hs=(h[0]+h[1])/2 w=(hs+b)*a/2 if abs(w-s)<chk: break elif w>s: h[1]=hs elif w<s: h[0]=hs print(90-math.atan(a/(b-hs))*180/pi)
コンテスト中はAC出来ませんでした。無駄な部分があるので書き直しをいつか。
水を溢れさせずに最大の角度を傾けた時に水の姿?は台形か三角形の2種類になります。
水筒の中の水の体積xをaで割り、面積で考えることにします。
ソレがa×b/2より大きければ台形、そうでなければ三角形にまでの傾きになります。
台形ならば水筒の高さbの中に同じ面積になる点を探します、三角形なら底aの中に点を探します。
同じ面積になる点を見つけられたら三角関数でえいやっとします。
E - Gluttony
PyPy3
n,k=map(int,input().split()) a=[int(i) for i in input().split()] f=[int(i) for i in input().split()] a.sort() f.sort(reverse=True) w=[0,0] for i in range(n): w[1]=max(w[1],a[i]*f[i]) x=50 while x>0: x-=1 ws=(w[0]+w[1])//2 p=k for i in range(n): if a[i]*f[i]>ws and p<a[i]-ws//f[i]: p=-1 break elif a[i]*f[i]>ws: p-=a[i]-ws//f[i] if p>=0: w[1]=ws else: w[0]=ws print(w[1])
コンテスト中には出来ませんでした。
Aは昇順、Fは降順でソートしています。なぜそうするかの証明は公式解説にあります。
チーム全体の成績の最小は0、最大は上記の昇順降順でソートしてi番目同士の積で最大のものになります。
最小と最大で二分探索します。
(最小+最大)/2を仮の解としてi番目同士の積をソレ以下に出来るかを調べます。
修行K回が足りなくなったなら最小を更新、余ったなら最大を更新します。等しかった場合(がおそらく解だと思うのですが)は上記では最大を更新にしています。
十分であろう回数を探索して最大の方の値を出力するようにしてACしました。なぜこれでACかの証明はありません。