えびちゃんの日記

えびちゃん（競プロ）の日記です。

TDPC うめうめ記

TDPC こと Typical DP Contest を埋めました．

色づけや提出日時についてはこの Userscript を使っています．

greasyfork.org

B 問題がめちゃむずで 10 日かかったということではないです．

記録については精進つりーにも書いているんですが，少し振り返ってみようと思います．

解いているときは以下のブログを参考にしました． 写経はしたくなかったので，コード部分は見ないようにしていました．

suikaba.hatenablog.com

おもったこと

DP で何々の個数を求めるとき，実際に何々は持たないで個数だけを管理しますが，「ここの添字で管理される何々が満たす条件はなにか？」というのを意識するようにしていた気がします．

いや，最初から意識していたような気もするんですが，状態の分け方が（何番目まで見たほどは）シンプルでないと混乱しがちなので，意識的にやっていたということです．

また，小さなケースで手で試してみるのをちゃんとするようにしました． 遷移の仕方を確認しながら行うことで理解が深まり，実装の見通しもよくなります．

ふりかえり

A

やるだけ．せっかくなので bitset で 64 倍高速化とかをしてみました．

B

得点系の二人ゲームをします． 冷静に読むとプレイヤーの目標が書かれていなくて何が最善なのかわからないんですが，価値の最大化だと察します．

negamax 法というアルゴリズムを実装します． メモ化再帰で，ある局面から最適に行動したときの得点を返すようにします． 手を指すときは「その手で得られる得点」から「次の局面から始めたときの最大得点」を引くことでいい感じになります．

自分と相手の得点の総和が定数になることから，足し引きをしていい感じにします．

メモ化を書くのを後回しにしていたんですが，提出した瞬間に気づいてジャッジにごめんなさいしていました．

C

確率 DP です． 「そこまで勝ち進む確率」と「そこで勝てる確率」を掛けて足していきます． トーナメント表は完全二分木なので，二進数で扱うと楽です．

D

確率 DP です． 素因数 2, 3, 5 がいくつ出たかをカウントします． \(N\) が持つ素因数の個数と min をとって計算することで，最終的な答えを得るのが楽になります（しなくても適当に計算すればなんとかなると思います）．

E

桁 DP です． それはそうみたいなことをします．

F

これ非自明っぽくないですか？

連続していくつの駅に止まったか（\(0\)，\(1\)，\(2\) 以上の三つに分ける）を状態として持つことで，うまく足し引きして遷移を計算できます．

解説ブログでは状態を二つに分けていたので，そういう解法もあるんだと思います．

G

部分列 DP です． ある場所以降での，ある文字の最初の現れの位置を覚えておきます． 「この文字を選んだ場合にそれ以降で作れる部分列は？」というのを数えます． "aabab" のような例を作って手で試しました．

H

ナップサックの亜種です． 種類数に制限があってたいへんそうです． 種類ごとに見ていって，「今見ている種類の物を入れたか？」という分け方をしました．

解説ブログでは「最後に入れた物の種類は何か？」というのを管理していて，そういうのもあるねとなりました．

I

"iiwiwiwii" は 2 ではなく 3 なんですよね．

区間 DP です． "i" * "w" * "i" で　* が消せるときは全体が消せます．両方の * が空でない場合を忘れないようにしましょう．

J

期待値で bit DP です． 期待値の遷移に関して，自己ループを消すやつをします． 落ちついて紙で書くと簡単です．

K

Topcoder のターゲットという概念を知っていますか？ えびちゃんは知っています． 二次元の幾何問題かと思って不可能枠かと思っていました...

区間を終端でソートして順に見ていきます． 各区間について，ネストの深さを求めればいいです（自分から見て覆う深さ）．

今見ている区間の内部にある区間での答えの最大値 +1 が，その区間のネストの大きさです． この値を，区間の始端の位置に持っておきます．

包含関係が strictly であることに注意しましょう．

L

にゃぁ．

すきな実数の位置におけるので，順序関係だけが大事です． 「\(i\) 番目のねこちゃんは \(j\) 番目までのねこちゃんまでが幸福度に寄与する」というのを覚えておきます．

たとえば，四匹のねこちゃん A, B, C, D がこの順に並んでいるとします． C のねこちゃんは B までが寄与する状態を考えます． ここに D のねこちゃんを追加するとき，A までが寄与するような並べ方はできません．

というような感じのことを考えて，それはそうみたいな DP を書きます． 累積和などを用いてループを一つ減らします．

M

名前からしてセグ木実家 DP だと思っていたんですが...

まず bit DP で，一階建てのときの \(i\) から \(j\) に行く通り数を数えます（全点対）． あとは，行列累乗をすることで所望のものが得られます．

