【競プロ精進ログ】【2021/03/13】ABC194: D

競技プログラミングのための精進履歴をブログ形式で残していきます。

目標は AtCoder 水色！
今のレートは茶色です。

本日の精進ツリーは以下のとおり。

精進ツリー

ABC195: B – Many Oranges
ABC195: D – Shipping Center
まとめ

ABC195: B – Many Oranges

ABC195 より、 ABC195: B – Many Orangesを解きました。
難易度は茶色。

コンテスト中にテンパってスキップしてしまった問題です。
「UNSATISFIABLE」になる場合の条件が、 max が min と等しいときではなく、max と min が逆転したときにしていなかったのが、 AC できなかった原因でした。

この辺の実装の正当性の証明は雰囲気でやっているとこういうことになるといういい例でしたね。
ちなみに個数 N の取りうる値を全探索する方法でも解けたようです。

提出コードはこちら。

from math import floor, ceil

A, B, W = map(int,input().split())

W = W * 1000
max = floor(W / A)
min = ceil(W/ B)

if max < min:
    print("UNSATISFIABLE")
    exit()

print(min, max)

ABC195 より、 ABC195: D – Shipping Centerを解きました。
難易度は緑色。

貪欲法というのはすぐにわかったので解けそうではあったのですが、実装に手間取り間に合いませんでした。

各クエリごとにスキップしなくてはいけない箱がどれかを指定する部分の実装にバグがあったようです。
早解きも意識して訓練していかないといけないですね。

提出コードはこちら。

N, M, Q = map(int,input().split())
nimotsu = []
query = []

"""
NOTE: 
・荷物の価値の最大値は、貪欲法（？）で求められそう
・入れる荷物は多い順、試す箱は小さい順
  O(N^3) になるけど、N,M, <= 50 なので余裕
"""

for i in range(N):
    W, V = map(int,input().split())
    nimotsu.append((V, W))
nimotsu.sort(reverse=True)

X = list(map(int,input().split()))

for i in range(Q):
    l, r = map(int,input().split())
    query.append((l, r))

for q in query:
    l = q[0]
    r = q[1]
    Xbox = X[:l-1] + X[r:]
    Xbox.sort()
    val = 0
    for n in nimotsu:
        for i, x in enumerate(Xbox):
            if x < 0:
                continue

            if x >= n[1]:
                Xbox[i] = -1
                val += n[0]
                break

    print(val)