ABC416 備忘録

今回はPythonでABC416をABCを解くことができたので、備忘録を纏めました。

コンテスト概要

AtCoder Beginner Contest 416

開催日:2025年7月26日 21:00-22:40

---

A - Vacation Validation

方針

リストAからL以上R以下を取り出して、'o'しかない場合、Yesを返す問題。

N, L, R = map(int,input().split())
S = input()
s = S[L-1:R]

for i in range(len(s)):
    if s[i] != "o":
        print("No")
        exit()
print("Yes")

---

B - 1D Akari

方針

.と#からなる文字列Sが与えられ、
.だった場合、次に#があるまでのどこか１箇所をoとして、
リストTはo,.,#`でどう構成されるかを返す問題。

S = input()
T = ['.'] * len(S)

i = 0
while i < len(S):
    if S[i] == '#':
        T[i] = '#'
        i += 1
    else:
        T[i] = 'o'
        while i < len(S) and S[i] == '.':
            i += 1

print(''.join(T))

---

C - Concat (X-th)

方針

• 長さKの配列(A1,A2,...,AK)を全通り作成(各Aiは1〜N)
• 各数列に対応する文字列f(A1,A2,...,AK)=SA1+SA2+...+SAKを生成
  → 数列からの文字列はproduct()を使って前通りのインデックス列を作成
• それらを辞書順にソート
  → 辞書順ソートはsorted()で辞書順に並べ替える
• 小さい順からX番目の文字列を出力

from itertools import product

N, K, X = map(int, input().split())
S = [input() for _ in range(N)]

S.sort()

candidates = []

for indices in product(range(N), repeat=K):
    word = ''.join(S[i] for i in indices)
    candidates.append(word)

candidates.sort()

print(candidates[X - 1])

結果

ABC 3完
順位 4604th / 10840
パフォーマンス 788
レーティング 608 → 632 (+24)

感想

正直最近は日常業務が忙しく、平日の勉強が全く手付かずですが
隙間時間等を使って、次回こそD問題を解けるよう頑張ります。