昨夜は久しぶりにまともな時間に寝れた。今日起きたのは昼だった。

最近電子工作をしていたら死ぬほど遅い時間になっていることが何度もあるのでまともな生活に戻したい。

---

ABC276に出た。久しぶりのRatedだったが、6完早解きで黄perfを出しHighestを更新して1級になれた。1級に上がれるチャンスのたびにこけていたので嬉しい。

A: やるだけ

B: やるだけ

C: 後ろから見ていって最初に$P_k>P_{k+1}$になっているところを見つける。その時の$P_k$の次に大きい$P_i\ (k<i)$を探し、$P_k$と$P_i$の値を入れ替える。kより後ろを降順ソートすれば終わり。ちゃんとした証明をやらずに雰囲気でやってしまったので不安だったがACだった。

D: すべての$A_i$について、2と3で何回割れるか出しておく(2と3の素因数分解時の指数を求める)。これは$O(\log(A_i))$なので速度の心配はない。2と3で割れるだけ割った時の値が異なる要素があれば目標は達成できない。2と3それぞれについて、(指数-指数の最小値)の総和を求めれば答えになる。

最初2と3で割れるだけ割った時の値が1でなければ～としてしまい1WA。

E: 始点を壁としたうえで、始点の隣接4マスについてどこかから別のどこかに行けるかBFSなりなんなりで判定すればよい。$O(HW)$。

F: $\frac{\sum_{1\leq i \leq K} \sum_{1 \leq j \leq K} \max(A_i, A_j)}{K^2} $を求めればよい。$1/K$は普通に計算するか適宜前計算すればよい。問題は総和部分。

Kが1増えたときの総和部分の増分は$\sum_{1\leq i \leq K-1} 2\max(A_i, A_K) + A_K$となる。maxを含む総和が大変に面倒そうだが、$A_i$の値域が$10^5$程度のオーダーなので、適宜BITなどに記録していけば$A_K$未満の$A_i$の数と$A_K$以上の$A_i$の総和を出すことが出来る。これで答えが求まる。

わりかし式変形してやるだけな問題ではあるが、この問題が水diffで結構驚いた。こえ～。