Atcoder ABC239,240 振り返り

　土日連続でABCが開催された19，20日．あいにくこの二日間ちょうどインターンと重なってしまったのでRated参加できずバーチャルで参加しました．(239:87位, 240:82位)

A - Horizon【AC】

　そのまま実装します．

x = int(input())
print((x*(12800000+x))**(0.5))

B - Integer Division【AC】

　pythonはたったこの量書くだけでで切り捨ての計算が出来るので助かります．

x = int(input())
print(x//10)

C - Knight Fork【AC】

　距離がルート5であるものを見つければ良いですが，x, y軸からみて，点から3以上離れていたらその時点で距離がルート5を超えてしまうので探索範囲は少しで良いと分かります．

x1, y1, x2, y2 = map(int, input().split())
ok = False

for x in range(x1-2, x1+3):
    for y in range(y1-2, y1+3):
        if (x1-x)**2 + (y1-y)**2 == (x2-x)**2 + (y2-y)**2 == 5:
            ok = True

if ok:
    print("Yes")
else:
    print("No")

D - Prime Sum Game【AC】

　B<=100, D<=100なので整数の和の最大値は200である事が分かります．200までの素数をエラトネスのふるいを使って列挙します．高橋くんが上げる数字に対して，青木くんが出せる数字を出して，和が素数で無かったら，その数字を高橋くんが上げれば，青木くんは何を出しても素数を作れないので高橋くんの勝ちと言うことが分かります．

A, B, C, D = map(int, input().split())

def prime_namber_detail(n):
    prime = [True for i in range(n+1)]
    prime[0] = False
    prime[1] = False

    for i in range(2, int((n)**(0.5))+1):
        if prime[i]:
            for j in range(2*i, n+1, i):
                prime[j] = False

    return prime

prime = prime_namber_detail(200)
for t_number in range(A, B+1):
    if not True in prime[t_number+C:t_number+D+1]:
        print("Takahashi")
        break
else:
    print("Aoki")

A - Edge Checker【AC】

　数字が連続する時，線が繋がっていると図から分かります．例外として1と10が繋がっていることに気をつければ解けます．

a,b = map(int, input().split())
if abs(a-b) == 1 or (a==1 and b==10):
    print("Yes")
else:
    print("No")

B - Count Distinct Integers【AC】

　set型は値が重複しないようなデータ型です．種類の数を数えるときによく使います．

N = input()
print(len(set([i for i in input().split()])))

C - Jumping Takahashi【AC】

　ジャンプしてXを超えてしまったら，Xに止まることはありえないのでその時点で探索を止めます．それ以外は全探索すれば求まります．locationはset型にすることで同じ点からの探索を繰り返す事が無くなり時間が縮まります．ここをlistにして同じ点からの探索を繰り返しやるとTLEになります．

N, X = map(int, input().split())
locations = {0}

for _ in range(N):
    new_locations = []
    a, b = map(int, input().split())
    for loca in locations:
        if loca + a <= X:
            new_locations.append(loca+a)
        if loca + b <= X:
            new_locations.append(loca+b)
    locations = set(new_locations)

if X in locations:
    print("Yes")
else:
    print("No")

D - Strange Balls【AC】

　筒の一番上の値や同じ数が連続する個数などを適切に管理すれば解けます．
このプログラムに書いてある処理はそれぞれ計算量はO(1)のはずなので間に合います．実際に筒の様子を表したtubeというリストを作って解いたら，どうやらボールを消すtube=tube[:-count]という処理がボトルネックとなりTLEを連発してしまいました．スライスの取得はO(k)です．スライスがボトルネックとなりTLEとなるのは初めての経験でした．

N = int(input())
A = [int(i) for i in input().split()]
tube = []
last_tube = 0
counts = []
count = 0
len_tube = 0

for a in A:
    if last_tube != a:
        counts.append(count)
        count = 1
        last_tube = a
        len_tube += 1
        tube.append(a)
    elif count + 1 == a:
        len_tube -= a-1
        if len_tube == 0:
            last_tube = 0
        else:
            tube.pop()
            last_tube = tube[-1]
            count = counts.pop()
    else:
        count += 1
        len_tube += 1
    print(len_tube)
    # print(counts, count)