東京海上日動プログラミングコンテスト2020

↑tokyoじゃなくてtokioなんですね

無

注意力が本質かな～やっぱ

$0, 0 \cdots, 0$ から始めて何が起きるかに思いを馳せると思考要素が無いことに気づくことができる

木上のナップサック問題とかあったな～と思い出しながら考える、がとてもじゃないがdp的な方針では解けない

普通に半分全列挙だな～という気持ちになるが、ソートいるし困るな～

冷静になると上半分の候補は少ないから、そこだけ計算結果を持ってやればいいのでは？と気づく $2^A$ 未満を前計算するなら雑に見積もって $O(4^A \log + Q N \log / 2^A)$

$A=10$ で組んでテストすると普通に間に合いそうなので出すと通る

適切な前処理をすれば $S=0, T=2^k-1$ の問題になることはすぐわかる

この見た目で包除しないわけないので、どうやるかを考えると、bitごとに全部等しい / そうではないに分けるのが筋が良さそうとわかる

包除の計算で何が必要かと言うと、 $b_1,\cdots,b_k$ 番目のbitに注目してそれが $c_1,\cdots,c_k$ になるような個数を求め、適切な場合の数を掛ければよい

$b, c$ を全部試すと $3^{18}$ がついて終わるが、少し考えると $b$ を決め打ってそのbitだけ抜き出した値ごとに分類すれば十分高速に解ける

対称性を使って左の辺から1点、上下の辺から1点ずつ取るパターンに帰着する

色々考えると、上下の点を結ぶ辺の傾きが同じであれば、内部の点の個数は右に行くほど増加することがわかる。

(理由: 1動かすと面積は $\dfrac{H}{2}$ 増えるので、ピックの定理より周上の点が $H$ より多く増えなければ減少することはないが、そうはなりません

(もしそんなことがあったら、直感的に嫌な気分になります。))

ここからは、コードテスト上で熱烈枝狩り+定数倍改善で頑張る。何が最大ケースかわかりにくいが、この方針だと1000 100000 100000とかが遅かった。

なんか久しぶりに順調に問題が解けて満足したので競プロ最高～～の気持ちになれて良かったです

HIR180's diary