DEV Community: iwamutsu256

AtCoder Beginner Contest 456 参加記録と解答例 (A D問題)

iwamutsu256 — Sat, 02 May 2026 14:25:24 +0000

本記事は、AtCoder Beginner Contest 456 (Promotion of AtCoder Career Design DAY) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。

A - Dice

配点 : 100 点

問題文

6 つの面を持つサイコロが 3 個あります。どのサイコロも、面には 1, 2, 3, 4, 5, 6 が書かれています。
これらのサイコロを同時に振ったとき、出た目の合計が X になることはありますか？

制約

X は 1 以上 20 以下の整数

自分の解答の方針

サイコロ3個の合計値の最小は $1 \times 3 = 3$、最大は $6 \times 3 = 18$ なので、足して 3〜18 だったら OK。

提出したコード

X = int(input())
if 3<=X<=18:
    print("Yes")
else:
    print("No")

B - 456

配点 : 200 点

問題文

6 つの面を持つサイコロが 3 個あります。 $i$ 個目のサイコロの $j$ 個目の面には $A_{i,j}$ が書かれています。どのサイコロも、各面が出る確率は $\frac{1}{6}$ です。
これらのサイコロを同時に振ったとき、4, 5, 6 の書かれた目が 1 つずつ出る確率を求めてください。

制約

$A_{i,j}$ は 1 以上 6 以下の整数

自分の解答の方針

ぱっと見で難しそうに見えて焦った。すべてのパターン（4,5,6の順列）をごり押しで書いた。後で気づいたが、forで全パターン繰り返せばよかった。

提出したコード

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A4 = A.count(4)
A5 = A.count(5)
A6 = A.count(6)
B4 = B.count(4)
B5 = B.count(5)
B6 = B.count(6)
C4 = C.count(4)
C5 = C.count(5)
C6 = C.count(6)
ans1 = A4*B5*C6/6**3
ans2 = A4*B6*C5/6**3
ans3 = A5*B4*C6/6**3
ans4 = A6*B4*C5/6**3
ans5 = A5*B6*C4/6**3
ans6 = A6*B5*C4/6**3
ans = ans1+ans2+ans3+ans4+ans5+ans6
print(ans)

C - Not Adjacent

配点 : 300 点

問題文

a, b, c からなる文字列 S が与えられます。
S の空でない部分文字列であって、同じ文字が隣り合わないものの個数を 998244353 で割った余りを求めてください。
ただし、2 つの部分文字列が文字列として一致しても、取り出す位置が異なるならば区別するものとします。

制約

S は a, b, c からなる長さ 1 以上 3×$10^5$ 以下の文字列

自分の解答の方針

連続して同じ文字が続いていなければ、その個数は $|S|(|S|+1)/2$ となる。
連続に続いている場合、そこを境目として二つの連続してない文字列に分割することで同じように考えられる。
文字列を前から順に見ていくので計算量は $O(|S|)$ で、余裕があるのでとりあえず毎回答えを 998244353 で割っておく。

提出したコード

S = list(input())
ans = 0
len_count = 0
prev_char = "x"
for i in range(len(S)):
    if S[i] == prev_char:
        len_count = 0
    len_count += 1
    ans += len_count
    ans = ans % 998244353
    prev_char = S[i]
print(ans)

D - Not Adjacent 2

配点 : 400 点

問題文

a, b, c からなる文字列 S が与えられます。
S の空でない部分列であって、同じ文字が隣り合わないものの個数を 998244353 で割った余りを求めてください。
ただし、2 つの部分列が文字列として一致しても、取り出す位置が異なるならば区別するものとします。

制約

S は a, b, c からなる長さ 1 以上 3×$10^5$ 以下の文字列

自分の解答の方針

文字が 3 種類しかないので、最後の文字が a, b, c となる部分列の数を保持しておき、文字列を順番に見ながら更新していく。DP のような形で行けそう。C問題同様、毎回 998244353 で割っておけばよさそう。

提出したコード

S = list(input())
A = 0
B = 0
C = 0
for i in range(len(S)):
    if S[i] == "a":
        A += 1+B+C
        A = A % 998244353
    if S[i] == "b":
        B += 1+A+C
        B = B % 998244353
    if S[i] == "c":
        C += 1+A+B
        C = C % 998244353
ans = (A+B+C) % 998244353
print(ans)

AtCoder Beginner Contest 455 参加記録と解答例 (A~D問題)

iwamutsu256 — Sat, 25 Apr 2026 14:01:57 +0000

本記事は、AtCoder Beginner Contest 455 (ABC455) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。

A - 455

配点 : 100 点

問題文

整数 A,B,C が与えられます。 $A \neq B$ かつ $B=C$ であるならば Yes を、そうでないならば No を出力してください。

制約

1≤A,B,C≤9
入力される値はすべて整数

自分の解答の方針

そのまま $A \neq B$ かつ $B == C$ を判定。

提出したコード

A, B, C = map(int, input().split())
if A != B and B == C:
    print("Yes")
else:
    print("No")

B - Spiral Galaxy

配点 : 200 点

問題文

