見出し画像

ABC352参加後振り返り

ねこなべ

前書き

2024/3からAtCoderを始めました。
現職は、現場配属されて半年程度の新人SEです。
業務では、分かっていても実際に手を動かすのに時間がかかるという場面が多く、これを改善するために高パフォーマンスで3完できるように精進していきます。
AtCoderでは、Python3を使用しています。

ABC 352 振り返り

A問題 - Atcoder Line

問題
A - AtCoder Line

  • AtCoder 線には $${N}$$ 個の駅があり、それぞれ$${1,\cdots,N}$$の番号が付けられている。

  • 片道切符で$${X}$$駅から$${Y}$$駅まで移動する途中に$${Z}$$駅に停車することがあるか判定せよ。

答案①（AC）
素直に実装してAC（約 3 分）。

#input
N,X,Y,Z = map(int,input().split())

#process & output
m = min(X,Y)
M = max(X,Y)
if m <= Z <= M:
    print('Yes')
else:
    print('No')


B問題 - Typing

問題
B - Typing (atcoder.jp)

  • 高橋君は英小文字からなる文字列 $${S}$$ をキーボードで入力しようとしたが、$${T}$$を入力した。

  • $${T}$$は正しい文字列のなかにランダムにミスタイプした文字が混ざったものである。

  • $${T}$$の中で正しい文字がタイプされている文字は何文字目か、すべて列挙せよ。

主な制約

  • $${T}$$の文字数$${|T|}$$は、$${1\leq |T|\leq N}$$

答案①（TLE）
出力を"+"演算子で文字列の結合を繰り返して作る方法では、文字列の最後尾にアクセスするのに文字列の長さの計算量が必要となる。
従って、ループ内でこのような処理を実行すると、$${O(|T|^2)}$$を要するので、TLEしてしまう。

#input
S = input()
T = input()

#process
i=0
ans = ""
for j in range(len(T)):
    if S[i] == T[j]:
        ans = ans + str(j+1)+ " "
        i += 1

#output
print(ans[:-1])

答案②（AC）
以下のように修正してAC（約 8 分 + 1 TLE）。

  • append()メソッドにより、$${O(1)}$$でリストの末尾に解答を付加する。

  • リストに対してアンパック演算子" * "を適用することで、カンマ区切りのリスト内変数の列がprint()に渡されるので、リストの中身が空白区切りで出力される。

#input
S = input()
T = input()

#process
#iは「Sのi文字目まで正しく入力した状態」を保持するための変数で、0で初期化する。
i=0
ans = []

#Tを先頭から読んでいき、正しい文字がタイプされたときに、その位置の文字数をansに格納する。
for j in range(len(T)):
    #Tのj+1文字目において、Sのi文字目が正しく入力されたときの処理
    if S[i] == T[j]:
        ans.append(j+1)
        i += 1

#output
print(*ans)


C問題 - Standing On The Shoulders

問題
C - Standing On The Shoulders (atcoder.jp)

  • $${N}$$人の巨人が居て、それぞれの肩までの高さが$${A_i}$$で身長が$${B_i}$$である。

  • 与えられた$${N}$$人の巨人について、肩の上に別の巨人を立たせて積み上げるとき、一番上の巨人の頭の高さとして実現できる最大値を求めよ。

答案①（AC）
答えは$${ \max_{i=1}^n\{(B_i-A_i)\} + \sum_{i=1}^n A_i}$$なので、これを計算するアルゴリズムを実装すればよい。max()およびsum()はいずれも$${O(N)}$$で計算できるので$${O(N)}$$のアルゴリズムで実装できる。（約 9 分）

#input & process
N = int(input())
A = [0]*N
B = [0]*N
C = [0]*N
for i in range(N):
    A[i], B[i] = map(int,input().split())
    C[i] = B[i] - A[i]

#output
print(max(C)+sum(A))


D問題 - Permutation Subsequence

問題
D - Permutation Subsequence (atcoder.jp)

  • $${P=(P_1​,P_2​,\cdots,P_N​)}$$は$${1,\cdots,N}$$の順列。

  • 長さ $${𝐾}$$ の正整数列 $${(i_1​,\cdots,i_K​)}$$ であって、以下の条件を共に満たすものを良い添字列と呼ぶ。

    • $${1\leq 𝑖_1<𝑖_2<\cdots<𝑖_𝐾\leq N}$$

    • ある整数 $${a}$$ が存在して、$${\{𝑃_{𝑖_1}, \cdots, P_{i_K}\}=\{a,\cdots, a+K-1\}}$$が成り立つ。

  • 全ての良い添字列における $${i_k-i_1}$$​ の最小値を求めよ。

主な制約

  • $${1\leq K\leq N \leq 2×10^5}$$

答案①（TLE）

