1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@nakamin

【AtCoder】ABC452-455 ABCD問題まとめ（2026年4月実施分）

1
Last updated at Posted at 2026-04-26

茶色を目指しているなかみんです。
AtCoderのABCD問題をまとめています。
※ D問題について、緑色レベルだった場合パスしています

ABC452（2026年4月4日）

A問題

  • 入力例
3 3
  • 回答例
M, D = map(int, input().split())

check = [(1, 7), (3, 3), (5, 5), (7, 7), (9, 9)]

if (M, D) in check:
    print("Yes")
else: print("No")

B問題

  • 入力例
4 5
  • 回答例
H, W = map(int, input().split())

for h in range(1, H+1):
    if h == 1:
        print("#"*W)
    elif h == H:
        print("#"*W)
    else: 
        print("#"+ "."*(W-2) +"#")

C問題

  • 入力例
5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash
  • 回答例
import sys
input = sys.stdin.readline

N = int(input())
bones = [tuple(map(int, input().split())) for _ in range(N)]
# print(bones)

M = int(input())
string_list = list(input().strip() for _ in range(M))
# print(string_list)

possible_chars_list = [set() for _ in range(N)]
    
for s in string_list:
    L = len(s)
    # 各文字列 s が、どの肋骨の「材料」になれるかチェック
    for i in range(N):
        A, B = bones[i]
        if L == A:
            # 肋骨 i の条件に合うなら、その B 文字目を追加
            possible_chars_list[i].add(s[B-1])
# print(possible_chars_list)

# --- 判定 ---
results = []
for s in string_list:
    if len(s) != N:
        results.append("No")
        continue
    
    is_ok = True
    for i in range(N):
        # 脊椎 s の i 番目の文字が、肋骨 i の材料の中に存在するか
        char_at_spine = s[i] 
        if char_at_spine not in possible_chars_list[i]:
            is_ok = False
            break
    
    results.append("Yes" if is_ok else "No")

print('\n'.join(results))

ポイント

  • 脊椎の各文字が肋骨の特定の文字と一致しなければいけないという制約です。これはつまり、脊椎に書く文字$S_j$について、その$i$文字目を使って、条件を満たす肋骨$i$を作れるかを判定したいということです
  • $S_j$について、 「長さが $A_i$」かつ「その $B_i$ 文字目が $S_j$ の $i$ 文字目と一致する」ような文字列が、${S_1, \dots, S_M}$ の中にあるかを確認していきたいです
  • クエリごとに全体を探すと時間がかかりすぎてしまうおで、どんな文字が肋骨に使えるかをあらかじめ集合にまとめておきます
  • 各$S_j$についてチェックすることは以下のとおりです
    • まず、$S_j$ の長さが $N$ であるかを確認（違えば即 Noで次の$S_(j+1)$へ）
    • 次に、すべての $i = 1 \dots N$ について、「$S_j$ の $i$ 文字目」が possible_chars[i] に含まれているかを確認
    • すべて含まれていれば Yes、ひとつでも欠けていれば No

D問題

