ABC 390感想まとめ
AtCoder Beginner Contest 390 - AtCoder
今回はABC3問解答でした。D問題の難易度が高く、4問解答はハードルが高かったです。。。
B問題の等比数列かどうかを判定するところで1ペナになりました。入力例・出力例のところで小数の例があり、小数点の誤差の危険を感じてはいたのですけども、それでもまんまと引っかかってしまいましたね...。
コンテストでは、D問題は排他的論理和が入っていて難しそうなのでパスし、E問題に着手しました（実際に、D問題は青色レベルの問題で難しかった模様）。E問題も難易度が高く、なんとなく実装方針は立ったものの正解には及ばずでした。
A - 12435
素直に A の要素 i と i+1 を入れ替えて、判定しています。
A = list(map(int, input().split()))
for i in range(4):
A2 = A.copy()
# i と i+1 を入れ替える
sw = A2[i]
A2[i] = A2[i + 1]
A2[i + 1] = sw
# ソート済Aと一致判定
if A2 == sorted(A):
print("Yes")
exit()
print("No")
B - Geometric Sequence
1ペナしてしまい悔しい問題。
理屈としては、「A[0]/A[1] の比率と A[i]/A[i+1] の比率が一致しているか」を、全探索で確認すれば良いのです。ただし、整数を割り算をすると答えが小数になってしまって、誤差が出てきたりします。
ですので、式変形して掛け算にします。
A[0]/A[1] == A[i]/A[i+1] → A[0]*A[i+1] == A[i]*A[1]
こうすると誤差が出ないわけですね...。
N = int(input())
A = list(map(int, input().split()))
if len(A) == 2:
print("Yes")
exit()
for i in range(len(A) - 1):
# 比率が一致しているか判定
if A[0] * A[i+1] == A[i] * A[1]:
continue
else:
print("No")
exit()
print("Yes")
C - Paint to make a rectangle
まず、最も小さい黒の長方形は、どのようなサイズかを考えます。
黒マス(#)が確定しているマスは動かせないので、黒マス(#)のうち 一番上のマス、一番下のマス、一番左のマス、一番右のマスを含むような長方形が、最も小さい黒の長方形になります。
先ほど求めた最も小さい黒の長方形の範囲の中に、一個でも白マス(".")があるとNGになります。ですので、そのような判定を行えば ok でした。
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
# 黒マスのうち、最も上下左右の位置はどこかを記録する
top = H - 1
left = W - 1
right = 0
bottom = 0
# 黒マスのうち、最も上下左右の位置はどこかを記録する
for i in range(H):
for j in range(W):
if field[i][j] == "#":
top = min(top, i)
left = min(left, j)
right = max(right, j)
bottom = max(bottom, i)
# 先ほど求めた範囲の中に、一個でも白マス(".")があるとNG
for i in range(top, bottom + 1):
for j in range(left, right + 1):
if field[i][j] == ".":
print("No")
exit()
print("Yes")
E - Vitamin Balance (解説で復習)
コンテスト中は解けなかったので、解説を見て復習しました。
解き方は以下です。
手順1. 各ビタミン値とカロリー値の対応配列を作成する
ビタミン1〜3について、「カロリーが index のとき ビタミン値が value」の対応表を作成します。入力例1の場合、こんな感じ。
dp1=[0, 0, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]
dp2=[0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
dp3=[0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
単調増加なので、二分探索で「ビタミン値 v1 のときのカロリーは ？」がすぐに求められます。
手順2. 2分探索で、「ビタミン値=v2 のとき、カロリーはX以下に収まりますか？」 の上限を探す
この手の問題でよくある、二分探索する手法。手順1の結果を使って、ビタミン値-カロリー の対応がわかるので、これもすぐに求められます。
import bisect
N, X = map(int, input().split())
AC1 = []
AC2 = []
AC3 = []
for i in range(N):
V, A, C = map(int, input().split())
if V == 1:
AC1.append((A, C))
elif V == 2:
AC2.append((A, C))
else:
AC3.append((A, C))
# DPで indexがカロリー、valueがビタミン量の配列を作成する
def crateDP(AC):
dp = [[0] * (X+1) for _ in range(len(AC)+1)]
for i in range(len(AC)):
a, c = AC[i]
for j in range(1, X+1):
if j - c >= 0:
dp[i+1][j] = max(dp[i][j], dp[i][j-c] + a)
else:
dp[i+1][j] = dp[i][j]
return dp[-1]
# 各ビタミンの カロリー - ビタミン量配列
dp1 = crateDP(AC1)
dp2 = crateDP(AC2)
dp3 = crateDP(AC3)
# ビタミン値が指定されたとき、カロリーXに収まるかを判定
def isEnable(value):
v1index = bisect.bisect_left(dp1, value)
v2index = bisect.bisect_left(dp2, value)
v3index = bisect.bisect_left(dp3, value)
enable = v1index + v2index + v3index <= X
return enable
# 二分探索で最大スコアを求める
left = 0
right = min(max(dp1), max(dp2), max(dp3)) + 1
while right - left > 1:
mid = (left + right) // 2
if isEnable(mid):
left = mid
else:
right = mid
print(left)