📝

AtCoder Beginner Contest 278 レポート

2022/11/20に公開

AtCoder

Python 3

tech

摘要

ABCDE5完でした．三たび入水です．
C, D問題では詰めの甘さからそれぞれ1TLEを出してしまいましたが，それでもE問題まで43:10 (2TLE)で片付けられたのでよかったです．
とはいえ，E問題は簡単で差がつかないレベルだったこと，F問題についても1時間近く格闘した挙句方針からずれていたことなど，これで満足していてはいけないところだと思っています．

ABC278

コンテスト名: AtCoder Beginner Contest 278
順位: 1117th / 8936
パフォーマンス: 1382
レーティング: 1196 → 1216 (+20)
コンテスト参加回数: 63

A - Shift

A - 問題

数列 $A$ に対して，「先頭の要素を取り除き，末尾に0を挿入する」という操作を $K$ 回行った後の数列を求めよ．

A - 解法

言われた通りにforループ．

A - ACコード

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    arr = A
    for _ in range(K): arr = arr[1:] + [0]

    print(*arr)


if __name__ == '__main__': main()

B - Misjudge the Time

B - 問題

24時間表記した時刻 $AB$ : $CD$ に対して， $AC$ : $BD$ も24時間表記としてあり得るようなものを「見間違えやすい時刻」とする．
現在時刻 $HH$ : $MM$ 以降で最初に現れる見間違えやすい時刻を求めよ．

B - 解法

$0 \leq 10A+B \leq 23$ ， $0 \leq 10C+D \leq 59$ が成り立つような時刻を全探索．

B - ACコード

from itertools import chain


def main():
    H, M = map(int, input().split())

    fr = H*60 + M
    for time in chain(range(fr, 24*60), range(fr)):
        h0, m0 = divmod(time, 60)
        h1, m1 = 10*(h0//10)+m0//10, 10*(h0%10)+m0%10

        if 0 <= h1 < 24 and 0 <= m1 < 60: break

    print(f'{h0:02} {m0:02}')


if __name__ == '__main__': main()

C - FF

C - 問題

「ユーザーのフォロー」「ユーザーのフォロー解除」「相互フォローのチェック」の3種類の操作を順に処理せよ．

C - 解法

各ユーザーをノード，フォロー関係を辺としてグラフを構築し，順に処理するだけ．
ユーザー数 $N \leq 10^9$ であることを見落として[set() for _ in range(N)]を用意してしまい1TLE．
慌ててdefaultdictを使って解決．

C - ACコード

from collections import defaultdict


def main():
    N, Q = map(int, input().split())

    follow = defaultdict(set)
    for _ in range(Q):
        t, a, b = map(int, input().split())

        if t == 1: follow[a].add(b)
        elif t == 2: follow[a] -= {b}
        else: print('Yes' if b in follow[a] and a in follow[b] else 'No')


if __name__ == '__main__': main()

D - All Assign Point Add

D - 問題

長さ $N$ の数列 $A$ に対して， $Q$ 個のクエリを処理せよ．
ただし，クエリは以下の3種類がある．

1 $x_q$ : $A%の全ての要素に$ x_q$を代入．
2 $i_q$ $x_q$ : $A_i$ に $x_q$ を加算．
3 $i_q$ : $A_{i_q}$ を出力．

D - 解法

最初とクエリ1の実行後に $A$ の各要素の初期値をdic = defaultdictで管理する．
クエリ2の実行時にはdic[i] += xを行う．
これもはじめに初期値をlistで管理してしまい1TLE．

D - ACコード

from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))

    dic = defaultdict(int, {i+1: ai for i, ai in enumerate(A)})
    init = 0
    Q = int(input())
    for _ in range(Q):
        query = list(map(int, input().split()))

        if query[0] == 1: dic, init = defaultdict(int), query[1]
        elif query[0] == 2: dic[query[1]] += query[2]
        else: print(dic[query[1]] + init)


if __name__ == '__main__': main()

E - Grid Filling

E - 問題

$H \times W$ のグリッドに $1$ 以上 $N$ 以下の整数が書かれている．
可能な位置にある $h \times w$ の長方形を塗りつぶし，それぞれ残ったマスに書かれている数の種類を求めよ．

E - 解法

それぞれの整数について $y, x$ 座標の最小値と最大値を求めておくことで，塗りつぶす長方形の範囲に整数が全て収まってしまうかを判定できる．

E - ACコード

from collections import defaultdict


def main():
    H, W, N, h, w = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]

    dic = defaultdict(lambda: [H, 0, W, 0])
    for i, row in enumerate(A):
        for j, a in enumerate(row):
            dic[a] = [
                min(dic[a][0], i), max(dic[a][1], i),
                min(dic[a][2], j), max(dic[a][3], j)
            ]

    C = len(dic)
    for i in range(H-h+1):
        ansi = [C]*(W-w+1)

        for j in range(W-w+1):
            for y_min, y_max, x_min, x_max in dic.values():
                if i > y_min or i+h-1 < y_max: continue
                if j > x_min or j+w-1 < x_max: continue
                ansi[j] -= 1

        print(*ansi)


if __name__ == '__main__': main()

F - Shiritori

F - 問題

$N$ 個の単語を使って2人でしりとりを行い，最適な行動をした時の勝者を求めよ．

F - 検討

Grundy数を用いて解けるのではと考えた．解説を見た感じDPで解けるらしい．

感想

ポケモンSVで忙しいので復習は後回しにしようと思います．