AtCoder ABC393 振り返り感想戦(緑コーダーがPythonでABCD問題)

ABC 393感想まとめ

AtCoder Beginner Contest 393 - AtCoder

ABCまで3問解答でした。Cまで20分を切っており(自分としては早いペース)、D問題は時間がたっぷりあったのだけどTLE解法しか思い浮かばず。

先週のABC392は用事のためお休みで、2週ぶりの参加となりました。14日間、問題を解いたりしていなかったのが良くなかったのかもしれません。

A - Poisonous Oyster

牡蠣にあたってしまう問題。この季節、切実な問題ですね。牡蠣は食べたいが、当たりたくはない...。

4パターンをifで場合分けしました。

S1, S2 = input().split()

if S1 == 'sick' and S2 == 'sick':
    print(1)
    exit()
if S1 == 'sick' and S2 == 'fine':
    print(2)
    exit()
if S1 == 'fine' and S2 == 'sick':
    print(3)
    exit()
if S1 == 'fine' and S2 == 'fine':
    print(4)
    exit()

B - A..B..C

文字列の中から、A..B..C が何個あるかを求める問題。
先頭から一文字ずつAを探していきます。もしAだったら文字間隔を[0, 1, 2...]と増やして[A..B..C]かどうかを探す、全探索です。

S = list(input())

count = 0
for i in range(len(S)):
    # 文字が 'A' なら、B/Cを探索
    if S[i] == 'A':
        # 文字の間隔を d とする
        for d in range(1, 100):
            if i + d * 2 < len(S):
                # 'B' と 'C' が等間隔にあるか判定
                if S[i + d] == 'B' and S[i + d * 2] == 'C':
                    count += 1
            else:
                break

print(count)

C - Make it Simple

グラフの問題。
問題を要約すると、重複している経路、自己参照している経路の数を数えればokです。

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

line_dict = defaultdict(set) # a -> b の経路を保持する

same_count = 0 # 自己参照している経路の数
exist_count = 0 # 重複している経路の数
for i in range(M):
    a, b = map(int, input().split())

    # a == b のときは自己参照なので削除対象
    if a == b:
        same_count += 1
        continue

    # もし、a -> b への経路がすでにあれば、削除対象
    if a > b:
        a, b = b, a
    if b in line_dict[a]:
        exist_count += 1

    line_dict[a].add(b)

print(same_count + exist_count)

D - Swap to Gather [解説AC]

これはコンテスト中には解けず、解説のYouTubeを見て復習しました。

• 1の位置を記録する数列を求める
• 上記数列から、i番目の1の位置から i を引くことで、
  • [j, j+1 .... j+k] に1を集める という問題を、[j] に k 個の 1を集める に言い換えることができる
• 中央値の位置に 1 を集めるときが、最小になる

など、いろいろな考察テクニックが紹介されていました。

これは、アルゴリズムをそのまま使うというよりは、考察が必要な問題でしたね...。類似の過去問をやっていると、楽になったかもしれません。

解説動画が大変参考になりました

N = int(input())
S = list(input())

# 1の位置を取得
one_positions = []
for i, s in enumerate(S):
    if s == "1":
        one_positions.append(i)

# 1の位置をから0, -1, -2, ... を引く
# これにより、移動後の各点の位置を一点に集めることができる
for i in range(len(one_positions)):
    one_positions[i] -= i

# 1の位置の中央値
med = len(one_positions) // 2

# 中央値に集めるための移動回数を計算
answer = 0
for i in range(len(one_positions)):
    answer += abs(one_positions[i] - one_positions[med])

print(answer)