今週もAtCoder Beginner Contest 314に参加をしました。

結果

A-Dの４完ノーペナでした。

イニDを読み込んだ効果が早速出た。
QlitreさんのAtCoder Beginner Contest 314での成績：1434位
パフォーマンス：1337相当
レーティング：1057→1089 (+32) :)
Highestを更新しました！#AtCoder #ABC314 https://t.co/4G3L3defuN

— Qlitre (@kuri_tter) August 12, 2023

先週はレートが変わらずだったのですが、Highestを更新できたのが良かったです。

早速ですがA-Dまで振り返っていきたいと思います。

A - 3.14

https://atcoder.jp/contests/abc314/tasks/abc314_a

円周率の小数点以下N桁までを出力するという問題です。

幸いなことにNの最大は100桁で、100桁まで問題文に書かれているので、コピります。

後は入力を受け取って、答えを出力します。

s = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
s = s.split('.')
n = int(input())
c = s[1]
c = c[:n]
print('3.' + c)

B - Roulette

https://atcoder.jp/contests/abc314/tasks/abc314_b

N人の人がいて、それぞれの人がルーレットに賭けた目が与えられます。

最後にルーレットの出目が与えられて、当たった人のうち、最も少ない数の目をかけていた人を出力する、という問題です。

B問題で頻出のパターンですが、Nの制約は100までと非常に小さいので、愚直な探索でも十分に間に合います。

具体的には一回目のループでXが出た中で、一番少ない目の数を特定します。

次にもう一回ループして一番少ない目を出した人を調べます。

n = int(input())
roulette = []
for i in range(n):
    c = int(input())
    al = list(map(int, input().split()))
    roulette.append(al)

x = int(input())
mi = 10 ** 18
data = []
for i in range(n):
    al = roulette[i]
    if x in al:
        mi = min(mi, len(al))
        data.append([i + 1, len(al)])

if not data:
    print(0)
    print()
    exit()
ans = []
for p, cnt in data:
    if cnt == mi:
        ans.append(p)

ans.sort()
print(len(ans))
print(*ans)

C - Rotate Colored Subsequence

https://atcoder.jp/contests/abc314/tasks/abc314_c

文字列と文字ごとの色（１～M）が与えられます。

それで文字の色ごとに１つ右シフトをして、できた文字を出力する、という問題です。

例えば色１が文字列の１，４，７番目にあったら、

1 => 4

4 => 7

7 => 1

というように文字を入れ替えるイメージです。

色々と解き方はありそうですが、色ごとにインデックスを記録して、順番に組み替えて答えを作っていく、というようにやりました。

割と重実装になってしまいました。

from collections import defaultdict

n, m = map(int, input().split())
s = list(input())
colors = list(map(int, input().split()))

# 色ごとにインデックスを記録
d = defaultdict(list)
for i in range(n):
    color = colors[i]
    d[color].append(i)
# 答えの配列
ans = [''] * n
# 各色を繰り返す
for i in range(1, m + 1):
    index_list = d[i]
    for j in range(len(index_list)):
        # 今の文字
        now_i = index_list[j]
        now_char = s[now_i]
        # 移動されるインデックス、プラス１して余りを取る
        idx = (j + 1) % len(index_list)
        next_i = index_list[idx]
        # 移動される場所に今の文字を埋める。
        ans[next_i] = now_char

print(''.join(ans))

コンテスト中はやらなかったのですが、こういうくるっと回す系のやつはdequeを使うと見通しが良くなることがあります。

from collections import defaultdict, deque

n, m = map(int, input().split())
s = list(input())
colors = list(map(int, input().split()))

# 色ごとにインデックスを記録
d = defaultdict(deque)
for i in range(n):
    color = colors[i]
    d[color].append(i)
# 答えの配列
ans = [''] * n
# 各色を繰り返す
for i in range(1, m + 1):
    que = d[i]
    # 文字を記録
    tmp = []
    for j in que:
        tmp.append(s[j])
    # 一回くるっとする
    que.rotate(-1)
    # 割り当てる
    for j in range(len(que)):
        new_i = que[j]
        ans[new_i] = tmp[j]

print(''.join(ans))

D - LOWER

https://atcoder.jp/contests/abc314/tasks/abc314_d

文字列クエリ処理系の問題です。

まず、英小文字、英大文字からなる文字列が与えられます。

各クエリごとに以下の処理をして、最終的な文字列を出力するという問題です。

クエリ１：

文字のX番目を文字Cに変更します。

クエリ２：

文字を全て小文字に変換します。

クエリ３：

文字を全て大文字に変換します。

この手のクエリ処理系の問題は、明らかに都度やると重い動作を最後だけできないか、ということを考えます。

この場合だと、クエリ２とクエリ３の動作が明らかに重そうなので、最後にやりたい。

どちらも全部小文字もしくは大文字に変換するので、最後に起こったのはどちらか？を管理すればいいことが分かります。

最後に起こったクエリに合わせて、全て大文字ないし小文字に変換します。

また考慮しなければいけないのはクエリ１の文字変換です。例えば全て大文字にするクエリの後に、小文字で置換するようなクエリが入っていた場合、その箇所は小文字でないといけません。

そのため、集合で置換をした箇所を管理しておきます。大文字小文字変換のクエリが来たら、それまでの置換に関わらずいずれかに寄せられます。

なので、その場合は集合を空にします。

def job():
    n = int(input())
    s = list(input())
    q = int(input())

    change_to_upper = False
    change_to_lower = False
    # 変換の影響を受けないインデックス
    ignore_change = set()
    for _ in range(q):
        t, x, c = input().split()
        t = int(t)
        x = int(x)
        if t == 1:
            s[x - 1] = c
            ignore_change.add(x - 1)
        # 全部小文字に変換する
        elif t == 2:
            change_to_lower = True
            change_to_upper = False
            ignore_change = set()
        # 全部大文字に変換する
        elif t == 3:
            change_to_upper = True
            change_to_lower = False
            ignore_change = set()

    ans = []
    if change_to_lower:
        for i in range(n):
            if i in ignore_change:
                ans.append(s[i])
            else:
                ans.append(s[i].lower())
    elif change_to_upper:
        for i in range(n):
            if i in ignore_change:
                ans.append(s[i])
            else:
                ans.append(s[i].upper())
    else:
        ans = s

    print(''.join(ans))


job()

終わりに

EとFはどちらも問題文を見たのですが、期待値系で手も足もでず、、でした。

Dまではコンスタントにそこまで詰まらずに解けたので、満足のいく結果となりました。

XのPostにも書いてますが、イニDを読んでる影響か、「問題を攻める」という感覚を持って取り組めたのが速解きにつながったと思います。

攻めの感覚を持ってると、多少強引なコードでも突っ込んで乗り切る、という強気な気持ちが生まれるような気がします。ではでは。