H 行 W 列のグリッドがあります。各マスは白 (.) または黒 (#) で塗られています。
グリッドの長方形領域であって、点対称に塗られているものの個数を求めてください。

制約

1≤H,W≤10
H,W は整数
$S_i$ は ., # からなる長さ W の文字列

自分の解答の方針

H, W が小さいので、すべての長方形領域 $(h_1, w_1, h_2, w_2)$ について、領域内のすべてのマスを走査して点対称か判定する。

提出したコード

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
count = 0
for h1 in range(H):
    for h2 in range(h1,H):
        for w1 in range(W):
            for w2 in range(w1,W):
                flag = True
                for i in range(h1,h2+1):
                    if not flag:
                        break
                    for j in range(w1,w2+1):
                        if S[i][j] != S[h1+h2-i][w1+w2-j]:
                            flag = False
                if flag:
                    count += 1
print(count)

C - Vanish

配点 : 300 点

問題文

整数列 $A=(A_1, A_2, \dots, A_N)$ が与えられます。
「整数 $x$ を選び、$A_i = x$ なる各 $i$ について $A_i$ の値を 0 に置き換える」という操作をちょうど K 回行った後の A の各要素の和として考えられる最小値を求めてください。

制約

1≤K≤N≤3×$10^5$
1≤$A_i$≤$10^9$
入力される値はすべて整数

自分の解答の方針

同じ数字の出現回数をカウントし、「数値 × 出現回数」のリストを作成してソートする。
大きいほうからK個取り除いたものの和が答えになる

提出したコード

N,K = map(int,input().split())
A = list(map(int,input().split()))
dict = dict()
for i in A:
    if i in dict:
        dict[i] += 1
    else:
        dict[i] = 1
list = []
for key, value in dict.items():
    list.append(key*value)
list.sort()
# print(list)
if len(list) <= K:
    print(0)
else:
    print(sum(list[:len(list)-K]))

D - Card Pile Query

配点 : 400 点

問題文

N 枚のカードと N 個の山があります。はじめ山 $i$ にはカード $i$ のみが積まれています。
「カード $C_i$ 以上の束を、カード $P_i$ （山の一番上）の上に移動させる」というクエリに Q 回答えた後、各山のカードの枚数を出力してください。

制約

1≤N,Q≤3×$10^5$
操作の直前、カード $P_i$ は必ず山の一番上にある。

自分の解答の方針

指定されたカードがどの山に属するか、カードの山の一番下のカード、あるカードの下にいるカード、あるカードの上にいるカードをそれぞれ保持しておき、各クエリでそれらを更新する。
最終的にそれぞれの山の一番下からカードをたどっていきカウントすることで答えを得る。

提出したコード

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

# そのカードが現在どの山に所属しているか
current_place = dict()
for i in range(1,N+1):
    current_place[i] = i

# カードの山の一番下のカード
mountain_roots = [i for i in range(N+1)]

# 自分の上にいるカード
on_card = [None for _ in range(N+1)]

# 自分の下にいるカード
under_card = [None for _ in range(N+1)]

for _ in range(Q):
    C,P = map(int,input().split())
    if mountain_roots[current_place[C]] == C:
        mountain_roots[current_place[C]] = None
    else:
        on_card[under_card[C]] = None
    on_card[P] = C
    under_card[C] = P

ans = []
for i in range(1,N+1):
    if mountain_roots[i] == None:
        ans.append("0")
    else:
        count = 1
        current_card = mountain_roots[i]
        while on_card[current_card]:
            current_card = on_card[current_card]
            count += 1
        ans.append(str(count))
print(" ".join(ans))

AtCoder Beginer Contest 454 参加記録と解答例（A~D問題）

iwamutsu256 — Sat, 18 Apr 2026 14:26:50 +0000

本記事は、AtCoder Beginner Contest 454 (ABC454) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。

A - Closed interval

配点 : 100 点

問題文

整数 L,R が与えられます。
L 以上 R 以下の整数がいくつあるか求めてください。

制約

1≤L≤R≤100
入力される値は全て整数

自分の解答の方針

そのまま $R-L+1$ で計算します。

提出したコード

L, R = map(int, input().split())
print(R - L + 1)

B - Mapping

配点 : 200 点

問題文

1 から N の番号が付いた N 人の人がいます。
また、1 から M の番号が付いた M 種類の服があります。人 i は服 $F_i$ を着ています。
次の 2 個の質問に Yes か No で答えてください。

質問 1: N 人全員が異なる種類の服を着ていますか？
質問 2: M 種類の服全てについて、その服を着ている人が少なくとも 1 人ずついますか？

制約

1≤N≤100
1≤M≤100
1≤$F_i$≤M
入力される値は全て整数

自分の解答の方針

Fについて、重複を除いた数を数えることで質問1と2のどちらも答えられる。

提出したコード

N, M = map(int, input().split())
F = list(map(int, input().split()))
kind = len(list(set(F)))

if kind == N:
    print("Yes")
else:
    print("No")

if kind == M:
    print("Yes")
else:
    print("No")

C - Straw Millionaire

配点 : 300 点

問題文

アイテム 1 からアイテム N までの N 種類のアイテムがあります。はじめ、高橋君はアイテム 1 のみ持っています。
高橋君には M 人の友達がいます。i 人目 (1≤i≤M) の友達にアイテム $A_i$ を渡すと、アイテム $B_i$ をもらうことができます。
高橋君が手に入れることのできるアイテムはアイテム 1 を含めて何種類あるか求めてください。

制約

2≤N≤3×$10^5$
1≤M≤3×$10^5$
1≤$A_i, B_i$≤N
$A_i \neq B_i$
入力される値は全て整数

自分の解答の方針

アイテムの受け渡しが木のように枝分かれしていてたどっていくことができるので、幅優先探索（BFS）をする。

提出したコード

from collections import deque, defaultdict

N, M = map(int, input().split())
exchange = defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    exchange[A].append(B)

getItemCount = 1
geted = [False for _ in range(N+1)]
geted[1] = True
queue = deque([1])

while queue:
    item = queue.popleft()
    for can_exchange in exchange[item]:
        if not geted[can_exchange]:
            queue.append(can_exchange)
            geted[can_exchange] = True
            getItemCount += 1

print(getItemCount)

D - (xx)

配点 : 425 点

問題文

(, x, ) からなる文字列 A が与えられます。
あなたは A に対して次の 2 種類の操作を自由な順番で自由な回数行うことが出来ます。

A の部分文字列 (xx) を 1 カ所選び、xx に置換する。
A の部分文字列 xx を 1 カ所選び、(xx) に置換する。

(, x, ) からなる文字列 B が与えられます。
A を B と一致させることが出来るか判定してください。
T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。

制約

1≤T≤3×$10^5$
A, B は (, x, ) からなる長さ 1 以上 2×$10^6$ 以下の文字列
全てのテストケースに対する |A|+|B| の総和は 2×$10^6$ 以下

1回目の解答の方針

AとBの文字列の両方から"(xx)"とその両端についている"()"を取り除いていき、最終的に同じになればよさそう

1回目の提出

T = int(input())
for _ in range(T):
    A = list(input())
    B = list(input())
    stackA = []
    flag = False
    for i in A:
        stackA.append(i)
        if not flag and len(stackA) >= 2 and stackA[-2] == stackA[-1] == "x":
            flag = True
            stackA.pop()
            stackA.pop()
        elif flag and len(stackA) >= 2 and stackA[-2] == "(" and stackA[-1] == ")":
            stackA.pop()
            stackA.pop()
        elif flag and len(stackA) >= 2 and stackA[-2] == stackA[-1] == "x":
            stackA.pop()
            stackA.pop()
        elif flag:
            flag = False
    stackB = []
    flag = False
    for i in B:
        stackB.append(i)
        if not flag and len(stackB) >= 2 and stackB[-2] == stackB[-1] == "x":
            flag = True
            stackB.pop()
            stackB.pop()
        elif flag and len(stackB) >= 2 and stackB[-2] == "(" and stackB[-1] == ")":
            stackB.pop()
            stackB.pop()
        elif flag and len(stackB) >= 2 and stackB[-1] == stackB[-2] == "x":
            stackB.pop()
            stackB.pop()
        elif flag:
            flag = False
    if stackA == stackB:
        print("Yes")
    else:
        print("No")

結果：WA

2回目の解答の方針

"x"の数が異なることがあるかもしれないので、"x"の数をカウントしてみる

2回目の提出

T = int(input())
for _ in range(T):
    A = list(input())
    B = list(input())
    stackA = []
    xCountA = 0
    flag = False
    for i in A:
        stackA.append(i)
        if not flag and len(stackA) >= 2 and stackA[-2] == stackA[-1] == "x":
            flag = True
            stackA.pop()
            stackA.pop()
            xCountA += 2
        elif flag and len(stackA) >= 2 and stackA[-2] == "(" and stackA[-1] == ")":
            stackA.pop()
            stackA.pop()
        elif flag and len(stackA) >= 2 and stackA[-2] == stackA[-1] == "x":
            stackA.pop()
            stackA.pop()
            xCountA += 2
        elif flag:
            flag = False
    stackB = []
    flag = False
    xCountB = 0
    for i in B:
        stackB.append(i)
        if not flag and len(stackB) >= 2 and stackB[-2] == stackB[-1] == "x":
            flag = True
            stackB.pop()
            stackB.pop()
            xCountB += 2
        elif flag and len(stackB) >= 2 and stackB[-2] == "(" and stackB[-1] == ")":
            stackB.pop()
            stackB.pop()
        elif flag and len(stackB) >= 2 and stackB[-1] == stackB[-2] == "x":
            stackB.pop()
            stackB.pop()
            xCountB += 2
        elif flag:
            flag = False
    if stackA == stackB and xCountA == xCountB:
        print("Yes")
    else:
        print("No")

結果：WA

3回目の解答の方針

"(x(xx)x)"のようなとき、"(x(xx)x)"->"(xx)"->""とはならないことに気が付いた。なので、"(xx)"が離れているときは消さないようにし、連続しているときだけその両端の"()"も含めて消すようにしてみた。

3回目の提出

T = int(input())
for _ in range(T):
    A = list(input())
    B = list(input())
    stackA = []
    flag = False
    count = 0
    for i in A:
        stackA.append(i)
        count += 1
        if len(stackA) >= 4 and count >= 4 and stackA[-4:] == ["(","x","x",")"]:
            flag = True
            stackA.pop()
            stackA.pop()
            stackA.pop()
            stackA.pop()
        elif flag and len(stackA) >= 2 and stackA[-2] == "(" and stackA[-1] == ")":
            stackA.pop()
            stackA.pop()
        elif flag:
            flag = False
            count = 1
            last = stackA.pop()
            stackA.append("x")
            stackA.append("x")
            stackA.append(last)
    if flag:
        stackA.append("x")
        stackA.append("x")
    stackB = []
    flag = False
    for i in B:
        stackB.append(i)
        count += 1
        if len(stackB) >= 4 and count >= 4 and stackB[-4:] == ["(","x","x",")"]:
            flag = True
            stackB.pop()
            stackB.pop()
            stackB.pop()
            stackB.pop()
        elif flag and len(stackB) >= 2 and stackB[-2] == "(" and stackB[-1] == ")":
            stackB.pop()
            stackB.pop()
        elif flag:
            flag = False
            count = 1
            last = stackB.pop()
            stackB.append("x")
            stackB.append("x")
            stackB.append(last)
    if flag:
        stackB.append("x")
        stackB.append("x")
    # print("".join(stackA),"".join(stackB))
    if stackA == stackB:
        print("Yes")
    else:
        print("No")

結果：WA

4回目の解答の方針

そもそも"x"を消す必要がなく、"(xx)"が現れたら"xx"に置き換えていくだけでいいことに気が付いた。

4回目の提出

T = int(input())
for _ in range(T):
    A = list(input())
    B = list(input())
    stackA = []
    for i in A:
        stackA.append(i)
        if len(stackA) >= 4 and stackA[-4:] == ["(","x","x",")"]:
            stackA = stackA[:-4] + ["x","x"]
    stackB = []
    for i in B:
        stackB.append(i)
        if len(stackB) >= 4 and stackB[-4:] == ["(","x","x",")"]:
            stackB = stackB[:-4] + ["x","x"]
    # print("".join(stackA),"".join(stackB))
    if stackA == stackB:
        print("Yes")
    else:
        print("No")

結果：TLE

5回目の解答の方針

配列の上書き部分が原因で遅くなっていそう。 popとappendは計算量がO(1)なはずなので、それに入れ替える。

5回目の提出

T = int(input())
for _ in range(T):
    A = list(input())
    B = list(input())
    stackA = []
    for i in A:
        stackA.append(i)
        if len(stackA) >= 4 and stackA[-4:] == ["(","x","x",")"]:
            stackA.pop()
            stackA.pop()
            stackA.pop()
            stackA.pop()
            stackA.append("x")
            stackA.append("x")
    stackB = []
    for i in B:
        stackB.append(i)
        if len(stackB) >= 4 and stackB[-4:] == ["(","x","x",")"]:
            stackB.pop()
            stackB.pop()
            stackB.pop()
            stackB.pop()
            stackB.append("x")
            stackB.append("x")
    # print("".join(stackA),"".join(stackB))
    if stackA == stackB:
        print("Yes")
    else:
        print("No")

結果：AC

【初心者向け】Git & GitHub 超入門：基本操作からブランチ管理、リポジトリ公開まで

iwamutsu256 — Tue, 14 Apr 2026 11:26:45 +0000

プログラム学習を始めた方が次にマスターすべき「Git」と「GitHub」。ファイルの変更履歴を管理し、過去の状態に戻したり、安全に新機能を開発したりするための必須スキルを、ステップバイステップで解説します。

結論：Git 操作の基本サイクル

Git の操作は、基本的には以下の 「3つのエリア」 を意識したサイクルで動きます。

git add: 変更を「ステージングエリア（準備場所）」へ送る
git commit: 準備した変更を「ローカルリポジトリ（記録場所）」へ保存する
git push: 保存した履歴を「GitHub（共有場所）」へアップロードする

1. Git の基本概念

Git は「分散型バージョン管理システム」です。自分の PC 内で完結して履歴を残せるため、ネットワークがない環境でも作業でき、他の人に影響を与えずに試行錯誤が可能です。

Git の 3 つのエリア

作業ディレクトリ: 実際にファイルを編集する場所
ステージングエリア: コミット（保存）するファイルを一時的にリストアップする場所
ローカルリポジトリ: 変更履歴が正式に記録される場所

2. 実践：ローカルで Git を操作する

まずはリポジトリを作成し、最初のコミットを行ってみましょう。

リポジトリの初期化と初コミット

# フォルダ作成と移動
mkdir git-practice
cd git-practice

# Gitリポジトリを初期化
git init

# ステータスを確認（こまめに実行するのがコツです）
git status

# ファイルを作成・編集した後、ステージングへ追加
git add .

# メッセージを添えてコミット（保存）
git commit -m "first commit"

# 履歴を確認
git log

ブランチ操作：安全に作業を切り替える

「メインのコードはそのままに、新しい機能を試したい」ときに使うのが ブランチ（枝） です。作業を分岐させることで、本番環境のコードを安全に保てます。

# 1. 新しいブランチを作成して、そのブランチに切り替える
git switch -c new-branch
# ※古いGitバージョンの場合は: git checkout -b new-branch

# 現在のブランチを確認（星印がついているのが現在の場所です）
git branch

作業が終わったら、メインの枝に合流させます。

# (ファイルを編集し、addとcommitを済ませた後...)

# 2. メインブランチ（main）に戻る
git switch main

# 3. new-branch の変更を main に統合（マージ）する
git merge new-branch --no-ff

ポイント: --no-ff をつけることで、枝分かれして統合したという「マージコミット」が記録され、後から履歴を追いやすくなります。

3. GitHub への公開

作成したローカルの履歴を、GitHub 上のリモートリポジトリへアップロードします。

手順

SSH設定: GitHub公式を参考に、PCとGitHub間の安全な通信設定を済ませます。
リポジトリ作成: GitHub上で「New」ボタンからリポジトリ（git-practice）を作成します。
コマンド実行:

# リモートリポジトリの場所を登録
git remote add origin https://github.com/[ユーザー名]/git-practice.git

# メインブランチの名前を main に確定
git branch -M main

# GitHub へ送信
git push -u origin main

4. AI 時代の Git 操作への向き合い方

現在、AI がコマンドを生成してくれますが、Git には履歴を破壊的に書き換えるような強力なコマンドもあります。仕組みを理解せずに実行すると、取り返しのつかないミスに繋がることもあります。「今、自分がどのエリアを操作しているのか」を意識して使うことが、プロへの第一歩です。

まとめ

Git は手元で「いつ、誰が、何を変えたか」を記録するツール。
GitHub はその記録を世界（やチーム）と共有する場所。
ブランチ を使いこなすことで、本番コードを壊さず安全に開発できる。

参照公式ドキュメント

【ABC453 D】Go Straight 復習メモ：BFSの状態管理とTLE対策

iwamutsu256 — Mon, 13 Apr 2026 09:58:32 +0000

まずは結論から。
この問題は単純なBFSではなく、「直前の移動方向」も状態に含めて管理する必要があった。
また、Pythonで実装する場合、訪問管理に set() を使うとTLEになるため、3次元配列による定数倍の高速化が必須だった。

コンテスト中に考えたこと

幅優先探索（BFS）または深さ優先探索（DFS）で解けそう。
しかし、前回動いた方向に依存するマス（o や x）がある。
そのため、単純に「一度通ったマスを候補から消す」というやり方はできなさそう。
どうやってそれを解決するか分からず、時間切れ……。
経路復元のやり方についても分からなかった。

解説をみて：状態の持ち方と経路復元

解説を確認して、以下の2点に気づいた。

状態の再定義
位置 (y, x) に加えて、「前回進んだ方向」を保持することで、マスの進入制限をクリアしつつ同じ状態を回避できることが分かった。
経路復元のアプローチ
別で配列（prevs）を作成し、木構造のようにループ毎に「どこから来たか」と「その向き」が分かればできるはず。
実装としては、queueの探索ごとに配列に現在のノード（親のインデックスと移動方向を含む）を追加してインデックスを増やしていく。そして、キューに追加するタイミングで現在のインデックスも一緒に保持しておくと、ゴールから逆走して「どこから来たか」が辿れるようになる。

失敗

訪問済みの管理は、Pythonでよくやる visited = set() で書いた。以下が当時の省略なしの全コード。

from collections import deque

# 幅優先探索かも
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
start = [0,0]
goal = [0,0]
for i in range(H):
    for j in range(W):
        if S[i][j] == "S":
            start = [i,j]
        if S[i][j] == "G":
            goal = [i,j]

# 位置と前回動いた方向をセットで状態とし、状態をノードとして幅優先探索をする。
# 状態を(y,x,direction)で定義する
# キューには経路復元用のprev上のインデックスを持たせる
queue = deque([[start[0],start[1],None,None]])
visited = set()
prevs = []
flag = False
index = 0
while queue:
    node = queue.popleft()
    visited.add(tuple(node[:3]))
    prevs.append(node)
    if node[:2] == goal:
        flag = True
        break
    cur_y,cur_x,prev_direction,prev_index = node
    if S[cur_y][cur_x] in [".","S","G"]:
        for (dy,dx,direction) in [(1,0,"D"),(0,1,"R"),(-1,0,"U"),(0,-1,"L")]:
            ny,nx = cur_y+dy,cur_x+dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != "#" and (ny,nx,direction) not in visited:
                queue.append([ny,nx,direction,index])
    elif S[cur_y][cur_x] == "o":
        for (dy,dx,direction) in [(1,0,"D"),(0,1,"R"),(-1,0,"U"),(0,-1,"L")]:
            ny,nx = cur_y+dy,cur_x+dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != "#" and (ny,nx,direction) not in visited and direction == prev_direction:
                queue.append([ny,nx,direction,index])
    elif S[cur_y][cur_x] == "x":
        for (dy,dx,direction) in [(1,0,"D"),(0,1,"R"),(-1,0,"U"),(0,-1,"L")]:
            ny,nx = cur_y+dy,cur_x+dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != "#" and (ny,nx,direction) not in visited and direction != prev_direction:
                queue.append([ny,nx,direction,index])
    index += 1

if flag:
    print("Yes")
    # 経路復元
    # prevsのindexからさかのぼる
    reversed_path = []
    while index != 0:
        reversed_path.append(prevs[index][2])
        index = prevs[index][3]
    path = reversed(reversed_path)
    print("".join(path))
else:
    print("No")

結果：TLE

状態空間が広いため、ループのたびにタプルを生成し、set のハッシュ値を計算して追加・検索する処理が重すぎたらしい。

ACをするためにやったこと

set をやめて、処理の軽い「配列のインデックスアクセス」に入れ替えた。
方向は4つ（D, R, U, L）しかないので、visited[y][x][方向] を表す3次元配列を用意すればいい。

結果：ギリギリAC！

最終的なACコード

from collections import deque

# 幅優先探索かも
H, W = map(int, input().split())
S = [input() for _ in range(H)]
start = [0, 0]
goal = [0, 0]

for i in range(H):
    for j in range(W):
        if S[i][j] == "S":
            start = [i, j]
        if S[i][j] == "G":
            goal = [i, j]

# 位置と前回動いた方向をセットで状態とし、状態をノードとして幅優先探索をする。
# 状態を(y,x,direction)で定義する
# キューには経路復元用のprev上のインデックスを持たせる
queue = deque([(start[0], start[1], None, None)])

# setから3次元配列に変更して高速化
visited = [[[False] * 4 for _ in range(W)] for _ in range(H)]
prevs = []
flag = False
index = 0

# (dy, dx, 方向の文字, 訪問配列用のインデックス)
moves = [(1, 0, "D", 0), (0, 1, "R", 1), (-1, 0, "U", 2), (0, -1, "L", 3)]

while queue:
    node = queue.popleft()
    prevs.append(node)

    if node[0] == goal[0] and node[1] == goal[1]:
        flag = True
        break

    cur_y, cur_x, prev_direction, prev_index = node
    cell = S[cur_y][cur_x]

    for dy, dx, direction, d_idx in moves:
        if cell == "o" and direction != prev_direction:
            continue
        if cell == "x" and direction == prev_direction:
            continue

        ny, nx = cur_y + dy, cur_x + dx

        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != "#" and not visited[ny][nx][d_idx]:
            queue.append((ny, nx, direction, index))
            visited[ny][nx][d_idx] = True

    index += 1

if flag:
    print("Yes")
    # 経路復元
    # prevsのindexからさかのぼる
    reversed_path = []
    while index != 0:
        reversed_path.append(prevs[index][2])
        index = prevs[index][3]

    path = reversed(reversed_path)
    print("".join(path))
else:
    print("No")

参考・出典

AtCoder Beginner Contest 453 参加記録と解答例 (A〜C問題)

iwamutsu256 — Sat, 11 Apr 2026 15:11:48 +0000

本記事は、AtCoder Beginner Contest 453 (ABC453) に参加した際の、A〜C問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。

A - Trimo

実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 100 点

問題文

長さ N の文字列 S が与えられます。

S のうち先頭に連続する o をすべて取り除いた文字列を出力してください。
なお、 S 中のすべての文字が o である場合は空文字列を出力してください。

制約

N は 1 ≤ N ≤ 50 を満たす整数
S は英小文字からなる長さ N の文字列

自分の解答の方針

先頭からo出ない文字が初めに出てくる場所を調べ、それ以降の文字列を出力する。

提出したコード

N = int(input())
S = list(input())
i = 0
while i <= N-1 and S[i] == "o":
    i += 1
print("".join(S[i:]))

B - Sensor Data Logging

実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 200 点

問題文

ある測定では、時刻 0,1,…,T におけるセンサーの測定値を以下の規則で記録します。

時刻 0 では、測定値を保存する。
時刻 1,2,…,T では、「現時刻の測定値」と「直前に保存された測定値」との差の絶対値が X 以上であるとき、またその時に限り値を保存する。

時刻 i=0,1,…,T におけるセンサーの測定値は Ai でした。
測定値が保存された時刻と保存された値とを、時刻の昇順に出力してください。

制約

1 ≤ T ≤ 100
1 ≤ X ≤ 100
0 ≤ Ai ≤ 100
入力はすべて整数

自分の解答の方針

問題の通りに実装する。

提出したコード

T,X = map(int,input().split())
A = list(map(int,input().split()))
sensor = 0
for i in range(T+1):
    if i == 0:
        sensor = A[i]
        print(i,sensor)
    elif abs(A[i] - sensor) >= X:
        sensor = A[i]
        print(i,sensor)

C - Sneaking Glances

実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 300 点

問題文

数直線上の座標 0.5 に高橋君がいます。
高橋君はこれから N 回の移動を行います。

i 回目の移動では、「正の方向」「負の方向」のいずれかを選び、その方向に Li 進みます。
高橋君は座標 0 を最大で何回通り過ぎることが出来るでしょうか？
なお、この問題の制約上、座標 0 で完了する移動が生じることはありません。

制約

1 ≤ N ≤ 20
1 ≤ Li ≤ 10^9
入力はすべて整数

自分の解答の方針

Nが最大でも20なので、すべての選択を全探索しても2^20で10^6程度
2進数に変換して各桁の数字で正か負かを選択することで全探索できる。

提出したコード

N = int(input())
L = list(map(int,input().split()))
# 全探索
ans = 0
for i in range(2**N):
    bit = bin(i)[2:].zfill(N)
    count = 0
    current = 0.5
    for j in range(N):
        if bit[j] == "1":
            # 正の方向
            if current < 0 and current + L[j] > 0:
                count += 1
            current += L[j]
        else:
            # 負の方向
            if current > 0 and current - L[j] < 0:
                count += 1
            current -= L[j]
    ans = max(ans,count)
print(ans)

AtCoder Beginner Contest 452 参加記録と解答例 (A〜D問題)

iwamutsu256 — Sat, 11 Apr 2026 15:11:35 +0000

本記事は、AtCoder Beginner Contest 452 (ABC452) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコード、そして後から振り返って気づいた計算量の課題などについて整理しています。

A - Gothec

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点: 100 点

問題文

以下の 5 つの日を五節句と呼びます。

1 月 7 日
3 月 3 日
5 月 5 日
7 月 7 日
9 月 9 日

M 月 D 日が五節句に含まれるならば Yes を、含まれないならば No を出力してください。

制約

M, D は整数
M 月 D 日はグレゴリオ暦における閏年（うるうどし）の日付として正しい。

自分の解答の方針

5つすべてと比較する。

提出したコード

M,D = map(int,input().split())
if (M,D) in [(1,7),(3,3),(5,5),(7,7),(9,9)]:
    print("Yes")
else:
    print("No")

B - Draw Frame

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点: 200 点

問題文

縦 H 行、横 W 列のマス目があります。高橋くんは、このマス目のそれぞれのマスを白か黒で塗ろうとしています。

高橋くんは、マス目に含まれるマスのうち端にあるマスをすべて黒く塗り、それ以外のマスを白く塗ります。高橋くんが色を塗ったあとのマス目を出力してください。

より厳密には
H × W のマス目があります。
上から i 行目 (1 ≤ i ≤ H)、左から j 列目 (1 ≤ j ≤ W) のマスをマス (i,j) と呼ぶことにします。

マス (i,j) とマス (k,l) が |i-k|+|j-l|=1 を満たすとき、かつそのときに限りこれらのマスは辺で隣接していると言います。
マス (i,j) と辺で隣接しているマスが 3 個以下のとき、かつそのときに限りマス (i,j) は端にあると言います。

次の条件を満たす H 個の文字列 S_1, S_2, ..., S_H を求めてください。

S_i は長さ W の文字列であり、S_i の j 文字目は、マス (i,j) が端にあるとき # 、そうでないとき . である。

制約

3 ≤ H ≤ 10
3 ≤ W ≤ 10
入力はすべて整数

自分の解答の方針

H * W の全てが . の2次元配列を作成し、二重ループですべての条件を調べる。

提出したコード

H,W = map(int,input().split())
mapping = [["." for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if i == 0 or i == H-1 or j == 0 or j == W-1:
            mapping[i][j] = "#"
for i in range(H):
    print("".join(mapping[i]))

C - Fishbones

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点: 300 点

問題文

アーティストの高砂君は、魚の骨をかたどったオブジェを作りました。
オブジェは N 本の肋骨と 1 本の脊椎からなります。肋骨には 1 から N までの番号が付けられています。

高砂君は、以下の条件をすべて満たすように N+1 本の骨に 1 つずつ文字列を書こうと考えています。

脊椎に書く文字列の長さは N である。
肋骨 i=1,...,N に対して、以下が成り立つ。
- 肋骨 i に書く文字列の長さは A_i である。
- 肋骨 i に書く文字列の B_i 文字目は、脊椎に書く文字列の i 文字目に一致する。
N+1 本の骨に書く文字列はいずれも、S_1, ..., S_M のいずれかである（重複してもよい）。
S_1, ..., S_M は英小文字からなる文字列であり、互いに異なります。

j=1,...,M に対して、以下の質問に答えてください。

条件を満たす書き方のうち、脊椎に書く文字列が S_j であるものは存在しますか？

制約

1 ≤ N ≤ 10
1 ≤ B_i ≤ A_i ≤ 10
1 ≤ M ≤ 200000
1 ≤ |S_j| ≤ 10
S_1, ..., S_M は相異なる

自分の解答の方針、考えたこと

骨に書く文字列は重複してもいいことから、各骨に最大 M 個の文字の候補がある。
これを集合（set）として持っておくと、文字列 S_j が書けるかどうかを O(N) で判定できる。
前処理を O(NM) で行い、全体で O(MN) で解くことができる。
これは制約下で十分高速。

提出したコード

N = int(input())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b-1)
M = int(input())
S_list = []
for i in range(M):
    s = list(input())
    S_list.append(s)

# 長さNのset()の配列に文字を保存
char_list = [set() for _ in range(N)]
# max2000000
for i in range(N):
    for j in range(M):
        if len(S_list[j]) == A[i]:
            char_list[i].add(S_list[j][B[i]])

for i in range(M):
    target = S_list[i]
    flag = True
    if len(target) != N:
        print("No")
        continue
    for j in range(N):
        if S_list[i][j] not in char_list[j]:
            flag = False
    if flag:
        print("Yes")
    else:
        print("No")

D - No-Subsequence Substring

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点: 400 点

問題文

英小文字からなる文字列 S,T が与えられます。
S の空でない部分文字列 s のうち、T を（連続するとは限らない）部分列として含まないものの個数を求めてください。
ここで、S の 2 つの部分文字列は、取り出した箇所が異なれば文字列として等しくても区別するものとします。

部分文字列とは
文字列 X の部分文字列とは、X の先頭から 0 文字以上、末尾から 0 文字以上を削除して得られる文字列のことを指します。

部分列とは
文字列 X の部分列とは、X の要素を 0 個以上選んで削除し、残った要素を元の順序を保って並べた文字列のことを指します。

制約

1 ≤ |S| ≤ 2 × 10^5
1 ≤ |T| ≤ 50

自分の解答の方針、考えたこと

S の空でない部分文字列 s は全部で |S|(|S|+1)//2 個ある。
S の start 文字目から end 文字目までの部分文字列を S(start,end) としたとき、start を固定したまま end を増やすことを考えると、ある時点で T を含んでいたら、その後はずっと確定で含み続ける。
また、start を一つ増やしたとき、T を含む瞬間が start が一つ少ない時より遅くなることはあるが、早くなることはない。
なので、含まないマスを数えるのには尺取り法が使える。

あとはある時点での部分文字列内に T が含まれるかどうかの判定ができればよい。
提出コードでは len(S) の文字列に T が割り当て可能かを前から順に見ていったが、コンテスト中は残り時間が少なく焦っていてこれがO(|T|)だと思い込んでいた。後から考えるとこれは最悪計算量 O(|S|) なので、全体で O(|S|^2) となり、キラーケースではTLEとなっていた可能性が高い。なので、これでACできたのは運が良かっただけだと思う。

提出したコード

def check(S,T):
    i = 0
    for t in T:
        while i < len(S) and S[i] != t:
            i += 1
        if i == len(S):
            return False
        i += 1
    return True

S = input()
T = input()
R = [0 for _ in range(len(S))]
for i in range(len(S)):
    if i == 0:
        R[i] = 0
    else:
        R[i] = R[i-1]
    while R[i] < len(S) and not check(S[i:R[i]+1],T):
        R[i] += 1
ans = 0
for i in range(len(S)):
    ans += R[i] - i
print(ans)

CSS中央揃えの迷路から抜け出す！「要素の中身」と「要素自体」の明確な違い

iwamutsu256 — Sat, 11 Apr 2026 15:10:58 +0000

CSSで中央揃えを実装しようとして、paddingで無理やり余白を埋めたり、小さい要素がどうしても動かず混乱した経験はありませんか？

中央揃えの仕組みを理解する鍵は、「要素の中身（テキストなど）を動かす」のか、「要素（箱）そのものを動かす」のかを明確に区別することです。

要素の中身（インライン）を中央に寄せる: text-align: center; を使う
要素自体（ブロック）を中央に配置する: 幅（width）を指定し、margin: auto; を使う

この2つのルールの違いと、なぜpaddingで寄せるのが非推奨なのかを、インライン要素とブロック要素の違いを交えて解説します。

要素の中身（テキストなど）を中央に寄せる：text-align

テキストや画像など、箱の中に入っている「コンテンツ（インライン要素）」を中央に揃えたい場合は、親のブロック要素に対して text-align: center; を指定します。

text-align は CSS のプロパティで、ブロック要素内におけるインラインレベルコンテンツの水平方向の配置を設定します。

<div class="text-box">
  <p>このテキスト（インラインコンテンツ）が中央に寄ります。</p>
  <span>spanなどのインライン要素も同様です。</span>
</div>

.text-box {
  background-color: #f0f0f0;
  /* ブロック要素内のインラインコンテンツを中央揃えにする */
  text-align: center;
}

この方法はあくまで「箱の中の文字」を整列させるものです。要素そのものの大きさや位置が変わるわけではありません。

要素（箱）そのものを中央に配置する：margin: auto

見出しやカード型コンポーネントなど、ある程度の大きさを持った「要素自体（ブロック要素）」を画面や親要素の中央に配置したい場合は、margin を使用します。

ブロック要素はデフォルトで横幅いっぱい（100%）に広がろうとする性質があります。そのため、要素自体を中央に配置するには、まず要素に特定の幅（width）を持たせる必要があります。その上で左右のマージンに auto を指定します。

左右のマージンが auto の場合は、両方に均等に余白が割り当てられます。

<div class="parent-container">
  <div class="center-block">
    この箱（ブロック要素）自体が中央に配置されます。
  </div>
</div>

.center-block {
  /* 1. 箱の幅を指定する */
  width: 300px;
  background-color: #add8e6;

  /* 2. 左右のマージンにautoを指定し、余白を均等に割り当てる */
  margin-left: auto;
  margin-right: auto;
  /* 短縮表記: margin: 0 auto; でも可 */
}

なぜ padding で中央に寄せてはいけないのか？

要素自体の大きさを広げて padding で無理やりコンテンツを中央に押しやる方法は、一見中央に揃っているように見えますが、レイアウト崩れの原因になります。

マージンは要素の外側に余白を作成し、padding は要素の内側に余白を作成します。つまり、paddingを増やすと「箱自体が巨大化」してしまい、他の要素との間隔（マージン）の制御が難しくなるためです。要素を動かす時は外側の余白である margin を使うのが適切なアプローチです。

迷ったら Flexbox を使うのも手

現代のCSSでは、上記の違いを意識しつつも、より直感的に配置を制御できる Flexbox が主流になっています。親要素をFlexコンテナにすることで、要素自体も中身のコンテンツも、一貫したルールで中央配置が可能です。

.flex-container {
  display: flex;
  justify-content: center; /* 水平方向の中央揃え */
  align-items: center;     /* 垂直方向の中央揃え */
}

「中身を動かすのか」「箱自体を動かすのか」。この原則を覚えておけば、もうCSSの中央揃えで迷うことはなくなるはずです。

参考資料