ブログで書いてほしい内容受付中!!

AtCoder Beginner Contest 128を解きたかった【Python3】

こんにちは。

最近マジで忙しくて AtCoder なんてやってる暇ねぇだろ!!って感じなんですが、現実逃避のためにこの土日は ABC に参加しました。

日曜に開催された ABC128 の記録です。 C まではわりとスムーズに解けましたがその後死にました。

サトゥー

まだ緑までの道は長そうです

ABC128 A – Apple Pie

林檎が \(A\) 個、林檎の欠片が \(P\) 個あります。
林檎 \(1\) 個は、砕くことで林檎の欠片 \(3\) 個になります。また、林檎の欠片 \(2\) 個を鍋で煮込むことで、アップルパイが \(1\) 個作れます。
今ある材料で作れるアップルパイの最大数を求めてください。

https://atcoder.jp/contests/abc128/tasks/abc128_a

りんご \(A\) 個 = かけら \(3 * A\) 個ですから、合計でかけらが \(3 * A + P\) 個。これを2で割った商が作れるアップルパイの最大個数ですね。

解答案

A, P = map(int, input().split())
print((A * 3 + P) // 2)

ABC128 B – Guidebook

あなたは美味しいレストランを紹介する本を書くことにしました。 あなたは \(N\) 個のレストラン、レストラン \(1\) 、レストラン \(2\) 、…、レストラン \(N\) を紹介しようとしています。レストラン \(i\) は \(S_i\) 市にあり、あなたは \(100\) 点満点中 \(P_i\) 点と評価しています。異なる \(2\) 個のレストランに同じ点数がついていることはありません。
この本では、次のような順でレストランを紹介しようとしています。
・市名が辞書順で早いものから紹介していく。
・同じ市に複数レストランがある場合は、点数が高いものから紹介していく。
この本で紹介される順にレストランの番号を出力してください。

https://atcoder.jp/contests/abc128/tasks/abc128_b

これは複数の要素についてソートをして出力したいという問題。こういうときは多重キーでのソートを活用します。

多重キーでのソート

たとえば、次のようなリストがあったとします。

# [アルファベット、数a, 数b]
A = [["ABC", 1, 3], ["ZBC", 3, 2], ["DEF", 1, 4]]

このリストを、数aの小さい順にソートするときは次のようにします。

print(sorted(A, key = lambda x: x[1]))

>>>  [["ABC", 1, 3], ["DEF", 1, 4], ["ZBC", 3, 2]]

ただ、数aについては ["ABC", 1, 3]["DEF", 1, 4] はともに 1 で等しくなっています。
これを比較するために、この2つについては数bの大きい順にソートすることにしましょう。

print(sorted(A, key = lambda x: (x[1], -x[2])))

>>>  [["DEF", 1, 4], ["ABC", 1, 3], ["ZBC", 3, 2]]

てなかんじで、 key のところに複数個指定してあげることで、先頭のキーから優先的に、順番にソート処理を行ってくれるっぽいですね。

解答案

これをもとに B 問題の解答を考えてみます。最終的に出力するのが番号なので、番号も一緒に入れ込んだリストを生成しておきます。

N = int(input())
X = [[input().split(), i + 1] for i in range(N)]
X = sorted(X, key = lambda x:(x[0][0], -int(x[0][1])))
for i in range(N):
	print(X[i][1])

こんな感じで AC 。

ABC128 C – Switches

on と off の状態を持つ \(N\) 個の スイッチと、\(M\) 個の電球があります。スイッチには \(1\) から \(N\) の、電球には \(1\) から \(M\) の番号がついています。
電球 \(i\) は \(k_{i}\) 個のスイッチに繋がっており、スイッチ \(s_{i 1}, s_{i 2}, …, s_{i k_{i}}\) のうち on になっているスイッチの個数を \(2\) で割った余りが \(p_i\) に等しい時に点灯します。
全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。

https://atcoder.jp/contests/abc128/tasks/abc128_c

問題文を解読するのがやたら大変な気がしますが、 N が高々 10 までしかないので、 \(2 ^ N\) 通りの押し方を全部試しても計算間に合いそう。

ということで、 on/off の表現を 0/1 にすることで、 2 進数でパターンを表現することにし(この発想に至った自分天才では?)、愚直に全パターンを試してみます。

後々調べてみると bit 全探索っていう方法として典型的な手法とされていたようですが、そんなこと知らないのでゴリゴリ考えながらコードを書いてみます。

解答案

N, M = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(M)]  #sの各要素のはじめはk
p = list(map(int, input().split()))
ans = 0

# 0をoffとして2進数でパターンを表現

