問題 解法 お絵描きしたのでメモ. 部分点は O(N2) の区間DP. それ以上に早くやるにはどうするか. 遷移が O(1) なので状態を減らすしかない. しかし,DPテーブルは疎でもなく,あまりまとめられそうにもない. よってある状態(操作)を禁止して状態を減らすことを…

問題 解法 最初に右を向いていて,次に右折するパターンを考える. 各マスで上方向に累積和をとると下に何マス進めるかというのがO(NM)でわかる. それを左方向に累積和をとっていくとその場所を始点として1マス以上進み,右に何マス進めるかというのがわかるの…

問題 問題概要 N個の点(xi,yi)と色(B|W),自然数Kが与えられる. 幅Kの市松模様で,(xi,yi)を与えらえれた色にするという希望を最大何個満たすことができるか. 1 <= N <= 105, 1 <= K <= 103, 0 <= xi,yi <= 109 解法 全てのマスに対して,(x,y)の色C(x,y)は,C(x…