Magicode logo
Magicode
1
15 min read

AtCoder Beginner Contest 260 の A 〜 E を解く

https://cdn.apollon.ai/media/notebox/507e843c-dc80-45c6-a11c-9276c4d39b40.jpeg

はじめに

この記事は 2022-07-17(日) に行われた AtCoder Beginner Contest 260 の解説です。
私は ABCD 4 完でした。
コンテスト中に考えたことの整理を兼ねて忘備録として書いておこうと思います。(E 問題は後から解きましたのでその時の考察を書いてます。)
この記事が一緒に AtCoder を楽しんでいる人の役に立てたら嬉しいです。
説明不足・間違いがありましたらコメントをください。

A - A Unique Letter

考察

  • 文字の並びは答えに関係ないので、個数だけ集計しても良い。

実装

def resolve():
  from collections import Counter

  # {<文字>: 含まれる個数} という形式になるように集計する。
  S = Counter(list(input()))

  # k : 文字
  # v : その文字が与えられた文字列に含まれている個数
  for k, v in S.items():
    # 与えられた文字列に k が 1 個だけ含まれているとき、それが答え
    if v == 1:
      print(k)
      return
  # 該当する文字が見つからなかった場合、-1 を出力する。
  print(-1)

resolve()

B - Better Students Are Needed!

考察

  • N <= 1000 なので O(N^2) 程度なら通りそう。
  • 手順 2, 3 で「既に合格した人を新規合格者として扱わない」といった処理が必要なので合格者を set で管理する。

実装

def resolve():
  N, X, Y, Z = map(int, input().split(" "))
  A = [int(x) for x in input().split(" ")]
  B = [int(x) for x in input().split(" ")]

  # 数学・英語・数学+英語それぞれの点数が大きい順に並べる。
  # 点数が同じだった場合、受験番号が小さい方が前に来るように、受験番号を負の値にする。
  MATH = sorted([(a, -(i+1)) for i, a in enumerate(A)], reverse=True)
  ENGLISH = sorted([(b, -(i+1)) for i, b in enumerate(B)], reverse=True)
  SUM = sorted([(A[i]+B[i], -(i+1)) for i in range(N)], reverse=True)

  # fixed: 合格した人のインデックスの集合
  fixed = set()

  # 数学の点数が高い方から X 人合格させる。
  for _, i in MATH:
    if len(fixed) == X: break
    fixed.add(i)

  # 英語の点数が高い方から Y 人合格させる。
  # 既に X 人合格しているので、この処理が終わった時点で X + Y 人合格していることになる。
  for _, i in ENGLISH:
    if len(fixed) == X+Y: break
    fixed.add(i)

  # 数学 + 英語の点数が高い方から Z 人合格させる。
  # 既に X + Y 人合格しているので、この処理が終わった時点で X + Y + Z 人合格していることになる。
  for _, i in SUM:
    if len(fixed) == X+Y+Z: break
    fixed.add(i)

  # ソートする時にインデックスを負の値にしたので再度反転させる。
  ans = sorted([-i for i in list(fixed)])

  print(*ans, sep="\n")

resolve()

C - Changing Jewels

考察

  • レベル 2 以上の宝石に対しては全て操作を行なって使い切る必要がある。
    • 最終的にレベル 1 の青い宝石が欲しい。
    • レベル 2 以上の宝石に操作を何回か行うことで最終的にレベル 1 の青い宝石を増やすことができるので、レベル 2 以上の宝石を残しておいてはいけない。
    • レベル 2 以上の宝石を残しておいて、後で使い切っても最大値が増えることはない。
      • 手元にあるレベル n の宝石に操作するとき、一度に全てのレベル n の宝石に操作をまとめて行なった方が実装が楽そう。
  • レベル n の宝石を操作して、レベル n-1 の宝石に操作する挙動は動的計画法っぽい。

実装

def resolve():
  N, X, Y = map(int, input().split(" "))
  # dp[n][c]: レベル N の赤い宝石 1 個からはじめた時に、
  # レベル n の c (c == 0: 赤、c == 1: 青) 色の宝石の最大の個数。
  dp = [[0, 0] for _ in range(N+1)]

  # 初期値。レベル N の赤色の宝石を 1 個持っている状態から始まる。
  dp[N][0] = 1
  for n in range(N, 1, -1):
    # 赤色の宝石に操作を行うときの遷移
    dp[n-1][0] += dp[n][0]
    dp[n][1] += X*dp[n][0]

    # 青色の宝石に操作を行うときの遷移
    dp[n-1][0] += dp[n][1]
    dp[n-1][1] += Y*dp[n][1]

  # 最終的にレベル 1 の青色の宝石を何個作ることができるかを出力する。
  print(dp[1][1])

resolve()

D - Draw Your Cards

結構難しく感じました。水色くらいの印象でしたが緑 diff なんですね。

