USA Compution Olympiad 2014 US OPEN, SILVER
Problem 1: Fair Photography
原文 (English)
FJ's N cows (2 <= 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 is either a plain white cow or a spotted cow. No two cows occupy the same position, and there is at least one white cow.
FJ wants to take a photo of a contiguous interval of cows for the county fair, but in fairness to his different cows, he wants to ensure there are equal numbers of white and spotted cows in the photo. FJ wants to determine the maximum size of such a fair photo, where the size of a photo is the difference between the maximum and minimum positions of the cows in the photo.
To give himself an even better chance of taking a larger photo, FJ has with him a bucket of paint that he can use to paint spots on an arbitrary subset of his white cows of his choosing, effectively turning them into spotted cows. Please determine the largest size of a fair photo FJ can take, given that FJ has the option of painting some of his white cows (of course, he does not need to paint any of the white cows if he decides this is better).
和訳 (Japanese)
Farmer John の N (2 ≦ N ≦ 100,000) 頭の牛 が、長い一次元のフェンスに沿った様々な位置に立っています。i 番目の牛は xi に立っていて (0 ... 1,000,000,000 の範囲の整数)、その牛は 白い牛か汚れた牛のどちらかです。2頭が同じ位置に立つことはなく、最低 1 頭の白い牛がいます。
Farmer John は農産物品評会のために、牛の連続区間の写真を撮りたいが、牛の品種のすべてが公平に表されていて欲しいです。そのため、彼は写真中に存在している白および汚れた牛の頭数が等しくなるような写真を撮りたいです。
より大きい写真を撮るいっそうよいチャンスをFarmer John 自身に与えるために、バケツ 1 杯のペンキを持っている彼は、何匹か白い牛を選び、その牛を汚れた牛に変えることができる。Farmer John が白い牛のいくつかをペンキによって汚れた牛に変えることが可能であることを考え、彼が撮ることができる公正な写真の最大サイズを求めてください(もちろん、ペンキを使わない方が良い場合、ペンキを使用する必要はありません)
入力形式
N x1 b1 x2 b2 : xN bN
1行目に牛の頭数 N が与えられる。
2行目から N 行にかけて、牛の位置 xi と 牛の状態 bi が半角スペース区切りで与えられる。牛の状態は、'W'(白い牛)か 'S'(汚れた牛) のどちらかである。
出力形式
1行に、写真の最大の大きさを整数で出力せよ。
入出力例
入力例
5 8 W 11 S 3 W 10 W 5 S
出力例
7
解説
3 から 10 の範囲を選ぶと、3 頭の白い牛、1 頭の汚れた牛が存在する。3 頭の白い牛のいづれか 1 頭 を ペイントすることで、公平な写真となる。