yukicoder contest 240

　Eまでの五完でした。Fは難しかったので仕方ないかな、という印象。
　ただ、たくさんWAを出しているのはよくないですね。yukicoderはペナルティなどないので、ついたくさん提出してしまう。

コンテストへのリンク

No.1006 Share an Integer

　エラトステネスの篩の要領で全てのiについてD[i]を列挙するのが自然だと思うけど、解説(writer解)では違うことをやっていた。

　うーん、解の絞り方が難しい（よく分からず……）。

No.1008 Bench Craftsman

　解説AC。

　cに関する単調性は見えるので、二分探索がまず思い浮かぶ。しかし、愚直にやると判定にO(NM)かかり困る。

　困って、違う方法がないか……と考えてしまったのだけど、二分探索の方針は正しかった。

 ｃを固定して判定問題を考えたとき、各人の重さのベンチへの寄与が山形の一次関数（等差数列）二つになるので、それらの和をimos法（など）で計算できないか？　と考える方針が正しかった。
　二回累積和を取るという方法は見たことなかったと思う。覚えておきたい。

　なお、二分探索を考えたとき、一点への寄与が上手く式で表されるのでは？　と考えたのだが、これでは上手くいかない。0とのmaxを取る部分のせいで簡単な式に表せない。

　一点に着目する方針を考えて上手くいかなかったのなら、次は一人に着目するというのは自然な流れなはずだけど……。

　なかなか視点を変えて考えるのは難しい。