AtCoder Regular Contest 106 感想

f:id:knzk398:20201025205646p:plain

めっちゃ時間かけてクソほどペナつけて3完した　くそげーーーーーーーーーーー

解説を見てDまで通したので、書く

A. 106

$3^{a}+5^{b}==N$ になるa,bを見つける　aの最大値としてあり得る値は $log_3 (1e18)$ ぐらいなので全探索すればよい　 $M=N-3^{a}$ としてwhile(m%5==0)m/=5;みたいなことをすればよい。M==0のときとかbが0のときとかなんか場合分けを忘れて3ペナ　適当に提出しない！(素振り)

https://atcoder.jp/contests/arc106/submissions/17653717

B. Values

問題よく読んでないけどこれは連結ならできそうということがわかるので、やります。union findで頂点の値をマージできるようにすると。はい。

https://atcoder.jp/contests/arc106/submissions/17654475

C. Solutions

区間スケジューリングを知っていますか？僕は知っています

Rの昇順にソートするのが最適解なのでM<0のときは無理で、N==Mのときは無理で、M==0は自明なのでそれをはじきます。つぎにM=1,2,3,...について考えると [ ] みたいにすれば大きい区間に含まれるやつは青木くんはとれなくて高橋君はとれるのでMを任意に調整できそうな気がする。これでM=1,2,..N-2は構築できました。提出すると、WAで苦しい気持ちになってif(N==M)return 1;みたいなことをしてWAのケースであるN==1,M==0を特定してACした。つらい　これぐらい3秒で思いついてほしいですね

https://atcoder.jp/contests/arc106/submissions/17654575

D. Powers

これは二項定理で展開してごちゃごちゃすると $O(NK^{2})$ になって、TLEします。つらい