茶色コーダによるABC379振り返り

はじめに

前回マジで投稿遅れてすいません(やっと反省した)
今回はコンテスト翌日の投稿です。

結果としてはABDの3完でパフォは800ちょいでした。
予想通りCが難しくなってて、すぐパスできて良かったです
えーと ものすごく申し上げにくいのですがBで4ペナくらいましたw(よく緑パフォでたな)
Dはすぐに解法が思いついたものの二分探索がうまくいかず、結構実装に手間取ってしまいました
AJLの中１参加者が、C問題解けてる割合が結構高くてなんの差だろうと、考えています(明らかに数学とかの差だろ)

使用しているライブラリ

グラフのクラスと、複数行入力をサポートするライブラリを追加しました
githubのPerformansの.template/codeにおいてあります じっくり見たい方はそちらを見てください

# ライブラリと関数と便利変数
# ライブラリ
from collections import deque, defaultdict, Counter
from math import pi
from itertools import permutations
import bisect
import sys
import heapq
from typing import List

# cortedcontainersは使うときだけ wandbox非対応なので
# from sortedcontainers import SortedDict, SortedSet, SortedList

sys.setrecursionlimit(5 * 10**5)


# 関数
def pow(x: int, n: int, t: int = 1):
    # O(log N)
    if t == 1:
        ans = 1
        while n:
            if n % 2:
                ans = ans * x
            x = x * x
            n >>= 1
        return ans
    ans = 1
    while n:
        if n % 2:
            ans = (ans * x) % t
        x = (x * x) % t
        n >>= 1
    return ans


def is_prime(n: int) -> bool:
    # O(√N)
    if n == 1:
        return False

    i = 2
    s = n**0.5

    while i < s:
        if n % i == 0:
            return False

        i += 1

    return True


def eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0], primes[1] = False, False
    i = 2
    while i**2 <= n:
        if primes[i]:
            for k in range(i * 2, n + 1, i):
                primes[k] = False

        i += 1

    return [i for i, p in enumerate(primes) if p]


def gcd(a, b):
    while a > 0 and b > 0:
        if a > b:
            a = a % b
        else:
            b = b % a

    return max(a, b)


def lcm(a, b):
    return (a * b) // gcd(a, b)


