Dまで四完。
コンテスト後のツイート
Educational Codeforces Round 164 (Rated for Div. 2)
— titia (@titia_til) April 12, 2024
A m個均等に分けて一番大きいのを除く
B A[0]ではない数のindexの間にある個数
C できるだけ差を小さくする
D 難読。理解できればDP[i]でi個の場合は何通りか持ってDP
E 加算される箇所が√max(A)になるはずと思って実装したがWAでした。
E. Chain Reaction
解説ツイートを見たところ、√max(A)回加算するというところは合っているみたい。
→落ち着いて書き直したら答えがあった。
ただし、PyPyだと制限時間が厳しく、PyPy2で2999msでACした。ルートだけでなくlogもかかっているからねぇ。二分探索使わない方法はあるのだろうか……と書いていたら、使わなずにできそうな気がしてきた。
a/xの繰り上げが変化する場所をメモしていけばいい（後で累積和を取る）ので、前半はxを一個ずつ増やし、後半はa/xの値を一個ずつ減らしていけば良さそうです。
0 件のコメント:
コメントを投稿