コンテンツにスキップ

貪欲法

タグ「貪欲法」の記事 10 件

SamCoding Round 10 (Div. 4) C - Chakra Run

忍者が数直線上を地点 00 から地点 LL まで走ります。11 メートル走るごとにチャクラを 11 消費し、最初はチャクラを cc 持っています。道の途中に nn 軒のラーメン屋があり、ii 軒目は地点 pip_i にあって、立ち寄るとチャクラが aia_i 増えます(チャクラに上限はありません)。到着した時点でチャクラがちょうど 00 でも立ち寄れます。地点 LL に着くまでに立ち寄る回数の最小値を求め、たどり着けないなら −1-1 を出力する問題です(n≤2×105n \le 2 \times 10^5、L,c,ai≤109L, c, a_i \le 10^9)。

立ち寄った店の集合を決めると、走れる距離は cc にその店の aia_i の和を足したものです。どの店に立ち寄るかの順番は関係なく、「地点 xx にたどり着けるか」は、xx より手前で立ち寄った店だけで決まります。

そこで、前から順に店を見ていき、通り過ぎた店をいったん「候補」としてためておきます。次の店(または地点 LL)までたどり着けないときは、それまでの候補の中から aia_i が最大の店に「さかのぼって立ち寄ったことにする」のを、たどり着けるようになるまで繰り返します。候補が尽きたらたどり着けないので −1-1 です。

各時点で、立ち寄る回数を増やすなら、手前の店の中で aia_i が最大のものを選ぶのが最も遠くまで走れます。なので、この貪欲法で立ち寄る回数が最小になります。候補から最大値を取り出すのは優先度付きキュー(ヒープ)でできるので、計算量は O(nlog⁡n)O(n \log n) です。

Python
import heapq
N, L, C = map(int, input().split())
PA = [tuple(map(int, input().split())) for i in range(N)]
PA.append((L, 0))
hq = []
ans = 0
for p, a in PA:
while p > C:
if not hq:
break
C -= heapq.heappop(hq)
ans += 1
if p > C:
print(-1)
break
heapq.heappush(hq, -a)
else:
print(ans)

C は「今たどり着ける最も遠い地点」として使っています。末尾に地点 LL を a=0a = 0 の店として足し、ゴールも店と同じように判定しています。heapq は最小値を取り出すヒープなので、−ai-a_i を入れて最大値を取り出しています。

repovive standard round 9 A - Pair Distances

位置 1,2,…,n1, 2, \dots, n に nn 人が並んでいます(nn は偶数)。全員を 2 人ずつのペアに分けます。人 ii は「自分とペアの相手の位置の差は did_i だ」と言っています。全員の言っていることが正しくなるようにペアに分けられるか判定する問題です(2≤n≤2×1052 \le n \le 2 \times 10^5、1≤di<n1 \le d_i < n、テストケースは最大 10410^4 個で nn の総和は 2×1052 \times 10^5 以下)。

左から順に、まだ相手が決まっていない人を見ていきます。

まだ相手が決まっていない人のうち一番左の人を ii とします。ii の相手は位置 i−dii - d_i か i+dii + d_i にいるはずです。しかし ii より左の人はすでに全員相手が決まっているので、i−dii - d_i は候補になりません。したがって、相手は j=i+dij = i + d_i に決まります。

このペアが作れるのは、次の 3 つをすべて満たすときです。

  • j≤nj \le n である。
  • jj の相手がまだ決まっていない。
  • dj=did_j = d_i である(jj から見ても相手との距離は did_i なので)。

満たしていれば ii と jj をペアにして先に進み、満たしていなければ答えは No です。最後までペアを作れれば答えは Yes です。相手が一通りにしか決まらないので、この方法で作れなければ、どう分けても作れません。

計算量は O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
D = list(map(int, input().split()))
pair = [None] * N
for i in range(N):
if pair[i] is not None:
continue
j = i + D[i]
if j not in range(N) or pair[j] is not None or D[j] != D[i]:
print("No")
break
pair[i] = j
pair[j] = i
else:
print("Yes")

