問題 codeforces.com 解法 前使ったばかりの, データ構造をマージする一般的なテクを使います。M[v][color] = (頂点 v 以下の subtree において, 色が color の頂点がいくつあるか) N[v][num] = (頂点 v 以下の subtree において, 頂点数が num 以上ある col…

問題 arc021.contest.atcoder.jp 解法 まず浮かぶのは, priority_queue に値を突っ込んでいく形でコストが小さい順に貪欲にやることです。ただ, K そこで, K 回の増築の中で, 最もコストのかかる増築のコスト x について二分探索しましょう。コスト x 以下で…

問題 codeforces.com 解法 maxi[row][l] = (row 行目の l 番目の要素から始めると, 1 が最大どこまで連続しているか) というのを, 各行 row について, しゃくとりっぽく O(m) で求めます。そしたら, l 列目からスタートする長方形について, 面積が最大にする…

問題 codeforces.com 解法 1, 6, 8, 9 を適当に並び替えると, 7 で割った余りが 0, 1, ..., 6 のいずれにもなりえます。ということで, 0, 1, 6, 8, 9 以外をとりあえず並べて, 1, 6, 8, 9 を全体の数が 7 の倍数になるように並べます。最後に, 0 を並べて終…