「AtCoder Beginner Contest 347 – AtCoder」のPythonの解説です。
A – Divisible
特に悩むところはありません。
Python
N, K = map(int, input().split())
A = list(int(i) // K for i in input().split() if int(i) % K == 0)
A = [str(i) for i in A]
A = " ".join(A)
print(A)B – Substring
集合を用いることで簡単に、重複は打ち消せます。
よって、集合の長さが答えとなります。
Python
S = input() # 文字列の入力
s = list(S)
setS = set()
for i in range(len(s)):
for x in range(len(s)+1):
if s[i:x]:
setS.add("".join(s[i:x]))
print(len(setS))C – Ideal Holidays
解答は、以下のサイトを参考にしました。
AtCoder Beginner Contest 347 C問題 解説 - Qiita
ArCoderの問題の解き方を自分用に記録する。難しいなあ...。問題考え方今日を0日目と…
qiita.com
非常に悩んだ問題です。一見すると、少し頭を捻るだけ解けそうに思えますが、それがドツボにはまらせます。
多くの人は、A+Bで割った余りを使うところまでは辿り着くと思います。それで解こうとしますが、何度試してもACに至りません。
この問題のポイントは、3つです。
- 各予定の日付を、1週間の日数で割った余りに変換することで、問題を簡略化する
- 予定をソートし、隣り合う予定の間隔を計算することで、全ての予定が休日に収まるかどうかを判定する
- 最後の予定と最初の予定の間隔も考慮する
問題の争点は、日付の間隔の最大値が、Bより多いかどうかということです。
あとは何も考える必要がありません。
Python
N, A, B = map(int, input().split())
D = list(map(int, input().split()))
# 各予定の日付を、1週間の日数で割った余りに変換
D = [d % (A+B) for d in D]
# 予定の日付を昇順にソート
D.sort()
# 隣り合う予定の間隔を計算
diffs = []
for i in range(N-1):
diffs.append(D[i+1] - D[i])
diffs.append((A+B) - D[-1] + D[0]) # 最後の予定と最初の予定の間隔も考慮する
# 間隔の最大値が平日の日数より大きければYes
if max(diffs) > B:
print("Yes")
else:
print("No")D – Popcount and XOR
※未解答です
E – Set Add Query
※未解答です
F – Non-overlapping Squares
※未解答です
G – Grid Coloring 2
※未解答です
まとめ
この記事では、AtCoder Beginner Contest 347のA問題からC問題までのPythonによる解説を行いました。
- A問題は簡単な問題で、特に悩むところはありませんでした。リストの内包表記を使って、条件を満たす要素だけを抽出し、文字列に変換して出力しました。
- B問題は、部分文字列の重複を避けるために集合を使いました。全ての部分文字列を集合に追加することで、重複は自動的に取り除かれます。最終的に集合の要素数が答えになります。
- C問題は非常に難しい問題でした。一見すると簡単そうに見えますが、A+Bの余りを使うだけでは解けません。この問題のポイントは3つあります。詳細な解説は記事中のコードを参照してください。
- D問題以降はまだ解答していませんが、今後挑戦していきたいと思います。
コンテストの結果は300点でした。A問題とB問題は解けましたが、C問題で躓きました。今回のコンテストを通して、まだまだ学ぶべきことが多いと実感しました。これからも精進していきたいと思います。
