AtCoder Beginner Contest 347をPythonで解く-Shinoryo's Weblog

Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 347を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Divisible
2B - Substring
3C - Ideal Holidays
4D - Popcount and XOR
5E以降
6参考にしたサイト等

A - Divisible

空のリストquotientsを用意します. リスト $A$ をループして, 各要素 $A_{i}$ に対して次の操作を行います.

$A_{i}$ が $k$ で割り切れる場合：quotientsに $A_{i} / k$ を追加する.
$A_{i}$ が $k$ で割り切れない場合：何もしない.

	# 入力
	n, k = map(int, input().split())
	a = list(map(int, input().split()))

	# リストaをループして、kで割り切れる要素の商を計算し、quotientsに追加する
	quotients = []
	for a_i in a:
	if a_i % k == 0:
	quotients.append(a_i // k)

	# 出力
	print(*quotients)

view raw atcoder-abc-347-a.py hosted with ❤ by GitHub

B - Substring

$S$ の部分文字列を全探索して, 何種類あったかを数え上げればよいです. $S$ の部分文字列を取得するには, 文字列のスライスを用います. 重複なく用いるには, 集合(set)に追加していって, 最後にその要素数を数えます.

	# 入力
	s = input()

	# 文字列sの部分文字列を格納するセットを作成
	substring_set = set()

	# 全ての部分文字列を探索し、substring_setに追加する
	for i in range(len(s)):
	for j in range(i + 1, len(s) + 1):
	substring_set.add(s[i:j])

	# 出力
	print(len(substring_set))

view raw atcoder-abc-347-b.py hosted with ❤ by GitHub

C - Ideal Holidays

1週間の何日目に予定があるかが重要なので, $D$ の各要素を $(A + B)$ で割った余りを用意し, ソートしてしまいましょう.

高橋くんの予定が全て休日であるということは, ある予定とその次の予定の間に全ての平日が含まれればよいです.

例えば, 1週間のうち2日が休日で5日が平日の例を考えてみます. 次の表のようになっている場合, 3, 4, 5, 6, 0日目が平日であれば, 高橋くんの予定は全て休日です.

次の表のようになっている場合, 1, 2, 3, 4, 5日目が平日であれば, 高橋くんの予定は全て休日です.

次の表のようになっている場合, 平日をどのように設定しても, 高橋君の予定のどれかが平日になってしまいます.

	# 入力
	n, a, b = map(int, input().split())
	d = list(map(int, input().split()))

	# 週の長さ
	week_length = a + b

	# 予定のある日を1週間の何日目かに変換し、重複を排除する
	days = [d_i % week_length for d_i in d]
	distinct_days = list(set(days))
	distinct_days.sort()
	distinct_days_count = len(distinct_days)

	# 「門番」を加える
	distinct_days.append(distinct_days[0] + week_length)

	# 予定のある日の間隔がbを超えるかどうかをチェック
	for i in range(distinct_days_count):
	if distinct_days[i + 1] - distinct_days[i] > b:
	print("Yes") # 予定のある日がb以上離れている場合、Yesを出力して終了
	exit()

	print("No") # 予定のある日がb以上離れていない場合、Noを出力

view raw atcoder-abc-347-c.py hosted with ❤ by GitHub

あるいは, 全ての予定が休日の範囲に収まればよいです.

	from collections import deque

	# 入力
	n, a, b = map(int, input().split())
	d = list(map(int, input().split()))

	week_length = a + b

	# 予定のある日を1週間の何日目かに変換し、重複を排除する
	days = [d_i % week_length for d_i in d]
	distinct_days = list(set(days))
	distinct_days.sort()
	distinct_days_deque = deque(distinct_days)

	# 予定のある日の範囲がaを超えないかどうかをチェック
	for _ in range(n):
	if distinct_days_deque[-1] - distinct_days_deque[0] < a:
	print("Yes") # 予定のある日の範囲がa以内の場合、Yesを出力して終了
	exit()

	distinct_days_deque.rotate(-1)
	distinct_days_deque[-1] += week_length

	print("No") # 予定のある日の範囲がaを超える場合、Noを出力

view raw atcoder-abc-347-c-2.py hosted with ❤ by GitHub

D - Popcount and XOR

基本的には, 公式解説どおりです.

$n_{0, 0}$ , $n_{0, 1}$ , $n_{1, 0}$ , $n_{1, 1}$ が非負整数であるための条件だけ補足します. $a$ , $b$ , $c$ が整数であることを用いて, 次のように考えることができます.

$n_{0, 0}$ が非負である $\Leftrightarrow$ $\begin{array}{r} (1) & 60 - \frac{a + b + c}{2} \geq 0 \Leftrightarrow a + b + c \leq 120 \end{array}$
$n_{0, 0}$ が整数である $\Leftrightarrow$ $a + b + c$ が $2$ の倍数 $\Leftrightarrow$ $\begin{array}{r} (2) & a + b + c \equiv 0 (\mod 2) \end{array}$
$n_{0, 1}$ が非負である $\Leftrightarrow$ $\begin{array}{r} (3) & \frac{- a + b + c}{2} \geq 0 \Leftrightarrow a \leq b + c \end{array}$
$n_{0, 1}$ が整数である $\Leftrightarrow$ $- a + b + c$ が $2$ の倍数 $\Leftrightarrow$ $\begin{array}{r} (4) & - a + b + c \equiv 0 (\mod 2) \Leftrightarrow a + b + c \equiv 2 a \equiv 0 (\mod 2) \end{array}$
$n_{1, 0}$ が非負である $\Leftrightarrow$ $\begin{array}{r} (5) & \frac{a - b + c}{2} \geq 0 \Leftrightarrow b \leq c + a \end{array}$
$n_{1, 0}$ が整数である $\Leftrightarrow$ $a - b + c$ が $2$ の倍数 $\Leftrightarrow$ $\begin{array}{r} (6) & a - b + c \equiv 0 (\mod 2) \Leftrightarrow a + b + c \equiv 2 b \equiv 0 (\mod 2) \end{array}$
$n_{1, 1}$ が非負である $\Leftrightarrow$ $\begin{array}{r} (7) & \frac{a + b - c}{2} \geq 0 \Leftrightarrow c \leq a + b \end{array}$
$n_{1, 1}$ が整数である $\Leftrightarrow$ $a + b - c$ が $2$ の倍数 $\Leftrightarrow$ $\begin{array}{r} (8) & a + b - c \equiv 0 (\mod 2) \Leftrightarrow a + b + c \equiv 2 c \equiv 0 (\mod 2) \end{array}$

最終的に, $a + b + c \leq 120$ , $a + b + c \equiv 0 (\mod 2)$ , $a \leq b + c$ , $b \leq c + a$ , $c \leq a + b$ にまとめることができます.

	# 入力
	a, b, input_c = map(int, input().split())
	c = input_c.bit_count()

	# a, b, cが条件を満たすかを確認する
	if (a + b + c) % 2 == 1:
	print(-1)
	elif a + b + c > 120:
	print(-1)
	elif a > b + c:
	print(-1)
	elif b > c + a:
	print(-1)
	elif c > a + b:
	print(-1)
	# 条件を満たすならば、xとyを計算する
	else:
	i = 60 - (a + b + c) // 2 # xのn桁目が0、yのn桁目が0となるようなnの個数
	j = (- a + b + c) // 2 # xのn桁目が0、yのn桁目が1となるようなnの個数
	k = (a - b + c) // 2 # xのn桁目が1、yのn桁目が0となるようなnの個数
	l = (a + b - c) // 2 # xのn桁目が1、yのn桁目が1となるようなnの個数

	x = 0
	y = 0

	# 上の桁から計算する
	for now_digit in range(59, -1, -1):
	# input_cのnow_digit桁目が1の場合、xのn桁目かyのn桁目のどちらか一方のみが1である
	if (input_c >> now_digit) & 1:
	if j:
	y \|= 1 << now_digit
	j -= 1
	else:
	x \|= 1 << now_digit
	k -= 1
	# input_cのnow_digit桁目が0の場合は、xのn桁目かyのn桁目の両方が0、または両方が1である
	else:
	if i:
	i -= 1
	else:
	x \|= 1 << now_digit
	y \|= 1 << now_digit
	l -= 1

	# 出力
	print(x, y)

view raw atcoder-abc-347-d.py hosted with ❤ by GitHub

あるいは, ユーザー解説のようにも実装することができます. $X$ と $Y$ のビットを試しに立ててみて, $X$ や $Y$ のpopcountが目標数ちょうどに達したかを確かめてみる方法です.

	# 入力
	a, b, input_c = map(int, input().split())

	x = 0
	y = 0

	# 下の桁から計算する
	for now_digit in range(60):
	# input_cのnow_digit桁目が1の場合、xのn桁目かyのn桁目のどちらか一方のみが1である
	# aとbの余っている方を優先して消費する
	if (input_c >> now_digit) & 1:
	if a > b:
	x \|= 1 << now_digit
	a -= 1
	else:
	y \|= 1 << now_digit
	b -= 1

	# 下の桁から計算する
	for now_digit in range(60):
	# input_cのnow_digit桁目が0の場合、xのn桁目かyのn桁目の両方が0、または両方が1である
	# aとbが両方余っている場合のみ1にする
	if ((input_c >> now_digit) & 1 == 0) and a > 0 and b > 0:
	x \|= 1 << now_digit
	y \|= 1 << now_digit
	a -= 1
	b -= 1

	# 出力
	if a == 0 and b == 0:
	print(x, y)
	else:
	print(-1)

view raw atcoder-abc-347-d-2.py hosted with ❤ by GitHub

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

「解説 - AtCoder Beginner Contest 347」
Editorial - AtCoder Beginner Contest 347
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う」
Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う | note.nkmk.me
Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと, データをキューやスタック, デック（両端キュー）として効率的に扱うことができる. collections.deque --- コンテナデータ型 — Python 3.11.4 ド ...
nkmk様による「Pythonで2進数の1の数をカウント（int.bit_count）」
Pythonで2進数の1の数をカウント（int.bit_count） | note.nkmk.me
Pythonで, 整数intの2進数表記における1の数（立っているビットの数）をカウントする方法について説明する. このような処理はpopcount（population count）とも呼ばれる. int.bit_count()（Python 3.10以降） bin(s ...

AtCoder Beginner Contest 347をPythonで解く

A - Divisible

B - Substring

C - Ideal Holidays

D - Popcount and XOR

E以降

参考にしたサイト等

0 件のコメント:

コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)

Search

About Me

Labels

Blog Archives

Twitter