N

木 DP をします． 根から子側に辺を描いていき，木にする書き方は何通りあるか？ というのを数えます． というのを各頂点を根として行い，2 で割ります（辺一つに対して，同じ書き方が二つ数えられるため）．

高校数学の一年生を落ちついてやるといいです．

ものを並べます． 種類 \(i\) のものは \(n_i+1\) 個あります． ただし，各 \(i\) について，ちょうど一つ特別なものがあり，それは種類 \(i\) のもののうちで最も左に置く必要があります． また，各 \(i\) について，特別でない \(n_i\) 個のもの（各々区別される）の合法な並べ方は \(p_i\) 通りあります． 全体で合法な並べ方は何通りあるでしょう？

...という問題を解きます．

O

挿入 DP です． これも高校数学の一年生をやります．

\(i\) 番目までの文字を使って文字列を使ったとき，隣り合いが \(j\) 箇所発生したとします． たとえば "aabaaabb" では 4 箇所になると思います．

そして，次の文字を空でない \(k\) グループに分けて挿入することを考えます． たとえば，c が三つ使えるなら，c, cc のように二グループに分けたり，ccc のように一グループにしたりして挿入します．

さらに，挿入位置として，\(k\) 個のうちちょうど \(l\) 個は隣り合いの位置に入れることにします．

隣り合いの個数の変化と，挿入の通り数を落ちついて考え，合法な値の範囲にも気をつけながら書くとよいです．

P

うな木？ 木 DP をします．

今見ている頂点以下の部分木で，「何本のパスを作ったか？」「今見ている頂点の次数はいくつか？」というのを管理します．

後者はたかだか 2 になることに注意です． これは当然なんですが，今見ている頂点を使ったかどうかの場合分けでは不十分なんですよね．

R

強連結成分分解をして，グラフをつぶします． 元のグラフを \(h\)，つぶした後のグラフを \(g\) とします．

\(g\) での頂点は重みを持っていて，\(h\) での対応する強連結成分に属する頂点数が重みです．

\(g\) をトポロジカル順に見ます． 二本のパスの先端の頂点のトポロジカル順での番号を \(i\) 番と \(j\) 番とし，\(i \gt j\) とします．

このとき，\(i\) はどう伸ばしても重複しませんが，\(j\) は重複を防ぐために \(i\) を飛び越える必要があります． \(j\) から \(j'\) に行くとき，\( (i, j)\) から \( (j', i)\) に遷移することに注意です． また，このとき \(j'\) の候補は \(g\) での辺ではなく，（\(g\) での遷移を任意回繰り返す）\(g^*\) での辺を用いることに注意します．

S

フロンティア法？ ZDD 界隈で有名そうです． 横方向に進めていきます．

「今後の塗り方が同じなら，左上と右下のマスの連結関係も同じになる」という状態をまとめます．

たとえば，次のような状態はまとめられます．

(1)  (2)

***  ***
*.*  ..*
***  ..*
..*  ..*
***  ..*

Union-find などを使って連結関係を管理していくんですが，意図と違う状態がまとめられたり，何が意図なのかわからなくなったりして時間が溶けました．

各列について，「塗らないなら \(0\)」「塗るなら \(1\) 以上 \(H\) 以下の値」を割り振る \(H\) 桁の \(H+1\) 進数を考えます．

塗るときは，Union-find の代表元の値を使って，その桁にどの値を割り振るかを決めます． 左上のマスと連結な集合は \(1\) を割り振るように強制して，適宜 swap などをしました．

要素数が \(2H\) の Union-find を使って次の列での値の割り振り方を決めました． 塗り方を決めると割り振り方が決まるので，計算量は \(\widetilde{O}(W\cdot (H+1)^H\cdot 2^H)\) とかだと思います．

MLE で一回落ちました（かなしい）． 直前の列しかいらないので，いらなくなったら捨てましょう．

T

きたまさ法を知っていますか？ えびちゃんは知っています．

sugarknri.hatenablog.com

ここがわかりやすかったです． いい感じに実装すると通ります．うれしいですね． 実質ウィニングランです．

ペナ内訳

  • WA (F I K P P Q R R)
  • TLE (B)
  • MLE (S)

感想

完走した感想ですが，何年か前に A と E だけ解いて（T を写経して）力尽きていたときから比べて，成長したなぁと思ってうれしいです． 自明と言って一瞬で解けたわけではなかったですが，一応力はついているのかなぁと思いました．

おさんぽ中などに，複数問をまとめて考察する癖がつきました．

承認欲求がいくらか満たされました．

おわり

にゃん．