天色グラフィティ

技術ちっくなことを書きます

AGC023に参加した (412位)

f:id:ejinote:20180428233923p:plain

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

さて、AGC023に参加しました。AとBを解いて、Cで撃沈した結果、412位でした。 レートは11211240になりました。 ついに水色に突入! 名実ともに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になる場合をカウントするので、

  1. 全体の累積和を取る
  2.  i番目の要素について、以前にその数字が出てきた回数カウントする
  3.  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 (問題)

↓思考回路

  1. 与えられた行列を 2\times 2個ならべて考えよう
  2. 数字に置換してnumpyで愚直にカウントすれば間に合うんじゃね?→TLE
  3. (A, B)がOKなら(A+1, B+1)もOKじゃん
  4. あーじゃあ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)

C - Painting Machine (問題)

解けませんでした。

  • N=2からN=5まで手で書き出して規則性を探す
  • 愚直解でいろいろな情報を吐き出すプログラムを書いて眺める

あたりを試して、少なくとも1番目とN-1番目のマシンは動かさなきゃいけない、などの条件を集めましたが、決定的な法則は見つかりませんでした。

解説読んだときの「それはそう」感がすごかったのでたいそう悔しゅうございます。

とはいえ、愚直解でN=11くらいまでは答えを出せるので、それをぱぱっとテストケースに追加できたのは成長だと思います。

おわりに

解き終わったあと、ジュースが飲みたくなって自販機で買ったら当たりが出たので今日は良い日です。

f:id:ejinote:20180429005839j:plain

いじょ。