位置は 0 始まりにしています。pair[i] は人 ii の相手の位置で、まだ決まっていなければ None です。j not in range(N) で、相手の位置が列の外に出ていないかを調べています。

for 文に付けた else は、break せずに最後まで回ったときだけ実行されます。途中で No を出力して break したときは Yes を出力しません。

SamCoding Round 9 (Div. 4) D - Printer Queue

nn 人の生徒が 1 台のプリンターで書類を印刷します。生徒 ii の書類の印刷には tit_i 秒かかります。プリンターは一度に 1 つの書類しか印刷できず、時刻 00 から休みなく順に印刷します。各生徒の待ち時間を「時刻 00 から自分の書類が印刷し終わるまでの時間」とするとき、印刷する順番をうまく決めて、待ち時間の合計の最小値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、1≤ti≤1061 \le t_i \le 10^6)。

印刷時間の短い順に印刷するのが最適です。

jj 番目に印刷する書類の印刷時間を sjs_j とすると、jj 番目の生徒の待ち時間は s1+s2+⋯+sjs_1 + s_2 + \dots + s_j です。待ち時間の合計では、sjs_j は jj 番目以降の n−j+1n - j + 1 人の待ち時間に含まれるので、

∑j=1n(n−j+1) sj\sum_{j=1}^{n} (n - j + 1) \, s_j

になります。前に印刷するものほど大きな係数が掛かるので、短いものを前に置けばよいです。

実際、隣り合う sj>sj+1s_j > s_{j+1} があれば、2 つを入れ替えると合計は sj−sj+1>0s_j - s_{j+1} > 0 だけ減ります。そのため、最適な順番では印刷時間が短い順に並んでいます。

あとは tt をソートして累積和をとり、その合計を出力すれば答えです。O(nlog⁡n)O(n \log n) です。

Python
from itertools import accumulate
input()
print(sum(accumulate(sorted(list(map(int, input().split()))))))

accumulate でソート後の累積和、つまり各生徒の待ち時間を求め、その合計を出力しています。

DOJ Beginner Contest 13 D - Vassals

頂点 11 を根とする NN 頂点の根付き木があり、頂点 ii (i≥2)(i \ge 2) の親は PiP_i です。各頂点 ii には容量 BiB_i があります。辺をいくつか選び、各頂点 ii に接する選んだ辺が BiB_i 本以下になるようにするとき、選べる辺の最大本数を求める問題です(2≤N≤2000002 \le N \le 200000、0≤Bi≤2000000 \le B_i \le 200000)。

葉の側から貪欲に決めます。頂点 uu を見るときには、uu の子の部分木の中の辺はすでに決まっているとして、次のようにします。

  1. uu の各子 vv について、vv の容量が残っていて、uu の容量も残っていれば、辺 (u,v)(u, v) を選びます。
  2. そのあと uu の容量が残っていれば、uu と親を結ぶ辺の候補になります。実際に選ぶかは親を見るときに決めます。

この貪欲が最適であることは、次の 2 つの入れ替えで示せます。

  • 子の部分木の中の辺を、親への辺より優先してよい。 子 vv が親への辺 (u,v)(u, v) を選ぶために、部分木の中の辺 (v,w)(v, w) をあきらめたとします。(u,v)(u, v) を外して (v,w)(v, w) を選び直しても本数は変わらず、uu の容量が 11 空くだけです。
  • 子への辺を、親への辺より優先してよい。 子への辺 (u,v)(u, v) を選べるのに、uu の容量を親への辺に使い切った最適解があるとします。親への辺を外して (u,v)(u, v) を選んでも本数は変わりません。vv の容量はほかに使い道がなく、親の容量は 11 空きます。

子どうしの間では、どの子との辺を選んでも uu の容量を 11 使うだけで、子の残りの容量はほかで使えないので、どれから選んでも同じです。

