こんにちは、こんぶちゃ(茶コーダー)です！
初心者視点から競プロAtCoderのABC356のA問題〜C問題の自身の解答と解答説明をしていきます。
- 競技プログラミング初心者で、問題の解き方がわからない方
- AtCoderの公式解説は読んだが、内容が理解できなかった方
- Pythonでの解法を知りたい方
まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。
では早速行ってみましょう！
今回の参加コンテスト(ABC356)
A問題：Subsegment Reverse
問題文
正整数 N,L,R が与えられます。
長さ N の数列 A=(1,2,…,N) に対し、 L 項目から R 項目までを逆順に並べ替えるという操作を一度行いました。
操作後の数列を出力してください。
解答
# 入力を読み込む
n, l, r = map(int, input().split())
# 長さ n の数列 A を作成
A = [i for i in range(1, n + 1)]
# L-1 までの部分と L から R までの逆順部分と R 以降の部分を結合
subR = A[:l-1] + sorted(A[l-1:r], reverse=True) + A[r:]
# 結果の数列を出力
print(*subR)考え方）
主には下記の順番で解いていきます。
- 数列Aを自身で作成・・・内包表記を用いています
- スライスとソートを用いて求めるリストを作成・・・スライスの区切れ目に注意
コード詳細
- 入力の読み込み: n, l, r の3つの整数を入力から読み込む。
- 数列 A の作成: 長さ n の数列 A を生成。これは 1 から n までの連続する整数からなる。
- 部分の逆順並べ替え:
- 数列 A の先頭から l-1 までの部分をそのまま取り出す。
- A の l 項目から r 項目までの部分を逆順に並べ替える。
- A の r+1 項目以降の部分をそのまま取り出す。
- これら3つの部分を結合して新しい数列 subR を作成する。
- 結果の出力: 新しい数列 subR を出力する。
B問題：Nutrients
問題（要約）
健康に気を使っている高橋君は、M 種類の栄養素について、食事によって十分な量を摂取できているか気になりました。
i 番目の栄養素は 1 日あたり Ai 以上摂取することが目標です。
高橋君は今日 N 品の食品を食べ、i 品目の食品からは栄養素 j を Xi,j 摂取しました。
M 種類全ての栄養素で目標を達成しているかどうかを判定してください。
解答
# N (食品の数) と M (栄養素の種類) を入力から読み込む
n, m = map(int, input().split())
# 各栄養素の目標摂取量 A をリストとして読み込む
A = list(map(int, input().split()))
# 各栄養素の合計摂取量を格納するリストを初期化
nutrients = [0] * m
# 各食品についての栄養素摂取量を読み込み、合計を更新する
for _ in range(n):
x = list(map(int, input().split()))
for j in range(m):
nutrients[j] += x[j]
# 各栄養素について、目標を達成しているかをチェック
for j in range(m):
if A[j] > nutrients[j]:
exit(print("No")) # 目標未達成の場合 "No" を出力して終了
print("Yes") # 全ての栄養素で目標を達成している場合 "Yes" を出力考え方）
下記の考え方で解いています。
- 各栄養素の合計摂取量を格納するリスト nutrients を準備
- 各食品の栄養素摂取量更新
- リスト nutrients と目標摂取量リスト A の各項目を比較
コード詳細
- 入力の読み込み:
- n (食品の数) と m (栄養素の種類) を入力から読み込む。
- 各栄養素の目標摂取量 A をリストとして読み込む。
- 栄養素の合計摂取量の初期化: 各栄養素の合計摂取量を格納するリスト nutrients をゼロで初期化する。
- 各食品の栄養素摂取量の加算:
- N 品の食品について、それぞれの栄養素の摂取量を入力から読み込む。
- 各栄養素の摂取量を nutrients リストに加算していく。
- 目標摂取量の達成判定:
- 各栄養素について、合計摂取量が目標摂取量 A を満たしているかをチェック
- 一つでも目標を達成していない栄養素があれば “No” を出力してプログラムを終了する。
- 全ての栄養素で目標を達成している場合は “Yes” を出力する。
C問題：Keys
問題(要約)
N 本の鍵のうち、正しい鍵を K 本以上挿し込んだ時に開くドアがあり、M 回のテスト結果から正しい鍵の組み合わせの個数を求める。テスト結果には、ドアが開いた (o) か開かなかった (x) かが含まれている。条件に矛盾しない組み合わせの個数を求める。
解答
# N (鍵の数), M (テストの回数), K (必要な正しい鍵の数) を入力から読み込む
n, m, k = map(int, input().split())
# テスト結果を格納するリスト
tests = []
# M 回のテスト結果を読み込み、リストに追加
for _ in range(m):
c, *a, r = input().split()
tests.append((list(map(int, a)), r))
# 条件を満たす鍵の組み合わせの個数をカウントする変数
ans = 0
# 全ての鍵の組み合わせをビット列で表現し、試行
for bit in range(2 ** n):
valid = True
# 各テスト結果について確認
for a, r in tests:
# 各テストに対して挿し込まれた正しい鍵の数をカウント
cnt = sum(bit >> (key - 1) & 1 for key in a)
# 条件に矛盾がある場合、無効とする
if (r == 'o' and cnt < k) or (r == 'x' and cnt >= k):
valid = False
break
# 条件を満たす場合、カウントを増やす
if valid:
ans += 1
# 条件を満たす組み合わせの個数を出力
print(ans)ポイント）
問題文に記載がありますように組み合わせは 2N 通りあるため、bit全探索を用いて全ての組み合わせを確認していきます。
- 全ての鍵の組み合わせを全探索・・・bit全探索
- それぞれの鍵の組み合わせに対して各テスト条件が矛盾がないかを確認
- 矛盾がない場合は、カウントを増やす
注意）CPythonでは、実行時間超過で不正解になりましたが、PyPyを用いることによりACになりました。
解き方(詳細)：
- 入力の読み込み:
- n (鍵の数)、m (テストの回数)、k (必要な正しい鍵の数) を入力から読み込む。
- テスト結果をリスト tests に格納する。各テスト結果は、使用した鍵のリスト a と結果 r の組み合わせである。
- 組み合わせの初期化:
- 条件を満たす鍵の組み合わせの個数をカウントするための変数 ans を初期化する。
- 鍵の組み合わせの試行:
- 全ての鍵の組み合わせ（2^N 通り）をビット列で表現し、各組み合わせを試行する。
- 各組み合わせに対して、各テスト結果を確認する。
- 挿し込まれた鍵のうち正しい鍵の数をカウントし、テスト結果と比較して条件に矛盾がないか確認する。
- 条件を満たす組み合わせのカウント:
- 条件を満たす場合、カウントを増やす。
- 結果の出力:
- 条件を満たす鍵の組み合わせの個数 ans を出力する。
感想
今回はB問題までしか解けませんでした。
A問題は、リスト内の特定位置の並べ替え問題でした。スライスを用いて特定位置を取り出し、逆順ソートを行うことで解決できました。
B問題は、栄養素リストがすべて基準値を超えているかを判断する問題でした。各食事の各栄養素を加算していき、基準値を超えたかを調べることで解決できました。しかし、当初は各栄養素の最大値を勘違いして実装してしまい、不正解となってしまいました。慌てずに問題をしっかり読むことが重要ですね。
C問題は、bit全探索の問題でした。bit全探索を用いて各テスト条件をすべて確認することで解決できました。ただし、bit全探索の考え方やシフト（>>）の考え方、NGになる条件を理解するまでに2週間かかりました。3回ほど復習しましたが、またすぐに忘れてしまいそうなので、定期的に復習が必要だと思いました（復習が苦手なので、bit全探索の問題が出ることを期待）。
今回はオンタイムで参加できず、レーティングは変わりませんでしたが、B問題で一度間違え、C問題は解けませんでしたので、厳しい結果だと思います。わからないところがわかったということで、引き続き楽しみながら頑張りたいと思います。
皆さんも競技プログラミングを楽しんでくださいね！(*＾▽＾)／
コメント