コンテストページ
https://codeforces.com/contest/130
✔A - Three Strings
a[i]==c[i] or b[i]==c[i] がすべての場所で成り立っているかどうかを確かめればよいです。
✔B - Motarack's Birthday
-1 と隣接しているものを列挙して、それの最大と最小の平均にするとよいです。
✔C - Ayoub's function
n-m を（'0' の数）m+1（'1' の間の数）箇所になるべく均等に散らしましょう。商と余りを使います。
✔D - Time to Run
- 次のものを h-1 回です。
- 'R' が w-1 個
- "DUL" が w-1 個
- 'D' が 1 個
- そして 'R' を w-1 個
- 'L' を w-1 個
- 'U' を h-1 個です。
圧縮パートいります？ という気持ちになったのですが、たしかにこれがなければそのときに行ける場所に適当に行くだけで絶対に詰みませんから、仕方がありません。
✖E - Nanosoft
'G','Y','R','B' それぞれに関してそれぞれの方向に、どれだけ四角く伸びているかを DP して、それらの Min を計算です。すると与えられた範囲で大きさ x が作れる条件は、x くらい小さくした範囲での Max が x 以上であることですから、二分探索が出来ます。
計算量です。Max( N, M ) を L と表しましょう。累積和と二次元セグツリーの構築は Θ( L ^ 2 ) です。取得クエリは 1 回あたり Θ( (lg L) ^ 2 ) ですから、二分探索をして、Θ( (lg L) ^ 3 ) です。合わせると Θ( L2 + Q * (lg L) ^ 3 ) です。間に合うわけがありません。（はい！？）
ツイッターのご様子
E
各クエリに答えるとき，答えに対して二分探索できる．250個の数値が指定した長方形領域にあるかを調べるために500*500の二次元累積和を250個作っておけば良い．メモリ怖かったけど計算したら大丈夫だった．
— laycrs (@laycrs) February 13, 2020
難しそうです。
log3つ乗せて落ちて虚無定数倍高速化をやりまくったなれの果てがこれですhttps://t.co/nxMC64dING
— アルメリア (@armeria_betrue) February 13, 2020
え〜〜、間に合うのですね。これが徳の違いということでしょうか。ぐぬぬ……
