しいだよー

久々にABCに参加したのでそのまとめ結果はABCD(3)E5完で水色パフォの1338 レート上がると嬉しい

A - Heavy Rotation

偶奇判別

n = int(input())
if (n%2==0):
    print('White')
else:
    print('Black')

B - Trapezoid Sum

等差数列の和の公式をループ回す最初書いた数字の個数と読み間違えたけど。。

    n = int(input())
    ans = 0
    for i in range(n):
        a,b= map(int,input().split())
        ans += (b-a+1)*(a+b)//2
    print(ans)

等差数列は最近やったから覚えてたけど数列の公式系をまとめて確認できるようにしといたほうがいいかも

C - Collinearity

３つの点が数直線状にある場合を判断する問題。制約が N<＝１００で三重ループしても間に合うものだったので全探査。差分をとって傾きが一致するかで判断した。

傾きでやったためゼロの場合を分ける必要があったが、外積だったらその必要がなかったなと今になって思うかも。慣れていきたいね

＜変更前（傾きで確認）＞

    n = int(input())
    l = []
    for i in range(n):
        x,y = map(int,input().split())
        l.append([x,y])
    f = 0
    for e,i in enumerate(l):
        for E,j in enumerate(l[e+1:]):
            e2 = E+e+1
            # print(e,E,e2,i,j)
            for T in l[e+E+1+1:]:
                a = T[0] - i[0]
                b = T[0] - j[0]
                c = T[1] - i[1]
                d = T[1] - j[1]
                if a==0 and b==0:
                    f=1
                    break
                elif a==0 or b==0:
                    break
                if  c/a == d/b:
                    f = 1
    if f:
        print('Yes')
    else:
        print('No')

＜変更後（外積で確認）＞

    n = int(input())
    l = []
    for i in range(n):
        x,y = map(int,input().split())
        l.append([x,y])
    f = 0
    for e,i in enumerate(l):
        for E,j in enumerate(l[e+1:]):
            e2 = E+e+1
            # print(e,E,e2,i,j)
            for T in l[e+E+1+1:]:
                a = T[0] - i[0]
                b = T[0] - j[0]
                c = T[1] - i[1]
                d = T[1] - j[1]
                if  c*b==a*d:
                    f = 1
    if f:
        print('Yes')
    else:
        print('No')

D - Hachi

https://atcoder.jp/contests/abc181/tasks/abc181_d

与えられた１−９で成り立つ文字列が並び替えて８の倍数になるかという問題。 ８の倍数になるためには下三桁が８の倍数であればいいので三桁以下の８の倍数をすべて確かめてやればいい。とおもって愚直にすると一つのケースのみWA。コーナーかなと思いつつも０の場合はないため範囲を変えて提出し直すとどうやら桁数が２のときに挙動がおかしいことがわかる。82といった場合に反応していたため1桁、２桁、３桁以上の三通りで場合分けを行ってAC。

各８の倍数で文字数をカウントとして考えたがあんまりしっくりこないので改善の余地あり。解説見たらCounterから引いてて何これ！？！？

    for i in range(112, 1000, 8):
      if not Counter(str(i)) - cnt:
        print("Yes")
        exit()

<十分後>

なるほど、辞書型が帰ってくるからその差分をとって何も残ってなかったら８の倍数が作れるってことか、かしこいな。。allで回答してる型もあったからそっちもまとめとこう。

<私の回答（変更前）> Counterを使わず配列で各文字数を確認し、実装した。８の倍数であるかの識別もrangeを８飛ばしで取るようにしたほうがきれいだね。調整しないと

    ans = 0
    S = input()
    dp = [0]*10
    for i in S:
        dp[int(i)]+=1
    if len(S)>=3:
        for i in range(100,1000):
            tdp = [0]*10
            if i%8==0 :　#ここが少し余分
                s = str(i)
                for i in s:
                    tdp[int(i)]+=1
                f = 1
                for i in s:
                    if dp[int(i)] < tdp[int(i)]:f=0
                if f:
                    ans = 1
    else:
        if int(S)%8==0:
            ans = 1
        for i in range(10,100):
            tdp = [0]*10
            if i%8==0 :
                s = str(i)
                for i in s:
                    tdp[int(i)]+=1
                f = 1
                for i in s:
                    if dp[int(i)] < tdp[int(i)]:f=0
                if f:
                    ans = 1
    if S == '8':
        ans =1
    if ans:
        print('Yes')
    else:
        print('No')

<変更後（辞書型）>

    from collections import Counter
    ans = 0
    S = input()
    cnt = Counter(S)
    if len(S)>=3:
        for i in range(112,1000,8):
            c = Counter(str(i))
            if not c - cnt:ans = 1
    else:
        if int(S)%8==0:
            ans = 1
        for i in range(16,100,8):
            c = Counter(str(i))
            if not c - cnt:ans = 1
    if S == '8':
        ans =1
        
    if ans:
        print('Yes')
    else:
        print('No')

E - Transformable Teacher

https://atcoder.jp/contests/abc181/tasks/abc181_e

問題文概要：N人の児童がおり、それぞれにHiの身長が割り当てられる。あなたは先生で体の大きさをWiのどれかにすることができます。二人一組のペアを作ったときの距離の差の総和を最小化したときの値。

身長順にソートしたら番号順にペアを作るのが最適であることも未証明で実装したがあっていたみたい。絶対値を分解したらわかったことだが、足す側と引く側に分けて先生の挿入位置で場合分けした。添字バグが怖すぎてめっちゃ時間かかったけど最終的に一発ACできたのでヨシ！

    from bisect import bisect_left
    n,m = map(int,input().split())
    h = list(map(int,input().split()))
    w = list(map(int,input().split()))
    h.sort()
    ho = [0]
    he = [0]
    w.sort()
    for e,i in enumerate(h):
        if e%2==0:ho.append(ho[-1]+i)
        else:he.append(he[-1]+i)
    inf = float('INF')
    ans = inf
    for i in w:
        t = bisect_left(h,i)
        # print(t,i)
        EO = (t%2==0)
        if not EO:
            tho = (t+1)//2
            the = tho-1
            tmp1 = abs(he[the]-ho[tho-1])
            tmp2 = abs(i-h[t-1])
            tmp3 = abs(he[-1]-he[the])
            tmp4 = abs(ho[-1]- ho[tho])
            tmp5 = abs(tmp3 - tmp4)
            # print(tmp1,tmp2,tmp3,tmp4,tmp5)
            tmp= tmp1+tmp2+tmp5
        elif EO:
            tho = (t)//2
            the = tho
            tmp1 = abs(he[the]-ho[tho])
            tmp2 = abs(i-h[t])
            tmp3 = abs(he[-1]-he[the])
            tmp4 = abs(ho[-1]- ho[tho+1])
            tmp5 = abs(tmp3 - tmp4)
            # print(tmp1,tmp2,tmp3,tmp4,tmp5)
            tmp= tmp1+tmp2+tmp5
        ans = min(tmp,ans)
    print(ans)

感想

久々にしては頭回ってたし、累積和、二分探索の問題に慣れてきてるんだと思う。今回は問題のあたりが大きかった気もするけど、もう少しコードを最適化できるところあると思うからまたまとめたい。

ここまで読んでいただきありがとうございます

しい

whitesiro1107’s blog

ABC 181　ざくざくまとめ

A - Heavy Rotation

B - Trapezoid Sum

C - Collinearity

D - Hachi

E - Transformable Teacher

感想