NS Solutions Corporation Programming Contest 2023(AtCoder Beginner Contest 303)F,G,Ex問題メモ

F - Damage over Time

問題

  • $N$ 種類の魔法で、体力 $H$ のモンスターに攻撃して0以下にしたい
  • 1ターンに1個の魔法を選んで使える
  • 魔法 $i$ をターン $t$ に使用すると、$t$ から $t+T_i-1$ の $T_i$ ターンにかけて、1ターン毎に $D_i$ のダメージを与える
    • 効果は加算で累積して、次ターンに魔法 $j$ を使うと $D_i+D_j$ のダメージを与える(魔法 $i$ が切れていなければ)
  • 最も早く倒すには何ターンかかるか、求めよ
  • $1 \le N \le 3 \times 10^5$
  • $1 \le H \le 10^{18}$
  • $1 \le T_i,D_i \le 10^9$

解法

二分探索が浮かんだが、無くても解けるみたい。でもせっかくだし二分探索解法をメモ。

魔法 $i$ は、時間いっぱいかければ計 $T_iD_i$ のダメージを与えるが、、、

H = 100

10000 ターン毎ターン   1 のスリップダメージ
    1 ターン毎ターン 100 のスリップダメージ

T*D が小さくても、2番目を使った方がいいのは明らか

ゴールが見えていないと、どれくらい先まで有効な魔法を使っていいのか、見えづらい。

なので、ゴールを固定し「$K$ ターンまでに倒せるか?」の判定問題が $O(N)$ くらいで解ければ、二分探索で $O(N\log{H})$ で求められる。

判定問題

いま、$K$ まで残り $r$ ターンとする。

$T_i$ が $r$ 以上か、未満かで分ける。(その魔法の集合をそれぞれ $X,Y$ とする)

  • $X$ から選んで使うとしたら、有効なターン数は $r$ なので、計 $rD_i$ の総ダメージ
    • → $D_i$ 最大のものを使うべき
  • $Y$ から選んで使うとしたら、フル($T_iD_i$ の総ダメージ)で与えられる
    • → $T_iD_i$ 最大のものを使うべき

総ダメージの大きい方を使う。図化すると、

D ↑
  |───┐
  |      │
  |───┼──┐
  |───┼──┼──┐
  +----------------|-----> T,残りターン
                    r

各長方形が魔法で、r より左のやつは面積が一番大きいの、
                    右にはみ出てるやつは一番高いのを選んで使う

魔法を1回使うと、$r$ が1減る。同時に $X$ の魔法で与えられる総ダメージも減る。

$H$ が馬鹿でかいので、1ターンずつこれを処理しているとTLE。
変曲点毎にまとめて処理する。(変曲点:使う魔法を変えた方が得になる可能性がある点)

変曲点は、以下の2つ。

  • はじめ、$X$ を使った方がダメージが大きかったが、途中から $Y$ を使った方がよくなる $r$
  • $Y$ から $X$ に移る魔法がある $r$

1つめは、$T_yD_y/D_x$ で出せる。
2つめも、あらかじめソートしておけば次に来る $T_i$ は分かる。

このような変曲点は、ざっくり見積もりで最大 $2N$ 個あるので、計算オーダーもその程度となる。

細かな注意点として、

  • $T_iD_i$ 基準と $T_i$ 基準でそれぞれソートした配列がほしくなるが、これは二分探索で毎回ソートしていると $O(\log{N})$ が余分にかかってしまう。結果は不変なので、全体で1回ソートしたものを使い回せる
  • $X$ の魔法を繰り返し使う場合、有効ターンが1ターンずつ減っていくので、延べターン数は等差数列の和になる

Python3

解法2

解法1と近い考え方で、二分探索が不要であるようにできる。(むしろ二分探索考察時に、何故これに気がつかないのか)

ターンを逆順から考える。
先ほどの説明中の、残りターン数 $r$ を、$r=1$ から徐々に増やしていく感じ。

