ちょっとくらい散歩に出ようと思っていたのだが、基板をいじっていたら夕方になっていた。

---

ABC292に出た。

A: toupper

B: イエローカードとレッドカードを別に管理してもいいと思うが、めんどいのでレッドカード=イエローカード2枚として実装した

C: 各k≦Nについてk=ABとなるような(A,B)の組の数を数える。これをS(k)とする。各k≦NについてS(k)×S(N-k)の和をとる。これでO(N)で解ける。

D: UFかなんかで連結成分を管理して愚直に実装すればよい。条件からして全て輪になるのでそのことを利用した実装もあるかもしれないが、アドホックな考察は脳のリソースの無駄にしかならなさそうなのでやめた。

E: ちょっと実験してみれば分かるが、要するにある頂点から到達可能な全ての頂点に辺を張れということになる。ある頂点から到達可能な頂点はBFSでO(N+M)くらいで出せる。これで求めた到達可能な頂点の数から既にある辺の数を引けばよい。各頂点についてやればO(N(N+M))であり、NとMが小さいので間に合う。

F: 十分に長細い長方形なら長辺に正三角形の一辺を重ねればよい。ここから少しでも傾けると損にしかならないことが分かる。具体的には、長辺が短辺の2/√3倍以上ならこの方針で行ける。問題は正方形に近い長方形の場合。

ちょっと実験してみれば、正三角形の1点が長方形の隅であとの2点が長方形の辺に接する形にするべきことが分かる。このような正三角形は一意であり、図を描いて三平方の定理で受験数学よろしく頑張ると$x^2=2a\sqrt{b^2-x^2}+2b\sqrt{a^2-x^2}$という方程式が出る。これをwolframにぶちこむと$x=2\sqrt{a^2+b^2-\sqrt{3}ab}$という答えが出てくるのでそのまま実装して終了。O(1)数学だった。にぶたんとかの想定なのかもしれんがめんどい。

G: 何もわからない。

Ex: 割と考察が進んだのだがWAがとれず。区間最大値取得と区間加算が出来る遅延セグ木に(パフォーマンスの累積和, コンテスト数)のペアを乗せ、区間加算によってパフォーマンス累積和を更新して、平均パフォの最大がBを超えるようならセグ木上の二分探索で平均パフォがBを超える場所を探す感じにした。たぶん大筋としては解けていると思うのだが、どうにもWAがとれない。

---

今日摂取したコンテンツ。

移動の開始・終了、ジャンプの感覚などについて他のゲームと比較して詳しく述べられているのがとても参考になった。

英語なのであんまりよく分からない部分が多いがスライドで分かる部分もある。複数の解法を用意するあたりは参考になった。その内もうちょっとちゃんと見る。