総括
A,BのみACでした。
もう少しでC,Dも解けそうなきがするものの、なかなか解けない・・・。
#問題
https://atcoder.jp/contests/abc174/tasks
A. Air Conditioner
回答
X = int(input())
if X >= 30:
print('Yes')
else:
print('No')
これは書くだけ。
B. Distance
回答
N, D = map(int, input().split())
count = 0
for _ in range(N):
x, y = map(int, input().split())
distance = (x ** 2 + y ** 2)**0.5
if distance <= D:
count += 1
print(count)
これも問題文通り書くだけですが、ルートで距離をだして判定するよりも、距離の2乗どうしを比較したほうがよさそうです。
C. Repsept
回答(コンテスト時)
K = int(input())
answer = -1
target = 0
for i in range(K):
target += 7 * 10**i
if target % K == 0:
answer = i + 1
print(answer)
break
print(answer)
問題文通り実装すると当然通りません。
入力例3の999983が問題の最大値となりますが、これを解こうとすると10の999983乗を計算しなければならず明らかに無理です。
回答(後日)
K = int(input())
count = 1
mod = 7
answer = -1
for _ in range(K):
if mod % K == 0:
answer = count
break
count += 1
mod = (mod * 10 + 7) % K
print(answer)
10の累乗を減らすことを考えます。
問題は7,777,777....の数字を割り切れる最初の数がわかればよいので7,777,777....を保持しておく必要はなく、あまり(mod)を保持しておけば解けそうです。
言い換えると、target += 7 * 10**iではなくmod = (mod * 10 + 7) % KをK回繰り返せばよさそうなことがわかります。
ここまでくれば後は書くだけです。
D. Alter Altar
回答（コンテスト時）
N = int(input())
stones = input()
count_R = stones.count('R')
if N == count_R:
answer = 0
elif N - count_R > count_R:
answer = count_R
else:
if 'R' in list(stones)[:N//2]:
answer = count_R - 1
else:
answer = count_R
print(answer)
これでは解けません。
難しく考えすぎ、条件分岐がぐちゃぐちゃになってしまいました。
この方針でいくと、条件分岐が足りていないです。
回答（後日）
N = int(input())
stones = input()
total_count_R = stones.count('R')
left_count_R = stones[:total_count_R].count('R')
answer = total_count_R - left_count_R
print(answer)
後日、すっきりした頭で考えるとシンプルにとけることがわかりました。
WR という並びがなくなるように操作を行えばよいので、結局、すべてのRが左側に集まるように操作を行えばよいことがわかります。
すべてのRが左側に集まるような操作の回数は、何通りか実験してみると下記であることがわかります。
- すべての
Rの個数であるtotal_count_Rから - 左から
total_count_Rまでに含まれているRの個数であるleft_count_Rを引く
ここまでわかれば、コードはかなりシンプルに書くことができます。
E. Logs
回答(コンテスト時)
import heapq
N, K = map(int, input().split())
K_copy = K
A = list(map(int, input().split()))
A = list(map(lambda x: x*-1, A))
heapq.heapify(A)
while K:
max1 = heapq.heappop(A)
max2 = heapq.heappop(A)
for i in range(2, K_copy+1):
temp = max1 / i
if temp > max2:
heapq.heappush(A, temp)
heapq.heappush(A, max2)
K -= 1
break
print(A)
これでは通りません。
「一番長い丸太を半分に切り続ける」という方針ですが、これだと、例えば同じ丸太を2回切ることとなった場合に、本来であれば3等分に切るべきところ、中途半端な切り方になってしまいます。
また、少し改良して、「一番長い丸太を見つけて、最適な切り方で切りなおす」という方法も考えられますが、これは実装が難しそうですし、たぶんTLEになるだろうということで断念しました。
回答(後日)
N, K = map(int, input().split())
A = list(map(int, input().split()))
def check(l):
count = 0
for L in A:
count += L // l
if L % l != 0:
count += 1
count -= 1
return count <= K
bottom, top = 0, max(A)
while top - bottom > 1:
mid = (top + bottom) // 2
if check(mid):
top = mid
else:
bottom = mid
print(top)
「丸太をK回切って最小にする」を逆から考えます。
「丸太を特定の長さ（最小）にするためにK回以内で行えるか？」です。
2分探索で「丸太の長さを最小にするちょうどよい場所」を探しにいき、
その際の「K回以内で行えるか」の判定をdef check()でを行っていきます。
E問題については、かつっぱさんのYouTubeを参考にさせていただきました。
https://youtu.be/0jwtdtinPiE