Codeforces Round #566 (Div. 2):C. Beautiful Lyrics
問題
解法
まず,同じ母音の数で分類する.その中で,最後の母音が同じもの同士を下の句のペアになれるものとしてまとめる(seconds とおく).ここでまとめられなかったもの同士を上の句のペアになれるものとして別にまとめる(firsts とおく).firsts の数が seconds の数と同じか,1 多い状態にすることで句の数を最大化することができる.seconds にある要素は firsts ともなりうるので,seconds の数が firsts より多い場合は,いくつか seconds から firsts にペアを移せばよい.O(sum|S|)
解答