C. Anna, Svyatoslav and Maps

難しかった。頂点集合p を前から順番に辿っていき、v に入れるかどうかを決めていく。頂点p[i-1] まで決めたとき、頂点p[i] を入れるかどうかは、v に最後に入れた頂点 (p[j] とする) からp[i+1] までの最短距離をd とすると、d < i+1 - j であればv に入れる。そうでなければ入れない。これは、d < i+1 - j のとき、p[i] を入れなかった場合、p[i] は通らずにパスを構成されてしまうため。全頂点対最短距離はワーシャルフロイドで求めておけばおけ。

D. Kirk and a Binary String

全ての連続部分列で条件を満たすので、とりあえず短い部分列を具体的に考えてみる。長さ2 の部分列は4 種類で"00", "01", "10", "11" である。このうち、"10" のみ最長非減少部分列の長さが1 である。そのため、s において"10" の部分はt でも"10" である必要がある。それ以外の部分は全て0 にしてt をとりあえず作ってみる。このとき、s において1 の部分を0 に変えた場所については記録しておく。次に、s, t それぞれ、[0, r) の区間についてr を増やしながら最長非減少部分列の長さを求めていく。長さが一致しなかったら、s において1 の部分を0 に変えた場所でr より小さいの場所のうち最大の場所のt を1 に戻す。これで、t の最長非減少部分列の長さは1 減り、s と一致する。これでいっか〜？って投げたら通ってしまった。ちゃんと解説を読みます。

E. Natasha, Sasha and the Prefix Sums

解説ACをした。まずは数列を過不足なく構築する方法について考える。+1 がn 個、-1 がm 個からなる数列を構築する。数列の先頭を+1 に決めてみると、その後ろの部分は+1がn-1 個、-1 がm 個の数列である。-1 を先頭にしたとすれば、後ろの部分は+1 がn 個、-1 がm-1 個の数列になる。ここで、数列の先頭に+1 をつけると、max prefix sum が1 増えることがすぐわかる。また、数列の先頭に-1 をつけると、max prefix sum は1 減ることもわかる。ただし、元々max prefix sum が0 であった数列に-1 をつけても0 のままなので注意。以上の考察から、数列を構成する+1 の数、-1 の数を状態に持つDPが出来そうである。

dp[x][y] := x 個の +1、y 個の -1 から構成される数列におけるmax prefix sum の総和 ( 求めるもの )

遷移は、$$ dp[x][y] = dp[x-1][y] + _ {x-1+y}C_ {y} + dp[x][y-1] - ( _ {x+y-1} C _ {y-1} - k[x][y-1] ) $$

二項係数の部分は、+1 を追加することで増える数 ( 後ろの数列の総数 ) と-1 を追加することで減る数である。k[x][y] は x 個の +1 、y 個の -1 から構成される数列のうち、max prefix sum が0 のものの数である。これは、簡単なDP で作成することができる。答えはdp[n][m] になる。

998242853 ってなに？？