「今が何ターン目かは分からないが、倒しきる最終ターン」であると考える(ちょっと奇妙だが)。
$r=1,2,3,...$ の時々に最適な魔法は決まるので、その総ダメージの合計値が $H$ になった時が、倒せるターン。

1魔法当たりの総ダメージのグラフは以下のような感じになる。

f(i,r): 残りターン r で放った魔法 i が与える総ダメージ

 総ダメ↑
       |
 Dk*Tk_|              ____↙魔法 k の線
 Dj*Tj_|       _____-~____↙魔法 j の線    斜線の傾きが各 $D$ を表す。
 Di*Ti_|  ___/__-~_______↙魔法 i の線
       | / /_-~
       |//-~
       ┼-------------------> r
          Ti   Tj     Tk

$r$ を増やしてって、$r$ ごとに $\max_i f(i,r)$ を合計していき、 合計が $H$ になればその時の $r$ が答え。

解法1と同様、変曲点(グラフの屈折点、または最適な魔法が変わる交点)毎にまとめれば、 $O(N)$ で $r$ までの総ダメージを計算できる。

G - Bags Game

問題

  • $N$ 個のバッグが横一列に並び、$i$ 番目には $X_i$ 円入っている
  • 太郎と次郎が、太郎を先手として交互に、以下の3つから1つ選んで行動する
    • 残っている両端のどちらかのバッグから1個取る
    • $A$ 円失う。「残っている両端のどちらかのバッグから1個取る」ことを $B$ 回まで繰り返す
    • $C$ 円失う。「残っている両端のどちらかのバッグから1個取る」ことを $D$ 回まで繰り返す
  • バッグがなくなるまで繰り返し、最終的に「バッグから獲得した金額 - 失った金額」を利得とする
    • (※利得が負になるだけで、2,3番目の行動はいつでも取れる)
  • 「自分の利得 - 相手の利得」を「スコア」とし、両者、これを最大化するように行動する
  • 太郎が実現できるスコアの最大値を求めよ
  • $1 \le N \le 3000$
  • $1 \le X_i,A,C \le 10^9$

解法

バッグは常に連続した区間が残り続ける。問題設定的にも、制約的にも、いかにも区間DPっぽい。

行動指針や取れる行動が、太郎も次郎も変わらないので、 「ある盤面から、次に行動する方(先手)が実現できるスコア」は、太郎も次郎も一緒。

また、行動指針が「自分 - 相手」なので、
「ある行動をして、その後、ある盤面を相手に引き渡したときのスコア」は、
「その行動によって得られた利得 - その盤面から先手が実現できるスコア」となる。

以下のDPを考える。

  • $DP[w,l]=$ 長さ $w$、左端 $l$ の区間のバッグから始めて、先手が実現できるスコア

(通常、区間DPは $[l,r)$ の区間を添え字 $(l,r)$ で表現することもあるが、今回はこっちの方がやりやすい)
$r=l+w$ となる。

初期値を

  • $w=0$ の場合は $DP[0,*]=0$
  • $w=1$ の場合は $DP[1,l]=X_l$

として、狭い区間から、より広い区間を求めていく。

$[l,r)$ の時に取れる行動は、

      l                    r
...   o  o  o  o  o  o  o  ...

      x  o  o  o  o  o  o    左端を取る
      
      o  o  o  o  o  o  x    右端を取る
      
      x  x  o  o  o  x  x    A円払ってB個取る(この例では4)
      
      x  o  o  x  x  x  x    C円払ってD個取る(この例では5)

それぞれ、「x のバッグに入っている金額の和 - 支払った金額 - 残った区間のDP結果」がスコアになるので、 その中の最大値を取れば良い。

ただ、$A$ 円払う行動では、どの区間を残すかが $B+1$ 通りある。

制約的に、$O(N^2)~O(N^2 \log{N})$ くらいまでしか許容されないので、これを1つ1つ調べることは $O(N^3)$ となりできない。
これを効率的に計算したい。

高速化

