ABC170 復習

AtCoder ABC

今回もC問題までしか解けませんでした。
いつになったらD問題を安定して解けるようになるのやら・・。

というわけで、復習始めます。

A - Five Variables

リスト中に含まれる0のインデックス値を出力する問題です。
出力の際には1_indexにすることに気をつけます。

a = list(map(int, input().split()))

for i in range(5):
    if a[i] == 0:
        print(i + 1)

B - Crane and Turtle

いわゆる鶴亀算というものですね。
数学的な解法もあるのでしょうが、制約が小さいので、全探索をしてしまえば簡単に解けますね。

x, y = map(int, input().split())

for i in range(x + 1):
    j = x - i
    legs = i * 2 + j * 4
    if legs == y:
        print('Yes')
        break
else:
    print('No')

C - Forbidden List

少してこずりました。
任意のXに最も近い（絶対数が小さい）もので、リストに含まれないものを出力する問題です。
解き方は色々あるのでしょうが、Xを基点としてインクリメントとデクリメントを繰り返す方法を取りました。
もう少しエレガントな解き方は要勉強ですね。

x, n = map(int, input().split())

if x == 0:
    print(x)
    exit()

p = list(map(int, input().split()))
p.sort()

large = 0
for i in range(101):
    if not x + i in p:
        large = x + i
        break

small = 0
for i in range(101):
    if not x - i in p:
        small = x - i
        break

if abs(x - large) == abs(x - small):
    print(small)
elif abs(x - large) < abs(x - small):
    print(large)
else:
    print(small)

D - Not Divisible

解けませんでした。
問題を見た時点で、制約的にループで回そうとするとN2かかるので、TLE案件であることは気付いたのですが、計算量の減らしかたが分からず・・。
以下のコードはTLE発生のものです。愚直に2重ループしたので、当然といえば当然なのですが。

import math
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n):
    no_div = True
    for j in range(n):
        if i == j:
            continue
        if a[i] < a[j]:
            break
        if a[i] % a[j] == 0:
            no_div = False
            break
    if no_div:
        ans += 1

print(ans)

解説を見たところ、エラトステネスの篩（ふるい）と同様のアルゴリズムで解けるようです。
下記にACしたコードを載せます。
書いてみればなんてことはないですね。
なお、エラトステネスの篩と１点異なることとして、リスト中に同じ数が現れることにだけ注意します。
（下記のコードでは、現れた回数を保持しているので、出現回数が1回を超える値は答えに含めていません。）

n = int(input())
a = list(map(int, input().split()))
maxi = max(a)
a.sort()

div = [0] * (maxi + 1)
for n in a:
    div[n] += 1
    if div[n] == 1:
        for j in range(n*2, maxi + 1, n):
            div[j] += 100
print(div.count(1))

今回はここまでです。
無事、レーティングが−6されてしまいました・・。
それでは。