反省会 - Google Code Jam 2012 - Qualification Round - Problem B.

いよいよ始まりましたGoogle Code Jam 2012。

まずは予選です。

Problem A.
単にアルファベット26文字をマッピングするだけなので省略します。

Problem B,Cですが、考え方はあっていたのに大ポカをやらかしてLargeで誤答してしまいました。
というわけで今回のお題は反省会です。

Problem B.
問題の内容は以下になります。
・N個のスコアを、分割した結果の差が1以内で3つに分割
・N個のうち、S個については、分割した結果の差が2になる
・分割した結果の最大値がP以上の数を数える

まずは分割した結果の差が1以内の条件で、分割した結果の最大値がちょうどPとなる最小値を
考えてみると、
　(P-1, P-1, P)
となります。

次に分割した結果の差が2の場合を考えます。
先ほどの最小値から1引いた状態 (P-1, P-1, P-1)について1点だけ移動させると、
(P-2, P-1, P)となり、条件を満たします。

さらに続けると、
　(P-2, P-1, P-1) => (P-2, P-2, P) : OK
　(P-2, P-2, P-1) => (P-3, P-2, P) : NG
となります。

ここで、分割した結果の点数は0以上でなくてはならないので、
P-2 >= 0を満たすことが必要です。

というわけで実装したのが、恥ずかしながら以下の結果です。
なんとなく楽しいのでC++11のRange based forを使っています。

なにが恥ずかしいって、なんでわざわざ div 3した結果で判定しているんでしょうか。

そして肝心の大ポカですが、3つめのif分の"d > 0"が誤りです。
『分割した結果の点数は0以上』を判定したつもりだったのですが……
これ、ある条件で数え漏らします。
（そしてその条件がsmallにはなくlargeにのみ出現する罠)

この問題、こんなワケのわからない判定文を書かなくても、以下の条件で見るだけでOKでした。

・Ti >= (P-1) + (P-1) + P = 3P-2　のときは無条件に数え上げ
・Ti = (P-1) + (P-1) + (P-1) or (P-2) + (P-1) + (P-1) = > 3P-3, 3P-4の時は、
　Sがまだ残っていれば数え上げ
　ただし、 P-2 < 0のときは数え上げない
・上記以外は無視

Largeでも100問しか無いので余裕です。

タグ：gcj Google Code Jam