/
最近
.rdf
追記
編集
設定
本棚
翌日へ
前日へ
脳log
[20230502]
2023年05月02日 (火)
[AtCoder] 精進。ARC100-D「
Equal Cut
」(青 diff)。最大値とか最小値とか見えるので二分探索で解きたい気持ちになる。何をボーダーにして判定するか。最初に考えたのは4つの部分列 B,C,D,E の和 P,Q,R,S が最低いくつ以上でなければならないか。そうすれば部分列の和は途中までは基準を少し超えたところで揃う。これの何が良くないか。たとえば前の方の部分列が基準を多少大きく超えた方が全体としては凸凹が均されるかもしれない。それは A 数列の配列による。他には部分列の和の差(つまり答え)が超えてはいけないラインを決め打って探索ができるか考えたり。でもまとまらなかった。■
提出 #41124597
(AC / 339 Byte / 812 ms)。まず数列を2つに割った。これは総当たりで。次にそれぞれをできるだけ均等に割った。これは二分探索で。仮に2つに割った前半/後半が2等分できるときに、あえて差をつけた方が答えが良くなるケースがあるかをよく検討した。なかった。
翌日へ
前日へ