Ccmmutty logo
Commutty IT
2
17 min read

5完できない芸人の緑コーダーがABC260のA~Eまで

https://cdn.magicode.io/media/notebox/blob_QYoXPr1

AtCoder Beginner Contest 260

ABC260のA~Eに関する解説(という名の自分用メモ書き)です。

戦績

今回も4完止まりでした!!!(N回目)
Eが青diffだったので、まぁ、解けなくても仕方ないかなぁ…と思ったり…。
ただ、内容自体は水色以下の組み合わせで理解できると思うので…うーん、時間さえ残せれば…。
Dでがっつり溶かしちゃいましたねぇ…勿体ない…。
今回実装問題多かったですね…!!!
次こそ!5完!したい!(N回目定期)

全体のざっくり解説

  • A : カウントしたり、条件分岐したり
  • B : ソートしたり、スライスしたり
  • C : 再帰したり、DPしたり
  • D : SortedSet!!!!!
  • E : しゃくとり + にぶたん!!!!!

A - A Unique Letter

問題要約

長さ3文字の文字列SSが与えられます。
SSに1度だけ含まれる文字を1つ出力してください。
但し、そのような文字が存在しない場合は変わりに-1と出力してください。

制約

  • SSは英小文字のみからなる3文字の文字列

考察

  • たった3文字の判定なので、どうにでもなる、いわゆる「やるだけ」問題
  • 方針としては、
    • 全部脳死でカウントして、個数が1個の要素がある/無いを判定
    • 一旦文字列SSをソートして、条件分岐で判定
  • 多分後者が簡単でシンプルかなー、と…(尚本番に提出したのは前者)
python
# 入力
S = input()

# リスト化してソート
L = list(S)
L.sort()

# 1文字目と2文字目が一緒じゃないなら、1文字目がユニーク
if L[0] != L[1]:
    print(L[0])

# そうでない場合(1文字目=2文字目)、2文字目と3文字目が一緒じゃないなら、3文字目がユニーク
elif L[1] != L[2]:
    print(L[2])

# そうでもない場合(1文字目=2文字目=3文字目)、ユニークなものは無いので-1
else:
    print(-1)

B - Better Students Are Needed!

問題要約

NN人の受験者が居ます。
試験の結果、ii番目の受験生は、数学でAiA_i点、英語でBiB_i点を取りました。
試験の合格者を下記の条件に基づいて求めて下さい。
  1. 数学の点が高い方からXX人を合格とする
  2. 次に、この時点で合格となっていない受験者のうち、英語の点数が高い方からY人を合格とする
  3. 次に、この時点で合格となっていない受験者のうち、数学と英語の合計点が高い方からZ人を合格とする
  4. ここまでで合格となっていない受験者は不合格とする ただし、1~3の段階で、同点であった場合は受験生の番号の小さい方を優先する

制約

  • 1N10001 \leq N \leq 1000
  • 1X,Y,ZN1 \leq X,Y,Z \leq N
  • 1X+Y+ZN1 \leq X+Y+Z \leq N
  • 0Ai,Bi1000 \leq A_i,B_i \leq 100
  • 入力は全て整数

考察

  • NNの制約が小さいため、「合格リスト」を作った上で、それぞれの手順について、合格不合格を確認してあげるのが正統派っぽい
    • 実際黒ココアさんも本番はこの流れで通しました
      • Aのリスト、BのリストからA+Bのリスト作って、
      • それぞれをソートして、大きい順に合格させていくスタイル
  • 適当にソートとかしちゃってもいいですねぇ
    • 2次元配列ソートして、一発で決められると格好良いですね!おしゃれ!
python
# 入力
N, X, Y, Z = map(int, input().split())
A_L = list(map(int, input().split()))
B_L = list(map(int, input().split()))

# 合計点と受験者番号を纏めた2次元配列を作成
score_L = []

for num, scores in enumerate(zip(A_L, B_L), 1):
    a, b = scores

    tmp_L = [-a, -b, -(a + b), num]
    score_L.append(tmp_L)

# ソートして、先頭からX(Y,Z)人除いた人だけ残して…
score_L = sorted(score_L, key=lambda x: (x[0], x[-1]))[X:]
score_L = sorted(score_L, key=lambda x: (x[1], x[-1]))[Y:]
score_L = sorted(score_L, key=lambda x: (x[2], x[-1]))[Z:]

