AtCoder ABC 174 Python (A~E)

総括

A,BのみACでした。
もう少しでC,Dも解けそうなきがするものの、なかなか解けない・・・。

問題

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