各頂点を帰りがけ順に 1 回ずつ見るだけなので、計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N);
VL(P, N - 1);
VL(B, N);
Tree<> tree(N);
rep(i, N - 1) {
tree.add_edge(i + 1, P[i] - 1);
}
RootedTree<> rooted(tree, 0);
vl dp(N);
for (ll u : rooted.postorder) {
for (ll v : rooted.child[u]) {
if (dp[v] && B[u]) {
B[u]--;
} else {
dp[v] = 0;
}
}
if (B[u] && u != rooted.root) {
dp[u] = 1;
} else {
dp[u] = 0;
}
}
print(sum(dp));
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

rooted.postorder は帰りがけ順に並べた頂点の列、rooted.child[u] は uu の子です。B[u] は子との辺を選ぶたびに減らすので、uu の残りの容量になります。

dp[u] は、uu を見終わった時点では「uu の容量が残っていて、親への辺の候補になるか」を表します。親を見たときに、その辺を選ばなかった子の dp[v] を 00 に戻すので、最後には dp[v] が「vv と親を結ぶ辺を選んだか」になり、その総和が答えです。

使用ライブラリ:cpp_include@4b58304

repovive starter round 10 B - Rise to the Occasion

長さ nn の整数列 aa と正の整数 x,yx, y が与えられます。カウンタ tt は最初 00 です。aa を好きな順に並べ替えてから順に見ていき、値 vv について t≤vt \le v なら tt を xx 増やし、そうでなければ tt を yy 減らします。最後の tt の最大値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、1≤x,y≤1091 \le x, y \le 10^9、−109≤ai≤109-10^9 \le a_i \le 10^9)。

aa を昇順に並べてシミュレーションした結果が答えです。

kk 個の値を見た時点の tt は、増やした回数を pp として px−(k−p)y=p(x+y)−kypx - (k - p)y = p(x + y) - ky です。よって、同じ個数を見た時点の 2 つのカウンタの値 t≤t′t \le t' の差は x+yx + y の倍数です。

