cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM500 の成績・ソース (要ログイン) : AC/TLE/- : 好きな問題セット。汚く書くと酷いことになりバグだらけとなるが整理して書けばバグる余地などなく綺麗になる、というのが顕著に出てくる問題が好きです。
cafelier50^4 は余裕で行けるとして50^5オーダのループはどのくらいまで通るのか問題。今回のだと
Σ_{S=1～N} (N-S)^2 S^2
＝ Σ_{S=1～N} ((N-S)S)^2
≦ Σ_{S=1～N} ((N/2)^2)^2（周の長さが同じなら長方形では正方形が一番デカい理論）
＝ N^5 / 16
≒ 2000万
くらいで評価すればいいのかな。Σ(N-k)k は N(N/2)^2 弱。
presented by
cafelier/k.inaba
under
自分のコードでなのですが，式変形した場合，テストケースで最大約600msかかり，しないとTLEを起こしてしまいました。式変形をする事も出題した方の意図だったのでしょうか。
mint X = 0;
for(int d=1; d<=9; ++d){
mint f = d*v[d]*FACT[N-1];
for(int i=1; i<=9; ++i)
f = f * FACT_INV[v[i]];
X = X + f;
}
answer = answer + X * ONES[N];
でTLEでした。なるほど。Σ と C(...) の計算で x9x9 で 2Mx81 回の整数演算となると厳しかったですね。なかなか絶妙なラインの問題設定でした。