# 最終的に残ったものが「不合格者リスト」
failure_s = set()
for scores in score_L:
    failure_s.add(scores[-1])

# 不合格者リストに入っていないのなら、その人は合格!
for num in range(1, N + 1):
    if num not in failure_s:
        print(num)

C - Changing Jewels

問題要約

高橋君はレベルNNの赤い宝石を1個だけ持っています。
高橋君は次の操作を好きなだけ行うことができます。
  • レベルnnの赤い宝石(n2n \leq 2)を、レベルn1n-1の赤い宝石1個と、レベルnnの青い宝石XX個に変換する
  • レベルnnの青い宝石(n2n \leq 2)を、レベルn1n-1の赤い宝石1個と、レベルn1n-1の青い宝石YY個に変換する
高橋君はレベル1の青い宝石ができるだけたくさん欲しいです。
最大何個入手できますか?

制約

  • 1N10 1 \leq N \leq 10
  • 1X5 1 \leq X \leq 5
  • 1Y5 1 \leq Y \leq 5
  • 入力される値はすべて整数

考察

  • 制約がとても小さいので、愚直シミュレート問題
    • 1055=250パターンしか無いので、時間いっぱいかけるなら手計算でもなんとか…まぁ…いけなくは…???
  • DPだったり再帰だったりで解ける問題
  • 直接NNから答えを求めずに、問題自体を小さい領域に分けて考えるイメージ
    • Lvnnの赤い宝石1つから、Lvn1n-1の青い宝石がいくつできますか?
  • イメージができたら、後は実際に実装するだけ…
    • 再帰関数 or DPで実装
      • 今回本当に実装問題ばっかりでしたねぇ…
  • DPでの実装
python
# 入力
N, X, Y = map(int, input().split())

# 青石、赤石の個数テーブルをそれぞれ作るよ!
# Lvで見たいので、なんとなく直感的に1-indexedにしちゃいました…
# b_L[i] := Lviの青石の個数
# r_L[i] := Lviの赤石の個数
b_L = [0] * (N + 1)
r_L = [0] * (N + 1)

# r_L[N] := Nレベルの赤石が1個ある状態!
r_L[-1] = 1


# LvNからLv2まで、それぞれ小さくする作業
for i in range(N, 1, -1):
    
    # 赤石Lviがそのまま赤石Lv(i-1)になって…
    r_L[i - 1] += r_L[i]
    
    # 赤石LviのX倍が、青石Lviになって…
    b_L[i] += r_L[i] * X
    
    # 青石Lviが、赤石Lv(i-1)になって…
    r_L[i - 1] += b_L[i]
    
    # 青石LviのY倍が、青石Lv(i-1)になる!
    b_L[i - 1] += b_L[i] * Y

# 青石Lv1の数を出力して終了!
print(b_L[1])
  • 再帰関数での実装
python
# 入力
N, X, Y = map(int, input().split())


# 「Lv○の赤石を△個、操作1で変換するとどうなるの?」関数
def red_conversion(lv, cnt):
    # Lv1なら、何も返さないよ。
    # Lv1の赤石は青石には変換できないので、捨てちゃうイメージで。
    if lv == 1:
        return 0

    # Lv2以上なら、Lv(n-1)の赤石が個数分と、Lvnの青石が個数*X個できるよ!
    return red_conversion(lv - 1, cnt) + blue_conversion(lv, cnt * X)


# 「Lv○の青石を△個、操作2で変換するとどうなるの?」関数
def blue_conversion(lv, cnt):
    
    # Lv1なら、そのまま個数返すよ!
    # Lv1の青石の個数が欲しいからね!
    if lv == 1:
        return cnt

    # Lv2以上なら、Lv(n-1)の赤石が個数分と、Lv(n-1)の青石が、個数*Y個出来るよ!
    return red_conversion(lv - 1, cnt) + blue_conversion(lv - 1, cnt * Y)



# じゃあ、LvNの赤い石を変換するとどうなるの?
print(red_conversion(N, 1))

D - Draw Your Cards

問題要約

