まえがき
ぺこだよ〜〜！！！
最近，今日の一曲で載せるような曲が思いつかね
本文
昨日と一昨日は二日連続でAtCoderのコンテストがありましたね．
一昨日も昨日も，どっちも後１問解けそうなのに解けない．っていうやらかしをして激激激激激激....
破滅です．
とまあ競プロの話題をブログにあげるくらいには競プロのモチベが回復してきました．
ABC181 E- Transformable Teacher
- [二分探索,尺取り法,計算量削減,if文,else文]
解説してません
まず，N人の児童について，Hをソートして，H_0 <= H_1 <= H_2 <= ... <= H_n-1 とします．
ここに，先生をくわえて，
H_0 <= H_1 <= ... <= W_i <= ... <= H_n-1
となるように，まあ，いわゆる背の順に並んでもらいます．
この時，背の順に並んだN+1人でペアを作ってもらうとき，ペアを組むべき人間は両隣の人間のどちらかにするのが最適だと示せます（僕は示せました)
え，本当に示せたのかな？まあ示せてるのか知らないけどいいや．（あれ…？）
まあ，四人取り出してみます．
その身長を A (<=) B (<=) C (<=) D とします．
この時，AB,CDというふうにペアを組んだ時のスコアがAC,BDの時，AD,BCの時のスコアより小さいみたいな感じなことを数式で見ていきましょう．
AB,CDの時 スコアは B-A + D-C
AC,BDのとき
スコアはC-A + D-B 1との大小を比較する
(B-A+D-C) - (C-A+D-B) = 2B - 2C = 2 (B-C) <= 0 (∵ B <= C)
よって，AB,CDの時のスコアの方がAC,BDでペアを組んだ時のスコアより低いAD,BCのとき
スコアは D-A + C-B 1との大小を比較する
(B-A+D-C) - (D-A+C-B) = 2B - 2C = 2 (B-C) <= 0
AB,CDの時のスコア < AD,BCで組んだ時のスコア
で，隣同士で組んだ時のスコアが一番低い！
って言おうと思ったんだけど，これだと4人に対してしか示せてないからダメなのかもしれないな〜って思い始めてきた…
まあ結局はACしてるから，N人の時でも身長が近い人間と組むのがいいんだけど...
まぁ，N+1人が背の順に並んだとしよう，そしたら前から二人ずつペアを作って行けばスコアが低くなる！！（って示せたとしよう！)
先生の身長がw_i(0<=i < m)のときの先生の位置っていうのを求めるんだけど，これを毎回N人の並び見て決めてたら大変(計算量的に)だから，ここは尺取り法とか二分探索を使って求めるのじゃ．
まずこの部分から説明〜
俺は尺取りバズーカを使ったので尺取バズーカで話します．
とりあえずWはソート出来ているっていう前提で．
まず，w_0のとき背の順で前から
h0, h1, w_0, h2, ... , hnっていうふうに並んでいた
この次に，w_1で背の順に並べると
h0, w_1, h1, h2 , ... ,hn-1
こんなふうに並ぶことはありません．なぜなら w_0 <= w_1 だからです
つまり，w_0が，i番目の児童のより背が大きかったとき，w_1はi番目の児童より背が小さくなることはない
こんな感じで先生の位置を求める方針にすると，M個の先生の身長に対して，先生の適切な位置を求める計算は，全体でN回程度で求めることが出来るのです！！！
（僕はここで実装を失敗してN回で求めることが出来ずTLEでした)
解けない原因を思い出したらこれ以上ブログ書く気が起きなくなったので終わりにします
あとがき
ごめんｗｗ