for i in range(2 ** N):
	ptn = bin(i)[2:].rjust(N, "0")  # N桁の2進表現にする
	light = True  # 着目している電球が点灯していないときはこれがFalseになる
	for j in range(M):
		tmp = 0  # 着目している電球について、スイッチのonの個数をカウントする
		for n in range(1, s[j][0] + 1):
			if ptn[s[j][n] - 1] == "1":
				tmp += 1
		if tmp % 2 != p[j] % 2:
			light = False
	if light:
		ans += 1

print(ans)

bit 全探索について

bit 全探索について、調べてみると練習としていい問題が見つかったので、練習したい方はこちらを是非。問題文が長いので端折ります。

ABC014 B – 価格の合計

問題文はリンクからご覧ください。https://atcoder.jp/contests/abc014/tasks/abc014_2

n, X = map(int, input().split())
*a, = map(int, input().split())
x = bin(X)[2:].rjust(n, "0")
ans = 0
for i in range(n):
	if x[i] == "1":
		ans += a[n - i - 1]
print(ans)

ABC128 D – equeue

あなたは誕生日プレゼントとして友人から dequeue \(D\) を貰いました。
\(D\) は左右に長い筒であり、\(N\) 個の宝石が一列に詰められています。
宝石の価値は左から順に \(V_1, V_2, …, V_N\) です。負の価値の宝石が詰められている場合もあります。
はじめ、あなたは \(1\) つも宝石を持っていません。
あなたは、\(D\) に対して以下の \(4\) 種類の操作から \(1\) つを選んで実行することを \(K\) 回まで行うことができます。
・操作 A: \(D\) に詰められた宝石のうち、左端の宝石を取り出して手に入れる。\(D\) が空の場合、この操作を行えない。
・操作 B: \(D\) に詰められた宝石のうち、右端の宝石を取り出して手に入れる。\(D\) が空の場合、この操作を行えない。
・操作 C: 持っている宝石を \(1\) つ選んで \(D\) の左端に詰める。宝石を持っていない場合、この操作を行えない。
・操作 D: 持っている宝石を \(1\) つ選んで \(D\) の右端に詰める。宝石を持っていない場合、この操作を行えない。
操作終了後に持っている宝石の価値の合計の最大値を求めてください。

https://atcoder.jp/contests/abc128/tasks/abc128_d

一度操作 C, D で詰めた宝石はもう一度取り出すことはないので、最後にまとめてやれば OK 、つまり一旦考えなくて OK ですね。

てなわけで、操作 A で取り出す操作と、操作 B で取り出す操作に着目します。ひとまず A で左から \(l\) 個、 B で右から \(r\) 個取り出すという方針で、あとはこの変数を動かせばイイ感じになりそう。

解答案

N, K = map(int, input().split())
*V, = map(int, input().split())
ans = 0

for l in range(K + 1):
	for r in range(K - l + 1):
		inHand = []
		if l + r > N:  # Nを超えてしまうありえない場合を処理
			break
		# inHandに左からl個、右からr個の要素を追加
		inHand = V[: l]
		inHand.extend(V[N - r:])
		tmp = sum(inHand)  # 現時点でのinHandの和をtmpとして負の要素をtmpから引いていく
		# inHand中の負の要素を消せるだけ消す
		inHand.sort()
		for i in range(min(K - l - r, l + r)):
			if inHand[i] >= 0:
				break
			tmp -= inHand[i]
		ans = max(ans, tmp)

print(ans)

コンテスト中に AC は取れませんでしたが、改めて見てみるとそこまで難しくないな、と。

うまく言語化できませんが、順番などの制約を考察でうまく単純化して、いかにして探索するだけの状態に持っていくかの勝負な感じがあります。

ABC128 E – Roadwork

東西に無限に続く \(1\) 本の大通りがあり、数直線とみなすことができます。
この大通り上で \(N\) 回道路工事が行われます。 \(i\) 番目の道路工事は時刻 \(S_i − 0.5\) から時刻 \(T_i − 0.5\) まで座標 \(X_i\) を通行止めにします。
\(Q\) 人の人が座標 \(0\) に立っています。 \(i\) 番目の人は時刻 \(D_i\) に座標 \(0\) を出発し、速度 \(1\) で正の方向へ歩き続けます。 歩いている途中で通行止めとなっている地点に到達した場合には、そこで歩くのをやめます。
\(Q\) 人それぞれが進む距離を求めてください。

https://atcoder.jp/contests/abc128/tasks/abc128_e

問題文は x 座標と 時間 t で x – t グラフを考えてみると結構かんたんに理解できますね。(ここから先は執筆途中)

サトゥー

F は知りません。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)