緑色レベルなので省略(^^;

ABC453（2026年4月12日）

A問題

  • 入力例
7
ooparts
  • 回答例
N = int(input())
S = input()

for n in range(N):
    if S[n]!="o":
        print(S[n:])
        exit()

B問題

  • 入力例
6 10
30 35 40 21 30 12 31
  • 回答例
T, X = map(int, input().split())
A_list = list(map(int, input().split()))

ans = A_list[0]
print(0, ans)

for t in range(1, T+1):
    # 現在の基準点 ans と、今見ている地点 A_list[t] の距離を比較
    if abs(A_list[t] - ans) >= X:
        ans = A_list[t]
        print(t, ans)

C問題

5
2 5 2 2 1
  • 回答例
N = int(input())
L = list(map(int, input().split()))
L = [x * 2 for x in L]

best = 0

for i in range(1 << N): # for i in range(2 ** N)と同じ意味
    pos = 1 # 全体を2倍しているため
    count = 0

    for j in range(N):
        # j番目の移動方向を決める
        # bit が 1 なら正、0 なら負
        if (i >> j) & 1:
            next_pos = pos + L[j]
        else:
            next_pos = pos - L[j]

        # 正から負、または負から正に変わったら 0 を通過
        if pos * next_pos < 0:
            count += 1

        pos = next_pos

    best = max(best, count)

print(best)

ポイント

  • 各移動で 0 をまたいだかどうかは順に判定しますが、
    「その回だけ正方向に行くか負方向に行くか」を個別に決めるのではなく、全体の移動パターンを 1 つ決めて、そのとき何回 0 をまたげるかを数えます

  • 今回は、選択の2択があることと、Nが小さいことから「Bit全探索」を用います

    • 具体的には、選ぶ/選ばない、正/負や右/左、状態オン/オフのような2択がある
    • N <= 20ぐらいならBit全探索を使える（計算量$O(N*2^N)$）

  • 今回は、正方向への移動を1、負方向への移動を0としています

  • bit全探索の動き（N=3のとき）

    for bit in range(8): # 行動パターン全体
  for i in range(3): # i回目の移動
      if (bit >> i) & 1:
          ...
    bit 2進数
    0 000
    1 001
    2 010
    3 011
    4 100
    5 101
    6 110
    7 111

    • ここでbit=5のとき2進数では101です

      移動番号 i bit 行動
      0 1 正方向へ移動
      1 0 負方向へ移動
      2 1 正方向へ移動

    ⇒ 正 → 負 → 正 という移動パターンを表しています。つまりbit列自体が行動のパターンを示していると言えます

    • bit の i 桁目が 1（正方向） か 0（負方向） かを調べるために、まず bit >> i で i 桁目を一番右までずらし、そのあと & 1 で一番右の桁だけを取り出します
    if (bit >> i) & 1: # i回目のbitを取り出す
  new_pos = pos + L[i]   # 正方向
else:
    new_pos = pos - L[i]   # 負方向

  • 移動前の位置 pos と移動後の位置 new_pos の符号が変わっていれば、途中で 0 を通過したと判定できます

D問題

緑色レベルなので省略(^^;

ABC454（2026年4月18日）

A問題

  • 入力例
3 5
  • 回答例
L, R = map(int, input().split())
print(R-L+1)

B問題

  • 入力例
3 4
1 2 4
  • 回答例
N, M = map(int, input().split())
F_list = list(input().split())
distinct_count = len(set(F_list))

# 質問1: N人全員が異なる服か（服の種類がN種類あるか）
print("Yes" if distinct_count == N else "No")

# 質問2: M種類の服すべてが使われているか
print("Yes" if distinct_count == M else "No")

C問題

  • 入力例
5 5
1 2
2 3
3 4
2 4
5 2
  • 回答例1(再帰DFS)
import sys
input = sys.stdin.readline
# 再帰DFS
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
graph = [ [] for _ in range(N+1) ]
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)

visited = [False] * (N + 1)
visited[1] = True
cnt = 1

def dfs(a):
    global cnt
    for next_item in graph[a]:
        if not visited[next_item]:
            visited[next_item] = True
            cnt += 1
            dfs(next_item)

dfs(1)
print(cnt)
  • 回答例2（非再帰DFS）
# 非再帰DFS
N, M = map(int, input().split())
graph = [ [] for _ in range(N+1) ]
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)

visited = [False] * (N + 1)
visited[1] = True
stack = [1]
cnt = 1

while stack:
    current = stack.pop() # 末尾
    for next_item in graph[current]:
        if not visited[next_item]:
            visited[next_item] = True
            cnt += 1
            stack.append(next_item)

print(cnt)
  • 回答例3（deque）
# dequeを使う
from collections import deque

N, M = map(int, input().split())
graph = [ [] for _ in range(N+1) ]
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)

visited = [False] * (N + 1)
visited[1] = True
queue = deque([1])  # stack の代わりに deque を使用
cnt = 1

while queue:
    current = queue.popleft()  # 先頭から
    for next_item in graph[current]:
        if not visited[next_item]:
            visited[next_item] = True
            cnt += 1
            queue.append(next_item)  # 追加は末尾
print(cnt)

