ABC017-C ハイスコア

 概要

https://atcoder.jp/contests/abc017/tasks/abc017_3

N個の区間とそれに対応する得点が与えられる。

それぞれ区間は1から始まる長さMの区間に含まれる。

区間を重ね合わせたときに1からMの区間と一致しないよう0個以上の区間を選ぶ。選び方について得点を合計し、その最大値を求めよ。

 解法

方針

区間[1,2)、区間[2,3)、...、区間[M, M+1)を含まないように区間を選んで得点を計算する。

求める解はその最大値となる。

優先度付きキューを使用し、将来使えなくなる区間と、現在使えない区間を管理する。

初期の除外区間を[0, 1)とすると、与えられた区間[L, R]はすべて将来使えなくなる区間に登録することになる。合計得点は与えられた区間の得点の合計値となる。

除外区間を1ずつ進めながら下記の処理を行うことで、すべての除外区間についての合計得点を求めることができる。

・将来使えなくなる区間のうち、左端が現在の区間にかぶるものは使えなくなるので、合計得点から得点を引き、現在使えない区間に登録する。

・現在使えない区間について右端が左のほうにあるものについて調べ、すでに左にあるものについては再び得点に加える。

https://atcoder.jp/contests/abc017/submissions/20210178

ABC013-C 節制

 概要

https://atcoder.jp/contests/abc013/tasks/abc013_3

N回次の3つの操作を選択する。初期値をHとする値hが一度も0にならないようにするとき、コストの最小値を求めよ。

・コストA払い、hにBを加算する

・コストC払い、hにDを加算する(C<A かつ D<B)

・コストは変化せず、hにEを減算する

解法

すべての日について3つ目の選択肢を選んだ場合、hはNEだけ減少する。

このとき、コストを払う選択肢を選ぶよう変更すると、最終的なhは(例えば)B+E増加する。

hが0以下になることが許されないので、求める答えはコストを払う選択肢をN回以下選択することで、H-NEを正の値にできる最小のコスト ということになる。

これは、以下の2つのパターンで

・k日間、1つ目の選択肢を取り続けたとして、H-NEに満たない場合については2つ目の選択肢を足りない分だけ加える

とすると、各日についてO(1)で払うコストを求めることができるので、全体としてO(N)で解を求められる。

https://atcoder.jp/contests/abc013/submissions/20193158

ABC027-C 倍々ゲーム

概要

A, Bの2人が交互に、2種類の操作から1種類を行う。Nを超える操作を行った方の負け。

初期値は1とする。
操作1: 数を2倍する。

操作2: 数を2倍し、1を足す。

解法

Nを2進数表記した際の桁数の偶奇により、A、Bがどちらの操作を選ぶが反転する。

完全二分木を書くとわかりやすい。

方針が決まればシミュレーションすれば正解できる。

ABC018-D バレンタインデー

ABC018-D バレンタインデー

概要

https://atcoder.jp/contests/abc018/tasks/abc018_4

N(<=18)人の男、M(<=18)人の女からそれぞれP、Q人選ぶ。

得点についての条件が、以下のような内容でR(<=N*M)個与えられる。

・男xと女yを含む選び方のとき、z(<=10000)点が得られる。

合計点を最大化せよ。

解法

　まず、男をP人選んだものとして考える。

このとき、各女を選んだときの得点がO(R)で求められる。

よって、男の選び方1つに対してO(R + MlogM)で得点が最大化できる。

　また、男の選び方は2^18通りを全探索することでP人選ぶパターンを網羅でき、26万通りの探索で最大 18P9 = 約45000通り が得られる。

　男のすべての選び方について得点を計算すると解が得られる。

https://atcoder.jp/contests/abc018/submissions/20169029