SRM 444

4並びの記念回
20:00-と日本人に優しい時間帯でした

Room

Room 12
赤多いorz
250-500-1000を確認。KMCoderがver.2になってから何度か練習してきていた250→1000→500を決行することにした

250

問題文むずい
250なのでということでオーダー気にしなかったが実は50^5だった。もちろん、÷たくさんがつくので問題なし

1000

開けた瞬間は数学に見えたがmod10...07でとか書いてあってDPか行列累乗じゃないかと思って問題文をちゃんと見た。nがでかいので行列累乗だった
44..44の倍数桁とかを包除原理でやれば、行列の等比数列の和を求めるだけになる
どっかで覚えた[ [A,I], [0,I] ]^nの右上にI+A+...+A^(n-1)ができるっていうのを使って計算
大量にバグが生じて時間がかかったorz

500

開いた時点で残り10分もなかったが、どうみても2^10なDP
もったいない

Challenge

500で最初にあけたやつが貪欲と見せかけて全探索だったが、準備不足だったせいでやられてしまった

System Test

通った
500のPassed率が高いなあ

Result

201.71 + 0.00 + 425.53 + 0.00 = 627.24
14位 (部屋2位)
2485→2575

highestを更新した。あと+50があればなあ
気付くと最近Mediumが全然通せていない