AtCoder Beginner Contest 223 (ABC 223) に参加して， ABCDEFの6完92'59" 259位でした．記録です．

問題へのリンク

A - Exact Price

cout << (X > 0 and X % 100 == 0 ? "Yes\n" : "No\n";

B - String Shifting

回数に制限はないので，全部左シフトだとして良いです． 0 回から S.size() - 1 回までの左シフトを順に作って， 辞書順最小と最大のものを作れば良いです．

$O(N^3)$ のような気が一瞬してしまいましたが，そんなことはなくて $O(N^2)$ ですから間に合います．($N := $S.size())

C - Doukasen

公式解説 に載っている賢い解にびっくりしてしまいましたが，コンテストでは 次のように解きました．

以下の(1),(2),(3)が成り立つ間，(4)を実行する．

  • (1) 左の火が区間 i に時刻 p に入ろうとしている．

  • (2) 右の火が区間 j に時刻 q に入ろうとしている．

  • (3) i < j

  • (4) p < q なら，p += A[i] / B[i]; i++; そうでなければ， q += A[j] / B[j]; j--;

このループを抜けると，左右の火が時間差 p-q で同じ区間 i に 入ろうとしているので，どこで出会うか計算できる．

D - Restricted Permutation

各 i = 1, …, N に対して，2つの集合 prv, nxt を用意します． 気分は次の通りです．

  • prv[i] … i よりも先に来なければならない数
  • nxt[i] … i よりも後に来なければならない数

実際には，各 $(A_i, B_i)$ に対して，$A_i$ を $\text{prv}[B_i]$ に， $B_i$ を $\text{nxt}[A_i]$ に入れます．

答を左から書いていくことにして，prv[i] が空なら，i を書くことができます． 辞書順最小にしたいので，priority queue を使います．

  • 最初の状態で prv[i] が空である i を全部キューに入れておきます．
  • キューがからでない間ループ:
    • キューから i を取り出して出力します．
    • nxt[i] の要素 j に対して，
      • prv[j] から i を取り除きます．
      • prv[j] が空になったら，j をキューに入れます．

このままだと，同じ j が複数回キューに入ってしまう可能性があります． キューに入れる前に重複チェックが必要です．これを忘れて， また，直し方を間違えて，2 ペナルティーでした．もったいない….

E - Placing Rectangles

3つの長方形の配置は以下のいずれか (ということを無証明で通してしまいました)

  • 3つ縦に並ぶ
  • 3つ横に並ぶ
  • 横2行で，1行に1個，もう1行に2個．
  • 縦2列で，1列に1個，もう1列に2個．

各々の場合について，A, B, C が X, Y に入るかどうか判定します．

F - Parenthesis Checking

( を 1 に，) を -1 に置き換えて，位置 i までの累積和を $S_i$ と すると，括弧列が全体として正しいための 必要十分条件は，$S_N = 0$ かつ すべての $i$ について $S_i \geq 0$ であることです． したがって，位置 l から 位置 r までの括弧列が正しいための条件は， 下の両方が成り立つことです．

  • $S_{l-1} = S_r$
  • すべての $i \in [l, r]$ に対して，$S_i \geq S_r$

これは，次のように言い換えられます:

  • $S_{l-1} = S_r$ かつ $\min\{S_i \mid i \in [l, r]\} = S_r$

また，位置$l$と$r$の文字を入れ替えたときには，$S$ は次のように変わります:

  • 両方が同じ文字なら，変化無し
  • ( と ) の場合には，$i \in [l, r-1]$ について，$S_i$ が 2 減る．
  • ) と ( の場合には，$i \in [l, r-1]$ について，$S_i$ が 2 増える．

したがって，$S_i$ の値を，区間加算と区間最小値取得ができる セグメント木で管理することで答が得られます．

G - Vertex Deletion

E が解けた時点で残り40分でした． F と G の問題文をざっと読んで，G は解けそうになく (そもそもマッチングという ことばが分からない (ので検索した))，F は解けそうだったので，F に 行きました．結果的には， G は 40分あれば解けたことがわかったので失敗だったのですが， すぐには方針が思いつかなかったのでやむを得ないですかねえ．うーむ．

最小マッチングというのは，pairwise に頂点を共有しない辺の集合 $X$ で 要素数最小のもの，ということが検索して分かったので，それで考えます． グラフは木ですから，$X$ は，葉から順に貪欲に取っていけば良いです (ということにすぐ思い当たれば G に行けたかもしれない．未練たらしい…)

正確には次のようになるでしょうか: 適当に根を考えたとき， $X$ に入っている辺の両端の頂点のうち，根に近い方の点からなる集合を $Y$ とします．$Y$ は次の条件を満たすとして良いです: 頂点 $v$ に関し，

  • $v$ の子がすべて $Y$ に属していれば $v$ は $Y$ に属さない．
  • $v$ の子で $Y$ に属していないものがあれば，$v$ は $Y$ に属する．

上の条件は当然で，下の条件はもし満たしていなければ， 満たすように $X$ を (要素数を変えずに) 変更することができます． 上の条件から，根 $r$ を決めたときに $Y$ は確定します．これを $Y_r$ と 書くことにします． $r$ が $Y_r$ に属するときには，$r$ とその辺を取り除いてしまうと 最小マッチングが減り，$r$ が $Y_r$ に属さなければ，最小マッチングは 減りません．ということで，各$r$に対して $r \in Y_r$ かどうかを判定すれば よいことになりました．

$r \in Y_r$ かどうかは， $f(p) = \bigvee \{ \neg f(q) \mid q \text{ は } p \text{ の子 }\}$ と，子の値からモノイド演算で定義した $f(r)$ の値として決定できますから， 全方位木DPで求めることができます．

H - Xor Query

問題も読めませんでした． あとで解説ACしました ．