APIO2016 Gap 解法
1か月後のAPIOに向けてOJ-OIで精進中。APIO2016は珍しく日本語の問題文があるものの、英語でも解説が見当たらなかったので、解法を書き残しておきます。
3 Gap
インタラクティブ問題でした。小課題1と2でMの値の数え方が違うので、それぞれ別々の実装をします。
小課題1
両端からだんだん狭めていけばよく、ceil(N/2)回で求められます。これは瞬殺です。
小課題2
こっちは少し苦戦しました。とりあえず両端を求めて、m、Mとでもおきます。このとき、答えは絶対に(M-m)/N以上になります。うまく均等にしても(M-m)/Nなので、位置にばらつきが出ればこれ以上になります。
よって、区間(m,M)をN個に分割したとき、差が最大になる組は必ずこの分割をまたぎます。図を書きましょう。
よって、両端を求めるのにN+1回、残りのN個の区間を見ていくのに、あとN-2要素含まれているから、N-2+N回
全部でだいたい3N回で、この問題が解けました。
