Codeforces Round #699 (Div. 2) virtual

https://codeforces.com/contest/1481

ABCの3完、むーん

A. Space Navigation

どれだけ消してもいいので最短距離で進むのが良い。px が正(負)なら、R(L)が|px|個以上あればいい。pyも同様にやる。

B. New Colony

nもhも小さいので愚直シミュレーションで通る。

C. Fence Painting

m回目のペイントでbに無い色を塗ってしまう場合はNO、以降ある場合を考える。各目的の色ごとに塗り変えなければいけない (ai != biのもの) plankの番号をメモしておく。前から見ていき、塗り変えなければいけないものから順番に貪欲に塗っていけばおっけー。bに存在しない (最終的に存在しない) 色が現れたらm回目のペイントで塗るplankを塗っておけばおっけー。最終的にちゃんと塗り変わっていればYES。塗り変わっている判定でミスって1WA。

D. AB Graph

構築。構築の典型として、単純な操作で構築できないかを考える、というのがある (？)。全ての文字が同じ文字列は回文であることに気づくと、ある頂点対を結ぶ2つの有向辺のラベルが等しいとき、その2つの頂点をひたすら往復すると、全ての文字が同じ文字列ができる。このような頂点対が一つでもあればYES。以降は無い場合、つまり全ての頂点対を結ぶ2つの有向辺のラベルが異なる場合を考える。まず、mが奇数のとき、2つの頂点をひたすら往復するだけで回文ができることがわかる。あとはmが偶数の場合についてのみ考える。ある3つの頂点を取り出してみると、同じラベルの有向辺でサイクルができているパターンとそれ以外に分けられる。サイクルがあるパターンはサイクルをたどり続ければいける。それ以外のパターンは非常に説明しづらいが、回文の真ん中の2文字だけ同じ文字になるように構築できる。サンプルをみると、m=2のときはNOなのがわかる。これで良いと思ったが最後までWAが取れず。終了後に何が間違っていたかを見てみると、YESの出力し忘れだった......

E. Sorting Books

時間外で解いた。「ABC-006D トランプ挿入ソート」を思い出す。トランプ挿入ソートのように、動かさなくても良い要素の数の最大化を目指してみる。ある値の要素を動かさないことにした場合、それらの間に挟まれている値が異なる要素は全て動かさなければならない。一番左にある値 x の要素の位置 lx と一番右にある値 x の要素の位置 rx と値 x の要素の個数を記録しておけば、Flog DP (蛍光灯DP?) のように index を状態に持つ一次元のDPでいける。サンプル2のように最初から後ろにある要素を動かさないという選択もできるのでうまいこと対処する。

まとめ

時間外だけど、Eが解けたのは良かった。デバッグ環境を整えたいなあと常々思っている。