脳log[20230502]

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