← 返回题目列表

AtCoder · typical90_au

047. 单色对角线(★7)

中文机器翻译题面 查看原题

配点: 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' 仅由

小课题·得点

这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。
每个小任务在满足上述约束之外,还需满足以下约束。

  1. (2 点): N\leq2000
  2. (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