これ系の計算量削減テク、いつも思いつかない。 http://agc017.contest.atcoder.jp/tasks/agc017_f

Dよりこっちの方が解けてたかも。 http://agc017.contest.atcoder.jp/tasks/agc017_e