ポイント

  • 3つのやり方を試してみましたが、deque(BFS)が最も速いです。

    探索手法 実行時間 (ms) メモリ (KiB) 結果
    再帰DFS 1065 ms 453064 KiB AC
    非再帰DFS (Stack) 785 ms 145460 KiB AC
    deque (BFS) 498 ms 144244 KiB AC

  • 普通のリストと deque では、先頭の要素を扱うスピードが全く違います

    • リスト (list): pop(0) や insert(0, x) をすると、残りの要素すべてを一つずつ横にずらす必要があるため、要素数を $N$ とすると $O(N)$ の時間がかかる
    • deque: 先頭への追加・削除も $O(1)$（定数時間）で終わる（イメージとしては鎖で繫がった状態）
    操作 メソッド 計算量
    末尾に追加 d.append(x) O(1)
    先頭に追加 d.appendleft(x) O(1)
    末尾を取り出す d.pop() O(1)
    先頭を取り出す d.popleft() O(1)

  • BFSでは先頭から取り出すため、popleft()を使い、DFSでは末尾から取り出すためpop()を使っています。それは、BFSが出発地点から近い順に探索が進み、DFSは深掘りするような動きをするからです。今回の問題とは関係ありませんが、最短の距離や手数を知りたいならpopleft()になり、全部行けるかを確認するだけならどちらでもよいことになります。

D問題

  • 入力例
