Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@K_SIO

AtCoder ABC 174 Python (A~E)

総括

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

問題

A. Air Conditioner

image.png

回答

X = int(input())

if X >= 30:
    print('Yes')
else:
    print('No')

これは書くだけ。

B. Distance

image.png

回答
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

image.png

回答(コンテスト時)

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

image.png

回答(コンテスト時)
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

image.png

回答(コンテスト時)
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

0
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
0
Help us understand the problem. What is going on with this article?