AGC023に参加した (412位) - 天色グラフィティ

f:id:ejinote:20180428233923p:plain

アイコンが変わりました。クラウドソーシングサイトでお願いして写真を送ったところ、ものごっつい美化されて返ってきました。かわいいのでありとあらゆるSNSのアイコンを変更して回っています。

さて、AGC023に参加しました。AとBを解いて、Cで撃沈した結果、412位でした。レートは1121→1240になりました。ついに水色に突入！名実ともにABCを卒業ですね。

パフォーマンスは1800（青相当）だったので、ARCにちゃんと毎回出てればここまではあがるぞ、ということでしょうか。

500点〜800点の問題（ARCのD/E、AGCのA/B/Cあたり）を順に埋めていく季節が来たようです。

前回の記事

amalog.hateblo.jp

振り返り

A - Zero Sum Ranges (問題)

$(A, B$ ]の累積和は $[0, B$ ]の累積和から $[0, A$ ]の累積和を引いたものであることを利用。

今回はこれが0になる場合をカウントするので、

全体の累積和を取る
$i$ 番目の要素について、以前にその数字が出てきた回数カウントする
$i$ 番目の要素が0ならもう1回追加でカウントする

をしていけばよい。

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Acum = A.cumsum()
cache = {}
cnt = 0
for i in range(N):
    if Acum[i]==0:
        cnt += 1
    c = cache.get(Acum[i], 0)
    cnt += c
    cache[Acum[i]] = c+1
print(cnt)

B - Find Symmetries (問題)

↓思考回路

与えられた行列を $2\times 2$ 個ならべて考えよう
数字に置換してnumpyで愚直にカウントすれば間に合うんじゃね？→TLE
(A, B)がOKなら(A+1, B+1)もOKじゃん
あーじゃあAは固定でBだけずらして最後にN倍しよ→AC

import numpy as np
N = int(input())
alphabets = list('abcdefghijklmnopqrstuvwxyz')
A = np.zeros((N, N), dtype=int)
for i in range(N):
    for j, c in enumerate(input()):
        A[i,j] = alphabets.index(c)

B = np.concatenate([A, A], axis=0)
cnt = 0
for i in range(N):
    C = B[i:i+N, :]
    if (C==C.T).all():
        cnt += 1
print(cnt*N)