TopCoder Member SRM 458

12/18以降，2回連続不参加でしたので約1カ月ぶりの参加．

Member SRM458(1/15 1:00~3:00)

・Desertification(DIV2 Easy)
セルで構成された「島」が与えられる．セルは，forest(=森)か desert(=砂漠)のどちらかの状態を持つ．また，単位時間が経過すると，砂漠は自セルの上下左右の4近傍にある森を砂漠に変える．初期状態の島から時間Tが経過した時，砂漠となっているセルはいくつあるか．

■□□□
□□□□
□□□■
□□□□
↓
■■□□
■□□■
□□■■
□□□■
↓
■■■■
■■■■
■■■■
□□■■
こんな感じ(□=森，■=砂漠)．■は14個．

Tの最大値は10億でしたので，単純ループでは2秒以内に終わらないです．島の初期状態が全て森の時は0を返し(いくら時間が経過してもずっと森のまま)，ループ中に島が全て砂漠化した時には終了条件を待たずして終了するようにして提出．

Result:Passed System Test(220.00p)

・BouncingBalls(DIV2 Medium)
ライン上にボールが並んでいる．それぞれのボールは等確率で左or右に動来始める(=単位時間で+1or-1移動する)．ボール同士が衝突した時は，弾性衝突をするものとする．全ボールの初期位置が与えられた時，T時間以内でボール同士が衝突する回数の期待値を求めよ．

一々ボールを動かして云々とかやると，2秒以内に終わるはずが無いので，ボール同士の距離の差でどうにか計算しました．ボールがN個あった場合，ボールの動き方は2^N通りありますが，Nの最大値は12でしたので再帰を使用しても大丈夫でした．

Result:Passed System Test(260.44p)

・ProductTriplet(DIV2 Hard)
minx ≦ x ≦ maxx
miny ≦ y ≦ maxy
minz ≦ z ≦ maxz
x * y = z
となる(x, y, z)の組みは幾つあるか．

6つのパラメータは範囲が[1, 1000000000]なので，困りました．時間もMediumで取られてしまって，手をつけられず．

Result:Opened(0p)

・Challenges
あからさまなミスを撃墜しようとしたら，他の方に先に撃墜されました…．

Rating
1155->1216

というわけで，BlueCoderに昇進．再びDiv1の世界へ…．