考察

  • シミュレーションすることを考える。
    • 愚直にやると以下の 2 点が問題になりそう。
      • 新しく引いたカードがどのカードの上に置かれるか?というのを判定するのに時間がかかりそう。
        • 場に出ているカードを前から順に見ていくという方法だと O(N) かかる。
        • tatyam さんの作った SortedMultiset で場に出てるカードを管理すれば間に合いそう。
      • 山を食べる時、どのカードが食べる対象になるのかをどうやって管理するのか?
        • カードを重ねるタイミングでどのカードがどのカードの上に乗っているかを記録しておく。
        • カードを順に辿っていくことで食べる対象のカードを全て知ることができる。
        • 高々 N 枚のカードしか食べることはできないので、計算量的には問題ないはず。

実装

# SortedMultiset: tatyam さんの作った SortedMultiset を利用させていただいています。
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')

class SortedMultiset(Generic[T]):
  BUCKET_RATIO = 50
  REBUILD_RATIO = 170

  def _build(self, a=None) -> None:
    "Evenly divide `a` into buckets."
    if a is None: a = list(self)
    size = self.size = len(a)
    bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
    self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]
  
  def __init__(self, a: Iterable[T] = []) -> None:
    "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
    a = list(a)
    if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
        a = sorted(a)
    self._build(a)

  def __iter__(self) -> Iterator[T]:
    for i in self.a:
      for j in i: yield j

  def __reversed__(self) -> Iterator[T]:
    for i in reversed(self.a):
      for j in reversed(i): yield j
  
  def __len__(self) -> int:
    return self.size
  
  def __repr__(self) -> str:
    return "SortedMultiset" + str(self.a)
  
  def __str__(self) -> str:
    s = str(list(self))
    return "{" + s[1 : len(s) - 1] + "}"

  def _find_bucket(self, x: T) -> List[T]:
    "Find the bucket which should contain x. self must not be empty."
    for a in self.a:
      if x <= a[-1]: return a
    return a

  def __contains__(self, x: T) -> bool:
    if self.size == 0: return False
    a = self._find_bucket(x)
    i = bisect_left(a, x)
    return i != len(a) and a[i] == x

  def deck_count(self, x: T) -> int:
    "deck_count the number of x."
    return self.index_right(x) - self.index(x)

  def add(self, x: T) -> None:
    "Add an element. / O(√N)"
    if self.size == 0:
      self.a = [[x]]
      self.size = 1
      return
    a = self._find_bucket(x)
    insort(a, x)
    self.size += 1
    if len(a) > len(self.a) * self.REBUILD_RATIO:
      self._build()

  def discard(self, x: T) -> bool:
    "Remove an element and return True if removed. / O(√N)"
    if self.size == 0: return False
    a = self._find_bucket(x)
    i = bisect_left(a, x)
    if i == len(a) or a[i] != x: return False
    a.pop(i)
    self.size -= 1
    if len(a) == 0: self._build()
    return True

  def lt(self, x: T) -> Union[T, None]:
    "Find the largest element < x, or None if it doesn't exist."
    for a in reversed(self.a):
      if a[0] < x:
        return a[bisect_left(a, x) - 1]

  def le(self, x: T) -> Union[T, None]:
    "Find the largest element <= x, or None if it doesn't exist."
    for a in reversed(self.a):
      if a[0] <= x:
        return a[bisect_right(a, x) - 1]

  def gt(self, x: T) -> Union[T, None]:
    "Find the smallest element > x, or None if it doesn't exist."
    for a in self.a:
      if a[-1] > x:
        return a[bisect_right(a, x)]

  def ge(self, x: T) -> Union[T, None]:
    "Find the smallest element >= x, or None if it doesn't exist."
    for a in self.a:
      if a[-1] >= x:
        return a[bisect_left(a, x)]

  def __getitem__(self, x: int) -> T:
    "Return the x-th element, or IndexError if it doesn't exist."
    if x < 0: x += self.size
    if x < 0: raise IndexError
    for a in self.a:
      if x < len(a): return a[x]
      x -= len(a)
    raise IndexError

  def index(self, x: T) -> int:
    "Count the number of elements < x."
    ans = 0
    for a in self.a:
      if a[-1] >= x:
        return ans + bisect_left(a, x)
      ans += len(a)
    return ans

  def index_right(self, x: T) -> int:
    "Count the number of elements <= x."
    ans = 0
    for a in self.a:
      if a[-1] > x:
        return ans + bisect_right(a, x)
      ans += len(a)
    return ans

