SRM273 - bit 演算は int で行われるのね
SRM273 に挑戦．はじめて，平日の昼に挑戦です．今までは，日本時間の夜に開催される SRM にしか参加しませんでした．
FallingCoconuts (code)
250 点問題．ココナッツを上から落としておとしていきます．積みあがった形を返す問題です．テトリスみたいなものですね．番人(Sentinel)というちょっとして Tips を使いました．あらかじめ，一番下の段にココナツを敷き詰めておけば，ココナツが下にはみだすことはありません．一番下までココナツが落ちたときの条件をチェックする必要がなくなります．一番下の段に敷き詰めたココナツば番人がわりになってくれるわけです．今回は，特に Sentinel を使うまでもないですが，ときどきあらかじめ Sentinel を用意しておけば，条件チェックが非常に楽になるケースがあります．
SnakeTurbo (code)
500 点問題．
o---o-o-S--o--o--------G---o
S が Snake(へび)がいるスタート地点，G がゴール地点です．へびは 1 秒に 1 単位進むことができます． o はパワーアップえさです． o を食べるたびに，へびはスピードが 2 倍になります．
- 2 つ食べれば 4 倍
- 3 つ食べれば 8 倍
- 4 つ食べれば 16 倍
というふうに，効果は累積します．へびがスタート地点からゴールするまでの最短時間を求める問題です．
これも，前回の SRM272 の Level2 問題，RoundTable と同様に，Recursive + Memoization で解きました. 自信があったんですけど，System Test に落ちました．うーん，どこがおかしいかしばらく気づきませんでした．．発見してみてください．ここです
double boost = 1 << (right - left);
ここは，現在のへびのスピード，すなわち 2 の (right - left) 乗を求めているところです． 入力の条件は，
orbs will contain between 0 and 50 elements, inclusive.
なので，(right - left) は 32 以上になる可能性があります．右辺のビットシフトは int で計算が行われます． int は 32 ビットなので，(right - left) が 32 以上のときは対応できません． 素直に
double boost = Math.pow(2, (right - left) );
または
double boost = 1L << (right - left);
と long を使用しておけば，何の問題もなく，System Test に通っていました．残念．
RobotCollision
900 点問題． 時間たりず．Level3 問題にしては，簡単なほうだったみたいです． 条件を絞れば，Brute-force でいけます．
結果
System Test の結果です． ( Room Statistics )
レーティングはちょっとだけ上昇しました．