11からNNが書かれたNN枚のカードが裏向きで積まれた山札があります。
上からii枚目のカードには整数PiP_iが書かれています。
以下の行動をNNターン繰り返します。
  1. 山札の一番上のカードを引いて、そこに書かれた整数をXとする。
    • 場に見えている表向きのカードの中で、書かれた整数がX以上のものが存在する場合、
      • その中で最小のものの上に、引いたカードを表向きで重ねる
    • 場に見えている表向きのカードの中で、書かれた整数がX以上のものが存在しない場合、
      • どれにも重ねずに表向きで置く
  2. 表向きのカードがK枚重ねられた山が場に存在する場合、
    • その山のカードを全て消去する。
各カードについて、何ターン目に食べられる/最後まで場に残っているかを求めて下さい

制約

  • 入力は全て整数
  • 1KN2×1051 \leq K \leq N \leq 2 \times 10^5
  • PP(1,2,,N)(1,2,…,N)の順列((1,2,,N)(1,2,…,N)を並べ替えて得られる列)である

考察

  • カードのダブリは無さそう→全部ユニークっぽい
  • 制約から、カードの枚数が高々2×1052 \times 10^5
    • 其々のカードに対してO(1)とちょっとで求められるなら、間に合いそう…?
  • 場の管理と其々の山の管理だけ適切にできれば何かさらさらっと流せそうな…
    • 今回実装問題本当に多いですね…ひぃ…
  • とりあえず、サクッと「場に出てる表のカード」の中で「X以上のカード」を探したいので、tatyam様の、SortedSetをお借りする。
  • 後は、重ねた時の判定を…「iが書かれてるカードの下に、何枚ある?」を配列で管理して…
  • それから…「iのカードの下には何のカードが置いてある?」も、別で保管しておけば、処理としては全部足りる…かな…?
  • ええい、実装じゃ!!!添字ガチャも辞さない…!!!
python
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, TypeVar, Union, List

T = TypeVar('T')


