今日の競プロ(2020/4/4)

AtCoder 7問レーティング：1730→1707 (-23) :(

最近覚えた行列累乗を使ってみたくて、解いた。一般の $m$ 項間漸化式の $n$ 項目が $O(m^3 \log n)$ で求められてすごい。等比数列の和の公式と違って割り算が発生しないので、 $mod$ が素数じゃなくても大丈夫。すごい。

JOIもちょっとずつ埋めてます。

同じジャンルの中では基準価格が高い本から売るのがよい。そうするとまとめ売りサービスは結局「あるジャンルで $i$ 冊目に売った本の買取価格が $2*(i-1)$ 円高くなる」というサービスになるので、この下で $dp[i][j]=$ ジャンル $i$ までで $j$ 冊売った時の買取価格の最大値。

除算の挙動にやられて1WA。これほんまに難しい。

ボールが跳ね返るイメージで。

一生「 $N$ を $N-K$ で置き換える」操作を行うことになり、最後には $N\%K$ が残る。よって、最終的に $N$ が $1$ になる $K$ は $N\%K=1$ となるような数、つまり $N-1$ の約数。

そのような $K$ は少ないので、全部試す。

ABC161 DとEは明日やります

gyouzasushi’s diary