def resolve():
  N, K = map(int, input().split(" "))

  # 後々カード同士の結合関係を使う処理を入れるので、カードに書かれた番号を 0-index に対応させるために -1 している。
  P = [int(x)-1 for x in input().split(" ")]

  # ans[i]: i 番目のカードが何ターン目に食べられるか
  ans = [-1]*N

  # deck_tops: 場に見えているカード
  deck_tops = SortedMultiset([])

  # parents[i]: i と書かれたカードの下に書かれたカードに書かれている数字
  parents = [-1]*N

  # deck_count[i]: 場に見えているカードに書かれた数字が i だった時、そのカードが乗っている山に何枚のカードが含まれるのか
  deck_count = [1]*N
  for turn in range(1, N+1):
    # p: 新しく引いたカードに書かれた番号
    p = P[turn-1]

    # 場に出ているカードの内、p 以上のカードの番号
    ele = deck_tops.gt(p)

    # 重ねる対象となるカードが存在する場合、
    # その山のトップと新しく引いたカードの関連付けを行なった上で deck_tops からその山のトップを除去する。
    # (直後に新しく引いたカードを山の一番上として登録するので山自体が消えるわけではない。)
    if ele is not None:
      deck_count[p] = deck_count[ele] + 1
      parents[p] = ele
      deck_tops.discard(ele)

    deck_tops.add(p)

    # 山を食べる動作
    if deck_count[p] >= K:
      deck_tops.discard(p)
      while p >= 0:
        ans[p] = turn
        p = parents[p]

  print(*ans, sep="\n")

resolve()

E - At Least One

コンテスト中に解けませんでした。 コンテスト後に考えたことを書きます。

考察

  • 数列 (1, 2, 3, ..., M) の連続部分列としてあり得るパターンに個数について考える。
    • 1 ~ M までの数字を一個選んで、それを L とする。L ~ M+1 までの数字を選んでそれを R とする。
    • [L, R) に含まれる整数を昇順に並べた物が数列 (1, 2, 3, ..., M) の連続部分列
    • よって、あり得る数列の個数は M*(M-1)/2 になる
      • 全ての連続部分列について愚直に計算していると間に合わない。計算量を落とす必要がある。
  • L を固定して考えてみる。
    • 以下の図のように、L を 2 に固定して R を右にずらしていった場合、R が 6 を超えた時点で良い数列になり、それ以降ずっと良い数列であることがわかる。
    • L を固定した時に、R がどの値を超えた時点で良い数列になるか?が分かれば答えが出せる。
      • 答えは数列の長さ毎に出さなきゃいけない。
      • 全ての L に対して長さ R-L ~ M+1-L まで毎回 1 ずつ足し算すると計算量が多くなりすぎる。
      • 決まった区間に定数を足す操作を行うので いもす法 が使える。
  • L を固定してから R を動かす時にかかる計算量の問題
    • 全ての L に対して、R を L+1 ~ M+1 まで動かすような操作を行うと、最悪ケースで M*(M-1)/2 回の計算を行う必要がある。
    • L を動かしたタイミングと R を動かしたタイミングで i 番目の整数の組が持っている数字の増減を管理すれば(図を参照してください)、整数の組の内どれが区間内に含まれているかがわかるので、尺取法でできる。

実装

def resolve():
  from collections import defaultdict
  N, M = map(int, input().split(" "))
  indexes = [[] for _ in range(M)]

  # 尺取法をする時に扱いやすいようにデータを持っておく。
  # indexes[X]: 整数 X を持っている整数の組の番号
  for i in range(N):
    a, b = [int(x)-1 for x in input().split(" ")]
    indexes[a].append(i)
    indexes[b].append(i)

  # imos[k]: 長さ k の
  imos = [0]*(M+1)

  # count[i]: 現在、整数の組の番号 i がもつ数字が区間 [L, R) に何個含まれているか
  count = [0]*M

  # includes: Ai, Bi どちらかが [L, R) に含まれる整数の組の番号を管理するための set
  includes = set()
  r = 0
  for l in range(M):
    # [l, r) が良い数列になるか、r をそれ以上右に動かせなくなるまで r を移動させる
    while r < M and len(includes) < N:
      for i in indexes[r]:
        count[i] += 1
        includes.add(i)
      r += 1

    # f(k) (k: r-l ~ M-l) の結果全てに 1 を足す操作
    # いもす法なので、操作する区間の先頭と末尾に値を差し引きするだけ
    if len(includes) == N:
      imos[r-l] += 1
      if M-l+1 <= M: imos[M-l+1] -= 1

    # 左を動かすタイミングで整数の組の番号 i がもつ数字が区間 [l, r) に何個含まれているか?を減らす
    for i in indexes[l]:
      count[i] -= 1
      # count[i] が 1 => 0 に変化したということは、
      # 整数の組 i が区間 [l, r) に含まれなくなったということなので includes から除く
      if count[i] == 0:
        includes.remove(i)

  # いもす法の全体シミュレートを実行する。
  for i in range(1, M+1):
    imos[i] += imos[i-1]
  print(*(imos[1:]))

resolve()

Discussion

コメントにはログインが必要です。