こんにちは。なかみんです。
いきなりですが、不定期でAtCoderに関して書いてきます。
私とAtCoder
2025年10月からpythonで参加し始めました。
それからできる限り毎週参加して解いていますが、復習に力を入れていなかった結果、10回参加しても茶色に届いていません...(;｡;)ﾜｰﾝ
なんとなくの傾向は分かってきましたが、本番でぱっとコードに落とせなくて時間が経ってしまうことを繰り返すのはよくないと思い、参加はお休みする代わりに復習に力をごりごり入れていきたいと思います。
なお、私が茶色を目指している身なので基本的にはA～Ｃ問題を記載していきます。
- (余裕があったら)D問題も記載します
- もし私がレベルアップしたら記載する問題もレベルアップします
目次
ABC435（2025年12月6日実施）
A問題
問題
入力例
5
回答例
N = int(input())
cnt = 0
for n in range(1, N+1):
cnt += n
print(cnt)
B問題
問題
- l≤i≤rの範囲のAは約数が含まれないようにする
入力例
5
8 6 10 5 7
回答例
N = int(input())
A = list(map(int, input().split()))
ok = 0
for i in range(N):
current_sum = 0
# 右端 r を i から順に伸ばしていく
for j in range(i, N):
current_sum += A[j]
# 範囲 A[i:j+1] のすべての要素について判定
is_condition_met = True
for k in range(i, j + 1):
if current_sum % A[k] == 0:
is_condition_met = False
break
if is_condition_met:
ok += 1
print(ok)
ポイント
- スライスはなるべく使わずに、インデックスで参照するようにする（スライスを使用すると元のリストの一部をコピーして新しいリストをメモリ上に作成する）
- 合計は
sum()を毎回呼ぶとメモリをくうので、current_sum += A[j]で計算する - 今回はNが50までの数字なのでこれでよいがNが大きいケースは、累積和で対応する
# 累積和（前もって合計を計算しておく）
S = [0] * (N + 1)
for i in range(N):
S[i+1] = S[i] + A[i]
# 任意の範囲 (iからj) の合計は引き算で算出できる
# 合計 = S[j+1] - S[i]
C問題
問題
- ドミノを想像しながら設定をイメージ（自分の左にいるドミノよりも背が低ければ自分も倒れる）
入力例
4
3 1 4 1
回答例
n = int(input())
A = [0] + [int(x) for x in input().split()]
# 座標1 + 高さA[1] = この値「未満」が倒れる
limit = 1 + A[1]
# 倒れたドミノの数
count = 1
# 2番目のドミノから順に、連鎖するか確認
for i in range(2, n + 1):
# 今のドミノの座標 i が、現在の limit 未満であれば連鎖する
if i < limit:
count += 1
# このドミノが倒れることで、届く範囲が広がるなら更新
# 新しい範囲は 「今の座標 i + 高さ A[i]」
if i + A[i] > limit:
limit = i + A[i]
else:
# 届かなかったら、これ以降のドミノは倒れない
break
print(count)
ポイント
- 直感的になるよう、
[0] + [int(x) for x in input().split()]のようにしてドミノのリストは0番目をダミーで加えておく - limitが届く範囲をどんどん更新していくようにする
# 新しい範囲は 「今の座標 i + 高さ A[i]」
if i + A[i] > limit:
limit = i + A[i]
ABC436（2025年12月13日実施）
A問題
問題
回答例
N = int(input())
S = input()
n = N-len(S)
result = "o"*n + S
print(result)
B問題
問題
- マス((r−1)modN,(c+1)modN) が空白ならばそのマスに、そうでなければマス((r+1)modN,c)に数字を順番に書いていく
- xmodN は x を N で割ったあまりを表す
入力例
3
→ 3行3マスのマス目になる
回答例
N = int(input())
# N×Nのグリッドを0で初期化
matrix = [[0] * N for _ in range(N)]
# 初期位置: 1行目の中央
r, c = 0, (N - 1) // 2
matrix[r][c] = 1
# 2 から N^2 まで順番に埋めていく
for k in range(2, N**2 + 1):
# 次の候補地点を計算
nr, nc = (r - 1) % N, (c + 1) % N
# もし候補地点がすでに埋まっていたら、真下のマスへ
if matrix[nr][nc] != 0:
nr, nc = (r + 1) % N, c
# マスを更新
matrix[nr][nc] = k
r, c = nr, nc
# 結果の出力
for row in matrix:
print(*(row))
ポイント
- マス目(r,c)を使って計算するので、空白ではなく最初に0で埋める
-
*(row)で" ".join(map(str, row))と同じ結果になるがより短く書ける
C問題
問題
- 1ブロック4マスの塊を何個置けるかを考える
入力例
4 3
1 1
2 2
2 3
回答例
n, m = map(int, input().split())
# すでにブロックが置かれているマスを記録する集合 (set)
occupied = set()
# 実際に置けたブロックの個数
ans = 0
for _ in range(m):
r, c = map(int, input().split())
# 今回のブロックが占有しようとする4つのマス
# (r, c), (r, c+1), (r+1, c), (r+1, c+1)
s1, s2, s3, s4 = (r, c), (r+1, c), (r, c+1), (r+1, c+1)
# 4つのマスのうち、1つでも既に埋まっていたら「置けない」
if s1 in occupied or s2 in occupied or s3 in occupied or s4 in occupied:
continue
# 置ける場合のみ処理を行う
ans += 1
occupied.add(s1)
occupied.add(s2)
occupied.add(s3)
occupied.add(s4)
print(ans)
ポイント
- 左上のマスだけ入力として与えられていますが、それを使ってチェックしたい4マスを表現するには、以下のように範囲を表現するとよいです
s1, s2, s3, s4 = (r, c), (r+1, c), (r, c+1), (r+1, c+1)
ABC437（2025年12月20日実施）
A問題
問題
回答例
A, B = map(int, input().split())
print(A*12+B)
B問題
問題
- 与えられた集合の中から数字があるかどうかをカウントしてその最大値を取得
入力例
3 4 5
12 3 5 7
6 10 11 9
1 2 4 8
2
4
9
6
11
回答例
H, W, N = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(H)]
B = set(int(input()) for _ in range(N))
max_count = 0
for row in matrix:
current_row_count = 0
for val in row:
if val in B:
current_row_count += 1
# 最大値を更新
if current_row_count > max_count:
max_count = current_row_count
print(max_count)
ポイント
- 見つける対象の数字はlistで持つと毎回中身を端から確認するので、setで集合型で持つことで検索がO(1)で終わる
B = set(int(input()) for _ in range(N))
- 流れとしては、一行一行Bに含まれるかどうかをチェックして含まれたらカウントする→そのカウントの最大値を更新していく
全ての行の結果を辞書で格納してmax()する必要はなくて、知りたいのはカウントの最大値 - もし行番号まで控えないといけない場合は辞書で格納して以下のように取り出す。
# 最大値とその行番号をセットで取得したい場合
top_pair = max(cnt_dict.items(), key=lambda x: x[1])
print(f"{top_pair[0]}行目が最多で、{top_pair[1]}個")
C問題
問題
- ソリを引くトナカイの力の総和が、ソリに乗るトナカイの重さの総和以上というルールを守って最大何匹のトナカイを載せられるかを出力する
入力例
3
3
3 1
4 1
5 9
5
1000000000 1
1000000000 1
1000000000 1
1000000000 1
1000000000 1
10
133180711 458704923
531424946 225863856
141986070 637075158
500770732 289806469
502866767 408857335
559714289 569084545
287444582 992432993
559747907 753133304
432846188 949871298
727072164 756020367
回答例
import sys
all_data = sys.stdin.read().split()
iterator = iter(all_data)
T = int(next(iterator)) # next(iterator) は、リストから要素を一つずつ取り出す
for _ in range(T):
N = int(next(iterator))
wp = []
sum_total_p = 0
for _ in range(N):
w = int(next(iterator))
p = int(next(iterator))
wp.append(w + p)
sum_total_p += p
wp.sort()
ans = 0
current_sum_wp = 0
# 小さい順に乗せていく
for val in wp:
if current_sum_wp + val <= sum_total_p:
current_sum_wp += val
ans += 1
else:
break
print(ans)
ポイント
- それぞれのトナカイについて、W（重さ）の総和よりもP（引く力）の総和が大きいときに条件を満たしています
$$\sum P_{pull} \geq \sum W_{ride}$$
トナカイがソリに乗ってしまうと発揮されない引く力が発生するので、1匹ソリに乗せるごとに、ソリが重くなる＋引っ張る力が減るという2つのコストがかかります。
$$\sum (W_{ride} + P_{ride})$$
このコストが小さい順にトナカイを乗せていき、全トナカイの引く力の合計を超えないようにします。
$$S_P \geq \sum (W_{ride} + P_{ride})$$
ここで$S_P$はソリに乗っている乗っていないにかかわらずすべてのトナカイの力の総和を表しています（=$S_P = \sum (P_{pull} + P_{ride})$ ）。
ABC438（2025年12月27日実施）
A問題
問題
- 7日周期で開催されるコンテスト
- 今年F日に開催された場合、次の年は何日目に開催されるか
入力例
365 4
回答例
D, F = map(int, input().split())
diff = D - F
# 7で割った余りを出す
rem = diff % 7
if rem == 0:
print(0)
else:
print(7 - rem)
ポイント
- 7日周期からはみ出た日は割り算の余りで考える
B問題
問題
- 各位の数字に＋1していき最短で部分文字列を作る
入力例
4 2
2025
91
回答例
n, m = map(int, input().split())
s = input()
t = input()
s_nums = [int(c) for c in s]
t_nums = [int(c) for c in t]
ans = 10**9
for st in range(n - m + 1):
res = 0
for i in range(m):
res += (s_nums[st + i] - t_nums[i]) % 10
ans = min(ans, res)
print(ans)
ポイント
- まずは候補となる部分文字列の桁（窓をイメージ）をfor文で作る
全ての候補をリストに保存してからループを回すのではなく、インデックス（st）を動かしながらその場で計算することでメモリ消費を抑えています。
for st in range(n - m + 1):
- 一つ一つの文字を見ていく
for i in range(m):
- 数字の差を足していく
s[st + i]として、窓の開始位置stに窓の中での位置[i]を足すことで元の文字列からチェックしたい文字を指しています。
res += (s_nums[st + i] - t_nums[i]) % 10
ここでは、8→2など＋1で循環して9になれば次は0という性質も考慮していかなければいけません。
試験時に私は条件分岐でこの循環が必要になるとき、＋10をして18-2を計算するようにコードを書いていましたが、% 演算子を使えば数式で表すことができます。
この% 演算子では、負の値に対しても正の余りを返す性質があるので、マイナスになっても大丈夫です。
例えば、2→8に動かしたいときは$(2-8)%10$で$4$と正にした値が出てくれます。
- 最小の数を更新していく
最初にans = 10**9のように大きな値で初期化してあるので、最初の一個目の計算結果が必ずminで採用されてその後の比較がスムーズです。
ans = min(ans, res)
C問題
問題
- ぷよぷよ的な感じで4つ並んだ数字の塊を消していき最短の長さにする
入力例
10
1 1 1 4 4 4 4 1 2 3
回答例
N = int(input())
A = list(map(int, input().split()))
# スタックの中身は [ [値, 個数], [値, 個数], ... ] という形式にする
stack = []
for x in A:
# スタックが空でなく、一番上の数字が今の数字と同じ場合
if stack and stack[-1][0] == x:
stack[-1][1] += 1 # 個数をカウントアップ
else:
# 数字が違う、またはスタックが空なら新しく積む
stack.append([x, 1])
# もし一番上の個数が4つに達したら消去（連鎖の起点）
if stack[-1][1] == 4:
stack.pop()
# 最終的な長さを計算（各塊の個数の合計）
ans = sum(item[1] for item in stack)
print(ans)
ポイント
-
まずはどの値が何個横に並んでいるかを把握する必要がある
どの塊を消すかを考えるにはどのような数字列なのかを記録しておきます。
ただ記録するのではなく、塊の場所も大事になるので積んでいく形にするためにfor文でまわしています。 -
塊へのアクセス
stackは例えば一番上に積まれている数字の個数にアクセスする場合はstack[-1][1]になります。 -
流れ
今積み上げられている数字と同じか違うかで処理が異なります。
以下のように積み上げられているものをイメージします。
次に、数字の4が来た場合以下の処理で数字の塊ごと削除します。
popの中に引数を入れることで位置を指定できますが、空にすると末尾になります。
# もし一番上の個数が4つに達したら消去（連鎖の起点）
if stack[-1][1] == 4:
stack.pop()
これで4の塊は消えました。
次の数字は1ですが、今積み上げられている1にそのまま加算されるので、これもpopされます。
結果として、リストは空になりました。
そのあとの数字は2,3なのでそのまま積み上げられて終了です。
2025年12月の振り返りは以上です。
読んでいただきありがとうございました。