PR

【Python】AtCoder Beginner Contest 347 【Cまで解説】

競プロ

AtCoder Beginner Contest 347 – AtCoder」のPythonの解説です。

WordPressブロガーの方必見! 外出先でもブログ執筆作業がはかどる、 Ankerの大容量モバイルバッテリー をご紹介します。

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日目と…

非常に悩んだ問題です。一見すると、少し頭を捻るだけ解けそうに思えますが、それがドツボにはまらせます。
多くの人は、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問題で躓きました。今回のコンテストを通して、まだまだ学ぶべきことが多いと実感しました。これからも精進していきたいと思います。

タイトルとURLをコピーしました