サボった A[RG]C の under 2600diff が 18 問にまで上ってしまったため、潰します
https://kenkoooo.com/atcoder#/contest/show/4151fce3-bd45-485f-8373-74ec924d182e
1-6問目はこちら : 自戒ばちゃ(1-6問目) - physics0523's 精進ログ
7-12問目はこちら : 自戒ばちゃ(7問目-12問目) - physics0523's 精進ログ
13. E - Examination (ばちゃ中15問目, 2553diff, 自力AC)
可能かどうかの判定は sort してやるだけだが、この考察はそんなに正解に繋がらない。
「今持っている点数が $A_i$ 点の人が、 $B_i$ 点以上取らないと留年」という設定なので、一旦すべてを $2N$ 個のイベントとしてソートしてその順に処理することを考える。
「 $B_i$ 点以上取らないと留年」を捌きやすいのは昇順ソート(一度入ってしまえばそのあと永遠に条件を満たし続けるようにできるので)。
ということで、制約を先に入れて得点が現れた時に好きな制約にマッチングすれば判定問題の別解が得られる。
あとは得点が変わらない人間の数の最大化。やるべきことを以下の二通りに分類する。
- 生徒 $i$ の得点が出てきたとき、生徒 $i$ の制約とマッチ
- 生徒 $j$ の得点が出てきたとき、生徒 $j$ の制約とはマッチできないので誰か適当な人間の制約とマッチする
まず、(得点昇順イベントソートの下で)得点が制約とマッチできるならして損しないことが示せる。
そのうえでマッチ可能性の判定は「全ての時点での残っている制約の個数を管理し、マッチングを作る際に【残っている制約の個数が負になってしまうような時点】ができないかどうか」で判定でき、これは遅セグを使うと実装できる。
Submission #50313460 - AtCoder Regular Contest 147
ドブ系だと思ったけど案外すんなり通せて偉いね
14. D - Neq Neq (ばちゃ中16問目, 2554diff, 自力AC)
とりあえず $A_i$ に同じ要素が隣接していたらどちらも消せない。
しかもそれらを超えて要素が干渉することは無いので同じ要素が隣接する点で問題を分けられ、各問題中には同じ要素が隣接する点は無い。
このもとで、要素の取り出し方が何通りあるかを調べる。
まず、先頭と末尾は絶対に消せない。このもとで、 dp[最後に選んだ要素]={場合の数} をしようとする。
1つ前と2つ前からは絶対に遷移できるが、それ以外の遷移はどうなるか?
実は、遷移元と遷移先の要素を含めて、飛ぶ区間に要素が $3$ 種類以上あれば遷移でき、そうでない時は間1軒までしか遷移できない(もっとも、要素が $2$ 種類なのは ababab... のパターンしかない かつこの事が証明に活きる)ことが示せる。
要素が $3$ 種類以上あると遷移できるが、そのような区間は尺取なりsetを活用するなりでどうにかできる。自分がどうしたかは実装を見てほしい(説明するのがめんどいので)
これ解けるようになったの我ながら偉いなぁ
15. D - Sum of Min of Xor (ばちゃ中18問目, 2593diff, 自力AC)
$A_i$ の下から $d$bit 目を $A_{i,d}$ みたいに書く。
上の桁から見た時に $A_{i,d} \neq A_{j,d}$ と $B_{i,d} \neq B_{j,d}$ の丁度一方が成り立つとき $A_i \oplus A_j$ と $B_i \oplus B_j$ との大小関係が決定づけられる。
この条件をこねると、 $A_{i,d},A_{j,d},B_{i,d},B_{j,d}$ のうち奇数個が $1$ であると言い換えられ、更に言い換えると $C_i= A_i \oplus B_i$ としたときに $C_{i,d} \neq C_{j,d}$ が成り立つと言い換えられる。ここが最重要考察。
ここまで来ればウィニングラン。 $C_{i,d}$ を上の桁から調べて、こいつで問題を分割していく。但しだいぶねっとりしてるので詳細を全て書き留めることはしない。
Submission #50433859 - AtCoder Regular Contest 127
割と地力でどうにかなるのにここまでdiff高いの意外だな、この手の問題の考察/実装速度上げたい。
