AtCoder ABC395 振り返り(緑コーダーがPythonでABCD問題)

AtCoder ABC395を復習する

AtCoder Beginner Contest 395 - AtCoder

ABC394ABCDまでの4問解答でした。

B問題で思ったような結果が出なくて、時間がかかりました。

また、D問題も苦労して3回TLEを出してしまいました。
終了時間30秒前に「なんとかなれ〜(ハチワレ)」の勢いでダメ元の提出を実行したところ、ACになりました。
最近、時間制限ありの詰将棋アプリをやっていて、時間ギリギリまで粘って解答できた経験が良かったのかもしれません。

A - Strictly Increasing?

数列が単調増加かどうかを調べる問題。数列を初めから調べていき、一箇所でも単調増加でない場合はNoを出力して終了するようにしています。

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    if A[i-1] < A[i]:
        # 単調増加なら続行
        continue
    else:
        # 単調増加でない場合はNoを出力して終了
        print("No")
        exit()
print("Yes")

B - Make Target

これは凡ミスで解答に20分くらいかかってしまった。

ミスの内容は、

• 問題文の座標系は1始まり、配列は0始まり
• 描画する四角形の右下の座標を j まで描画するのですが、ループはj+1 までしないとダメ...

というのに躓いたのでした。

N = int(input())

answers = []
for i in range(N):
    s = ["_"] * N
    answers.append(s)

for i in range(1, N + 1):
    j = N + 1 - i
    if i > j:
        continue
    # 色を決定
    color = "#" if i % 2 == 1 else "."

    # 0始まりに合わせる
    correct_i = i - 1
    correct_j = j - 1 
    
    if j > N:
        continue

    # iからjの区間を塗る
    for mi in range(correct_i, correct_j + 1):
        for mj in range (correct_i, correct_j + 1):
            answers[mi][mj] = color

for i in range(N):
    line = answers[i]
    print("".join(line))

C - Shortest Duplicate Subarray

数列中で、最後に数値 x が出現した位置を、dict( last_index_dict ) に保存しておきます。
数値 x が再度出現した場合、その位置〜最後に出現した位置までが、対象の連続部分列となります。
連続部分列のサイズは その位置 - 最後に出現した位置 + 1 なので、最小値を更新していきます。

from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
last_index_dict = defaultdict(int) # 最後に数値が出現した位置を保存する
answer = INF

for i in range(N):
    a = A[i]
    if a in last_index_dict:
        # 数値がすでに出現している場合
        distance = i - last_index_dict[a] + 1

        # 最小値を更新
        answer = min(distance, answer)
        last_index_dict[a] = i
    else:
        # 数値が初めて出現する場合
        last_index_dict[a] = i

print(answer if answer != INF else -1)

D - Pigeon Swap

問題なのが操作2で、巣箱a内の鳩と、巣箱b内の鳩を入れ替えるという操作です。この操作をその通りに実装してしまうと、結構な数の鳩の移動操作が必要になり、TLEを出してしまいます。

そこで、この操作は巣箱をまるごと入れ替えることで、代用するように考えました。これにより、操作2の負荷を減らすことができ、TLEを回避することができます。

巣箱ごとの入れ替えを行うため、以下の変数を用意しました。

• pointers は、巣箱の並び順を保存しておくリストです。pointers[1] は、1番目は 巣箱s かを保存しています。
  • pointersは、C言語のポインタのように、実際の巣箱への参照を保存するイメージです。
• key_to_index は、巣箱s が何番目の巣箱かを保存しておく辞書です。key_to_index[s] は、巣箱s が何番目の巣箱かを保存しています。

from collections import defaultdict

N, Q = map(int, input().split())

positions = [] # 鳩n が、どの巣箱Sにいるか
pointers = [] # x 番目の巣箱は、どの巣箱かを保存
key_to_index = defaultdict(int) # 巣箱s は、x番目の巣箱かを保存

# 初期化
for i in range(N + 1):
    key = i
    positions.append(key) # 鳩1は巣箱1、鳩2は巣箱2、鳩3は巣箱3...
    pointers.append(key)  # 並びの1番目は巣箱1、2番めは巣箱2...
    key_to_index[key] = i # 巣箱1は1番目、巣箱2は2番目...

for _ in range(Q):
    query = list(map(int, input().split()))

    if query[0] == 1:
        # 鳩a を巣箱b に移動
        a, b = query[1], query[2]

        nest_a = positions[a]
        nest_b = pointers[b]

        if nest_a == nest_b:
            continue

        positions[a] = nest_b

    if query[0] == 2:
        # 巣箱a と巣箱b を入れ替える
        a, b = query[1], query[2]
        nest_a_key = pointers[a]
        nest_b_key = pointers[b]

        pointers[a], pointers[b] = nest_b_key, nest_a_key
        key_to_index[nest_a_key], key_to_index[nest_b_key] = b, a

    if query[0] == 3:
        # 鳩a は巣箱sにいる → 巣箱s は何番目の巣箱か を出力
        a = query[1]
        nest_key = positions[a]
        index = key_to_index[nest_key]
        print(index)