t≤t′t \le t' のとき、同じ値 vv を見たあとも大小は逆転しません。両方が増える場合と両方が減る場合は明らかです。t≤v<t′t \le v < t' で tt だけが増える場合は、t′≥t+(x+y)t' \ge t + (x + y) なので t′−y≥t+xt' - y \ge t + x です(t>v≥t′t > v \ge t' となることはありません)。

したがって、途中のある時点でカウンタが大きいほうが、残りの並びが同じなら最後のカウンタも大きいか等しいです。

並びの中で u>vu > v が u,vu, v の順に隣り合っているとき、v,uv, u の順に入れ替えても、2 つを見たあとのカウンタは小さくならないことを示します。2 つを見る前のカウンタを tt とします。

  • t≤vt \le v のとき:どちらの順でも 1 つ目で増えて t+xt + x になります。2 つ目で増えるのは、元の順では t+x≤vt + x \le v のとき、入れ替えると t+x≤ut + x \le u のときで、後者のほうが条件が弱いです。
  • v<t≤uv < t \le u のとき:元の順では uu で増えて vv で減り、入れ替えると vv で減って uu で増えます(t−y<t≤ut - y < t \le u なので)。どちらも t+x−yt + x - y です。
  • u<tu < t のとき:どちらの順でも 1 つ目で減って t−yt - y になります。2 つ目で増えるのは、元の順では t−y≤vt - y \le v のとき、入れ替えると t−y≤ut - y \le u のときで、後者のほうが条件が弱いです。

どの場合も、入れ替えたほうが増える回数が多いか等しいので、カウンタも大きいか等しいです。上で示したことから、最後のカウンタも小さくなりません。この入れ替えを繰り返すと昇順になるので、昇順が最適です。

計算量はソートの O(nlog⁡n)O(n \log n) です。

Python
n, x, y = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
t = 0
for v in a:
if t > v:
t -= y
else:
t += x
print(t)

DOJ Beginner Contest 12 C - Nature-Friendly Village

R×CR \times C のグリッドの各マスは、家(#)か空き地(.)です。空き地に 1 本ずつ木を植えます。家ごとに周囲 8 マスに植えた木の本数を数え、その総和を KK 以上にしたいです。植える木の本数の最小値を求める問題です。できなければ −1-1 を出力します(0≤K≤8RC0 \le K \le 8RC、全テストケースの RCRC の総和は 10610^6 以下)。

総和を、木の側から数え直します。空き地 xx の周囲 8 マスにある家の個数を cxc_x とすると、xx に植えた木は、総和をちょうど cxc_x だけ増やします。したがって総和は、木を植えた空き地の cxc_x の和です。

この和を KK 以上にするには、cxc_x の大きい空き地から順に植えていくのが最善です。何本植えるにしても、同じ本数なら cxc_x の大きいほうから選んだときに和が最大になるからです。すべての空き地に植えても KK に届かなければ、答えは −1-1 です。

計算量はソートがいちばん重く、O(RClog⁡(RC))O(RC \log(RC)) です。

Python
from itertools import product
for _ in range(int(input())):
R, C, K = map(int, input().split())
S = [input() for i in range(R)]
l = []
for i, j in product(range(R), range(C)):
if S[i][j] == "#":
continue
c = 0
for di, dj in product(range(-1, 2), repeat=2):
if di == dj == 0:
continue
ni, nj = i + di, j + dj
if ni not in range(R):
continue
if nj not in range(C):
continue
if S[ni][nj] == "#":
c += 1
l.append(c)
l.sort()
s = 0
ans = 0
while l and s < K:
s += l.pop()
ans += 1
if s < K:
print(-1)
else:
print(ans)

l は空き地ごとの cxc_x の列です。昇順にソートして末尾から pop することで、大きいほうから取り出しています。s が KK に届くか、空き地がなくなるまで植えます。K=0K = 0 のときは 1 本も植えずに 00 を出力します。

ABC480 C - Self-Stopping Shower

シャワーのボタンを時刻 tt に押すと、時刻 tt から t+Kt + K までお湯が出ます(お湯が出ている間に押した場合も、最後に押した時刻から KK 秒間出ます)。NN 人の青木君が、それぞれ時刻 AiA_i にボタンを押します。時刻 00 から TT までずっとお湯が出ているようにするために、高橋君がボタンを押す回数の最小値を求める問題です(1≤N≤2×1051 \le N \le 2 \times 10^5、1≤K,T≤1091 \le K, T \le 10^9、0≤Ai≤1090 \le A_i \le 10^9)。

お湯が出ている時刻は、誰かがボタンを押した時刻 tt についての区間 [t,t+K][t, t + K] の和集合です。したがってこの問題は、青木君の区間 [Ai,Ai+K][A_i, A_i + K] に長さ KK の区間をいくつか足して、[0,T][0, T] を覆うときの、足す区間の個数の最小値を求める問題になります。

青木君の区間だけでは覆われない部分は、いくつかのすき間に分かれます。すき間の長さが gg なら、長さ KK の区間は少なくとも ⌈g/K⌉\lceil g / K \rceil 個必要で、すき間の左端から KK ずつずらして置けばちょうどその個数で覆えます。また、1 つの区間が 2 つのすき間にまたがることはありません。2 つのすき間の間には青木君の区間が丸ごと入っていて、またぐには長さが KK より大きくなければならないからです。よって、すき間ごとの ⌈g/K⌉\lceil g / K \rceil の和が答えです。

すき間は、青木君の押す時刻を小さい順に見ていけば求められます。今までの区間で覆われている右端を pp とします(はじめは p=0p = 0 です)。次の時刻 bb が p<bp < b なら、pp から bb までの長さ b−pb - p のすき間があります。最後に、TT を時刻の列に加えておくと、TT までに残ったすき間も同じように扱えます。TT 以上の時刻に押される分は [0,T][0, T] を覆うのに関係ないので、取り除いておきます。

計算量はソートがいちばん重く、O(Nlog⁡N)O(N \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, K, T);
VL(A, N);
vl B = {T};
for (ll a : A)
if (a < T)
B.push_back(a);
sort(B);
ll ans = 0, p = 0;
for (ll b : B) {
if (p < b)
ans += ceildiv(b - p, K);
chmax(p, b + K);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

B は、TT と、TT より前の青木君の時刻を並べてソートした列です。p が今まで覆えている右端で、b の前にすき間があれば ceildiv(b - p, K)(⌈(b−p)/K⌉\lceil (b - p) / K \rceil)回押します。そのあと b に押された分で、右端は b + K まで伸びます。Ai=0A_i = 0 の青木君がいないときは、最初のすき間に時刻 00 も含まれるので、高橋君が時刻 00 に押すことになります。

使用ライブラリ:cpp_include@9c33ee7

DOJ Beginner Contest 8 C - Mochi

NN 個の餅があり、ii 番目の餅の大きさは AiA_i です。まだ使っていない餅を 2 個選んで 1 組にできますが、上に置く餅は下に置く餅より真に大きくなければなりません。作れる組の最大数を求める問題です。

テストケースは T≤2×105T \le 2 \times 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

AA を小さい順に並べ替えておきます。

kk 組作れるなら、小さいほうから kk 個を下に、大きいほうから kk 個を上に、それぞれ小さい順に組にしても作れます。つまり、すべての ii (1≤i≤k1 \le i \le k) で Ai<AN−k+iA_i < A_{N - k + i} が成り立つかを調べれば判定できます。

理由を説明します。kk 組作れたとして、下の餅を小さい順に b1≤⋯≤bkb_1 \le \dots \le b_k、上の餅を小さい順に t1≤⋯≤tkt_1 \le \dots \le t_k とします。

  • 下の餅のうち大きいほうから k−i+1k - i + 1 個は、どれも bib_i 以上です。その上の餅は、それより真に大きいので bib_i より大きくなります。よって、bib_i より大きい上の餅は k−i+1k - i + 1 個以上あり、ti>bit_i > b_i です。
  • 小さいほうから ii 番目の AiA_i は bib_i 以下、大きいほうから数えた AN−k+iA_{N - k + i} は tit_i 以上です。

まとめると Ai≤bi<ti≤AN−k+iA_i \le b_i < t_i \le A_{N - k + i} が成り立ちます。

kk 組作れるなら、そこから 1 組外せば k−1k - 1 組も作れます。そのため、作れる最大の kk を二分探索で求められます。kk は ⌊N/2⌋\lfloor N / 2 \rfloor 以下です。

計算量は、並べ替えと二分探索で O(Nlog⁡N)O(N \log N) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
A.sort()
ok = 0
ng = (N + 2) // 2
while ok + 1 < ng:
mid = (ok + ng) // 2
if all(A[i] < A[N - mid + i] for i in range(mid)):
ok = mid
else:
ng = mid
print(ok)

二分探索では、ok 組は作れて、ng 組は作れない、という状態を保っています。ng の初期値 ⌊N/2⌋+1\lfloor N / 2 \rfloor + 1 は、どうやっても作れない組数です。

yukicoder contest 517 A - Happy End

英大文字からなる長さ NN の文字列 SS があります(5≤N≤3×1055 \le N \le 3 \times 10^5)。文字列 TT が「良い」とは、TT の末尾 5 文字が HAPPY で、それ以外の場所に HAPPY が部分文字列として現れないことをいいます。

SS の 1 文字を別の文字に書き換える操作を繰り返して SS を良い文字列にするとき、操作回数の最小値を求めてください。

末尾 5 文字は必ず HAPPY にしなければならないので、HAPPY と異なる文字の個数だけ書き換えが必要です。

次に、末尾以外に現れる HAPPY をすべて壊します。ここで大事なのは、HAPPY 同士は重なって現れないことです。HAPPY の中で H は先頭にしかないので、HAPPY の途中から別の HAPPY が始まることはありません。

そのため、末尾以外に現れる HAPPY は、末尾の HAPPY とも互いにも重なりません。重ならない HAPPY を 1 つ壊すには少なくとも 1 文字書き換える必要があり、1 回の書き換えで 2 つ同時に壊すこともできません。よって、末尾以外に現れる HAPPY の個数が、この段階で必要な操作回数の下限になります。

この下限は達成できます。各 HAPPY の 1 文字を、HAPPY に含まれない文字(たとえば Z)に書き換えればよいです。HAPPY に含まれない文字を含む位置からは新しい HAPPY が生まれないので、書き換えによって別の場所に HAPPY ができることはありません。

答えは 2 つの段階の操作回数の和で、計算量は O(N)O(N) です。

Python
N = int(input())
S = list(input())
ans = 0
for i in range(1, 6):
if S[-i] != "HAPPY"[-i]:
S[-i] = "HAPPY"[-i]
ans += 1
for i in range(N - 5):
if S[i : i + 5] == list("HAPPY"):
S[i + 4] = "Z"
ans += 1
print(ans)

前半のループで末尾 5 文字を HAPPY にそろえ、後半のループで末尾以外の HAPPY を見つけるたびに最後の Y を Z に書き換えています。

牛客小白月赛138 D - Light up the Graph

頂点 nn 個、辺 mm 本の単純無向グラフがあります。各頂点は白か黒で塗られています(文字列 ss の ii 文字目が 0 なら白、1 なら黒)。

好きな頂点の集合を点灯させます(何も点灯させなくてもよい)。各頂点について、隣接する点灯した頂点の個数をその頂点の「値」とします。白い頂点の値の総和から黒い頂点の値の総和を引いたものを最大化する点灯のしかたを 1 つ出力してください(n,mn, m の総和はそれぞれ ≤2×105\le 2 \times 10^5)。

頂点 vv を点灯させるとき cv=1c_v = 1、させないとき cv=0c_v = 0 とします。uu が白なら wu=1w_u = 1、黒なら wu=−1w_u = -1 とおくと、最大化したい値は

∑uwu∑v∈N(u)cv\sum_{u} w_u \sum_{v \in N(u)} c_v

です(N(u)N(u) は uu に隣接する頂点の集合)。

この式は「白い頂点 uu から見て、隣の何個が点灯しているか」を数えています。これを「点灯した頂点 vv から見て、隣に白と黒が何個ずつあるか」に数え直します。辺 (u,v)(u, v) ごとに足しているだけなので、和の順番を入れ替えて

∑vcv∑u∈N(v)wu\sum_{v} c_v \sum_{u \in N(v)} w_u

と書けます。tv=∑u∈N(v)wut_v = \sum_{u \in N(v)} w_u(vv に隣接する白い頂点の個数から、黒い頂点の個数を引いたもの)とおくと、値は ∑vcvtv\sum_v c_v t_v です。

tvt_v は cc によらない定数なので、各頂点の cvc_v は独立に決められます。tv>0t_v > 0 なら点灯させ、tv<0t_v < 0 なら点灯させなければ最大になります。tv=0t_v = 0 の頂点は、どちらにしても値は変わりません。

点灯させた頂点の色は関係ないことに注意してください。値に効くのは隣の頂点の色だけです。

tvt_v は各頂点の隣接リストを一度ずつ見れば求まるので、計算量は O(n+m)O(n + m) です。

1 つ目のサンプルの頂点 1 は、隣が頂点 4(白)と頂点 5(黒)なので t1=0t_1 = 0 です。そのため、サンプル出力では点灯させていますが、点灯させなくても最大値 44 は変わりません。

Python
for _ in range(int(input())):
N,M=map(int,input().split())
S=input()
g=[[]for i in range(N)]
for _ in range(M):
u,v=map(int,input().split())
u,v=u-1,v-1
g[u].append(v)
g[v].append(u)
ans = []
for u in range(N):
t = 0
for v in g[u]:
if S[v] == "0":
t += 1
else:
t -= 1
if t > 0:
ans.append(u+1)
print(len(ans))
print(*ans)

各頂点 u について、隣接する白い頂点を +1+1、黒い頂点を −1-1 として足した t を求め、正なら点灯させています。点灯させる頂点が 00 個のときは print(*ans) が空行を出力するので、問題の出力形式どおりになります。