2 3 12 19 22 26 ■ 2023 年 8 月 26 日
やつたこと
- 精進
- Educational DP Contest J
- 動的計画法． E_{i, j, k} を寿司が 1, 2, 3 個乗つた皿がそれぞれ i, j, k 枚あるときの操作回数の期待値とすると，以下の漸化式が成り立つ．
- E_{i, j, k} = (i/N)(E_{i-1, j, k} + 1) + (j/N)(E_{i+1, j-1, k} + 1) + (k/N)(E_{i, j+1, k-1} + 1) + ((N-i-j-k)/N)(E_{i, j, k} + 1).
- diverta 2019 Programming Contest 2 C
- A を昇順に整列し， A_1, ..., A_N とする．うち， A_1, ..., A_i が負， A_{i+1}, ..., A_N が非負とする．
- まづ， i-1 回操作をして， A_N - A_2 - ... - A_i を作る（これを X とする）．次に N-i-1 回操作をして A_1 - A_{i+1} - ... - A_{N-1} を作る（これを Y とする）．最後に X-Y とすれば最大化が達成される．
- これは負数と非負数の両方が存在する場合のみ成り立つ．負数だけ，非負数だけの場合も似たやうに考へればわかる．
- ABC 164 D
- S の i 文字目から j 文字目までを 10 進数として解釈した数を T_{i, j} とする．
- T_{i, j} = T_{1, j} - T_{1, i-1} * 10^{j-i+1} なので，これが 2019 の倍数になるのは， mod 2019 で以下が成り立つとき．
- T_{1, j} * 10^{-j} = T_{1, i-1} * 10^{-(i-1)}.
- 2019 = 3 * 673 なので， 10 の逆数を取つてもいい，はず．
- よつて，数列 (X_i) を X_i = T_{1, i} * 10^{-i} mod 2019 で定義して， i
- X_i = 0 mod 2019 なる i はそれ単体で 2019 の倍数となるので，最後に個数に加へる必要がある．
- AGC 3 B
- 動的計画法． X_{i, j} を 1 から i までのカードで作れるペアの個数の最大値であつて，かつ i のカードを j 枚残すもの（i のカードを A_i - j 枚使ふもの）とする．ただし j = 0, 1 である（同じ数字のカードを 2 枚以上残す場合は最大値とならないため）．
- 遷移式は A_i が奇数，非零の偶数，零の 3 通りで場合分けする必要がある． i が書かれたカードが 1 枚も無ければどうやつても 1 枚残すことができない為．
- ABC 264 E
- ABC 266 E
- 動的計画法． E[i][X] を i ターン目で X の目が出たときのスコアの期待値とすると， E[i][X] = max(X, \sum_{x=1}^6 E[i+1][x] / 6).
- ABC 198 D
■ 2023 年 8 月 22 日
やつたこと
- 精進
- 前回期待値で冷えたので，期待値 DP を埋めることにする．
- https://kenkoooo.com/atcoder/#/contest/show/3e870f02-b970-48d6-976d-3d1cfbb776d4?activeTab=Problems
- ABC194D
- これは DP なのか・・・？
- N 個の点のうち， i 個の点が (頂点 1 と) 連結になるまでの期待値を E_i とすると， E_1 = 0, E_i = E_{i-1} + ((N-i+1)/N)^{-1} つまり E_i - E_{i-1} = N / (N-i+1) だから，両辺 i=2 から N の総和を取つて E_N = \sum_{i=2}^N N / (N-i+1).
■ 2023 年 8 月 19 日
やつたこと
- 精進
- ABC96D
- 55,555 以下の素数を列挙し， 5 で割つた余りが 1 のものを N 個列挙すればいい．
- 多分余りが 1 のものだけで 55 個はあると思ふけど，足りないなら 2, 3, 4 のものも調べれば良い． 55,555 以下の素数は 5,000 個以上あるので，どれかは 55 個以上ある．
■ 2023 年 8 月 12 日
やつたこと
- 初めてプライベートで使用してゐるラップトップをモニタに繋げた．
- 久々にちやんと競プロをした．
- 精進
- ABC262D
- n = 1, ..., N に対して X_n を X_n = A から項を n 個選ぶ選び方で，その和が n の倍数となるやうなものの数 として定義すると，求める値は \sum_{n=1}^N X_n である．
- X_n は動的計画法で求められる．
- dp[i][j][k] = (a_1, ..., a_i) から項を j 個選ぶ選び方で，その和を n で割つた余りが k であるやうなものの数．
- パッと見 O(N^4) だが，解ける．
- ABC270E
- まだりんごが入つてゐるかごの総数を n とすると，もし高橋くんが一周できたならば，すべてのかごからりんごが 1 つ減り， K は n 減る．
- まだりんごが入つてゐるかごのうち，入つてゐるりんごの数が最小のかごに入つてゐるりんごの数を a とする．もし a * n <= K であるとする．高橋くんが a 周したあと，すべてのかごからりんごが a 減り， K は a*n 減り， n は 1 減る．
- もし a * n > K であるならば，高橋くんは K // n 周したあとで， 先頭から K % n 個のまだりんごが入つてゐるかごからりんごを 1 つづつ食べたあとで，操作が終了する．
- A の要素のヒープを持つておけば効率的に解ける．
- ABC157D
- 一先づブロック関係がないとして考へる．
- グラフ G = (V, E) を V = {1, ..., N}, uv \in E ⇔ 人 u と人 v が友達関係にある として定義する．
- 人 u と人 v が友達候補であることと，ある G の連結成分 C が存在し， u, v \in C かつ u と v が友達関係にないことは同値となる．
- よつて，人 u の友達候補の人数 = u が含まれる連結成分に含まれる頂点数 - u の次数 - 1 となることがわかる．
- ブロック関係をどう扱ふかだが，これは連結成分分解をしたあとで，人 u と人 v について， u と v が同じ連結成分に存在するならば，辺 uv を G に追加し，さもなくば何もしない といふ処理を行なへば良い．
- ABC200D
- A の全要素を 200 で割つて余りを求めておく．動的計画法．
- dp[i][j] = (A_1, ..., A_i) から 1 つ以上の項を選んでその和を 200 で割つた余りが j となるやうな選び方の総数．
- dp_index[i][j] = (A_1, ..., A_i) から 1 つ以上の項を選んでその和を 200 で割つた余りが j となるやうな選び方からなるリスト．
- つまり A_{i_1} + ... + A_{i_k} % 200 = j ⇔ [i_1, ..., i_k] \in dp_index[i][j].
- dp[i][j] >= 2 となつたところで打ち切り， dp_index[i][j] から 2 つ選んで出力すれば良い．
- ABC75D
- すべての頂点を含む最小面積の長方形を求める問題は典型問題で，これは最大・最小の x 座標， y 座標を持つ点いづれもが辺上にくる長方形を見つければいいのであつた．
- 今回は N 個の点のうち 4 つ p_0, p_1, p_2, p_3 を選び，左上の頂点の座標が (p_0.x, p_1.y)，右下の頂点の座標が (p_2.x, p_3.y) の長方形内に， K 個以上頂点が含まれてゐるか全探索すれば良い．
■ 2023 年 8 月 2 日
やつたこと
- 精進
- ABC300E
- P(N) を題意の確率とする．
- P(1) = 1 は明らかなので，以降 N >= 2 とする．
- N が 2, 3, 5 以外の素因数を持つならば， P(N) = 0 は簡単にわかるので，以降 N = 2^a 3^b 5^c と素因数分解できるときのことを考へて，それを p(a, b, c) と書くことにする．すると，以下が成り立つ．
- 1/5 (p(a-1, b, c) + p(a, b-1, c) + p(a-2, b, c) + p(a, b, c-1) + p(a-1, b-1, c)).
- ただし， p の引数のうちで 1 つでも負数のものがあるとき， p(-, -, -) = 0 とする．
- ポイントは 1/6 ではなく 1/5 が掛けられてゐる点．これは，例へば N = 27 で持つてゐる整数が 9 のとき，直後に 3 が出る必要はなく， n-1 回 1 が出たあとで 3 が出ても問題はない．したがつてこのとき \sum_{n=0}^{\infty} (1/6)^n = 1/5 の確率で目標が達成されるのである．