問題文 http://arc065.contest.atcoder.jp/tasks/arc065_c 解法 とりあえずマンハッタン距離の有名なテクニックである，45度回転みたいなことをする． すると，a と b の距離は D = max(|x[a] - x[b]|, |y[a] - y[b]|) となり，以降コンパスで点の位置が変わ…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack 解法 まず，色でソートしておく． すると以下の dp が書ける． dp[i][w][j][k] := i 番目まで見たとき，j 種類の色を使っていて，最後に使った色が k であって，重さの総和が w となるときの最大…