[AtCoder] ABC 162 D – RGB Triplets

2020年4月14日

問題

方針

まず初めに、\( S_i \neq S_j \wedge S_i \neq S_k \wedge S_j \neq S_j \) を満たす組の数を求めます。これは、\( i, j \) について、\( S_i \neq S_j \) となるものを求め、\( j + 1 \) 文字目以降に存在する \( S_i, S_j \) 以外の文字数を数えます。これは、累積和を使うことで高速に求まります。

つぎに、\( j – i = k – j \) を満たす \( i, j ,k \) について、\( S_i \neq S_j \wedge S_i \neq S_k \wedge S_j \neq S_j \) を満たすものを数えます。これは、\( i, j \) について全探索を行います。

コード