047 - Monochromatic Diagonal(★7)
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 7 点
問題文
文字 'R'
,'G'
,'B'
のみからなる、長さ N の文字列 S,T が与えられます。
S の i 文字目を s_i 、T の j 文字目を t_j とします。
N\times N のマス目があり、次の規則でマス目に色を塗ります。
ここで、文字 'R'
,'G'
,'B'
をそれぞれ赤色、緑色、青色に対応させます。
- s_i=t_j のとき、上から i 行目、左から j 列目のマスを色 s_i で塗る。
- s_i\neq t_j のとき、上から i 行目、左から j 列目のマスを赤、緑、青のうち s_i とも t_j とも異なる色で塗る。
このマス目には左上から右下に向かうような斜めの列は 2N-1 本あります。 マス目が一色のみで塗られている列は何本あるか、求めてください。
より厳密に書くと、次のようになります。 次の条件を満たす整数 k\ (-N<k<N) がいくつあるか求めてください。
- ある色 c が存在して、1\leq i\leq N かつ 1\leq i+k\leq N が成り立つ任意の i について、マス (i,i+k) が色 c で塗られている。
制約
- 1 \leq N \leq 10^6
- S,T は文字
'R'
,'G'
,'B'
のみからなる
小課題・得点
この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。
それぞれの小課題は上の制約に加えて、それぞれ次の制約を満たします。
- (2 点): N\leq2000
- (5 点): 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
N S T
出力
全てのマスが同じ色で塗られているような斜めの列の個数を一行に出力してください。
入力例 1
5 RGBGB GRGRB
出力例 1
6
k=-4,-3,-1,2,3,4 の 6 つが条件を満たします。
例えば、k=-3 が条件を満たすことは、マス (4,1),(5,2) がどちらも緑色で塗られていることから確かめられます。
入力例 2
3 RRR BBB
出力例 2
5
入力例 3
10 BGGGRBBGRG RGBBRGRGGG
出力例 3
4