全国統一プログラミング王決定戦本戦解説（C～E）

今回はオンサイト参加でした！

成績は200人中46位。なかなか健闘したんじゃないでしょうか。

f:id:betrue12:20190218220603p:plain

参加記はまた気が向いたら別記事で書きます。この記事ではいつものように問題解説を。

現在Eまで書いていますが、Fは後日追記したいと思っています。G以降はまだ通せていません…。

C - Come Together

解法

まず、縦の座標と横の座標を独立に考えられることに気付くと良いです。縦の座標を揃えるための操作回数と横の座標を揃えるための操作回数の合計が答えとなります。

では、縦の座標についてはどの座標に全ての駒を集めるのが最適でしょうか。結論を書くと、これは全部の駒の座標の中央値になります。これについては同じ知識を使う問題の解説を以前書いたので、そちらを参考にしてください。

ARC100 参加記録 - ARMERIA

というわけで中央値を求めたいですが、駒の数が全部で $HW-K$ 個あるので全てを列挙することはできません。そこで、次のようにして駒の縦座標の「分布」を求めることにします。

まず $K$ 個の駒を取り除く前の分布を作る。1行目から $H$ 行目まで全てに $W$ 個の駒があるので、分布は $\lbrack W, W, ..., W\rbrack$ となる。
そこから、 $K$ 個取り除いた駒それぞれについてそれぞれの $R_{i}$ に対応する個数を1減らす。

この累積和を下から取っていき、ちょうど $HW-K$ 個の半分以上になったところが全ての座標の中央値になります。中央値が求まれば、先程の分布をそのまま使って駒の移動回数を求めることが出来ます。縦と横それぞれについて同じ計算をして足したものが答えです。

ACコード

（C++）Submission #4314368 - 全国統一プログラミング王決定戦本戦

D - Deforestation

解法

それぞれの竹から得られるスコアは、その竹を最後に伐採した時刻と一致します。これを求める方法はいくつかありますが、一例を示します。

竹を番号1から順番に見ていきます。このとき、「今見ている竹を伐採する時刻の集合」を順序付き集合（C++なら std::set ）で持っておきます。この集合は、竹を順番に見ていきながら「区間 $\lbrack L_{i}, R_{i}\rbrack$ に入ったら $T_{i}$ をinsertし、区間から出たらeraseする」ことによって管理できます。順序付き集合で持っていればそれぞれの竹について一番大きい要素がわかるので、答えの値に足していけばよいです。

ACコード

Submission #4314235 - 全国統一プログラミング王決定戦本戦

本番は区間更新できるセグメント木を使いましたが、set でめちゃくちゃ簡単に書けますね…

E - Erasure

解法

魔法がたくさんあるので、いくつかにグループ分けして考えたいです。今回は区間の左端の値でグループ分けしてみます。

左から見ていって、左端が $1, 2, ..., i$ の魔法について使う/使わないを決め終わったとします。残りの魔法は $i+1$ 以降のブロックにしか作用しないため、問題の条件を満たすためにはこの時点で $1, ..., i$ のブロックが全て消えていなければいけません。そして $i$ より右側のブロックについては、連続してあるところまでが消えているような状態になっているはずです。

このことから以下のようなDPを考えます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 左端が $1, 2, ..., i$ の魔法について使う/使わないを決め終わったとき、 $1, ..., j$ のブロックが全て消えているような場合の数。ただし、 $i \le j$ とする。

これを計算しましょう。 $i-1$ の状態から遷移してきて $dp\lbrack i \rbrack\lbrack j \rbrack$ の状態になるのは、以下のいずれかのときです。

f:id:betrue12:20190218234730p:plain

左端が番目の魔法まででちょうど番目のブロックまで消えていて、左端が番目の魔法で番目より右側のブロックが消えないパターン。
- 遷移元の場合の数は $dp\lbrack i-1 \rbrack\lbrack j \rbrack$ 通り。
- 左端が $i$ 番目の魔法については、右端が $j$ 以下であるものの使う/使わないは自由。そのような魔法の個数を $m$ とすると $m = \max(0, j-i-K+1)$ であり、係数として $2^{m}$ が掛かる。
左端が番目の魔法までで番目未満のブロックまで消えていて、左端が番目の魔法でちょうど番目のブロックまで消えるパターン。
- 遷移元の場合の数は $dp\lbrack i-1 \rbrack\lbrack i-1 \rbrack + \cdots + dp\lbrack i-1 \rbrack\lbrack j-1 \rbrack$ 通り。
- 左端が $i$ 番目の魔法については、右端が $j$ であるものは必ず使う。そのため $j-i \ge K$ である必要がある。右端が $j$ 未満の魔法の使う/使わないは自由であり、そのような魔法の個数は $j-i-K$ なので係数として $2^{j-i-K}$ が掛かる。

これら2パターンからの遷移を足したものが $dp\lbrack i \rbrack\lbrack j \rbrack$ となります。このうち $dp\lbrack i-1 \rbrack\lbrack i-1 \rbrack + \cdots + dp\lbrack i-1 \rbrack\lbrack j-1 \rbrack$ については、DPの更新時に $j$ を回しながら累積和を取っていくと良いです。

区間の左端としてあり得るものは $N-K$ までなので、答えは左端を $N-K$ まで見て $N$ までのブロックが消えているような場合の数、すなわち $dp\lbrack N-K \rbrack\lbrack N \rbrack$ となります。