class SortedSet(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 SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"
        a = list(a)
        if not all(a[i] < a[i + 1] for i in range(len(a) - 1)):
            a = sorted(set(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 "SortedSet" + 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 add(self, x: T) -> bool:
        "Add an element and return True if added. / O(√N)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return True
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x: return False
        a.insert(i, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()
        return True

    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


# 入力
N, K = map(int, input().split())
P_L = list(map(int, input().split()))

# 色々情報保管変数の準備!
eat_L = [-1] * N # 何ターン目に食べられた?
cnt_L = [0] * N # cnt_L[i] := iのカードの下に何枚のカードがある?
bot_L = [-1] * N # bot_L[i] := iのカードの下にあるカードの番号は?
ss = SortedSet() # tatyam様のありがたいありがたいSortedSet!!!!!!!!!!
# 場の中で、表に見えてるカードを管理するよ!

# 1ターン目から順に操作していくよ!
for turn in range(1, N + 1):
    # phase1 : カードをドロー!!!0-indexedに直す!!!
    X = P_L[turn - 1]
    X -= 1
    
    # phase2 : 場に見えてるカードの中で、X以上のカードを探すよ!
    bot_card = ss.gt(X)
    
    # そんなのねぇ!なら、カードを場に出す流れ!
    if bot_card is None: 
        cnt_L[X] = 1
    
    # 重ねる場合の処理
    else:
        ss.discard(bot_card)
        cnt_L[X] = cnt_L[bot_card] + 1
        bot_L[X] = bot_card
    ss.add(X)

    # phase3 : 今出したカードの山、枚数がK超えてるなら全部墓場に流すよ!
    if cnt_L[X] >= K:
        ss.discard(X)
        while True:
            eat_L[X] = turn
            next_eat = bot_L[X]
            if next_eat == -1:
                break
            X = next_eat

# 何ターン目に処理されたかを出力して終わり!
for turn in eat_L:
    print(turn)

E - At Least One

問題要約

NN個の整数の組(A1,B1),(A2,B2),,(AN,BN)(A_1,B_1),(A_2,B_2),…,(A_N,B_N)と、整数MMが与えられます。
全てのiiについて、1Ai<BiM1 \leq A_i < B_i \leq Mが成り立っています。
次の条件を満たす数列SSを、良い数列と呼びます。
  • SSは、数列(1,2,3,,M)(1,2,3,…,M)の連続部分列である
  • すべてのiiについて、SSは、Ai,BiA_i,B_iの少なくとも一方を含んでいる
長さkkの良い数列としてあり得るものの個数をf(k)f(k)とします。
f(1),f(2),,f(M)f(1),f(2),…,f(M)を列挙してください。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 2M2×1052 \leq M \leq 2 \times 10^5
  • 1Ai<BiM1 \leq A_i < B_i \leq M
  • 入力は全て整数

考察

  • まさかの青diff。運営が黒ココアさんの5完を潰しに来た
  • 数学を極めし神々の戯れみたいな数学パズルではなかったけど、ガッツリゴリゴリ実装する感じでした…多分…。
  • 本番ACできず、解説ACだったので思考の遷移は残せず…
  • とりあえずサンプル1の出力例を眺めてみる。じーっと。
    • 一旦辞書順に並べてみたりすると、ハッピーに近づく。気がする。
      • (1,2)
      • (1,2,3)
      • (1,2,3,4)
      • (1,2,3,4,5)
      • (2,3,4)
      • (2,3,4,5)
      • (3,4,5) * SSは連続部分列なので、とりあえず一番左の数字をL,一番右の数字をRと表記することにしてみる
  • Lを固定して、Rを右に動かしていった時、どこかのタイミングでSS良い数列になる瞬間が来る。
  • それ以降、Rをどこまで右に動かしても、SSが悪い数列に戻ることはない。ずっと良い数列。
    • だって連続部分列なので!
  • このあたりを踏まえて、サンプル1の出力例に戻る。
  • L=1L=1にした時、R=2R=2になるとSS良い数列になる
    • この時の数列の長さは2!
    • このままRRを右に、MMまで伸ばしても全部良い数列!
    • じゃあ…R=MR=Mになったときの数列SSの長さは…5!
      • L=1L=1の時、長さ2の良い数列、長さ3の良い数列、長さ4の良い数列、長さ5の良い数列ができる!
  • L=2L=2の時は…?
    • R=4R=4の時初めて良い数列になる!長さは3!
    • R=MR=Mまで伸ばしても全部良い数列なので…
      • L=1L=1の時、長さ3の良い数列、長さ4の良い数列ができる!
  • LLを1つずつ動かして、良い数列となる一番左のRRを求めていくパートはしゃくとり法で行けそう…!
  • LLに対してRRが決まったときの、区間加算はimos法で行けそう…!
  • 後は実装!はい!実装!(無事死亡解説AC)
python
from collections import defaultdict
from collections import deque

# 入力
N, M = map(int, input().split())
# d[i] := iをしゃくとりに追加/削除した時に、満たされる/外される条件
d = defaultdict(set)

for i in range(N):
    a, b = map(int, input().split())
    d[a].add(i)
    d[b].add(i)

# 変数初期化色々
que = deque()
ans_L = [0] * (M + 10) # imos用の配列!
cnt_L = [0] * N  # cnt_L[i] := i番目の条件(A,B)のうち、いくつの数字がしゃくとり範囲に入ってる? 0なら区間外、1ならAかBの片方が入ってる、2ならABどっちも入ってる
zero_cnt = N  # 満たされていない条件の数!


# Rを右に動かした時(=しゃくとりの区間を広げた)の処理!
def func_add(num):
    if len(d[num]) != 0:
        global zero_cnt
        for i in d[num]:
            if cnt_L[i] == 0:
                zero_cnt -= 1
            cnt_L[i] += 1

# Lを右に動かしたとき(=しゃくとりの区間を減らす)の処理!
def func_red(num):
    if len(d[num]) != 0:

        global zero_cnt
        for i in d[num]:
            if cnt_L[i] == 1:
                zero_cnt += 1
            cnt_L[i] -= 1


# Lを1つずつ動かしていくイメージでしゃくとりパート!
for i in range(1, M + 1):
    if len(que) == 0:
        que.append(i)
        func_add(i)

    while True:
        if zero_cnt == 0 or que[-1] == M:
            break
        add_num = que[-1] + 1
        que.append(add_num)
        func_add(add_num)

    if zero_cnt == 0:
        idx = len(que)
        ans_L[idx] += 1
        end_idx = idx + (M - que[-1]) + 1
        ans_L[end_idx] -= 1

    red_num = que.popleft()
    func_red(red_num)

# しゃくとりは終わってimos前処理配列が出来上がってるので、IMOS!!!!!
accum_L = [0]
for score in ans_L:
    accum_L.append(accum_L[-1] + score)

# そのまま答えが出てくる!
print(*accum_L[2:2 + M])

Discussion

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