DEV Community: iwamutsu256

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の中央揃えで迷うことはなくなるはずです。

参考資料