USA Compution Olympiad 2014 US OPEN, BLONZE
Problem 2: Fair Photography
原文 (English)
Farmer John's N cows (1 <= N <= 100,000) are standing at various positions along a long one-dimensional fence. The ith cow is standing at position x_i (an integer in the range 0...1,000,000,000) and has breed b_i (either 'G' for Guernsey or 'H' for Holstein). No two cows occupy the same position.
FJ wants to take a photo of a contiguous interval of cows for the county fair, but we wants all of his breeds to be fairly represented in the photo. Therefore, he wants to ensure that, for whatever breeds are present in the photo, there is an equal number of each breed (for example, a photo with all Holsteins is ok, a photo with 27 Holsteins and 27 Guernseys is ok, but a photo with 10 Holsteins and 9 Guernseys is not ok). Help FJ take his fair photo by finding the maximum size of a photo that satisfies FJ's constraints. The size of a photo is the difference between the maximum and minimum positions of the cows in the photo. It is possible that FJ could end up taking a photo of just a single cow, in which case this photo would have size zero.
和訳 (Japanese)
Farmer John の N (1 ≦ N ≦ 100,000) 頭の牛 が、長い一次元のフェンスに沿った様々な位置に立っています。i 番目の牛は xi に立っていて (0 ... 1,000,000,000 の範囲の整数)、その牛は bi の種類('G' のガンジー種、'H'のホルスタイン種のどちらか)、です。2頭が同じ位置に立つことはありません。
Farmer John は農産物品評会のために、牛の連続区間の写真を撮りたいが、牛の品種のすべてが公平に表されていて欲しいです。そのため、彼は写真中に存在している牛の品種別の頭数が等しくなるような写真を撮りたいです(例えば、全てのホルスタイン種が写る写真は OK であり、27 匹のホルスタイン種と 27 匹のガンジー種が写る写真もOKであるが、10 匹のホルスタイン種と 9 頭のガンジー種が写る写真は OK ではない)。Farmer John の制約を満たしている写真の最大の大きさを見つけて、彼の公正の写真をとることをを助けてください。写真のサイズは写真中の牛の最小の位置と最大の位置との差です。Farmer John が、単に単一の牛の写真をとることは可能で、その場合の写真のサイズは 0 です。
入力形式
N x1 b1 x2 b2 : xN bN
1行目に牛の頭数 N が与えられる。
2行目から N 行にかけて、牛の位置 xi と 品種 bi が半角スペース区切りで与えられる。
出力形式
1行に、写真の最大の大きさを整数で出力せよ。
入出力例
入力例
6 4 G 10 H 7 G 16 G 1 G 3 H
出力例
7
解説
6 頭の牛は、左から G, H, G, G, H, G の順で並んでいる。Farmer John は、真ん中の 4 頭の牛を撮ることが可能で最大の大きさの写真となり、 ホルスタイン種を 2 頭、ガンジー種を 2 頭含んでいる。