結果
D問題までの4完で久しぶりにレートが下がった。
A問題
最近はA問題でもちょいひねりが入ったりしていた気もするが今回はいやに簡単だった。
B問題
特になし。
C問題
半分に切る場合が最大というのはすぐわかったが、それが複数ある場合の条件については確信が持てなかった。結局いくらか例を考えてたぶん複数ありえるのは両辺の半分ずつの点にある場合だけだろうと理屈はわからないままに提出してAC。解説PDFを見て中心がどうのこうのということに気づく。なるほどそういうことか(まだ微妙だけど)。
やや面倒だけど浮動小数点数もstd::coutを使って出力するように意識付けしている最中。ようやく調べずにstd::fixとstd::setprecision(15)が思い出せるようになってきた。
D問題
尺取り法が書けない人間なので二分探索を書く。尺取り法でできるものはおおむね累積和+二分探索でもできているので痛い目を見ない限りこのまま尺取り法を回避していくのだろうなぁ。
E問題
パッと見で最長共通部分列問題っぽいなと思ったし制約もでやってねというふうに見えたのでずっとそういうDPを考えていたが結局解けなかった。最長共通部分列問題っぽいと思いながら片方の文字だけで遷移を考えようとしていたのはひどい。
終了後少し落ち着いて考えたら変化分だけ考えて累積和取って前の結果に足すということをやれば大丈夫なことに気づいてAC。終わって11分後に通せたわけだけど、実際コンテスト時間があと11分あれば通せたかというとたぶん無理だった。無駄な考察をしてドツボにはまっている時間が長すぎたわけだし、残り30分くらいになったタイミングで一度冷静になるべきだった。
F問題
コンテスト後に少し考えてみたがわからず解説を見てAC。
端に来うるものだけを考えれば、たとえば右や上の最大値は「1減り続ける→変化なし→1増え続ける」となるのはすぐわかった。下限も反対の変化になるので、と
はそれぞれ凸っぽい感じになると思って、ならこれらの掛け算も凸になる？ と思って三分探索してみたけどWA。凸にならないこともたくさんありそう。
切り替わりタイミングだけしか候補になりえないというのは言われてみれば確かにというくらいで思いつきそうにない。実装もかなり重複の多いものになってしまって時間もかかったし、minとmaxを書き換え忘れるバグで1WA出してしまった。難しい。
