GCJ2012 Qualification Round Problem B. 解き方

Google Code Jam 2012 Qualification Round
Problem B. Dancing With the Googlers 解き方

コンテストで提出したコードは ここ からダウンロードできます（Python）。
あと このへん。移動してたら探してください。
問題紹介はこちら。

以下ネタバレ

与えられる情報が少ないので、どのGooglerが意外な結果(surprising)のスコアだったかを完全に知ることはできませんが、それを知る必要はありません。最大何人いるか（the maximum number of Googlers）を求める問題なので、ベストケースを考えればよいことになります。

3人の審判のスコアの点差を考えると、合計スコアを3で割った余りで場合分けして内訳を推測することができます。（t は合計スコア、// は切り捨て除算）


通常の場合（各スコアは0点差または1点差）:

• 合計スコア t を3で割った余りが 0 ⇒ (t / 3), (t / 3), (t / 3)
• 合計スコア t を3で割った余りが 1 ⇒ (t // 3 + 1), (t // 3), (t // 3)
• 合計スコア t を3で割った余りが 2 ⇒ (t // 3 + 1), (t // 3 + 1), (t // 3)

意外な結果(surprising)の場合（スコアが最大2点差）:

• 合計スコア t を3で割った余りが 0 ⇒ (t / 3 + 1), (t / 3), (t / 3 - 1)
• 合計スコア t を3で割った余りが 1 ⇒ (t // 3 + 1), (t // 3 + 1), (t // 3 - 1)
• 合計スコア t を3で割った余りが 2 ⇒ (t // 3 + 2), (t // 3), (t // 3)

各Googlerのスコアをこの表に当てはめて最高スコアを算出します。

• A: 通常の場合の最高スコアが目標最高スコア p を超えている
• B: 意外な結果(surprising)なら最高スコアが目標最高スコア p を超える
• C: 意外な結果(surprising)でも最高スコアが目標最高スコア p を超えない

A の人数はそのままカウントします。C は残念な結果なので無視します。
B のうち、入力データの「意外な結果(surprising)の出た回数 S」の人数だけ目標最高スコア p を超えることができます。
つまり「目標最高スコアを達成したGooglerが最大何人いるか」の答えは

A の人数 + min(B の人数, 意外な結果(surprising)の出た回数 S)

となります。