AtCoder ABC380 復習(緑コーダーがPythonでA〜Cを解答 + Dを復習)

ABC380 感想まとめ

AtCoder Beginner Contest 380 - AtCoder

またしてもUnratedで参加しました。最近平日に今日プロの練習をできていないので、Ratingを高める自信がないのです...。

今回はA-Cまで3解答でした。もしRated参加だったら730パフォくらいなので、レーティング微減といったところです。

---

D問題は悩んで、なんとなく解けそうだったのですが、うまく実装できずに無念...。解説では2進数に直して...と書いてありますが、その発想はなかった。

E問題は「グループ分けするからUnionFindかな？」と思ったら、それでは難しいようでした。「このグループは、何色か？」の情報をうまく保存できないのです...。
公式解説では SortedSet を使っていて、なるほどと思いました。SortedSetの存在を忘れがちなので、今後の修正課題ですね。
↓
追記: と書いていたら、解説動画ではUnionFindを使用して解答していました。勉強になります。

A - 123233

Nを文字列で扱って、"1", "2", "3" の出現回数をカウントします。

N = input()

if N.count("1") == 1 and N.count("2") == 2 and N.count("3") == 3:
    print("Yes")
else:
    print("No")

B - Hurdle Parsing

S を先頭から1文字ずつ処理していきます。区切り文字 '|' が来たら、前の区切り文字からの文字数(count)を答えの配列に保存していきます。

S = input()

answers = [] # 答えの配列
count = 0 # 文字"-"の連続カウント 

for i in range(1,len(S)):
    if S[i] == '|':
        # 区切り文字なので、答えに追加
        answers.append(count)

        # 文字"-"カウントをリセット
        count = 0
    else:
        # 文字"-"をカウント
        count += 1

print(*answers)

C - Move Segment

文字列を2文字ずつ処理することで、"1"の塊の開始位置・終了位置がわかります。

• "01" であれば、新しい塊の始まり
• "10" であれば、塊の終わり

答えを出すうえで必要なのは、以下の3つの情報。

• K-1番目の塊の終了位置
• K番目の塊の開始位置
• K番目の塊の終了位置

この３つさえわかれば、文字列 S を操作して答えを出すことが出来ます。

N, K = map(int, input().split())
S = input()

before_k_end = 0 # K-1番目の塊の終了位置
k_start = 0 # K番目の塊の開始位置
k_end = 0  # K番目の塊の終了位置

one_count = 0 # "1" の塊が何個あるか

# 最初から塊が始まっている場合のチェック
if S[0] == '1':
    one_count += 1

for i in range(1, len(S)):
    # 塊ではない
    if S[i-1] == "0" and S[i] == '0':
        continue

    # 塊の始まり
    if S[i-1] == "0" and S[i] == '1':
        # 塊の数を+1
        one_count += 1
        if one_count == K:
            k_start = i
        continue

    # 塊が続く
    if S[i-1] == "1" and S[i] == '1':
        continue

    # 塊の終わり
    if (S[i-1] == "1" and S[i] == '0'):
        # 終了位置を保存
        if one_count == K - 1:
            before_k_end = i
        if one_count == K:
            k_end = i

# 最後まで塊のまま終わった場合、終了処理をする
if S[-1] == "1":
    if one_count == K:
        k_end = len(S)

# 答えは [Sの1文字目〜K-1番目の塊の最後] + [K番目の塊] + [K-1番目の塊〜K番目の塊の間] + [K番目の塊〜Sの最後]
answer = S[:before_k_end] + S[k_start:k_end] + S[before_k_end:k_start] + S[k_end:]
print(answer)

D - Strange Mirroring (解説AC)

時間内には解けず、解説を見て解きました。公式のYouTube解説 がわかりやすく、これを見て理解出来ました。

解説の概要です

• 操作するごとに文字列長は2倍で増えていく
• 増えた分の右半分は、以前の文字列Sを、大文字・小文字変換した文字列T になる
• 反転操作をする場合を1、しない場合を0とすると、以下のような木構造が作れる
• よく見ると、その文字列の位置を2進数表記したときに以下のようになっています
  • 1の数が偶数であれば、S
  • 1の数が奇数であれば、T

(汚い図ですいません...)

というわけで、

• 与えられた文字の位置 k が、文字列 STTS...のどの位置(ブロック)にあるか
• 位置 k は、上のブロック内の何番目か

を求めれば、答えがわかるというわけでした。

S = input()
Q = int(input())
K = list(map(int, input().split()))

T = S.swapcase()

answers = []
for k in K:
    block = (k - 1) // len(S) # Kは何番目のブロックか
    index = (k - 1) % len(S)  # Kはブロック内の何番目か

    # blockを2進数に直して
    bin_block = format(block, 'b')

    # 1の数が奇数ならS, 偶数ならT
    count = bin_block.count('1')
    if count % 2 == 0:
        answers.append(S[index])
    else:
        answers.append(T[index])

print(*answers)

この規則性はわからなかった...。類似問題を知っていないと、思いつきにくいですね。
逆に初見で解けた人はすごい