読者です 読者をやめる 読者になる 読者になる

あるごリズム備忘録

学んだことの記録と日記

競プロの記録 (2016_09_24)

今日は星1を6問と、星2を1問解いた。
そのほか中途半端な星2が1問。

「yukicoder: 星2」

No.16 累乗の加算 - yukicoder

愚直にやると10^(2+8)で間に合わない。
指数が小さいほうから計算していき、その都度一つ前のものを利用していけば、毎回丸々指数の分だけ計算する必要は無くなる。
これにより、10^2+10^8で間に合う。
自分はこのやり方で通したが、「繰り返し二乗法」と呼ばれるやり方があるらしい。
これでN乗の計算が、O(N)からO(logN)になる。
どうしても、MODをとるのを忘れがちになるのを注意したい。

No.43 野球の試合 - yukicoder

これは解けなかった。試合数は高々15試合しかないので試す数は2^15 = O(10^4)となり、全探索することができる。
実装が長く、複雑になりそうなので、A予選を控える今日はやらない。方針は立っているので、後日実装しようと思う。

A予選まであと5分。