Codeforces Round #512
CでWAを引きすぎて飛ばしてしまい、Dから解いたので574位になってしまいました、、、
C - Vasya and Golden Ticket
0を除いて考えても同じなのではじめに0を除去しておきます。除去後の文字列が空列なら、これは"0...0"という入力に対する場合であり、"YES"を返します。
そうでない場合、番目の桁までの桁和(累積和)をとり、とします。1ブロックの桁和としてありえるのは、 なので、それぞれに対し可能かどうか判定していきます。なお、ここでの文字列の長さ、はトリミング後の長さとします。
可能かどうかの判定は左から貪欲に見ていけばいいです。事前に0を削除しておかないと、貪欲で判定していくときに、可能な最長の部分列を見たり、特別処理をしたりする必要が出てきて多少バグらせやすくなると思います。
たとえば、"1100000"は、明らかに可能ですが、"1" + "1" + "00..."に分けようとするとダメで、"1" + "100..."に分けないとだめです。もしくは最後に"00.."が続いた場合は特別処理するとかしないとダメですね。
D - Vasya and Triangle
1以上の整数と整数が与えられるので、長方形に収まっているような 格子点3点からなる三角形で面積がとなるものを一つ構成せよ、という問題
考えたことと解法
格子点からなる三角形の面積が0.5刻みであることは知っていたので、とりあえず、が半整数じゃない場合は"NO"を 返して、半整数の場合にどうなるかを考えました。
いくつか試してみると、作れるなあという気分になって構成を試みます(後述しますが、長方形内に収まる三角形の面積は、実は0.5からまでの0.5刻みのものがすべて構築可能です。)。
面積が半整数となる場合を考えましょう。このときは整数です。
うまく約分するとこれが整数になることから、となるような1以上の整数が存在し、 これらを使って2整数を またはとなるように作ることができます。このどちらかは、がそれぞれ以下になっているはずですなので)。 よって3点を選べば、面積がの面積が得られます。
としては、のgcdを考えればいいですね。
もっと良い方法
いま、面積がとなるような面積の三角形を構成することを考えます。 三点、からなる三角形の面積が、 となることを用います。 いま、とりあえず絶対値の中身が正になる場合を考えると、です。 このとき、をに固定し、として、残りの項で、面積を調整する ことを考えます。このとき、となります。 さて、ここまで来るととすればいいことがわかります。
こうして構築した、が長方形内に入っていることを確認してみましょう。 は明らかに大丈夫ですね。はであることから以下です。 いま、ですからが示せ、結局三角形が長方形に収まっていることがわかりました。
E - Vasya and Good Sequences
考えたこと
popcountが同じ数字は作ることができるので、数字そのものは重要ではなく、数字のpopcountのみが重要です。そこで、 の代わりに、対応する要素のpopcountの配列を考えることにします。 連続部分列がGood Sequenceになる必要十分条件は、それに含まれるの和が偶数で、 かつ、そのうち最大のをとしてが成り立つことです。
これをセグ木でも使って高速に数え上げるんだろう、と考えましたがお手上げでした。実は、問題文の条件にあったという条件が本質でした。
まず、popcountの和が偶数になる条件を考えましょう。これのみを満たす連続部分列を数えることは、累積和などを使うことによって簡単にできるので省略します。
2つ目の条件が成り立たないようなものを数え上げることにしましょう。 これが成り立たないのはの場合ですが、が高々30程度で、であることに注目すると、連続部分列の長さは長くても30程度です。なので、それぞれのをとした場合を考え、数え上げれば大丈夫です。こうしてこの問題がで解けました。