$DP[l,r]$ を求めるに当たっての行動 $(A,B)$ の最適なスコア計算を考える。($(C,D)$ も同様に考えられる)

(取ったバッグに入っている金額の和 - 支払った金額 $A$ - 残った区間のDP結果)をよく考えると、

  • 取ったバッグに入っている金額の和 = (区間 $[l,r)$ の $X$ の和) - (残した区間の $X$ の和)

なので、残す区間を $[p,q)$ として、

  • (区間 $[l,r)$ の $X$ の和) - (区間 $[p,q)$ の $X$ の和) - $A$ - (区間 $[p,q)$ のDP結果)

「区間 $[l,r)$ の $X$ の和」と「支払った金額」は一定なので、結局

  • (区間 $[p,q)$ の $X$ の和) + (区間 $[p,q)$ のDP結果) … ①

を最小化するような $[p,q)$ を選べばよいことになる。

区間長 $w$ から $B$ 個取ったときに残るのは $w-B$ 個なので、$DP[w-B,(p=0,1,...)]$ から①をそれぞれ求めておく。 ($Y_p$ とする)

$[l,r)$ を求めるときに使うのは $p=l~l+B$ なので、$Y_l~Y_{l+B}$ の最小値が求められればよい。

この区間最小値は、$l+1,l+2,...$ のDPを求めるときにも使い回したいことを考えると、スライド最小値などで求められる。

スライド最小値だと、$w$ ごとに $O(N)$ なので、全体で $O(N^2)$。セグメント木に載せてもよくて、$O(N^2 \log{N})$ となる。

「1つずつずれた区間の値を示す数列の、さらに区間最小値」を求めるので、添字など混乱してしまう。頑張る。

Python3

Ex - Constrained Tree Degree

問題

  • $N$ 頂点の木のうち、以下の条件を満たすものの個数を $\mod{998244353}$ で答えよ
    • 全ての頂点は区別できる(ラベル付き木)
    • どの頂点の次数も、与えられる $K$ 個の整数集合 $S=\{S_1,...,S_K\}$ に含まれる
  • $2 \le N \le 2 \times 10^5$

解法

知識寄りの問題。

ラベル付き木は、プリューファーコードと呼ばれる数列に変換できることが知られている。

数列の個数を数え上げることで、木の個数も数え上げられる。

頂点 $i$ の次数を $d_i$ とすると、$i$ はプリューファーコードにおいて必ず $d_i-1$ 回現れる。
(葉から処理する過程で、隣接する葉が消される時に自身が記録され、自身が葉になり処理される最後の1回は記録されないため)

プリューファーコードの長さは $N-2$ なので、

  • 各 $i$ につき、$d_i \in S$
  • $(d_1-1)+(d_2-1)+...+(d_N-1)=N-2$

の2つを満たすような全ての $(d_1,...,d_N)$ の組み合わせについて、

  • 1 を $d_1-1$ 個、2を $d_2-1$ 個、、、$N$ を $d_N-1$ 個並べるときの並べ方の個数は?
  • → $\displaystyle \frac{(N-2)!}{(d_1-1)!(d_2-1)!...(d_N-1)!}$

を足し合わせたものが答えとなる。

分母のような形の計算は形式的冪級数を使うと表現しやすく、たとえば $S=\{1,4,6\}$ のとき、

  • $X = \dfrac{1}{0!}x^0 + \dfrac{1}{3!}x^3 + \dfrac{1}{5!}x^5$

という1頂点当たりの情報をもった $X$ を想定すると、$X^N$ における $x^{N-2}$ の係数に

  • $\displaystyle \sum_{条件を満たす全ての (d_1,...,d_N)}\frac{1}{(d_1-1)!(d_2-1)!...(d_N-1)!}$

が現れるので、$(N-2)!$ をかけたものが答えとなる。

繰り返し二乗法の要領で畳み込みをおこなうことで、$O(N(\log{N})^2)$ で答えが求められる。

Python3

programming_algorithm/contest_history/atcoder/2023/0527_abc303.txt · 最終更新: 2023/06/02 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0