ABC382 復習 (CD) python

はじめに

ABC382の復習メモです。

C - Kaiten Sushi

使用言語：Python (PyPy 3.10-v7.3.12)

説明

本番ではかなり汚い2分探索で解いてしまったので、公式解説の解き方2パターンで復習。

美味しさ全パターンについて事前に評価

公式解説の解き方です。
美味しさの取りうる値が高々2*10^5なので、全パターンについて評価が可能であることを利用します。

美味しさ１～６のすしがあるとき、それらをA～Eの誰が食べるかは以下のようになります。

美味しさ
1	--->	--->	--->	〇
2	--->	--->	--->	〇
3	--->	〇
4	〇
5	〇
6	〇
人	A	B	C	D	E
美食度	4	3	5	1	2

各人は、自分の美食度以上のすしを総取りして、それ未満のすしを下流に流します。
このことから、美味しさが大きい順に先頭の人から食べる食べないを調べていけば、逆戻りなく誰が食べるかを探索できることが分かります。

import sys

input = sys.stdin.readline


def main():
    N, M = input_to_int_list()
    A = input_to_int_list()
    B = input_to_int_list()

    record = {}
    eater = 0
    for taste in range(2 * (10**5), 0, -1):
        # 美味しさが美食度よりも低い場合は、次の人に移動
        while eater <= N - 1 and taste < A[eater]:
            eater += 1

        # 食べられる人がいない場合
        if eater == N:
            record[taste] = -1
            continue

        record[taste] = eater + 1

    for b in B:
        print(record[b])


def input_to_int_list():
    return list(map(int, input().split()))


if __name__ == "__main__":
    main()

すしを食べられる人を特定して、その中から2分探索

別解の考え方です

前の解き方で用いた食べ方の例を見ると、１つもすしを食べられない人がいますね（CとE）。
これらの人は自分よりも美食度の低い人が前にいるため、自分の食べられるすしが流れてこなくなっています。
ということは、そういった人は今回の問題を解くうえで考慮から外してよいことになります。
すると残るのは先頭から美食度が降順に並んだ人々となるので、二分探索が利用できそうです。
（本当にリストから消してしまうと何番の人かの管理が別途発生するので、前の人と美食度をそろえることで2分探索の探索候補から外れるようにする）

import sys
from bisect import bisect_right

input = sys.stdin.readline


def main():
    N, M = input_to_int_list()
    A = input_to_int_list()
    B = input_to_int_list()

    for i in range(1, N):
        # 前の人のほうが美食度が低いときは、考慮から外すために美食度を同じにする
        if A[i - 1] < A[i]:
            A[i] = A[i - 1]

    A_reversed = A[::-1]

    for b in B:
        i_reversed = bisect_right(A_reversed, b)
        ans = -1 if i_reversed == 0 else N - i_reversed + 1
        print(ans)


def input_to_int_list():
    return list(map(int, input().split()))


if __name__ == "__main__":
    main()

D - Keep Distance

使用言語：Python (PyPy 3.10-v7.3.12)

説明

公式解説と同じ考え方で解いてはいるのですが、
後ろから考えた方が私は理解が早かったのでメモ。

1 11 21
1 11 22
2 12 22
3 13 23

というような条件を満たす数列について、
上限Mがない場合に取りうる値として、
1番目の数字は1 ~ ?
2番目の数字は11 ~ ?
N番目の数字は10(N-1)+1 ~ ?
というように最小値は分かっているが最大値は分からない状態です。

ここに上限Mを加えて考えると、
最後をN番目とした数字が10(N-1)+1 ~ M
と定まります。

次にN-1番目を考えると、
N番目の数字がXのとき、
10(N-2)+1 ~ X-10
と定まります。

このような発想を再帰で記述すると以下のようになりました。

import sys

input = sys.stdin.readline


def main():
    N, M = input_to_int_list()

    ans = []

    def search(li: list, length: int) -> None:
        if length == N:
            ans.append(li)
            return

        minimum = 10 * (N - length - 1) + 1
        for j in range(minimum, li[0] - 10 + 1):
            search([j] + li, length + 1)

    last_minimum = 10 * (N - 1) + 1
    for i in range(last_minimum, M + 1):
        search([i], 1)

    print(len(ans))
    for i in sorted(ans):
        print(*i)


def input_to_int_list():
    return list(map(int, input().split()))


if __name__ == "__main__":
    main()

感想

Eがさっぱり分からん