#atcoder

In the realm of software development, competitive programming stands out as a thrilling and intellectually stimulating activity. It challenges programmers to solve complex problems under tight time constraints, fostering skills that are invaluable in both academic and professional settings. This blog delves into the world of competitive programming, exploring its significance, benefits, and the…

問題リンク

https://atcoder.jp/contests/abc365/tasks/abc365_g

公式解説1の考え方

公式解説に倣い、$i$番目の高橋くんがオフィスの中にいた時間の区間の集合を$S_i$とする。 クエリの組$(A, B)$について、下記パターンI, Ⅱに分けて考える。

パターンI： 愚直にイベントソートして処理。 高橋くんそれぞれのイベントを予め分けておく。 クエリの組$(A, B)$のイベントをマージ→重複している時間を求める。 クエリ1回あたり$O(C_{})$かかる(イベントは入力でソート済みなのでlogはかからない)。 クエリ$Q$回全部$C$以下があり得るので、クエリ全体で$O(QC)$かかる。

パターンⅡ： クエリの組$(A, B)$は、 ・$C$より大きい高橋くんが$\frac{M}{C}$ ・任意の高橋くんが$N$ この2種から1つずつ選ぶので$O(\frac{NM}{C})$個のクエリがパターンⅡに当てはまり得る。 これらクエリを予め計算してキャッシュし、クエリに答えるようにする。

$S_i$が$C$を超える高橋くんを$i$、任意の高橋くんを$x$として、クエリの組$(i, x)$をまとめて前計算する。 前計算1回あたり、イベント全走査して$x$を全通りキャッシュするので、時間計算量$O(N+M)$、空間計算量$O(N)$かかる。

$i$のあり得る個数は$O(\frac{M}{C})$ (イベント個数$M$から閾値$C$が何個取れるか)により、 キャッシュ計算全体で時間計算量$O(\frac{(N+M)M}{C})$ 空間計算量$O(\frac{NM}{C})$

$C=O(\sqrt{\frac{NM}{Q}})$ とすることで、 全体$O(\sqrt{NMQ}+M\sqrt{\frac{MQ}{N}})$で解ける。

提出コード https://atcoder.jp/contests/abc365/submissions/56695169

平方分割の考え方1

可能ならクエリの答えをすべて予め計算してキャッシュしたいが時間が掛かりすぎるため、 何個キャッシュを持っておくべきか？ →$\sqrt{N}$くらいキャッシュする キャッシュで持ちきれない分は都度愚直計算する。 都度愚直計算する負担が少ないものはどういう性質がある？ →$S$が小さいもの

平方分割の考え方2

クエリ全部を都度愚直計算で答えるとする。 愚直で答え切れるクエリ1回あたりの限界は？ →$S$が$\sqrt{M}$くらい 範囲外のものは予め計算しておいてキャッシュから答える。

公式解説2の考え方

合計が$M$のとき、$Q$個の相異なるペアについて小さい方の和は$O(M\sqrt{Q})$で抑えられる。 クエリ１つ捌くところで計算量を「ペアの小さい方log(ペアの大きい方)」になるように書けば間に合うイメージ。

$O(M√Q)$で抑えられる抑えられる理由のイメージは、 ペア$(A, B)$について、$A$も$B$も$M$への寄与分が同じときが一番きつい。 ペアに登場する要素の種類数が$x$のとき、その全組み合わせは${}_xC_2=O(x^2)$なので 要素の種類数を$\sqrt{Q}$個にして、$M$を$\sqrt{Q}$に均等に割り振るのが最悪ケース。 このとき要素一つあたり$O(\frac{M}{\sqrt{Q}})$、 クエリ$Q$個飛んでくるので$O(\frac{M}{\sqrt{Q}}*Q)=O(M\sqrt{Q})$。

クエリ１つ捌くところで計算量を「ペアの小さい方log(ペアの大きい方)」にするパートは ABC305D-Sleep Logと同じ。

クエリは相異なるペアである必要があるので、同じクエリが来たときようにキャッシュが必要な点に注意。

提出コード https://atcoder.jp/contests/abc365/submissions/56669241

問題リンク

https://atcoder.jp/contests/abc353/tasks/abc353_g

考察(セグ木)

