2020年5月28日木曜日
JOI2010 春合宿 - Sengoku
$(i, j)$を通る傾き$1$の直線の切片は$j-i$で、傾き$-1$の直線の切片は$i+j$になる。
とりあえず重複のことは忘れて番兵毎に数えると、傾き$1$の直線の通るマスは$L - |i-j|$個あり、傾き$-1$の直線の通るマスは$i+j < L$のとき$i+j+1$個、$i+j \ge L$のとき$2L - (i+j+1)$個あることがわかるので、まずはこれらの総和が基本になる。
次に、重複を除くことを考える。まず、切片と傾きが同じ直線は完全に重なるので、登場した切片を記録しておいて、前に見たものは無視することで重複を避けられる。
最後に傾き$1$の直線と傾き$-1$の直線の交点の数を引く必要がある。まず、交点が格子点になるのは切片が偶数同士、奇数同士の場合なので、切片が偶数の直線についてのみ考えることにする。（奇数のものの交点も同様に数えられる。） 傾き$1$で切片が$C$の直線と傾き$-1$の直線が与えられた領域内で交わるのは、後者の切片が$[|C|, 2(L-1) - |C|$]に入っているとき、またその時に限るので、ソートしておいてそれぞれ二分探索で数えられる。
2020年5月25日月曜日
CodeChef May Cook-Off - Chefina on a Trip
無向辺を2つの有向辺と見て、スコアが下がる向きに重み$-1$、上がる向きに$+1$、変わらないなら$0$を付与すると、ある有向パスが上りになっている$\Leftrightarrow \min$クエリが$1$である、下りになっている$\Leftrightarrow \max$クエリが$-1$である、と判定できる。
ダブリングLCAの構築をする時に、同時にmin/maxについてもダブリングのテーブルを作っておけばパス$u - v$がbeautifulかどうかは適当に判定できる:
- $u$から根に向けてスコアが上がる限りダブリングで上る。$\operatorname{LCA}(u, v)$の深さより上(inclusive)に行けたら3に行く。
- さらに根に向けてスコアが下がる限り上る。$\operatorname{LCA}(u, v)$の深さより上に行けなかったらfalseを返す。$\operatorname{LCA}(u, v)$の深さより上に行けたら頂上が$u- \operatorname{LCA}$の側にあると記録しておく。
- $v$から根に向けてスコアが上がる限り上る。$\operatorname{LCA}(u, v)$の深さより上に行けたらtrueを返す。頂上が$u-\operatorname{LCA}$の側にあるのに$\operatorname{LCA}(u, v)$の深さより上に行けなかったらfalse。
- さらに根に向けてスコアが下がる限り上る。$\operatorname{LCA}(u, v)$の深さより上に行けたらtrueを返す。
- falseを返す。
山のイメージに従って書くだけなので特に難しいとは感じなかった。でも、振り返ってみると、$u$と$v$を完全に対称に扱ったほうがいい気がする。
2020年5月24日日曜日
パ研コンペティション3日目 E - 美しい和音
$f(i, x) := A_1, ..., A_i$を使って作れる総和$x$の美しい和音の総数、とする。$f$の漸化式は$A_i$を使う/使わないの二択の和で$f(i, x) = f(i-1, x) + f(i-2, x-A_i)$と書ける。これでDPすれば部分点が取れる。
また、DPのほとんどの枝で不可能な状態の遷移をしていることに注目すると高速化できる。例えば、$A_1, ..., A_i$から作れる美しい和音の最大スコア$g(i)$がDPで求まるので、これを事前に求めておいて、$g(i)$が$x$より小さくなったら枝刈りしてよい。これで満点が取れた。
でも、計算量がよくわからない。
2020年5月21日木曜日
ふか杯 5th contest E - すごろく
$f(i) :=$ マス$i$からゴールするまでにサイコロを振る回数の期待値、として降順にDPしたいが、振り出しに戻る場合の扱いを考えなくてはならない。
通常、ループを含む確率DPは左辺と右辺の両方に$f(i)$が登場する式が立式できて、$f(i) = ...$となるように整理すると遷移がわかるはずだが、この場合は紙の上で式変形するのは難しそうに見える。そこで、$f(1)$の係数も別にDPで求めることにする。つまり、$f(i) = a(i) + b(i)f(1)$と表して、$a, b$を降順で求める。
$x_i>0$なら
$$ a(i) = a(i + x_i) $$ $$ b(i) = b(i + x_i) $$$x_i = 0$なら
$$ a(i) = \frac{1}{6}(a(i+1) + ... + a(i+6)) + 1 $$ $$ b(i) = \frac{1}{6}(b(i+1) + ... + b(i+6)) $$$x_i = -1$なら
$$ a(i) = 0 $$ $$ b(i) = 1 $$これで$a(1), b(1)$が得られるので、答えは$f(1) = a(1)/(1-b(1))$と求まる。
2020年5月18日月曜日
第一回日本最強プログラマー学生選手権予選 C - Cell Inversion
区間の組み合わせの総数が求まれば、操作の順番の総数は$N!$を掛けて得られるので、前者を求めればよい。
$S$を左から走査して、閉じていない区間を保持しながらDPすることを考える。つまり、
$\operatorname{dp}[x][y] := x$文字目までみて、閉じていない区間が$y$個あるような場合の数
というDPをする。$x$文字目が$W$で$y$が偶数、もしくは$x$文字目が$B$で$y$が奇数なら、ここで$y$個の（閉じていない）区間のどれかを閉じるのが正しいので、
$$ \operatorname{dp}[x+1][y-1] \operatorname{+=} y \cdot \operatorname{dp}[x][y] $$$x$文字目が$B$で$y$が偶数、もしくは$x$文字目が$W$で$y$が奇数なら、さらに新しい区間を開始して反転を1増やすべきなので
$$ \operatorname{dp}[x+1][y+1] \operatorname{+=} \operatorname{dp}[x][y] $$このDPは${O}(N^2)$の形になっているが、実際にやってみると各$x$について有効な$y$は高々1つしかないことがわかるので、線形で書ける。
コンテスト当時にはまったくわからなくて、解説を読んでも天才解法に見えた問題だった。今見ると、いわゆる箱根駅伝DPを書けばアドホックな考察をしなくても解けてしまうことがわかる。
ただ、${O}(N^2)$のDPが見えているときに、それの延長として想定解が導ける場合とかなり難しい場合があって、コンテスト中にそちらにどこまで頭を使うかは微妙なところとは思う。今出ても、ムーブ次第ではまりかねない気がする。
ABC 168 F - . (Single Dot)
縦線と横線で分割される$(N+1)(M+1)$個くらいの矩形について、隣接している矩形との連結性を調べながらBFSすればよい……のだが、なかなか通らなかった。
$C_i = C_j$のような場合の扱いが問題だった。そういうケースがありえることは承知していて、間に面積0の矩形があると考えて問題ないと思っていたのだが、$(3, 1) - (5, 1), (4, 1) - (6, 1)$のように縦線が重なっている場合（$\Leftrightarrow A_i \le B_j \land A_j \le B_i$）に、前者の左にある矩形→中間の（面積0の）矩形→右の矩形、のように本来移動できないところを迂回して移動できてしまう可能性があることに気づいた。結局、前処理の時点でつながっている線分は1本につなげてしまうことで解決した。