CCO '22 P3 - Double Attendance

https://dmoj.ca/problem/cco22p3
Милая задача :)

Писал CCO 2022 Day1, набрал по ней 21 из 25 возможных, сейчас решил дорешать и она, оказывается, достаточно очевидна, если просто посмотреть с другой стороны!

Я писал dp-шку вида (dp[side][x] -> max # of segments), ее достаточно просто придумать, а чтобы бороться с тем, что мы можем учитывать один отрезок два раза, надо обновлять не dp[side ^ 1][x + k], а dp[side ^ 1][max(x + k, R[x] - k)].

Дальше, мне кажется, это практически невозможно и очень неприятно доделать до решения на 100, но раз на туре я смог набрать 21, думал, что достаточно рядом :)

Оказывается, надо просто посмотреть на задачу чуть с другой стороны и считать не dp[side][x] -> # of segments, а dp[side][# of segments] -> min x. Теперь применяем нашу идею выше и вуаля, получаем полный балл! :D

Эта задача напоминает нам о том, что полезно менять состояния dp / смотреть на задачи под другим углом.