読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

天下一プログラマーコンテスト2015予選A C - 天下一美術館

問題 問題概要 マスの状態を一致させるために、必要な最小コストを求める問題。 解法 はじめは、貪欲に、左上から見ていき、交換して変えて、一致するところを優先的にやればいけると思い書いたが、WA。原因は単純で、左上から貪欲にやるだけではだめで、ど…

天下一プログラマーコンテスト2016予選B D - 天下一数列にクエリを投げます

問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 segtreeぽいな感はある。90度回転させてみるのは思いつかない。 解法は公式解説がわかりやすい。 https://tenka1-2016-qualb.contest.atcoder.…

天下一プログラマーコンテスト2016予選B B - 天下一魔力発電

問題 問題概要 省略 解法 単純に全ての状態を全探索すると、2nで無理。 dpで解きました。状態を決めるために、何文字目までで'('が何文字あり、最後に反転させた位置が同じであれば、同じ状態とみなせると考えた。 dp[i][j][k] := s[i]文字目まで見て、'('が…