6
(xx)x
x(xx)
(x)x
(xx)
)x()x(
)x()x(
x
(x)
(((((xx)))))x
x((((((((((xx))))))))))
((xx)xx)xx
(x((xx))x)(xx)
  • 回答例
import sys

def canonical_form(s):
    stack = []
    for char in s:
        stack.append(char)
        # 末尾4文字が ['(', 'x', 'x', ')'] になったかチェック
        if len(stack) >= 4:
            if stack[-4] == '(' and stack[-3] == 'x' and stack[-2] == 'x' and stack[-1] == ')':
                # 末尾4文字を削除して 'x', 'x' を入れ直す
                for _ in range(4):
                    stack.pop()
                stack.append('x')
                stack.append('x')
                
    return "".join(stack)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    t_cases = int(input_data[0])
    pointer = 1
    
    results = []
    for _ in range(t_cases):
        # リストから順番に読み込んでいく
        a = input_data[pointer]
        b = input_data[pointer + 1]
        pointer += 2
        
        # Aの標準形とBの標準形を比較
        if canonical_form(a) == canonical_form(b):
            results.append("Yes")
        else:
            results.append("No")
            
    # 結果をまとめて出力
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

ポイント

  • 文字列AをBにできるかと問われており、これは「$A$ と $B$ をそれぞれ極限まで簡略化したとき、同じ形（標準形）になるか？」と言い換えることができます
  • できる操作は以下2つで双方向な変換です
    • 操作1: (xx) $\rightarrow$ xx （カッコを外す）
    • 操作2: xx $\rightarrow$ (xx) （カッコを付ける）
      ABC428 C問題に、ぷよぷよ的な連鎖を考えましたが、この問題も同じような着想で考えられます
  • つまり、ぷよぷよで「これ以上消せる場所がない状態」にするのと、この問題で「これ以上カッコを外せない状態（標準形）」にするということが同じ作業になります
  • 具体的には以下のような流れです
    • 文字列を1文字ずつスタックに追加していく
    • スタックの 末尾4文字 が (xx) になった瞬間、それを xx に置換する（4文字削って2文字足す）※ 変換は一方通行に固定して可能な限り文字数を減らす方向にだけ動かす（今回は操作1のみ）
    • この処理を繰り返すことで、一度の走査で「内側からの連鎖」をすべて解消した標準形が完成
    • 最後に $A$ と $B$ の標準形が完全に一致すれば Yes

ABC455（2026年4月25日）

A問題

  • 入力例
4 5 5
  • 回答例
A, B, C = map(int, input().split())
if A != B and B == C:
    print("Yes")
else: print("No")

B問題

  • 入力例
3 2
.#
#.
##
  • 回答例
H, W = map(int, input().split())
grid = [list(input().strip()) for _ in range(H)]

cnt = 0

for h1 in range(H):
    for h2 in range(h1, H):
        for w1 in range(W):
            for w2 in range(w1, W):
                
                is_ok = True
                for i in range(h1, h2 + 1):
                    for j in range(w1, w2 + 1):
                        # 点対称の位置 (ni, nj) を計算
                        ni = h1 + h2 - i
                        nj = w1 + w2 - j
                        
                        # 色が違ったらその長方形はfalse
                        if grid[i][j] != grid[ni][nj]:
                            is_ok = False
                            break # 内側のループ
                    if not is_ok:
                        break
                
                if is_ok:
                    cnt += 1
print(cnt)

ポイント

  • 問題文にある形式的な条件の記載に沿って組み立てていきます
  • 最初の4重ループで、グリッド内にある考えられるすべての長方形の範囲（枠）を全て列挙します
  • その枠が決まったら、その中身が点対称であるかを判定していきます
  • 今回はH,Wが小さいので間に合いました

C問題

  • 入力例
6 2
7 2 7 2 2 9
  • 回答例
import sys
input = sys.stdin.readline
from collections import Counter

N, K = map(int, input().split())
A = list(map(int, input().split()))
A_count = Counter(A)
A_score = sorted(A_count.items(), key=lambda x: x[0] * x[1], reverse=True)

ans = sum(k * v for k, v in A_score[K:])
print(ans)

ポイント

  • 合計を最小化することが目的なので、削除する量を最大化したいと考え、 (数値 * 個数) を基にソートします
  • これでK番目以降の (数値 * 個数) を合計すれば答えになります

D問題

  • 入力例
5 4
1 3
4 5
1 4
4 2
  • 回答例
import sys
input = sys.stdin.readline

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

# 1~Nはカードの番号、N+1~2Nは山の土台の番号
up = [-1] * (2 * N + 1)
down = [-1] * (2 * N + 1)

# 初期状態
for i in range(1, N + 1):
    up[N + i] = i
    down[i] = N + i
# print(up, down)

for _ in range(Q):
    c, p = map(int, input().split())
    
    # Ci の下 (D) を特定する
    d = down[c]
    
    # Ci を Pi の上に乗せる（Pi の上は Ci、Ci の下は Pi）
    up[p] = c
    down[c] = p
    
    # Ci がいなくなった後の D の上を空にする
    up[d] = -1

# 各山の枚数を数える
ans = []
for i in range(1, N + 1):
    count = 0
    current = up[N + i] # 山 i の土台の「上」からスタート
    while current != -1:
        count += 1
        current = up[current]
    ans.append(count)

print(*ans)

ポイント

  • この問題は物理的なカードの動きを意識すると、リストを操作してカードを動かすように見えますがそれだと実行時間制限にひっかかってしまいます

  • そこで、この問題が行っていることは、ある列を途中で切り離し、別の列の末尾につなげていると解釈します

    • カード $C_i$ の 「下」 にあるカードは何があっても変わりません
    • カード $P_i$ の 「上」 に新しく $C_i$ が乗ります

  • つまり、各カードについて管理することは、自分の上と下にはどのカードがいるかどうかだけで、リストの中身を移動させる必要はありません

  • データの持ち方は以下とします

    • カード $1 \sim N$ に加えて、山の土台を表すダミーカード $N+1 \sim 2N$ を用意する
    • up[i]: カード $i$ のすぐ上
    • down[i]: カード $i$ のすぐ下
    • 初期状態では、山 $i$（土台 $N+i$）の上にカード $i$ が乗っているのでup[N+i] = i、down[i] = N+i

  • N=5のときの初期状態イメージ↓
    ABC455_D_1.png

  • カード $C$ とその上をごっそり $P$ の上に動かすとき、書き換えるのは以下3つです

    • 移動させる塊の土台を変える
      • もともと $C$ の下にあったカードを $D$ とすると$D$ の上は誰もいなくなる ⇒ up[D] = -1
    • 移動先の「上」を変える
      • $P$ の上に $C$ が来る ⇒ up[P] = C
      • $C$ の下は $P$ になる ⇒ down[C] = P

  • N=5のときに、カード1をカード2の上に移動させるケース
    ABC455_D_2.png

  • N=5のときに、カード2をカード3の上に移動させるケース
    ABC455_D_3.png

以上です。読んでいただきありがとうございました。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?