昼まで寝てちょっと外出てごろごろしてたら夜で絶望的な一日だった。

---

ABC308に出た。

A: やるだけ

B: やるだけ

C: 比較関数で分母を払えばよい

D: (X,Y,文字がsnukeの何番目か)という組で位置を持ってBFSすればよい

E: DP[i][j][k]:=文字列Sをi番目まで見たとき、MEXの内j文字目まで持って、0,1,2の内ビットパタンkに対応する数字を含むような取り方のパターン数 とすればよい。最大でもN^3なので64bitに収まる。

F: 通されすぎ。二部マッチングを考えたが、辺の数が最大O(NM)なのでグラフを構築するだけでMLEになる。いい感じの貪欲法を考えるしかない。気付けばそこまで難しくないが、ある程度難しいだろうし時間をかけてもいいだろうでだらだら解いてしまった。

仮に全てのLiが同じ値だった場合、その値以上の価格の商品の数をKとして、Diの大きいクーポン上位K個を使えばよい。これを拡張する。

商品を価格でソートしてクーポンをLでソートする。クーポンをLが大きいものから順に見て行けば、クーポンの対象にできる商品数(Kとする)が単調に増えていくことが分かる。また、後に見るクーポンほどLが小さいので必ず自由に採用できる。優先度付きキューに入れて、その時々の上位K個を採用すればよい。

G: 解けず。Trie木とかを考えたが、もっと簡単な手段があったっぽい。ARCで出されてたら解けていたかもしれないとちょっと思う。まあ解けなかったことを言い訳してもしょうがない。

XORが小さいということは、とにかくビットパタンの差が少ない2項が欲しい。同じ値が2つあれば最良。仮に異なっているなら、なるべく下の桁で異なっている方がよい。と考えると、結局値のソート済み集合において隣接2項だけ見れればよい。multisetで値集合と隣接2項の集合を管理すればたやすく通る。これは気付きたかった。