AtCoder ABC 174 Python (A~E)

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


#問題
https://atcoder.jp/contests/abc174/tasks

# A. Air Conditioner
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/356e8e06-11f6-cdd6-6a55-d6b8920e5781.png)
##### 回答

```python

X = int(input())

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

```
これは書くだけ。


# B. Distance
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/bf86d603-1078-1495-584a-69b15db3988e.png)

##### 回答

```python
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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/fd953c5d-c699-eb35-b9c4-87880b91f33a.png)

##### 回答(コンテスト時)
```python

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乗を計算しなければならず明らかに無理です。

##### 回答(後日)
```python
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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/767beaae-e7a7-c4b7-ee13-d01cb9d20987.png)


##### 回答（コンテスト時）
```python
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)
```
これでは解けません。
難しく考えすぎ、条件分岐がぐちゃぐちゃになってしまいました。
この方針でいくと、条件分岐が足りていないです。


##### 回答（後日）
```python
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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/4722899d-aa6f-9278-014b-02730cb4cd04.png)

##### 回答(コンテスト時)

```python
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```になるだろうということで断念しました。


##### 回答(後日)

```python

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