【緑コーダー】【AtCoder解説】PythonでABC278のA,B,C,D,E問題を解いてみた

はじめに

ABC278のA~E問題をPythonで解いたので解説していきます。

A問題 「Shift」

考察

• 値を前から削除して、後ろに0を追加する
• Nが小さいので、pop(0)で十分間に合いますが、Nが大きい場合はcollections.dequeなどを使うと良いでしょう
  • （筆者も本番ではdequeを使用しました）

コード

N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
for _ in range(K):
  A.pop(0)
  A.append(0)
print(*A)

B問題「Misjudge the Time」

考察

• 全通りのパターンが24 * 60 = 1440なので、全検索が可能です
• 指定時間から見間違いやすい時間かどうかを判定して、見間違いなければ1分ずつ足していきます
  • 59分の場合は0分にして時間を1時間加えます
  • 23:59の場合はループから抜け出し0時0分となります

コード

H,M = list(map(int, input().split()))

# 見間違い時間かの判定
def is_valid(h,w):
  hh = str(h).zfill(2)
  ww = str(w).zfill(2)
  return 0 <= int(hh[0]+ww[0]) <= 23 and 0 <= int(hh[1]+ww[1]) <= 59

while H < 24:
  while M < 60:
    if is_valid(H,M):
      print(H,M)
      exit()
    M += 1
  if M==60:
    M = 0
  H += 1
# 当てはまらない場合は0時0分
print(0, 0)

C問題「FF」

考察

• データ構造をどのように持つかが鍵となります
• Mapのset型で持つことでO(logN)で追加・削除・検索ができます
  • defaultdictを使うことで、辞書のキーが存在するかの判定を省くことができます

コード

import collections
N,Q = list(map(int, input().split()))
# setの辞書型で保持する
obj = collections.defaultdict(set)
qs = []
for _ in range(Q):
  qs.append(list(map(int, input().split())))
for t,a,b in qs:
  if t==1:
    # aがbをフォローする
    obj[a].add(b)
  elif t==2:
    # aがbをフォロー解除
    obj[a].discard(b)
  else:
    # aがbをフォローし,bがaをフォローしているか判定
    if a in obj[b] and b in obj[a]:
      print('Yes')
    else:
      print('No')

D問題「All Assign Point Add」

考察

• Aの全ての要素に代入する箇所が肝となります
  • ここで毎回配列を入れ直しているとTLEになってしまいます
• それぞれのクエリに対する方針
  • 1になった場合はXq​を保持しておきます
  • 2になった場合はXqがあるか、すでに2になっているかで分岐処理します
  • 3になった場合は1,2を考慮して値を出力します
• 文字だけだとわかりづらいので、コード参照お願いします

コード

N = list(map(int, input().split()))
A = list(map(int, input().split()))
Q = int(input())

queries = []
for _ in range(Q):
  queries.append(list(map(int, input().split())))

# 1になった場合の代入する値
axq = -1
# 2に渡った数値を保持する集合
values = set()
for t,*x in queries:
  if t==1:
    # axqに代入する値を保持
    axq = x[0]
    # valuesを初期化
    values = set()
  elif t==2:
    i = x[0]-1
    if i in values or axq < 0:
      # すでに2に渡っているか、1に渡っていない場合
      A[i] += x[1]
    else:
      # 上記以外の場合、1に渡っているので、axq + 2の加える数値
      A[i] = axq + x[1]
    # 2に渡ったことを追加
    values.add(i)
  else:
    i = x[0]-1
    if i in values or axq < 0:
      # すでに2に渡っているか、1に渡っていない場合はA[i]
      print(A[i])
    else:
      # 1に渡っていて、2に渡っていない場合はaxq
      print(axq)

E問題「Grid Filling」

考察

• 全検索しようとする場合にTLEになってしまいます
  • 任意のH,Wを起点に縦h, 横w分をそれぞれ見て全体の種類数から引く
  • O(HWhw)のため最大 900^4 のため 81 * 10**8 で終わりません
• 縦列は任意にして横列の検索を差分更新にして計算量を減らします
  • 任意のHを起点にw,hマスを取得
  • そこから左端を削除して、右端を追加するようなことをします
  • 計算量が O(H*(hw + Wh))ほどとなり 900^3 = 27 * 10^6 で終わりそうです

コード

import collections
H,W,N,h,w = list(map(int, input().split()))

# N個の数値がそれぞれ何個あるかを保持
type_al = [0] * (N+1)

arr = []
for _ in range(H):
  v = list(map(int, input().split()))
  arr.append(v)
  for k in v:
    # それぞれ何個あるかを加える
    type_al[k] += 1

types = 0
# 数値が何種類あるか
for v in type_al:
  if v > 0:
    types += 1

# 黒マスが動ける縦分ループ
for h1 in range(H-h+1):
  ans = []
  # どの数値が何種類あるかを保持
  obj = collections.defaultdict(int)
  # 全体種類数の初期化
  ts = types
  # まずは先頭の四角形を出す
  for hh in range(h1, h1+h):
    for ww in range(w):
      k = arr[hh][ww]
      obj[k] += 1
      # 黒マスに含まれている数値が全体マスの数値数と同じ場合は種類が少ない
      if type_al[k] == obj[k]:
          ts -= 1
  # 先頭の四角形の場合の種類数
  ans.append(ts)

  ## ずらして出していく
  for ww in range(1, W-w+1):
    # 全体種類数の初期化
    ts = types
    for hh in range(h1, h1+h):
      # 一個前の列
      k = arr[hh][ww-1]
      obj[k] -= 1

      # 加える列
      k = arr[hh][ww+w-1]
      obj[k] += 1
    
    # 種類の全探索
    for k in obj:
      # 黒マスに含まれている数値が全体マスの数値数と同じ場合は種類が少ない
      if type_al[k] == obj[k]:
        ts -= 1
    ans.append(ts)
  print(*ans)

終わりに

• 今回初めてAtCoderの解説を記述してみました。
• 普通に解くのとは違ってそれぞれどういう意味で動いているかなどを改めて認識できるので、また書いていきたいと思います
• また、本番ではB問題に30分かかったり、D問題が1ペナ、E問題が解けなかったりなど、思うようにできませんでしたが、もう少し力をつけて水色目指していきたいです