Codeforces Round 1031

A. Shashliks

$x,y$ の大小関係を比べて，小さい方から可能な限り使っていく貪欲．

「サンプルの図のようなパターン」しかないです．縦方向または横方向に帯を作ってそれを自由にずらしながら並べていくパターン．

ある長方形の右辺に接するものが少し上下にずれていると，真上や真下に並べ続けなければならないということからいえます．

縦方向，横方向それぞれチェックします．

そもそも正方形境界に来ることがない g は # に置き換えておきます．

もし $1$ 回爆発させたら，その時点で残っている g はすべて回収可能です．$2$ 回目以降では爆発位置をひとつずつずらしていくことで，新しく破壊されるマスが常に正方形境界にくるようにできるからです．

そこで，最初の爆発で壊してしまうもの，つまり一辺が $2k-1$ の正方形部分に入るものの最小化を考えればよいです．二次元累積和テーブルを作って全探索すればよいです．

$k$ 回勝利可能かの判定を考えて二分探索します．すると，$B$ の先頭 $n-k+1$ 枚のうち最小のものをとったとき，$A$ の先頭 $k$ 枚がすべて上回っているというのが条件になります（必要・十分性ともに簡単）．

あとはスワップで条件を達成できるかの問題がありますが，$A$ の先頭 $k$ 枚のうち下回っているものを数えて，後ろ $n-k$ 枚のうち上回っているものを数えれば判定できます．

時刻ごとに，dp[v] を，自分がその時刻に $v$ に居ることが可能かの bool 値とする dp の方針が考えられます．

を順に行うという要領です．この解説では，この更新をこの順に行う前提で，したがって「同時刻」にある $v$ が true になってから false になるというのもありえます．

dp[v] が true から false になるのは $O(NM)$ 回しかありません．よって dp[v] が false から true になるのも $O(NM)$ 回しかありません。これらの候補を無駄なく列挙できればよさそうです．

true から false になるイベントの候補：各 $M$ 人のパスを求めておけばよい．
false から true になるイベントの候補：
- $v$ が true から false になったとき，その次の時刻に $v$ が false から true になるかもしれない（チェックする必要あり）
- $v$ がfalse から true になってその時刻で true のままだったとき，$v$ の近傍 $w$ について $\dp[w]$ が false ならば，その次の時刻に $w$ が false から true になる（必ず起こる）

false から true になるイベントの候補は 2 タイプあります．

前者は $v$ が候補になったときに $O(\deg(v))$ 時間かけて判定します．同じ $v$ が false になる回数は $O(M)$ なので，これで前者の候補列挙が $O(NM)$ 時間になります．

後者の候補については，$O(1)$ 時間で判定可能であることに注意しましょう．やはり $v$ ごとに考えると $O(\deg(v))$ 時間のイベントが $O(M)$ 回なのでこちらも $O(NM)$ 時間です．

後者の候補列挙・判定を $O(\deg(v)\cdot \deg(w))$ 時間かけた提出が通ったのですが，Hack 可能かもしれません．下の提出はまとも計算量になっているはず．

組 $(a_i,b_i)$ を無向辺と見なすと，

となります．

任意の点に対して，入次数と出次数の差が $1$ 以下となるように向き付けることが可能です（可能ならそれが最大値を達成していることは明らかです）．

適当な点からはじめて，同じ辺を 1 度しか使わないような walk で極大なもの（もう進める辺がない状態まで進んだもの）をとり，その方向に向き付けるということを繰り返します．

次数奇数の点があるうちは，そのような点を始点とします．次数偶数の点で詰むことはありえないので終点も次数奇数の点です．

次数奇数の点がなくなったら，好きな点からスタートします．今度は極大な walk はすべて始点に戻ってくるサイクルになります．

結局，辺集合が「次数奇数の始点・終点とするパス」「サイクル」に分割されます．この向き付けが条件を満たすことは明らかです．

このような分割は Eulerian Partition といったりすると思います．