def calc_divisors(N):
    # 約数全列挙
    result = []

    for i in range(1, N + 1):
        if i * i > N:
            break

        if N % i != 0:
            continue

        heapq.heappush(result, i)
        if N // i != i:
            heapq.heappush(result, N // i)

    return result


def factorization(n):
    # 素因数分解
    result = []
    tmp = n
    for i in range(2, int(-(-(n**0.5) // 1)) + 1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            result.append([i, cnt])

    if tmp != 1:
        result.append([tmp, 1])

    if result == []:
        result.append([n, 1])

    return result


# 標準入力系
# 一行に一つのstring
def s():
    return sys.stdin.readline().rstrip()


# 一行に複数のstring
def sl():
    return s().split()


# 一つのint
def ii():
    return int(s())


# 一行に複数のint
def il(add_num: int = 0):
    return list(map(lambda i: int(i) + add_num, sl()))


# 複数行の入力をサポート
def li(n: int, func, *args):
    return [func(*args) for _ in [0] * n]


# 自作型
class Heap:
    def __init__(self) -> None:
        self.heap: List[int] = []

    def push(self, x: int):
        """
        値を挿入する関数

        計算量 O(log N)
        Nはheapのサイズ
        """

        # 末尾に挿入
        self.heap.append(x)
        # 現在地の変数
        ind: int = len(self.heap) - 1

        # 更新処理
        while ind > 0:
            # 現在地の親を求める
            # 求め方はセグ木の要領で
            parent: int = (ind - 1) // 2

            # 親の方が小さかったら処理を終了
            if self.heap[parent] <= x:
                break

            # 親より小さかったら入れ替える
            self.heap[ind] = self.heap[parent]
            # 現在地を更新
            ind = parent

        # 最後に現在地にxを代入
        self.heap[ind] = x

    def min(self):
        """
        最小値を出力する関数

        計算量
        O(1)
        """
        if len(self.heap) == 0:
            print("\033[31m error heap is empty \033[0m")
            return
        return self.heap[0]

    def pop(self):
        """
        最小値を削除する関数
        返り値は削除した最小値

        計算量
        N = len(self.heap)
        O(log N)
        """
        # 返り値を取っておく
        result = self.min()

        # self.heapが空ならエラーを吐く
        if len(self.heap) == 0:
            print("\033[31m error heap is empty \033[0m")
            return

        # 末尾の値を取得
        x: int = self.heap.pop()
        # 現在地
        ind = 0

        # 要素がなくなった場合それが最小値なので出力する
        if len(self.heap) == 0:
            return result

        # 更新処理
        while ind * 2 + 1 < len(self.heap):
            # 現在地の子のインデックスを変数に入れとく
            child1 = ind * 2 + 1
            child2 = ind * 2 + 2
            # child2の要素がchild1の要素より小さければchild1をchild2にする
            if child2 < len(self.heap) and self.heap[child2] < self.heap[child1]:
                child1 = child2

            # child1の要素がxより大きければ処理を終了
            if self.heap[child1] >= x:
                break

            # 入れ替え
            self.heap[ind] = self.heap[child1]

            # 現在地を移動
            ind = child1

        # 現在地の要素をxにする
        self.heap[ind] = x

        # 削除した値を返す
        return result


# 無向グラフ
class Graph:
    def __init__(self, N: int, dire: bool = False) -> None:
        self.N = N
        self.dire = dire
        self.grath = [[] for _ in [0] * self.N]

    def new_side(self, a: int, b: int):
        # 注意　0-indexedが前提
        self.grath[a].append(b)
        if not self.dire:
            self.grath[b].append(a)

    def side_input(self):
        # 新しい辺をinput
        a, b = il(-1)
        self.new_side(a, b)

    def input(self, M: int):
        # 複数行の辺のinput
        for _ in [0] * M:
            self.side_input()

    def get(self, a: int):
        # 頂点aの隣接点を出力
        return self.grath[a]

    def all(self):
        # グラフの内容をすべて出力
        return self.grath


# 有向グラフ
class GraphW:
    def __init__(self, N: int, dire: bool = False) -> None:
        self.N = N
        self.dire = dire
        self.grath = [[] for _ in [0] * self.N]

    def new_side(self, a: int, b: int, w: int):
        # 注意　0-indexedが前提
        self.grath[a].append((b, w))
        if not self.dire:
            self.grath[b].append((a, w))

    def side_input(self):
        # 新しい辺をinput
        a, b, w = il(-1)
        self.new_side(a, b, w)

    def input(self, M: int):
        # 複数行の辺のinput
        for _ in [0] * M:
            self.side_input()

    def get(self, a: int):
        # 頂点aの隣接点を出力
        return self.grath[a]

    def all(self):
        # グラフの内容をすべて出力
        return self.grath


# 便利変数
INF = 10**18
lowerlist = list("abcdefghijklmnopqrstuvwxyz")
upperlist = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")


# テンプレ
class SegmentTree:
    # 鉄則本のパクリですけどよろしく
    def __init__(self, N) -> None:
        # サイズは要素の数

        self.size = 1
        while self.size < N:
            self.size *= 2

        self.data = [0] * (self.size * 2)

    def update(self, ind, x):
        ind = ind + self.size - 1
        self.data[ind] = x

        while ind >= 2:
            ind //= 2
            self.data[ind] = max(self.data[ind * 2], self.data[ind * 2 + 1])

    def query(self, l, r, a, b, u):
        if r <= a or l >= b:
            return -INF
        if l <= a and b <= r:
            return self.data[u]

        m = (a + b) // 2
        return max(self.query(l, r, a, m, u * 2), self.query(l, r, m, b, u * 2 + 1))


# コード

ほんじゃ一問ずつ、感想書きますか

A問題

問題文を要約
三桁の整数を右からa,b,cとしたときb,c,aを並び替えた整数とc,a,bを並び替えた整数を空白区切りで、出力してください。
みたいな感じの問題でした

まあササッと入れ替えれば簡単です
ACコード(ライブラリ抜粋) 全文
関数名はご想像にお任せします

a, b, c = list(s())
print(b + c + a, c + a + b)

おい過去一短いんじゃないか(ライブラリが増えて8000byteありますけどね)

B問題

問題文を要約
$S$の$i$文字目がOのとき、左から$i$番目がOなら歯は丈夫です。Xの場合は虫歯です

連続する$K$本の歯が丈夫なら、その$K$本の歯を使っていちごを一個食べられます。ですが、いちごを食べるとその$K$本の歯は虫歯になって使えなくなります
最大で何個のいちごが食べられますか?

普通にいちご一個食べるだけ虫歯になるなんて、怖いなおい
全然要約できてないじゃんw

普通に貪欲で解いた。
だけど調整ミスって、4ペナした(調整苦手)

ACコード(ライブラリ抜粋) 全文

N, K = il()
S = list(s())

L = [S[i] == "O" for i in range(N)]

ans = 0
i = 0

while i <= N - K:
    if all(L[i : i + K]):
        ans += 1
        for k in range(i, i + K):
            L[k] = False

        i += K - 1
        continue
    i += 1

print(ans)

C問題

問題文を要約
N個のマスが、あります
最初、M個のマスに、石が入っておおり、マス$X_i$には$A_i$個の石が入っています。
あなたは何回でも、以下の操作を、行うことができます
マス$i$に石が、あるならマス$i+1$に石を、移動させる

すべてのマスに石が入るように、するために、最小何回操作が必要か、求めてください。また、不可能な場合は-1を出力してください

全然要約できてないじゃんw(二回目)

貪欲かなーって、考えたりしたけど、結局ACできなかった。(結構いい線行ってた)
AJLの同学年(中１)は結構ACしていて、泣きかけた

D問題

問題文を要約　やっても無駄そうだしやらない(疲れてる)

偽解法で、ACした。(公式解説にも書いてない)　そして計算量は$O(Q log Q)$ぐらい公式解説は、$O(Q)$なんこれw

まあ、解けた解法書くか
多分計算量は、落ちるけど、わかりやすいと思う
解法は、二分探索系

クエリ1は、
何日伸びたか、取っておいてその変数$\times -1$した値を、appendする
クエリ2は、
何日伸びたかの変数に、$t$を足す
クエリ3は、
二分探索して、$ok$を出力して、リストには、ok以降の値を残す
具体的には、$L_{\text{mid}}$+何日伸びたかの変数を、足して判定する
あとは普通に二分探索

公式解説よりは、スマートにかけたと思います(公式解説C++だぞ)
なんか今回いつにもよらずスマートに、かけたと思います
前回、クソコード炸裂してたじゃないか

acコード 全文

Q = ii()
L = []
t = 0

for _ in [0] * Q:
    l = il()
    match l[0]:
        case 1:
            L.append(-t)

        case 2:
            t += l[1]

        case 3:
            ng, ok = -1, len(L)

            while abs(ok - ng) > 1:
                mid = (ng + ok) // 2

                if L[mid] + t >= l[1]:
                    ng = mid
                else:
                    ok = mid

            print(ok)
            L = L[ok:]

最後に

レートは32上がりました。現在レートは、572です
今日はAHC39を頑張りたいと思います。
用事があって、おそらく１時間半遅れの参加なんですけどね

長々と見ていただいて、ありがとうございます