以下の実装では、$${O(N \log N +NK)}$$の計算量が必要なため、本問の制約下ではTLEとなってしまう。実装内容をざっくり説明すると、

  1. Pと添え字を入れ替えてPの値の昇順にソートしたリスト"sorted_id"を作る
    （下記の実装での計算量はsorted()による$${O(N\log N)}$$である。）

  2. sorted_idの部分集合"sorted_id[ j : j + K]"の最大値・最小値を計算し、答えを求める
    （下記の実装での計算量は、$${K\geq 2}$$の場合において、最大値・最小値を求めるためのプロセスで用いた二重ループによる$${O(NK)}$$である。）
    解法についてもう少し丁寧に説明する。
    2. で求めるsorted_idの部分集合"sorted_id[ j : j + K]"の最大値とは、
    $${\{𝑃_{𝑖_1}, \cdots, P_{i_K}\}=\{j,\cdots, j+K-1\}}$$の左辺の添え字の集合$${\{i_1\cdots, i_k\}}$$に対する最大値である。
    よって、各$${ｊ}$$に対して$${\{P_{i_1}, \cdots, P_{i_K}\}=\{j,\cdots, j+K-1\}}$$を満たすような添え字の集合$${\{i_n(j)\}_{n=1}^K}$$の最大値と最小値を求め、その最大値-最小値の$${j\in\{1,\cdots N - K\}}$$に渡る最小値が求めるべき答えであるので、これを計算するアルゴリズムを実装する。

2. の実装中に以下の点でハマりかけたことも備忘として記録しておく。

  • Pythonのリストについて = は参照渡しとなることに注意する。
    具体的なシナリオでは、既存の配列と同じ値で初期化した別の配列を使いたい時には、copy()メソッドで別の配列を作成する。

#input
N,K = map(int,input().split())
P =  list(map(int,input().split()))

#process&output
#1. Pと添え字を入れ替えてPの値の昇順にソートしたリスト"sorted_id"を作る
indexed_P = list(enumerate(P, start=1))
sorted_P = sorted(indexed_P, key=lambda x: x[1])
sorted_id = [element[0] for element in sorted_P]

#2. sorted_idの部分集合sorted_id[j:j+K]の最大値・最小値を計算して答えを求める。
max_dp = sorted_id
min_dp = sorted_id.copy()
ans_dp = [20000]*(N-K+1)

if K == 1:
    print(0)
else:
    for i in range(1,K):
        for j in range(N-i):
            max_dp[j] = max(max_dp[j], max_dp[j+1])
            min_dp[j] = min(min_dp[j], min_dp[j+1])
        #print(max_dp,min_dp)
        #print()
        if i == K-1:
            for j in range(N-K+1):
                ans_dp[j] = max_dp[j] - min_dp[j]

    ans = min(ans_dp)
    print(ans)

答案②（AC / ユーザ（toamさん）解説の模写）
以下で説明する模範解答は答案①と同じ方針による解答であるが、1. 2.の計算量を改善したものとなっている。以下、どのように1. 2.の計算量を改善できるか説明する。

まず、1. に関しては、以下のような単純な実装により、$${O(N)}$$の計算量で$${P_i-1}$$とインデックス$${i}$$を入れ替えた配列（＝インデックスの配列を$${P_i}$$の値の昇順でソートしたもの）を得ることができる。

Sorted_id = [0] * N
for i in range(N):
    Sorted_id[P[i]-1] = i

本問の状況では、$${(P_i)_{i=1}^n}$$が$${(1,\cdots,n)}$$の順列であることから上記の簡単な実装ができるが、より一般的な状況ではそのまま使うことはできないことに注意する。

次に、2. に関しては、スライド最小値とよばれるアルゴリズムにより、$${O(N)}$$で最大値および最小値を求めることができる。
■参考
スライド最大（最小）値・ヒストグラム内最大長方形問題を俯瞰する #競技プログラミング - Qiita

全体としては、以下のように実装することができる。

from collections import deque

#dequeを用いてスライド最小値を求める関数を実装する。
def Sliding_Window_Minimum(A, L):
    ans = []
    dq = deque()
    for i, a in enumerate(A):
        while dq and a <= dq[-1][1]:
            dq.pop()
        dq.append([i, a])
        if i >= L - 1:
            ans.append(dq[0][1])
        if dq and dq[0][0] <= i + 1 - L:
            dq.popleft()
    return ans

#input
N, K = map(int, input().split())
P = list(map(int, input().split()))

#process
#1. Pと添え字を入れ替えてPの値の昇順にソートしたリスト"sorted_id"を作る
sorted_id = [0] * N
for i in range(N):
    sorted_id[P[i]-1] = i


#2. sorted_idの部分集合sorted_id[j:j+K]の最大値・最小値を計算して答えを求める。
#スライド最小値を求める関数により、スライド最小値を求める
min_pos = Sliding_Window_Minimum(sorted_id, K)

#順序と最大最小の双対性を用いて、スライド最大値の-1倍を計算する。
max_pos = Sliding_Window_Minimum([-i for i in sorted_id], K)

#答えは最大でN-1なので、それより大きな値で初期化する。
ans = N

#全域での「スライド最大値 - スライド最小値」の最小値を求める。
#max_posはスライド最小値の-1倍を格納したリストなので、"- mx " - mnの最小値を計算する。
for mn, mx in zip(min_pos, max_pos):
    ans = min(ans, - mx - mn)

#output
print(ans)

後書き

D問題以降は難しいですが、挑戦していかないと茶色から先は目指せないなと思うので、今後はD問題にもチャレンジしていきたいと思います。それに合わせて振り返りに関しても、C, D問題を中心とした内容に変えていきたいと思います。
来週のABC353 は私用で参加できないため、次回noteの更新はABC354後となります。

この記事が気に入ったらサポートをしてみませんか？