JOI Kakisemi Contest 2019：C - 魔法の宝石

問題

https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2154

解法

小課題１

H, W == 2．なので，全てのマスが同じ文字であるか調べればよい．

小課題２

H, W <= 30 なので，約 20 万通りしかなく全通り試せばよい．

小課題３

全ての文字は同じなので，答えは C(H, 2) * C(W, 2)．

小課題４

まず 2 行を固定し，2 * W の問題を考える．まず，2 列が異なっているものは採用できない．文字 c ごとに C(2 列が同じ c になっているものの数, 2) を足したものが 2 行を固定したときの答えとなる．これは O(W) で解ける．

あとは拡張して O(H^2 * W) で解ける．