AtCoder Beginner Contest 352 - あるぱかのブログ

家庭行事のため不参加

A - AtCoder Line
B - Typing
C - Standing On The Shoulders
D - Permutation Subsequence
結果

A - AtCoder Line

概要：2つの駅 $X$ と $Y$ の間に $Z$ が存在するか判定してね

$X \to Y$ もしくは $Y \to X$ の移動を行う中で駅 $Z$ があるかどうかを確認します。

駅の番号は整数昇順なので $X \leq Z \leq Y$ あるいは $Y \leq Z \leq X$ ならばYesを返します。

#ABC352 A - AtCoder Line
N, X, Y, Z = map(int, input().split())
if X <= Z <= Y or Y <= Z <= X:
    print('Yes')
else:
    print('No')

提出リンク：提出 #53157677 - AtCoder Beginner Contest 352

B - Typing

リンク：B - Typing (atcoder.jp)

概要：2つの文字列 $S,T$ で共通となる場所を教えてね

$S_i$ を握って $T_j,T_{j+1},$ …とみていきます。

$S_i = T_j$ なら $S$ を一文字進めます。

そして一致、不一致にかかわらず $T$ を一文字進めます。

$T$ の各文字を1回ずつ見るので計算量は $|T|$ になります。

本問題では必ず $S$ が $T$ の部分文字列となるので上記以外の判定は不要です。

N = len(S)
i = 0
j = 0
ans = []
while i < N:
    if S[i] == T[j]:
        #S[i] = T[j]ならSを一文字進める
        ans.append(j+1)
        i += 1
    #Tを1文字進める
    j += 1
print(*ans)

提出リンク：提出 #53157822 - AtCoder Beginner Contest 352

C - Standing On The Shoulders

リンク：C - Standing On The Shoulders (atcoder.jp)

概要：巨人を任意の順番で積んだときの高さ最大値を出力してね

各巨人の肩の高さと頭の高さが地面を0として与えられ、巨人の肩に次の巨人の足を置く形で積んでいきます。

積まれた側の巨人の頭は高さに寄与しないので、最終的な高さは $\sum$ 胴体+最上段の巨人の頭となります。

#ABC352 C - Standing On The Shoulders
N = int(input())
body = 0
head = 0
for _ in range(N):
    A, B = map(int, input().split())
    #全巨人の胴体の高さを合計する
    body += A
    #一番大きな頭のサイズをメモしておく
    head = max(head, B-A)
print(body + head)

提出リンク：提出 #53157864 - AtCoder Beginner Contest 352

D - Permutation Subsequence

リンク：D - Permutation Subsequence (atcoder.jp)

概要：”良い添字列”のサイズ（ $i_1 - i_K$ ）を出力してね

これが茶diffって嘘だろ・・・と思ったらpythonに不利なだけでC++等の言語では簡単に実装できるそうです。

やりたいことは以下の内容になります。

要素を先頭を削除したり末尾に追加したりする
集合の中の最大値と最小値を参照する

1番目だけならdequeあたりで高速に処理ができそうです。

問題は2番目で、pythonでは組み込み関数でちょうどいいものが用意されていないそうです。

（C++のstd::setなど平衡二分探索木が該当するらしいです）

無ければ作ればいいの精神で取り組まれている方々の記事はたくさんあるのでそちらを参照していただくとして、

今回はSortedSet（std::setに類似、2023年8月にAtCoderで使用可能になった）と優先度付きキューで解きます。

〇SortedSet

集合型setの中身が常にソートされているというものです。

標準では使えないので手元環境ではpipする必要があります。

そろそろ我々はsortedcontainersを使えるようになった方がいい #Python - Qiita

addで追加、discard()で任意のアイテムを探索して削除できます（計算量 $O(logN)$ ）

入力例1ではSortedSetの中身はこんな感じに推移します。

#ABC352 D - Permutation Subsequence
from sortedcontainers import SortedSet
N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = [0]*N
for i in range(N):
    pos[A[i]-1] = i
s = SortedSet()
for i in range(K):
    s.add(pos[i])    
ans = s[-1] - s[0]
for i in range(K, N):
    s.discard(pos[i-K])
    s.add(pos[i])
    ans = min(ans, s[-1] - s[0])
print(ans)

提出リンク：提出 #53171794 - AtCoder Beginner Contest 352

〇優先度付きキュー

最小の要素を高速に取り出すことができるデータ構造です。

標準ライブラリで用意されています。

最大値を参照したい場合は各要素に-1を掛けたものを用意すればOKです。

今回も最小値を参照する用の $mn$ と最大値を参照する用の $mx$ の2つのリストを使っていきます。

最小値以外の値の取り出しは面倒なので、削除済アイテムを識別する集合 $deleted$ を用意して、各配列から取り出したものが削除済アイテムなら捨てて新鮮な（？）最小値を取りに行くことにします。

上記の都合で $mx$ および $mn$ の要素数が $K$ を越えることになりますが題意は満足できるのでOKです。

（最小値と最大値以外に興味がないため。例えば全添字の合計を問われると困る）

入力例1では各配列の中身は以下のように推移します。

ちなみに $K=1$ のときは実行時エラーが出る（2ケース出た）ので処理を分けるか値の取り出しを工夫する必要があります。

#ABC352 D - Permutation Subsequence
from heapq import heapify, heappush, heappop
N, K = map(int, input().split())
A = list(map(int, input().split()))
#K=1のとき実行時エラーがでる（空の配列からのpopが発生する）ので場合分け
if K == 1:
    ans = 0
else:
    pos = [0]*N
    for i in range(N):
        pos[A[i]-1] = i
    mn = []
    mx = []
    heapify(mn)
    heapify(mx)
    #1巡目は手動で作っておく
    for i in range(K):
        heappush(mn, pos[i])
        heappush(mx, -pos[i])
    ans = -mx[0] - mn[0]
    deleted = set()
    for i in range(K, N):
        deleted.add(pos[i-K])
        #取り出した最小値が削除済にあれば捨てて新しい最小値を取りに行く
        while mn[0] in deleted:
            heappop(mn)
        while -mx[0] in deleted:
            heappop(mx)
        heappush(mn, pos[i])
        heappush(mx, -pos[i])
        ans = min(ans, -mx[0] - mn[0])
print(ans)

提出リンク：提出 #53173775 - AtCoder Beginner Contest 352

結果

2回連続でunratedというか参加すらできなかったの残念。

D問題はセグメント木も有効らしいけど勉強が追い付いていないので次のABCまでに見ておきます。