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)$ で解けました。