📝

AtCoder Beginner Contest 278 レポート

2022/11/20に公開約5,000字

摘要

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

ABC278

https://atcoder.jp/contests/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()

https://atcoder.jp/contests/abc278/submissions/36600202

B - Misjudge the Time

問題 / 解説

B - 問題

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

B - 解法

0 \leq 10A+B \leq 230 \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()

https://atcoder.jp/contests/abc278/submissions/36608081

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()

https://atcoder.jp/contests/abc278/submissions/36611830

D - All Assign Point Add

問題 / 解説

D - 問題

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

  • 1 x_q : A%の全ての要素にx_q$を代入.
  • 2 i_q x_q : A_ix_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()

https://atcoder.jp/contests/abc278/submissions/36617615

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()

https://atcoder.jp/contests/abc278/submissions/36624473

F - Shiritori

問題 / 解説

F - 問題

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

F - 検討

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

感想

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

Discussion

ログインするとコメントできます