Codeforces Round #512

CでWAを引きすぎて飛ばしてしまい、Dから解いたので574位になってしまいました、、、

C - Vasya and Golden Ticket

0を除いて考えても同じなのではじめに0を除去しておきます。除去後の文字列が空列なら、これは"0...0"という入力に対する場合であり、"YES"を返します。

そうでない場合、 i番目の桁までの桁和(累積和)をとり、 S[i]とします。1ブロックの桁和としてありえるのは、  S[1], S[2], \ldots, S[n - 1]なので、それぞれに対し可能かどうか判定していきます。なお、ここでの文字列の長さ、 nはトリミング後の長さとします。

可能かどうかの判定は左から貪欲に見ていけばいいです。事前に0を削除しておかないと、貪欲で判定していくときに、可能な最長の部分列を見たり、特別処理をしたりする必要が出てきて多少バグらせやすくなると思います。

たとえば、"1100000"は、明らかに可能ですが、"1" + "1" + "00..."に分けようとするとダメで、"1" + "100..."に分けないとだめです。もしくは最後に"00.."が続いた場合は特別処理するとかしないとダメですね。

D - Vasya and Triangle

1以上の整数 n, mと整数 kが与えられるので、長方形 (0, 0), (n, 0), (0, m), (n, m)に収まっているような 格子点3点からなる三角形で面積が \frac{nm}{k}となるものを一つ構成せよ、という問題

考えたことと解法

格子点からなる三角形の面積が0.5刻みであることは知っていたので、とりあえず、 \frac{nm}{k}半整数じゃない場合は"NO"を 返して、半整数の場合にどうなるかを考えました。

いくつか試してみると、作れるなあという気分になって構成を試みます(後述しますが、長方形内に収まる三角形の面積は、実は0.5から \frac{nm}{2}までの0.5刻みのものがすべて構築可能です。)。

面積が半整数となる場合を考えましょう。このとき 2S = \frac{2nm}{k}は整数です。

うまく約分するとこれが整数になることから、 k = k_1k_2となるような1以上の整数 k_1, k_2が存在し、 これらを使って2整数 a, b a = \frac{2n}{k_1}, b = \frac{m}{k_2} または a = \frac{n}{k_1}, b = \frac{2m}{k_2}となるように作ることができます。このどちらかは、 a, bがそれぞれ n, m以下になっているはずです \max(k_1, k_2) \ge 2なので)。 よって3点 (0, 0), (a, 0), (0, b)を選べば、面積が \frac{ab}{2} = 2S / 2 = Sの面積が得られます。

 k_1としては、 nとkのgcdを考えればいいですね。

もっと良い方法

いま、面積が k \ (1 \le 2k \le nm)となるような面積の三角形を構成することを考えます。 三点、 (0, 0), (x_1, y_1), (x_2, y_2)からなる三角形の面積が、 \frac{1}{2}|x_1y_2 - x_2 y_1| となることを用います。 いま、とりあえず絶対値の中身が正になる場合を考えると、 2k = x_1y_2 - x_2 y_1です。 このとき、 x_1 nに固定し、 y_2 = \lceil \frac{2k}{n}\rceilとして、残りの項で、面積を調整する ことを考えます。このとき、 x_2y_1 \lt nとなります。 さて、ここまで来ると y_1 = 1, x_2 = 2k - x_1y_2とすればいいことがわかります。

こうして構築した、 (x_1, y_1), (x_2, y_2)が長方形内に入っていることを確認してみましょう。  x_1, y_1は明らかに大丈夫ですね。 y_2 2k \le nmであることから m以下です。 いま、 x_2y_1 \lt nですから x_2 \lt nが示せ、結局三角形が長方形に収まっていることがわかりました。

E - Vasya and Good Sequences

考えたこと

popcountが同じ数字は作ることができるので、数字そのものは重要ではなく、数字のpopcountのみが重要です。そこで、  a_1, \ldots, a_nの代わりに、対応する要素のpopcountの配列 p_1, \ldots, p_nを考えることにします。 連続部分列 a_l, \ldots, a_rがGood Sequenceになる必要十分条件は、それに含まれる p_iの和が偶数で、 かつ、そのうち最大の p_i p_mとして p_l + \ldots + p_r \ge 2p_mが成り立つことです。

これをセグ木でも使って高速に数え上げるんだろう、と考えましたがお手上げでした。実は、問題文の条件にあった a_i \ge 1という条件が本質でした。

まず、popcountの和が偶数になる条件を考えましょう。これのみを満たす連続部分列を数えることは、累積和などを使うことによって簡単にできるので省略します。

2つ目の条件 p_l + \ldots + p_r \ge 2p_m成り立たないようなものを数え上げることにしましょう。 これが成り立たないのは p_l + \ldots + p_r \lt 2p_mの場合ですが、 2p_mが高々30程度で、 p_i \ge 1であることに注目すると、連続部分列の長さは長くても30程度です。なので、それぞれの p_i p_mとした場合を考え、数え上げれば大丈夫です。こうしてこの問題が O(n)で解けました。