1回の操作で多く塗りたい。行、列の長い方を選ぶと1回で $\max(H,W)$ 個塗れる。$N$ を割って切り上げた値が答え。
h = int(input()) w = int(input()) n = int(input()) print((n - 1) // max(h, w) + 1)
ロボットを、$[X_i-L_i, X_i+L_i)$ を覆う1つの区間と見なすと、これは区間スケジューリング問題そのものである。
右端が左にある区間から順に、残せるなら貪欲に残していけばよい。
典型とはいえ、ABCなら200点ではまず出されない気はする。ただ、問題の配点は1つのコンテスト内での相対的な関係以外、あまり参考にしない方がよい。
import sys
from operator import itemgetter
n = int(input())
robots = []
for line in sys.stdin:
X, L = map(int, line.split())
l, r = X - L, X + L
robots.append((l, r))
robots.sort(key=itemgetter(1))
curr = -1
ans = 0
for l, r in robots:
if curr > l:
continue
ans += 1
curr = r
print(ans)
問題Bとは打って変わって、思いつけば「え、そんなんでいいの」というような問題。
$0 \le K \le N$ という制約が鍵。つまり単独で $A_i=S$ であるような要素を $K$ 個作り、他の区間では和が $S$ にならないようにすれば、それで条件を満たす。
他の区緩和が $S$ にならないようにするには、たとえば $K$ 個以外の要素を $S$ より大きい数にすればいい。
ただし、$S=10^9$ の場合のみ、要素を $10^9$ より大きくはできないので、たとえば1にする。$N \le 10^5$ より、どんなに1が連続しても区間和が $10^9$ になることは無い。
n, k, s = map(int, input().split()) print(*([s] * k + [1 if s == 10 ** 9 else s + 1] * (n - k)))
$N$ も $A_i,B_i$ も小さい。
まず、手元で簡単な例を試すと、以下の点に気付く。
これで、カードを最終的に置く場所が決まれば、裏表の場合分けはしなくて済む。
しかし、最終位置は $N!$ 通りあるので、まだ全探索は不可能。動的計画法的に情報をまとめるか、枝刈りが必要。
最終位置を左から決めていくことを考える。
初期位置 1 2 3 4 5 最終位置 4 2 5 1 3
この最終位置に対する操作回数は転倒数であり、左から順に要素を確定させていった回数と一致する。 未確定のカードは初期位置順に並び、未確定の中で $k$ 番目のカードを左に持って行くには $k-1$ 回の操作がかかる。
4を移動 4 | 1 2 3 5 3回 2を移動 4 2 | 1 3 5 1回 5を移動 4 2 5 | 1 3 2回 1を移動 4 2 5 1 | 3 0回 => 計6回
左から $j$ 番目の位置まで確定していて、残りの部分からスコアを求めるには、どういった情報が必要か。
よって、以下のDPを考える。
これを、立っているbitの数が多い方から埋めていくと、$DP[0][num]$ の中で、最小の値を持つものが答えとなる。
計算量は、grpが $2^N$ 通り、$num$ も $A_i,B_i$ の値の種類数つまり最大 $2N$ 通りの状態があり、各遷移が $N$ かかるので、$O(N^2 2^N)$ となる。
一方、操作回数と最右の数字を入れ替えたこんなDPも作れるが、
こちらは、$op$ の状態数が大きくなりすぎるため、TLEとなる。 $A_i,B_i$ の範囲が小さいことを利用する。
def iter_bit(k, LIMIT):
v = (1 << k) - 1
while v < LIMIT:
yield v
x = v & -v
y = v + x
v = (v & ~y) // x >> 1 | y
def solve(n, cards):
dp = [{} for _ in range(1 << n)]
dp[-1][0] = 0
LIMIT = 1 << n
for d in range(n):
for state in iter_bit(n - d, LIMIT):
scores = dp[state]
k = state
curr = 0
while k:
b = k & -k
i = b.bit_length() - 1
num = cards[i][(d - i) % 2]
next_dp = dp[state ^ b]
for left_num, score in scores.items():
if left_num > num:
continue
ns = score + curr
if num not in next_dp or next_dp[num] > ns:
next_dp[num] = ns
k ^= b
curr += 1
if len(dp[0]) > 0:
return min(dp[0].values())
else:
return -1
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))
最小の $D_i$ を考えたとき、わりと可能な状態は少ないことに気付く。以下の例で、5が最小の $D_i$ であるとする。
b --- 5 --- a --- g --- f 数字,記号はDiを表す
`--- d ---' 便宜上、頂点のこともDiで呼ぶ
異色の頂点に距離5でたどり着くには、当然、その最短路に含まれる辺には5以下の重みをつけなければならない。
(頂点5の条件を満たす塗り分け方と重みの設定例) 頂点 5 --- a --- g --- f 色 B B B W 重み 1 3 1
しかし、5からまず最初に出る辺(5-a)を考えると、
なので、$a=5$ の時のみ、条件を満たす方法が存在する。
より広げていうと、ある頂点 $D_i$ に対してそこから直接繋がる頂点の内、最小のものを $D_j$、辺を $L_{i,j}$ とすると、
これを全ての頂点に対して繰り返す。矛盾する頂点が1つでもあると不可能。
サンプル1（丸付き数字はDi）
③--------④-----⑤-----⑦
`---③---'
注目中の頂点を黒丸で示す。
❸--------④-----⑤-----⑦ ❸にとって、隣接中最もDjの小さい頂点は③
3`--③---' よってその間の辺の重みを3に設定
③--------④-----⑤-----⑦ ❸にとっても同様
3`--❸---'
③----4---❹-----⑤-----⑦ ❹にとっては隣接最小は③（2つあるが、どちらか一方）
3`--③---' その間を4に設定
③----4---④--5--⑤--7--⑦ 以下同様。
3`--③---' ←の③-④を結ぶ辺は最後まで設定されなかった
この過程で重さが設定される辺数は、1頂点から1辺が設定されるので最大 $N$ 辺（重複する可能性はある）。 他の辺を最大値 $10^9$ にしておけば、とりあえず色を無視して「一番近い頂点に距離 $D_i$ で行ける」という距離の要件は満たす。
後は、その $N$ 辺の各辺について両端の頂点の色を逆にすると、条件を満たせる。
懸念点としては、$N$ 辺に奇数長の閉路が含まれると、隣り合う頂点同士が異なるように塗れない。 しかし、最も $D_j$ が小さい頂点を選んでいるため、閉路ができるのは閉路中の頂点が全て同じ $D$ を持つ場合しかありえない。 また、それも「$D_j$ が同じ場合は、辺番号（または頂点番号）が小さいものを優先する」とタイブレークを一意にしておけば防げるため、閉路の可能性は除外できる。
結果として $N$ 辺のみからなるグラフは森となり、連結成分ごとにDFSなどで隣り合う頂点を別にしながら色を設定していけばいい。
import sys
from operator import itemgetter
def solve(n, m, ddd, links):
ddi = list(enumerate(ddd))
ddi.sort(key=itemgetter(1))
LIMIT = 10 ** 9 + 1
costs = [LIMIT] * m
for v, dv in ddi:
du, li, u = min(links[v])
if du > dv:
print(-1)
return
costs[li] = dv
colors = [-1] * n
for i in range(n):
q = [(i, 0)]
while q:
v, color = q.pop()
if colors[v] != -1:
continue
colors[v] = color
for du, li, u in links[v]:
if costs[li] == LIMIT:
continue
q.append((u, color ^ 1))
MAX = 10 ** 9
costs = [MAX if cost == LIMIT else cost for cost in costs]
print(''.join('BW'[c] for c in colors))
print('\n'.join(map(str, costs)))
n, m = map(int, input().split())
ddd = list(map(int, input().split()))
links = [[] for _ in range(n)]
for li, line in enumerate(sys.stdin):
u, v = map(int, line.split())
u -= 1
v -= 1
links[u].append((ddd[v], li, v))
links[v].append((ddd[u], li, u))
solve(n, m, ddd, links)