AtCoder Beginner Contest 181 (A,B,C,D,E) 感想

ABC181の感想です。先に解きたい人は解いてから見てねー。（定型文）

atcoder.jp

A問題(Heavy Rotation)

Nが偶数なら白、奇数なら黒ですね。

N = int(input())
if N%2 == 0 :print("White")
else: print("Black")

B問題(Trapezoid Sum)

からまでの個の数字を足していけばいいですね。平均とって個数をかければいいです。（2で割るのを最後にしないと、が奇数の時に困っちゃいますね。）

N = int(input())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

ans = 0
for i in range(N):
    ans += (B[i] + A[i])*(B[i]-A[i]+1)//2

print(ans)

C問題(Collinearity)

全探索します。三つ点を選んできて、それらの点の傾きが同じだったらいいですね。ただ、割り算を計算機上で実行するときはゼロ除算などあって嫌な気持ちになるので、掛け算でできるように式変形しておきます。（ここに書くのは面倒なのでコード見てください。）

import sys
N = int(input())
x = [0]*N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if (x[k]-x[i])*(y[j]-y[i]) == (x[j]-x[i])*(y[k]-y[i]):
                print("Yes")
                sys.exit()

print("No")

D問題(Hachi)

これ皆さんWA出してて、気をつけなければいけない問題ですね。8の倍数の判定はネットで調べたりすると「下3桁が8の倍数ならば、その整数は8の倍数」というのが出てきます。あとは並び替えですが、普通にやると長さ10^5の文字列から3つとってくるので10^15通りくらいあります。なので工夫します。少し考えると、同じ数字が三つ以上あった場合、今回はその中から高々三つしか選ばないので四つ目以降は無視していいです。したがって、文字の長さは長くても9×3=27くらいです。これくらいなら並び替えても10^5くらいの計算量なので並び替えましょう。

また、文字列の長さが1と2の時はそもそも下3桁という概念がないので、素直に並び替えましょう。

from collections import Counter
from itertools import permutations
import sys
S = input()
C = Counter(S)
N = len(S)

if S == "8":
    print("Yes")
    sys.exit()
elif len(S) == 1:
    print("No")
    sys.exit()

    

s = set()
for i in range(N):
    s.add(S[i])
s = list(s)

for i in range(len(s)):
    if C[s[i]]>2:
        s.append(s[i])
        s.append(s[i])
    elif C[s[i]] == 2:
        s.append(s[i])

n = len(s)



if len(s)<=3:
    for i in permutations(s,min(len(S),3)):
        ans = "".join(i)
        ans = int(ans)
        #print(ans)
        if ans % 8 == 0:
            print("Yes")
            sys.exit()
#print(s)
for i in permutations(s,3):
    ans = "".join(i)
    ans = int(ans)
    #print(ans)
    if ans % 8 == 0:
        print("Yes")
        sys.exit()

print("No")

E問題(Transformable Teacher)

これは本番ではできませんでした。まず少し考えると、差を取るペアというのは、Hをソートした後の隣り合った人たちをペアにした方がいいということはすぐにわかります。なのでHをソートした後の差を持っておいて、あとは変形後の先生の身長Wで全探索して一番いい答えを探します。先生が誰とペアになるかを考えるときに二分探索をするのが肝です。先生と組む人以外は変わらないので、差の前からの累積和と後ろからの累積和をあらかじめ持っておくと制限時間に間に合います。(ソートでNlogN、先生の身長の全探索でM、二分探索でlogNでくらいの計算量ですかね？回答では先生の身長もソートしてるのでが入ってるんですが、別にしなくても間に合います。したほうが二分探索の範囲を狭めていけるので速いと思いますが。）先生が入る位置が奇数だとペアになる生徒の番号がずれてしまうので調整しています。(入力例を手で追うと分かります。)

from bisect import bisect_left
N, M = map(int, input().split())
H = list(map(int,input().split()))
W = list(map(int, input().split()))


W.sort()
H.sort()
ans = 10**9


H1 = [H[i+1]-H[i] for i in range(N-1)]
H2 = H1[1::2] + [0]
H1 = [0] + H1[::2]
#print(H1)
#print(H2)
for j in range(len(H1)-1):
    H1[j+1] += H1[j]
for j in range(len(H2)-1,0,-1):
    H2[j-1] += H2[j]
#print(H1)
#print(H2)
ans = 10**9

tmp = 0
for i in range(M):
    x = bisect_left(H,W[i])
    #print(x)
    tmp = x
    if x %2:
        x-=1
    res = H1[x//2] + H2[x//2] + abs(H[x]-W[i])
    
    ans = min(ans,res)

print(ans)

感想

4完(パフォーマンス923)でレートも52あがりました！うれぴよ。Eは後ろからの累積和っていうのがやったことなくて思いつきませんでした。ここからにぶたんっ！（二分探索）も練習したので、本番に活かせるように頑張ります。
ARCもB問題もう少し、ABCもE問題もう少しな気がしますが、あまり期待しすぎるとD解けない時に悲しいですね。
今週も来週もABCが生えているので、修行を続けます！（ベルマン・フォードの負の閉路の検出、分からん。というか負の閉路がなければN-1回でコストが収束するのがなぜなのか分かってない。ダイクストラ法みたいに順次決まっていくわけじゃないし。決まっていくのか？わけわかめ。）

Reference

AtCoder