Educational Codeforces Round 84 (Rated for Div. 2) A~E
Educational Codeforces Round 84 (Rated for Div. 2)のバチャをしました。( 12/1 )
Dashboard - Educational Codeforces Round 84 (Rated for Div. 2) - Codeforces
ABCD の 4完 ( 1:44 4ペナ ) でした。
A. Sum of Odd Integers
k 個の互いに異なる正の奇数を足し合わせて n にできるかを判定する問題です。YES である条件は、n と k のパリティが等しいことと、奇数を小さい方から k 個足し合わせた数、つまり k(k+1) - k が n 以下であること、です。
B. Princesses and Princes
がっつり問題文に絵が入っててびっくりしました。言われた通りに貪欲にマッチングしていって、完全にマッチングされれば"OPTIMAL"、王子と姫が余っていたら"IMPROVE"です。"IMPROVE" の場合は、余っている王子と姫を一人づつ選んでマッチングさせればいいです。
C. Game with Chips
ギャグでした。全てのチップが全てのマスを通るような操作ができたら何も考えることないな〜って思ってたら、できたので何も考えることがなかったです。とりあえず全てのチップを左上に集めて、全てのマスを通るように動かせばいいです。うなぎのように。範囲外に動くことはないからといって雑に操作すると、2nm 以上になってしまうことがあって落ちました。no more than 2nm action は 2nm action もアウトなんですね。
D. Infinite Path
こういうのはサイクルに注目するのが良いんですよね、Swapsを思い出しました。順列 {p} を i -> p[i] の有向辺を持つ n 頂点のグラフと見なし、サイクルに分割します。あるサイクルに注目してみます。サイクルのサイズを m とすると、そのサイクルに含まれる任意の頂点について、\( p ^ m [i] = i \) となります。このとき、明らかに頂点 i から始まる path は infinite path を形成します。そのため、サイクル分解した後のサイクルのサイズの最小値が答えの上限になります。これより小さくなる場合を考えます。サイクル分解した後のサイクルのサイズを再び m とおき、d を m の約数として、\( p ^ d \) を考えてみると、サイクル内の頂点 i から始まる path は \( i, p ^ d [i], p ^ d [ p ^ d [i]] ... p ^ m [i] = i \) となることがわかります。この path に出てきた全ての頂点 j で c[j] が等しければ d も答えの候補となります。あとはこの d を全探索すればできます。整数 N の約数の個数が \( \sqrt{N} \) 程度なので、計算量は\( O(N\sqrt{N}) \) 程度のはずです、多分。通ったので大丈夫だったのだと思います。
E. Count The Blocks
D を通して残り 15 分でしたが、1000 人以上に通されていたので、いけると思ったのですが、間に合いませんでした。焦りすぎました。問題を言い換えると、要素が 0~9、長さが N の整数列を全パターン考えた時に、同じ数字がちょうど k 連続するような場所がいくつあるか？を\( 1 \le k \le N \) 全てについて数えよ、という問題になります。同じ数字がちょうど k 連続するような部分では、k 個同じ要素が並び、その両端には別の要素が並んでいるはずです。例えば、長さ N の整数列のうち、前から i 番目から i + k - 1 番目までが、同じ要素で i - 1 番目とi + k 番目がそれとは別の要素であるような整数列の総数は、\( 10 \times 9 \times 9 \times 10 ^ {N - (k + 2)} \) 通りになります。全ての i \( ( 1 \le i \le n - k + 1 ) \) についてこれを足し合わせればいいですが、i = 1, i = n - k + 1 のときは、端が片方しかないことに気をつけて丁寧にやりましょう。反省。
感想
C のギャグに気づくのが早くてよかったのと、難しいっぽい D が解けてうれしかったです。E もしっかり通したかったですが。
Educational Codeforces Round 85 (Rated for Div. 2) A~E
Educational Codeforces Round 85 (Rated for Div. 2)のバチャをしました。( 11/27 )
Dashboard - Educational Codeforces Round 85 (Rated for Div. 2) - Codeforces
ABCD の 4完 ( 1:02 1ペナ ) でした。
A. Level Statistics
問題文が長すぎます。長い上によくわからないのでサンプルを見てエスパーをしました。総プレイ数と総クリア数をモニターした結果が入力で与えられるので、それが適切かを判断せよ、って感じです。たぶん。全ての i \( ( 0 \le i \le n ) \) で、\( 0 \le p[i] - p[i-1] , 0 \le c[i] - c[i-1], c[i] - c[i-1] \le p[i] - p[i-1] \) が成り立てばYESです。(p[0], c[0]) = (0, 0) の番兵を置いておくと楽です。
B. Middle Class
平均が x 以上となる部分集合のうち、サイズが最大のものを求めれば良いです。明らかに大きい方から集合に詰めていくのがいいので、降順ソートして上から詰めていきます。
C. Circle of Monsters
最初に kill するモンスターについてはきっちり体力分の弾丸を打ち込まなければいけないことがわかります。それ以外のモンスターについては、試しにa[0] のモンスターを kill した場合について考えてみます。すると、全ての i \( 1 \le i < n \) については、きっちり max(0, a[i] - b[i-1]) 発分の弾丸を打ち込めばいいことがわかります。つまり、a[0] を最初に kill する場合に使用する弾丸の総数は、\( a[0] + \sum _ {i = 0} ^ {n-1} max(0, a[i] - b[i-1]) - max(0, a[0] - b[-1]) \) となります。ここで、b[-1] = b[n-1] とします。結局、a[i] を最初に kill する場合に使用する弾丸の総数は、\( a[i] + \sum_{i = 0}^{n-1} max(0, a[i] - b[i-1]) - max(0, a[i] - b[i-1]) \) となり、sum の部分を前計算しておけば、各 i について O(1) で処理することができます。よって、全ての i についてa[i] を最初に kill する場合に使用する弾丸の総数を計算し、その最小値を求めれば良いです。これをそのまま書いたら TLE したので、入力を scanf に変えたら通りました。うーん。よく考えたら、a[i] - max(0, a[i] - b[i-1]) が最小となるような i を見つければいいだけなので、いちいち全部計算する必要は無いのか？
D. Minimum Euler Cycle
めんどくさかったです。まずは、全ての辺を通るパスのうち、通過した頂点を順に並べたものが辞書順最小になるようなパスを構築してみます。こういうのは、簡単な構築法があるはずなんですよね〜という気持ちで頂点数の少ないグラフを実際に書いて実験してみると、頂点数 n のグラフにおいて、1213...1n2324...2n34......1 というパスが条件を満たすことがわかります。あとはこのパスで前から i 番目の数字が何であるか？という問いに答えられればいいです。めんどくさいだけなので、割愛します。
E. Divisor Paths
おもしろかったです。エスパーしてサンプルがあったときは興奮しましたが、結局通りませんでした ( ただオーバーフローしてただけでした...悲しい )。かなりエスパーして何も理解していなかったので、後で解説を見てちゃんと解きました。まず、辺がどこに張られるかを考えてみます。y が x の約数であり、x / y が素数であるような x, y の間に辺が張られるとのことなので、頂点 x から張られる辺の先の頂点 y の条件は、y が x を x の素因数で割った商であること、です。x -> y のパスは、y が x の約数であるときには、x が y になるまで素数で割っていくことで構築できます。このパスのコストは、x の約数だが、y の約数でないものの数と等しいです。さて、x と y の最短パスについて考えます。実はこれは、途中で gcd(x, y) を経由するようなパスが最短であることがわかります。x から y に移動するということは、x から素因数をいくつか取り除いて、y になるまで素数を掛ける、ということと同じです。この操作において、取り出した素数の数とかけた素数の数の合計が、パスのコストになります。すると、x と y に共通する素因数を取り除いてしまうのは無駄で、そのような操作をするパスは最短にならないことがわかります。つまり、x から gcd(x, y) になるまで、素因数を取り除き、gcd(x, y) から y になるまで素数を掛ける、というパスが最短になります。あとは、x -> gcd(x, y) の最短パスの総数と、gcd(x, y) -> y の最短パスの総数を掛け算してあげればそれが、x -> y の最短パスの総数になります。x -> gcd(x, y) の最短パスは、x から gcd(x, y) になるまで、素因数を取り除いていくことで実現されますが、取り除く素因数についてはどの順番で取り除いてもパスのコストは変わりません。なので、取り除く素因数の集合 ( x / gcd(x, y) を素因数分解すれば得られます ) の要素の並べ替えの総数がパスの数になります。これは簡単な組み合わせ計算で出すことができます。gcd(x, y) -> y については、y -> gcd(x, y) のパスと同じであると考えることによって同様に処理できます。この計算は、d の約数全てについて素因数分解したものを持っておけば、十分高速に処理できます。d の約数全てを素因数分解するのは愚直にやると間に合いませんが、d を素因数分解した結果から差分を更新していくようにしてテーブルを作成すれば間に合います。( エスパーしたときは、gcd(x, y) を通るパスではなく、lcm(x, y) を通るパスを使用していました。なぜ？結果的にはそれでも解けるのですが、lcm(x, y) を計算する際に、x*y が発生してオーバーフローしてました。うーん、ライブラリ整備が甘い。)
感想
解けて欲しいものについては、そこそこ早く解けたので良かったです。E はやばい問題設定に面食らってる時間が長くてもったいなかったです。こういうのをしっかり解けるようになりたいね。
Educational Codeforces Round 94 (Rated for Div. 2)
Educational Codeforces Round 94 (Rated for Div. 2)のバチャをしました。( 11/26 )
Dashboard - Educational Codeforces Round 94 (Rated for Div. 2) - Codeforces
ABCD の 4完 ( 1:47 4ペナ) でした。
A. String Similarity
s の長さが 2n - 1 であるので、s は連続部分列として長さ n で全ての要素が 0 であるようなものと長さ n で全ての要素が 1 であるようなものの両方を持つことはありません。そのため、全て 0 の文字列か全て 1 の文字列のどちらかが答えになります。これに気づかずに s の部分文字列を全列挙し、貪欲に答えを構成していきました。通ったから良かったものの、正当性は何も証明していません。反省。
B. RPG Protagonist
B なのに難しくて焦りました (こんなのばっか)。
$$ sx + wy \le p $$
$$ sa + wb \le f $$
$$ x + a \le cnt_s $$
$$ y + b \le cnt_w $$
を満たすような (x,y,a,b) のうち、x+y+a+b が最大になるものを求めます。こういうのは一つ固定して考えると良いので x を固定してみます。
すると、\( y = min( \frac{p - sx}{w}, cnt_w) \) となります (徐算は切り捨て)。(a, b) は、
$$ sa + wb \le f $$
$$ a \le cnt_s - x$$
$$ b \le cnt_w - y $$
を満たすもののうち、a + b が最大になるものを見つければ良いです。実は、a < b とすると、a を取りうる最大の値にして、残りを b に割り振るのが最適です。全然気づかなかったので反省。
C. Binary String Reconstruction
B でめちゃくちゃ詰まってしまったので、取り掛かる頃には 4000 人くらいが通しており、簡単だろうと思いながら解きました。 s から w を構築するために、条件を言い換えると、\(s _ i\) = 0 のときは、\(w _ {i-x} = 0\) かつ \(w _ {i+x} = 0\) となります。これで指定されない w の要素については全て 1 として良いです。こうして構築した w から s を再構築してみて、s ができなければ -1、できたら w をそのまま出力します。
D. Zigzags
これすき。何かを固定してみて Zero Sum Rangesをする、が見えます。私は i と k を固定してみました！どうして？ b[x] := a[i+1] ~ a[k+1] に 出現する x の数、c[x] := a[k+1] ~ a[n] に 出現する x の数、とすると、a[i] = a[k] となる全ての (i, k) で、 全ての x について b[x] * c[x] を足し合わせたものが答えになります。これは愚直にやっては間に合いません。i と k を動かしたときに、b, c がどのように変化するかを考えてみます。i は固定し、k を k+1 に変化させたとすると b[a[k]] が 1 増え、c[a[k+1]] が 1 減ることがわかります。このとき、b[x]c[x] を足し合わせたものは、b[a[k+1]] 減り、c[a[k]] だけ増えることがわかります。なので、b, c, b[x]c[x] を足し合わせたもの、を管理しながら、i, k を動かしていき、a[i] = a[k] のときはb[x]*c[x] を足し合わせたもの、を答えに足していくことで答えが求められます。b, c を連想配列で管理すると TLE してしまいました。Codeforces はシビアですね。log は定数じゃない！
E. Clear the Multiset
これもすき。解けなかったので解説 AC しました。DP[i][j] := 整数 1 ~ i は全て削除し、整数 i のうち j ( \(\le\) a[i] ) 個は操作 1 で消しているという状態になるまでの最小操作数、とします。また、この状態を (i, j) とします。(i, j) から、i+1 を削除することを考えます。a[i+1] \(\le\) j のときは、i に適用した操作 1 を横に拡張して i+1 を削除することができ、操作数は増えないので、chmin(DP[i+1][a[i+1]], DP[i][j]) と遷移できます。この際、a[i+1] を超える数を操作 1 で消すことはできないので注意。a[i+1] > j のときは、i に適用した操作 1 を横に拡張するだけでは i+1 を消しきれないので、残りをさらに操作 1 で消していくか、操作 2 で一気に消すかの 2 通りの遷移があります。まず、操作 2 を行う場合操作回数が 1 増えて i+1 を全て消すので、chmin(DP[i+1][j], DP[i][j] + 1) となります。この際、a[i+1]個 のうち j 個は操作 1 で消したことにした方が得なので、そうしておきます。次に、残りを操作 1 で消すことにする場合、整数 i のうち j+1 個を操作 1 で消しているという状態に遷移すればいいことがわかるので、chmin(DP[i][j+1], DP[i][j] + 1) とできます。これで、遷移は全てですが、i \( \le\) n, j \(\le a[i] _ {max} \) なので状態数が、5000*10\(^9\) となり到底間に合いません。ここで、j をそんなに多くとる必要があるかを考えてみます。全ての整数を操作 2 で消すことが必ず可能であり、その際の操作数は n になるので、操作数の上限は n とすることができます。すると、j > n の状態はそこから最小の操作数に遷移することは無いことがわかるので、j > n の状態についてはみる必要が無いことがわかります。これで、状態数を n\(^2\) に抑えることができました。
感想
かなり酷かったです。A でギャグに気づかず、B でめちゃくちゃ詰まってしまいました。反省だらけです。
Educational Codeforces Round 98 (Rated for Div. 2) A~E メモ
Educational Codeforces Round 98 (Rated for Div. 2)のバチャをしました。( 11/25 )
Dashboard - Educational Codeforces Round 98 (Rated for Div. 2) - Codeforces
ABCD の 4完 ( 0:43 ) でした。
A. Robot Program
到達したい (x, y) において、x \( \le \) y とします。(x, x) までは 2x 回で到達できて、残りは 2(y-x) - 1 回かかります。x = y の時は注意です。
B. Toy Blocks
B にしては難しくて焦りました。まず、条件を満たすような数列の条件を考えていきます。明らかに、数列の総和が N-1 の倍数である必要があります。さらに、数列の要素の最大値が、(総和) / (N-1) 以下である必要もあります。これが必要十分条件で、これを満たすような最小の総和、を見つければ良いです。
C. Two Brackets
B を通した時点で、1000 人以上 C を通していたので、簡単なんだなと思いながら問題を見ました。すると貪欲に対応する括弧をマッチングしていけばいいと書いてあるので、やります。
D. Radio Towers
これすき。まず、求めるものは確率ですが、2n 通りの全事象のうち条件を満たす電波塔の並べ方がいくつあるかを数え上げれば良いです。次に、条件を満たすように電波塔を並べていきます。座標の小さい方から順番に電波塔を配置していくのが自然でしょうか。座標 1~i の範囲は既にカバーされているとします。ここから、座標 1~i の位置に電波塔を配置することはあり得ません。i+1 を必ずカバーしなければいけないことと、i を重複してカバーしてはいけないことを考えると、電波塔の置き方は、 i+1 に強さ 1 のものを置く、i+2 に強さ 2 のものを置く…、i+k に強さ k のものを置く、という置き方に限られることがわかります。少し見方を変えて ( 貰うDP を意識する感じ? ) 、1~i をカバーするような電波塔の配置の仕方は 1~i-1 までがカバーされている置き方に対して、i に強さ 1 の電波塔を置くパターンと、1~i-3 までがカバーされている置き方に対して、i-1 に強さ 2 の電波塔を置くパターン…となります。ここで、
DP[i] := (座標 1~i がぴったりカバーされているような電波塔の並べ方の総数)
とすれば、
DP[i] = DP[i-1] + DP[i-3] + ... = \( \sum_{k = 1}^{i - (2k - 1) = 0 or 1} DP[i - (2k - 1)] \)
となります。和のパートはテーブルを作っておいて順に更新していけば良いです。
こんな雰囲気のDPを最近よく見る気がします。
E. Two Editorials
解けなかったので、解説 AC しました。それぞれの参加者に対して、どちらの editorial を見るかを決めれば、editorial がカバーする範囲を全探索して解くことができます。ナイーブには、それぞれの参加者がどちらの editorial を見るかの決め方は 2m 通りあるので到底間に合わないですが、実は意味のある決め方は m 通り程度に抑えることができます。例えば、2 つの editorial がカバーする範囲を決めてしまうと、それぞれの参加者が見るべき editorial が決まります。具体的には、editorial のカバーする範囲の中心と、参加者が見たい範囲の中心の距離が小さくなる方の editorial を選べば良いことがわかります。つまり、参加者を、見たい範囲の中心位置でソートすると、参加者を前と後ろで 2 分割してしまう方法が意味のある決め方になっていることになります。あとは、
pre[i] := ( 前から i 番目の参加者までが 1 つめのeditorial を見るとしたときの、( editorial のカバーする範囲を動かした中での ) 参加者がeditorail を受けられる task の最大値 )
suf[i] := ( 前から i 番目の参加者から、m 番目の参加者までが 2 つめのeditorial を見るとしたときの、( editorial のカバーする範囲を動かした中での ) 参加者がeditorail を受けられる task の最大値 )
とすれば、答えは pre[i] + suf[i+1] の最大値 ( 0 \( \le i \le \) m ) です。
言われてみればそうだけど、難しい…。
感想
B を落ち着いて解けたのと、D を瞬殺できたのは良かったです。
Codeforces Round #574 (Div. 2) A~E メモ
Codeforces Round #574 (Div.2) のバチャをしました。( 11/18 )
Dashboard - Codeforces Round #574 (Div. 2) - Codeforces
ABCD1D2E の 6完 ( 1:33 ) でした。
A. Drinks Choosing
問題文の読解が難しかったです。2 人を割り当てられるドリンクから貪欲に取っていけば良いです。
B. Sport Mafia
飴を食べるタイミングはいつでも良いです。飴を x 個食べたとすると最終的な飴の数は、\( \frac{(n-x)(n-x+1)}{2} - x \) となります。これが k となるような x を全探索すれば良いです。
C. Basketball Exercise
DP をして欲しそうな顔をしています。DP[i][j] := i 列目まで見て、最後に j 行の選手を選んだときの身長の総和の最大値 でいけます。
D. Submarine in the Rybinsk Sea
各要素が総和にどのように寄与するかを調べます。典型ですね。ある要素の下から 1 桁目は、演算の結果、下から 1 桁目になるか、2 桁目になるかのどちらかで、それぞれ n 回発生します。ある要素の下から 1 桁目の数を x とすると、\( n(10x + x) \) が総和に足されることになります。全ての要素の下から 1 桁目について同じことをします。これで各要素の下から 1 桁目の寄与は確認できました。次に、2 桁目でも同様にして、\( n(1000x + 100x) \) を総和に足します。ただし、2 桁目が存在しない要素は特別に処理します。2 桁目が存在しない要素と存在する要素で演算を行うと、存在する要素の 2 桁目以降はそのまま総和に寄与することがわかります。これを全ての桁数分確認します。最初に要素を降順にソートしておくと簡潔に書ける気がします。
きれいに実装できた気がします。
int main() { int n; cin >> n; vi a(n); rep(i,n) cin >> a[i]; sort(a.begin(), a.end(), [](int x, int y){ return x > y; }); mint res; mint b(1); int m = n; while(a[0] > 0) { mint sum; int cnt = 0; rep(i,m) { int tmp = a[i] % 10; res += mint(m) * (mint(tmp) * b + mint(tmp) * b * mint(10)); a[i] /= 10; if(a[i] == 0) { cnt++; } else { sum += mint(a[i]); } } b *= mint(100); res += mint(cnt) * sum * b * mint(2); m -= cnt; } cout << res.x << "\n"; return 0; }
E. OpenStreetMap
範囲の最小値なので、セグ木がまず思いつきます。2 次元はめんどくさいので 1 次元に落とし込みます。典型ですね。(x, y) を左上に置くような範囲における最小値は、\( min( min ( h[i][j] | y \leq j < y+b ) | x \leq i < x+a) \) となります。先に、全ての場所で横向きにサイズ b の範囲の最小値をとって記録しておくとやりやすいです。セグ木でやると TL が微妙な気がしたので、スライド最小値を使いました。ほとんど書いたことがなかったので、適当な記事を見ながら書いて、いい練習になりました。セグ木でやると落ちるんでしょうか？私、気になります！
F. Geometers Anonymous Club
幾何。わからないし、時間もなかったのでとりあえず錆び付いた幾何ライブラリを使ってやろうと思い、愚直解を書きました。が、サンプルも合いません。終了。
感想
最近やばい実装方針で進めて爆発することが多かったので、簡潔な実装を意識してやりました。D2 ではちゃんと簡潔にできて良かったです。
Codeforces Round #577(Div.2) A~D メモ
Codeforces Round #577(Div.2) のバチャをしました。( 11/16 )
Dashboard - Codeforces Round #577 (Div. 2) - Codeforces
ABCD の 4完 ( 1:51 ) でした。
A. Important Exam
題意を理解するのに時間がかかりました。各問題に対して最も多い解答が正答だったことにすれば良いです。
B. Zero Array
これ、GP 2 で見たことがある！全ての要素を 0 にできるための必要十分条件は、1. 要素の総和が偶数、2. 要素の最大値が総和の半分以下、です。
C. Maximum Median
まず数列を昇順にソートします。操作を行う要素は後ろの \( \frac{N+1}{2} \) 個だけで良いです。それらを抜き出して、新たに数列 b を作ります。i = 0 から順に、\( (i+1) * (b _ {i+1} - b_i) \) ずつ \( b_0 \) から\( b_i \) に足していきます。このときにその分だけ k を減らしていきます。途中で k が足りなくなったらその時点で、\( b_i + \lfloor \frac{k}{i+1} \rfloor \) を答えとします。最後まで k が足りた場合は、\( b_{\frac{N+1}{2} - 1} + \lfloor \frac{k}{ \frac{N+1}{2}} \rfloor \) が答えです。
D. Treasure Hunting
かなりしんどかったです。見た瞬間に、Grid 上の DP がしたくなりますが、制約を見て一旦落ち着きます。下移動ができないので、その行にある宝物を全て拾ってからでなければ上に移動できません。このとき、全ての宝物を効率よく拾うと、最後に拾う宝物は一番左か一番右になるとわかります。最後に宝物を拾った位置から上の行に移動する際には、その宝物がある列から右を見たときに最も近くにあるsafety colmun か、左を見たときに最も近くにあるsafety column から上に移動すればいいことがわかります。これは二分探索で高速に求まります。各行で、最後に拾う宝物は高々 2 通りなので、上に移動する列は高々 4 通りになります。よって、
dp[i][j] := 下から i 行目までの宝物を全て拾い終えて、左から j 列目にいるという状態になるまでに移動した距離の最小値
という DP をすれば良いです。最後の行では、safety colmun に移動する必要が無いことに注意してください。
これ実装するの？嫌なんだけど、という気持ちになりながら実装し、WA を出してはバグを直して再提出を繰り返すこと 5 回、最終的には b がソートされていない、というバグを直して再提出したら通りました。かなりこどふぉっぽさを感じました。ソートしておいてくれ〜〜
E.
D で力と時間を使い果たした上に、インタラクティブだったので、投げ出しました。本番の Rated 内正解者数 0 でわろた。
Codeforces Round #581(Div.2) C〜E メモ
Codeforces Round #581(Div.2) のバチャをしました。( 11/10 )
https://codeforces.com/contest/1204
ABCD1D2 の5 完 ( 1:45 ) でした。
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 ってなに？？
