AtCoder Beginner Contest 193 A〜C問題
前書き
AtCoder Beginner Contest 193 A〜C問題を解きました。
B問題
難易度:灰
時間:10分
1≤N≤10**5なので一重ループである可能性が高いです。
在庫 - 所要時間による減少量 > 0となる店舗から値段が最小となる価格を調べれば良いです。
N = int(input()) APX = [list(map(int, input().split())) for n in range(N)] _min,clear = 1000000000,0 for apx in APX: A,P,X = apx[0],apx[1],apx[2] if X-A>0: clear += 1 _min = min(P, _min) if clear==0: print(-1) else: print(_min)
C問題
難易度:灰〜茶
時間:50分
正直苦戦しました。
1以上N以下の値で、a ** b(2以上N以下のab)で再現できない個数を調べる問題です。
1≤N≤10**10なので1つずつ調査できないです。
数学的な問題かと思いきや、泥臭く調べていく手法でAC。
ただその過程で工夫をしなければいけません。
ただa、bは2以上だと明言されているので、
b = 2だとしたらaは最大でも2**5の値になります。
すると2≤a≤10**5を調べるのは一重ループで可能です。
a**b≤nとなるまでaとbの組み合わせを調べ続けます。
n=10**10としても、b=log(2)10**10になりますので、bはそこまで大きくならず、計算できそうです。
以下のコードでACです。
import math n = int(input()) c = math.ceil(math.sqrt(n)) i,count = 2,[] while i<=c: j = 2 while i**j<=n: count.append(i**j) j+=1 i += 1 print(n-len(set(count)))