| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ||
| 結果 | AC | AC | AC | AC |
コンテスト後の提出：E → ■
全体感想
ABCD の89分4完 + 4ペナ。
問題Eも、考察が軽く易しい問題（ABC-Fでも出うるくらいのレベルだと思いました）だったのですが、解き終われず。レートが下がるのはまぁ良いのですが、先週と今週で、解けるべきレベル帯の問題を落としまくっているのが悲しいです。今回のDEあたりは、それこそ赤レート～くらいの人にとっては、やるだけに近いレベルでしょうし。
レートとしてはこれだけ不出来に感じる回でもパフォ2200～出ていたり、赤パフォも難なく出せそうな範囲に見えているのは希望ではあるのですが。そろそろ過去問環境に言語アプデ適用なので、atcoder埋めの再開しつつ、黄～橙あたりの問題（現状、しっかり考えればほぼ解けるが瞬殺はなかなかできない）の2周目をしっかりやり込むなどして速度・精度を鍛えたいと思います。
問題C – Lamps
最近、「一見計算量が足りなさそうだけど、実は間に合う」という問題、わりと続きましたね。この手の問題にはわりとすぐに反応できているので良い。
サンプルは [1,0,0,1,0] → [1,2,2,1,2] → [3,3,4,4,3] → [4,5,5,5,4] → [5,5,5,5,5] です。単調増加になることはすぐに分かり、巨大な $K$ では定数になることも分かります。わりと増大速度が速くて $K$ が小さくて済みそうかな？と思います。
とかやってみると、$\log N$ っぽいことも割と察せられると思います。
あとは累積和（imos法）を使った更新を実装を書いて、最悪ケースである[0,0,…,0,0] （20万個）で試したところ、50ステップ以内で済んだので、そのまま提出。
$\log N$ になることまで証明できなくとも最悪ケースが何であるかは単調性から簡単に分かるので、それで実行時間を確認するのがお手軽ですね。
（追記）数列自体が単調増加するのは嘘でした。[2,0,0] → [1,2,2] など。最悪ケースが [0,0,0,0] であることは、操作を $f$ として、操作の単調性（$A\leq B\implies f(A)\leq f(B)$）から分かります。
Cで数列が単調増加というの、どういう意味で言っていますか？(ex.[2,0,0]→[1,1,1]で、1番目を見ると減少しています)
— γ（橙） (@b2563125) June 14, 2020
問題D – Knapsack Queries on a tree
ナップサック問題の基本解法については上の問題で学べます。競プロでは、これら（dp・半分全列挙）以外が問われることはほとんどないように思います。
今回は根付き木上でこれを何度も解くわけですが、最低限ふつうのナップサック問題が解けないことにはお話にならないので、解法はこれらの延長線上で考えることになります。
$n = \log_2 N$ とします。
クエリごとに 1 から計算する
まずはこれを考えます。意外と悪くない計算量です。半分全列挙＋ソート＋尺取りで、$\Theta(Q2^{n/2}\log 2^{n/2})$ が実現できます。3秒制限時間で結構きわどいと思ったので、実装して提出します。→ TLE
コードテストで最悪ケースに近いもの（↓）を投げると、6800ms でした。
「定数倍改善を頑張る」「別方針を考える」「別問題にすすむ」などが考えられます。半分全列挙するときの、片方の集合についてメモ化（全列挙＋ソートまで）できるというのは気づいていたので、定数倍改善のアテもあったのですが、3秒を切れるか判断できず。別問題をうろうろしながら別方針を考えていました。（Pythonでは試していないので分かりませんが、一般には色々な高速化を頑張れば通る範囲のようです。）
根に近い部分の計算を再利用する
流石にこれをやらせたい問題なのだろうというのは分かります。上述の方針で、根に近い半分を全列挙＋ソートしてしまうのは、$\Theta(2^{n/2}\cdot 2^{n/2}\log2^{n/2})$ 程度なのでできそうです。しかし、下側集合を計算したあと結局（二分探索 / ソート+尺取り）で $\log$ がついてしまい、定数倍改善の範囲になってしまいます。
上側集合の事前計算が、クエリに対して計算量が軽そうなので、こちら側の負荷を高めて、クエリごとの（二分探索 / ソート+尺取り）を避けられるデータの持ち方をすることを考えます。
これは、全列挙＋ソートしたあとに、sparse なデータを dense なデータにしてしまうことで可能です。つまり、根に近いの各ノードに対して重さ上限から最大価値を求められる配列を作ってしまえば、任意の重さ上限のクエリに二分探索なしで答えられるようになります。実際にはこれを考えたあと、「全列挙＋ソート」という方針はやめて、直接 dense な配列を計算しました。
事前計算に $\Theta(2^{n/2} L_{\max}$、クエリごとに $\Theta(2^{n/2})$ で、計算量 $\Theta((Q+L_{\max})\sqrt{N})$ になって、ACをとることができました
その他
（１）「半分全列挙 ＋ 上側の事前計算・ソート」解法について、「上側の事前計算に余裕がある」ということでしたが、$18$ を $9+9$ と分けるのではなく、$10+8$ や $11+7$ と分けるだけでもクエリあたりの計算量が 約 $1/2$ 倍、約 $1/4$ 倍と軽くなります。事前計算の負荷との兼ね合いで調整すると良いですね。気づいていませんでした。
（２）そもそもナップサック問題の計算量
私は、半分全列挙＋（ソート＋ソート＋尺取り / ソート+二分探索）のどちらかで、いずれにしても $\Theta(2^{n/2}\log n)$ のオーダーだと思っていたのですが、 $\Theta(2^{n/2})$ になるようです。（これで愚直が通るかな？試しておきます）
「資料になった」ものを引用します。
マージソートの計算量解析で、$T(N) = 2T(N/2) + \Theta(N)$ より $T(N) = \Theta(N\log N)$ を導く議論がありますが、同様の分割統治の形で考えるのであれば、左半分のソート順と右半分のソート順が完全に一致することから、$T(N) = T(N/2) + \Theta(N)$ が言えるのですね。基本的なトピックで無知があったことが知れて、とても嬉しいです。
問題E – O(rand)
問題Dにつられて少し半分全列挙を考えますが、マージ対象の選定が簡単ではなくて上手くいきません。
とりあえず、桁ごとに分解して、どういう選び方が要求されているのか確認します。
- $S,T$ の $i$ 桁目が $(0,0)$ のとき：選ぶ数の $i$ 桁目はすべて $0$．
- $S,T$ の $i$ 桁目が $(1,1)$ のとき：選ぶ数の $i$ 桁目はすべて $1$．
- $S,T$ の $i$ 桁目が $(1,0)$ のとき：条件に合う選び方は存在しない．
- $S,T$ の $i$ 桁目が $(0,1)$ のとき：選ぶ数の $i$ 桁目は、$0,1$ が両方存在する．
という条件になっています。とりあえず、$(0,0)$ や $(1,1)$ があった場合には使えないと確定している数は捨ててしまい、$(1,0)$ があった場合には $0$ を出力して問題解決。$(0,1)$ になっている桁と、捨てていない数だけを計算対象とすることで、以下の問題に帰着されます。
$2^L$ 未満の数 $A_1,A_2,\ldots$ がある。どの桁も $0,1$ 両方が現れるように $1$ ～ $K$ 個を選べ。
（解説の「簡単のため $S = 0, T = 2^L − 1, 0 \leq A_i < 2^L$ としてよいです」部分です）
（１）dp 方針
(選んだものの個数、これまでに選んだものの状態) みたいなのを持とうとします。「選んだものの状態」→ 桁ごとに、「0のみ選んだ / 1のみ選んだ / 両方選んだ」があります。$3^{18}\cdot NK$ 程度の遷移があります。
（２）包除原理
「$0$, $1$ の両方とも使う」は、余事象の方が簡単です。$X_i$ を、「$i$ 桁目は $0$ しか選んでいない or $i$ 桁目は $1$ しか選んでいない」選び方全体として、$X_{i_1,i_2,\ldots} = X_{i_1}\cap X_{i_2}\cap\cdots$ の要素数を計算すればよさそうです。$2^{18}$ 程度の個数の集合ごとに、$\Theta(N)$ の計算を行えばよいです。
この両方とも思い浮かんだあと、本番中の私はなぜか、実装が簡単そうだなと思って（１）を選択してしまい、20分ロスします（「$3^{18}$ って意外と小さいの知ってますよ、$3^2=10$ と近似して $3^{18}=10^5$ 程度です！」とかやっていて…ひどすぎました）。
終了 6 分前くらいに気づいて慌てて（２）の実装を始めますが、解き終わらず…ｗ
$X_{i_1,\ldots,i_k}$ については、要するに 「$(i_1,\ldots,i_k)$ 桁目だけ取り出せば定数」という条件があるので、ビットマスクと and をとった上で、「定数だけを選んでいる」という条件になります。一意な値ごとに数列 $A_i$ での出現件数を数えて、二項係数を足し合わせるだけです。
