2020/3/15

Codeforces 965 A

周期性があるので えい

等比数列の和の公式→公比がmodを取った後に1になる場合に注意(mod10^9+9だと10^9+8が大量に因数を持つのでこういうケースがたくさんある)

 

Codeforces 1325 D

上の桁から決定しようとして大変なことに...

余ったsumを貪欲に上で消費するべきでない場合がある→DPをしないといけない

遷移を組むのも貪欲の証明も大変なのでギャグ路線を考えるべきだった(やばそうになってきた段階で異常な通され方をしていたら方針を疑うべき)

a^a=0を使ってxr,(sum-xr)/2,(sum-xr)/2とすれば偶奇が一致する限り必ずできる、xr=0の場合、((sum-xr)/2)&xr=0の場合はもっと短くできる

 

既視感

https://codeforces.com/contest/1270/problem/C

 

AOJ 2165 

配列の長さを途中で変える→全ての箇所を変えることに注意

非正規化数(0にとても近い数)になると桁数の情報を多く持つ必要が生じる→遅くなる

持つべき桁数の情報が多い時は下の桁から切り捨てられる→小さい数から計算して徐々に数を大きくする方が誤差が少なくなる