AtCoder Beginner Contest 181 参加ログ・感想

久しぶりのABC。最近調子がいいと思うのでいけるかと思ったら。詰めが甘く本番の弱さ際立つ・・・。実装できなかったけど考え方的にCD簡単だったから別記事にしない。

内容
結果
どう考えたか + α
おわりに
参考になる書籍

内容

Python3でやっている。
参加ログ。
所感。
コンテスト中に何を考えたか。
コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
問題の詳細で細かく書こうと思うものは別記事とする。

結果

AB完。5分以内に終わって、Cは $0$ 除算で場合分けしたのが失敗。約分すればよかった。DはCounterは引き算できるっていう知識がなかった。。。

どう考えたか + α

問題

A - Heavy Rotation

問題タイプ：偶数か奇数か

文意から偶数ならWhite。奇数ならBlack

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

B - Trapezoid Sum

問題タイプ：1からnまでの和

クエリの1つずつを、以下のように全部足し続けるとTLE

n = int(input())
cnt = 0
for _ range(n):
    for i range(a, b+1):
        cnt += i

クエリの1つを $\frac{(a+b)(b-a+1)}{2}$ として $O(1)$ として計算。
上記を足し合わせる。

昨日のARCのAでも同じような感じだった blacktanktop.hatenablog.com

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

C - Collinearity

問題タイプ：幾何（3つの点が同一直線上）

3点 $a, b, c$ が同一直線上にあるというのは、 $a, b$ , $b, c$ それぞれの傾きが同じであるということ。
つまり、 $\frac{by-ay}{bx-ax}$ = $\frac{cy-by}{cx-bx}$ ということ。
*ここで、分母が $0$ 割り算の可能性があるので、適当に条件分けしたら、失敗した。 $(bx-ax)(cx-bx)$ を掛けて通分してあげるとよかった。

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(i):
        for k in range(j):
            ax = xy[i][0] - xy[j][0]
            bx = xy[j][0] - xy[k][0]
            ay = xy[i][1] - xy[j][1]
            by = xy[j][1] - xy[k][1]
            # ay/ax = by/bx
            # 0除算を防止するために、ax*bxを両辺にかける
            if ay*bx == by*ax:
                print('Yes')
                exit()
print('No')

D - Hachi

問題タイプ：倍数判定

8の倍数判定。簡単と思って始めたが、実装で？ってなって死んだ。結論的にはCounterで引き算できるのでそれが一番手っ取り早い。

8の倍数なので下3桁が8の倍数ならいい。
先に8の倍数の辞書を保持しようとして失敗した。。。(あとでそこに組み合わせがあるかどうかを探そうとしてしまった。)
今回のポイントは、8の倍数の数字が含まれるかどうかを判定する方法
結論的にCounterを使えばよかった。8の倍数である数字を文字列としてCounterすればとその文字にすべて1が立つ。
クエリで入ってきたものも同様にCounterして、引き算して空っぽになるなら、それはクエリに８の倍数が含まれていたということになる。
まぁ具体例をみた方が早くて

from collections import Counter
a = Counter('568')
# Counter({'5': 1, '6': 1, '8': 1})
b = Counter('54683')
# Counter({'5': 1, '4': 1, '6': 1, '8': 1, '3': 1})
a - b
# Counter() ってなる 
if a - b == {}:
    print('からっぽ')
# からっぽ

3桁の8の倍数全てで試す。
- この時もいちいち0が含まれるものを排除する必要はない。
- 入力に制約があるだけで、調べ上げていく側に含まれていてもTrueにならないので。
2桁以下の場合は別処理。
- そのままで8で割り切れるか、逆順にして8で割り切れるかで判断する。

from collections import Counter
n = input()
if len(n) <= 2:
    if int(n) % 8 == 0 or int(n[::-1]) % 8 == 0:
        print('Yes')
        exit()
    else:
        print('No')
else:
    c = Counter(n)
    # 3桁だけ考えればよくかつ0を含まないものだが、
    # 入力が含まれないものしか来ないので全部辞書化
    for i in range(104, 1000, 8):
        if Counter(str(i)) - c == {}:
            print('Yes')
            exit()
    print('No')

おわりに

今回は、CD共に落ち着いて考えていればできたのに、本番実装できなかったのは悔しい。約分して条件分けを防ぐとか、同じ数文字を持っているかどうかっていうのはCounterで計算するとか、言われれば当たり前みたいな感じで、これは完全に身に染みたので、次回からは多分できる。

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。