公式解説(https://atcoder.jp/contests/abc353/editorial/9953)の解き方。

インラインDPを考えて、$dp[x]$を町$x$にいるときの所持金最大値とすると $i$番目の市場に参加したときの$dp[T[i]]$の更新は下記の通り。 (市場に参加するときのみ移動すると考える) $dp[T[i]]=P[i] + \max_{0\geq j<N}​ {dp[j]−C∣j−T[i]∣}$

$\max_{0\geq j<N}​ {dp[j]−C∣j−T[i]∣}$ を求めるところで、 公差$-C$の等差数列を足した上でのmaxが知りたいので、区間等差数列add区間maxが欲しくなる。

こういうときは、要素に予め $ -C*i, C*i$ を足した値をそれぞれ区間maxセグ木に乗せておく。 市場参加時のmaxを求めるときに、セグ木にクエリして得られた最大値に $C*T[i], -C*T[i]$ を足してずれを補正する。 セグ木の値を更新するときも、 $-C*i, C*i$ を足した値で更新するのを忘れずに。

提出コード https://atcoder.jp/contests/abc353/submissions/53402297

考察(Li Chao tree)

KumaTachiRenさんのユーザ解説(https://atcoder.jp/contests/abc353/editorial/9984)の解き方。

区間等差数列add区間min/maxはCHTの上位互換なので、区間等差数列add区間min/maxが欲しくなったときはまずCHTを疑う。

考察(セグ木)のときとは違って、$dp[x]$の更新を ・町$x$にいた状態で$i$番目の市場をスルーしてして、町$x$に居続ける ・$i$番目の市場に参加して、町$T[i]$から町$x$に移動してくる の最大値で書き換えと考える。 (市場参加後に各町に移動するところまでやるイメージ)

絶対値がついている場合は、正負の場合分けで絶対値を外すと考えやすいので $0\geq j<N$の$x$それぞれに対して、 $dp[x]$ $=\max(dp[x], P[i] + dp[T[i]] − C∣x-T[i]∣)$ $=\max(dp[x], Cx + P[i] + dp[T[i]] - CT[i]) (x<T[i])$ $ \max(dp[x], −Cx + P[i] + dp[T[i]] + CT[i]) (T[i]\geq x)$

maxの第2引数がxの一次関数になっているので線分追加のLi Chao treeで解ける。

提出コード https://atcoder.jp/contests/abc353/submissions/53404160

考察(区間等差数列add区間min)

区間等差数列add区間maxが欲しいので、そのまま実装する。 定数倍重いのでC++でしか通せない気がする。

考え方

食塩水候補をいくつか選んで混ぜたときにできる新食塩水の濃度の最大値は？のような問題。 基本は濃度$x\%$が達成できるか？の判定問題に落としてにぶたん。

食塩の重さを$A$, (食塩+水)の重さを$B$とすると ソート基準は $(\frac{A}{B}-x) * B$ もしくは $A - x * B$ で降順ソートして貪欲に選べばよい。 濃度$x\%$に必要な食塩と比較してどれだけプラスかを計算するイメージ。

ABC034D - 食塩水

https://atcoder.jp/contests/abc034/tasks/abc034_d

$A - x * B$でソート。 提出コード：https://atcoder.jp/contests/abc034/submissions/46661824

ABC294F - Sugar Water 2

https://atcoder.jp/contests/abc294/tasks/abc294_f

$A - x * B$でソート。 濃度$x\%$以上の砂糖水がK個以上作れるか？の判定問題。 提出コード：https://atcoder.jp/contests/abc294/submissions/46662307

ABC324F - Beautiful Path

https://atcoder.jp/contests/abc324/tasks/abc324_f

・濃度=食塩/(食塩+水), ・ABC324Fの求める値=美しさ/コスト で式が同じなので、 ・食塩=美しさ ・(食塩+水)=コスト で言い換えられる。 $A - x * B$でソート。 DAGなので普通に前からDPできる。 提出コード：https://atcoder.jp/contests/abc324/submissions/46661282

(おまけ)ABC236E - Average and Median

https://atcoder.jp/contests/abc236/tasks/abc236_e

・平均値最大化： $a_0, …, a_n$の平均値が$K$以上 $\Leftrightarrow (a_0-K)+ … +(a_n-K) \geq 0$ なので、 $b_i=a_i-K$とおいて、($b$から選んだ要素の総和)$\geq0$か判定

問題リンク

https://atcoder.jp/contests/abc314/tasks/abc314_e

考察

普通の期待値DP。 遷移に自分自身へのループがあるところの処理はEDPC J - Sushi と同じ。 https://atcoder.jp/contests/dp/tasks/dp_j

解説の 「$i$ 番目のルーレットが出しうる目 $P_i$​ 個のうち $Z_i$​ 個が 0 であるとき、このルーレットの代わりに $C_i​\frac{P_i}{P_i-Z_i}$ 円払ってもとのルーレットから 0 の目を取り除いたようなルーレットを用いることにしても結果は変わりません。」 の部分がよく分からなかったのでメモ。

これを一般化して、下記を考える。 ルーレットの出しうる目$A$個のうち、あたりが$A-t$個、はずれが$t$個ある。 ルーレットであたりが出るまで回し続けるとき、回す回数の期待値は？

期待値を求める式は、

$\frac{A-t}{A} + 2\frac{t}{A}\frac{A-t}{A} + 3(\frac{t}{A})^{2}\frac{A-t}{A} + \cdots$

$=\frac{A-t}{A} (1 + 2\frac{t}{A}+ 3(\frac{t}{A})^{2} + \cdots)$

$=\frac{A-t}{A} \lim_{n \to \infty} \sum_{k=0}^{n} {(k+1) * (\frac{t}{A})^k}$

$=\frac{A-t}{A} \lim_{n \to \infty} \frac{A^2 + (n+1)t^2(\frac{t}{A})^2 - A(n+2)t(\frac{t}{A})^n}{(A-t)^2}$

$=\frac{A-t}{A} \frac{A^2}{(A-t)^2} $

$=\frac{A}{A-t}$

となり、解説の式に一致する。

問題リンク

https://atcoder.jp/contests/abc310/tasks/abc310_f

考察

シンプルにdp[index][選んだサイコロの目の総和]で考えるとうまくいかない。

vector<vector<Modint>> dp(N + 1, vector<Modint>(11)); dp[0][0] = 1; rep(i, N) rep(j, 11) { repeq(k, min(10LL, A[i])) { ll nextj = j + k; if (nextj <= 10) dp[i + 1][nextj] += dp[i][j]; } dp[i + 1][j] += dp[i][j] * A[i]; } Modint ans = dp.back()[10]; rep(i, N) ans /= A[i]; cout << ans << '\n';

入力が 2 10 10 で、1つ目のサイコロ、2つ目のサイコロともに10が出たとする。 上のコードだと ・1つ目のサイコロを選んで2つ目のサイコロを捨てる ・1つ目のサイコロを捨てて2つ目のサイコロを選ぶ が別事象として扱われて2通りとしてカウントされる。 ただ、今回の問題では「10, 10が出た」という1通りの現象としてカウントを求められているので、これでは解けない。

DPは同一視したい状態をまとめて管理するのが鍵なので、 「出た目を使って総和に加算」「出た目を使わず総和そのまま」を1通りとして表現できるような状態設計が必要。

そこでdp[index][作成可能な総和を立てたbit]のbitDPを考える。 こうすることで、「出目kを使って総和に加算」「出目kを使わず総和そのまま」が

ll nextj = j | j << k;

でまとめて表現できる。

問題リンク

https://atcoder.jp/contests/arc137/tasks/arc137_b

考察

獲得可能なスコアの最小値〜最大値は全て達成できるので、取り得るスコアの最小値・最大値を求めればよい。 各始点でflipしたときのスコアの増加量、減少量を区間add区間maxの遅延セグ木で管理する。 解けるには解けるが遅延セグ木を持ち出す重厚感ある解法。

提出コード https://atcoder.jp/contests/arc137/submissions/43493156

考察+α

問題を少し言い換える。 ・数列$B$を$b_i = a_i == 0 ? 1 : -1$と定義する。 連続する区間を一つ選び、その総和をスコアとする。 取り得るスコアの最小値・最大値は？ 数列$B$はflipしたときのスコアの増加量を表している。

区間の終点をrに固定したとする。 スコアを最小化したいとき、始点lはその時点でのスコアが最も高いところを選びたい。 スコアを最大化したいとき、始点lはその時点でのスコアが最も低いところを選びたい。 (どちらも落差が一番大きいところを選びたいので)

累積和、および過去の累積和のうちの最小値・最大値を管理しておけば解ける。

問題リンク

https://atcoder.jp/contests/arc164/tasks/arc164_d

考察

括弧列の(と)を組み合わせるように+と-を組み合わせて、そのペア間の距離の総和を求めればよい。 $dp[index][c]$ := indexまで見て?に+をc個当てはめた時の総和・場合の数をそれぞれ管理する。

各電荷の寄与を考えるときに、累積和のような考え方を使う。 ペア間の距離を求めたい。 つまり、ペアの一方のインデックスがl, もう一方がrのときのr-lを足し合わせたい。 しかし、?の割り当て次第で誰がペアになるか分からない。

今のインデックスの文字が+であったときを考える。 (1)今のインデックスまでの電荷の総和が正であれば、さらに+を積むことになり、ペアの区間が新たに開始することになる。 (2)今のインデックスまでの電荷の総和が負であれば、余っている-と今の+でペアが完成し、ペアの区間が終了することになる。

(1)の区間開始時は-indexを、(2)の区間終了時は+indexを総和に加算することで、 r-lを足し合わせることに相当するので答えが求まる。

提出コード https://atcoder.jp/contests/arc164/submissions/43483636

考察+α

総和と場合の数をそれぞれ管理するDPでは二重数が便利らしい。 二重数は $\epsilon^2 = 0$ なる$\epsilon$を定義し、数を$a + b\epsilon$と表現する。

$dp, newdp = a + b\epsilon$の$a$で場合の数(kosu)を、$b$で総和(value)を管理するとして、

newvalue += value; newvalue += kosu * t; newkosu += kosu;

の3行が

newdp += dp * dual(1, t);

の1行で計算できる。

総和と場合の数をそれぞれ管理するとき、場合の数は単純に足し合わせるだけなので * dual(1, t); の1は常に固定でtだけ問題に応じて考えればよさそう。

提出コード https://atcoder.jp/contests/arc164/submissions/43484317

参考