ABC172に挑んだ回

ちょっと今回異様に難しくないですか?
B止まりはめちゃくちゃ悔しい。
発想力というか、柔軟さに欠けている。

C - Tsundoku

最初愚直に少ない方を加算してた。
その後問題文見返して、あぁDPか。DP理解できないって逃げた。
そして蓋を開けたらDPじゃない。なにこれ。

解答は解説通り。

D - Sum of Divisors

約数の情報を保存して計算回数減らしたりするかなー。
でも面倒だし、DPの勉強してこよって逃げた。
仮に約数に着目して続けてたとしても、時間的に間に合わないように作られてたらしい。
ある意味逃げてて正解。
そういう部分も計算量からぱっと理解できるようになりたい。

約数うんぬんから目をそらして、普通に計算式としてどうなりそうかに着目すべき?だった問題らしい。
(解説PDF見てもあんま理解できなくて、他の人の答えを見ながら考えて理解した。

例題ケースの[4]の場合、約数の件の詳細は以下のような感じ。
1:1→1個*1
2:1,2→2個*2
3:1,3→2個*3
4,1,2,4→3個*4

1は1,2,3,4…のすべてで登場するし、2は2,4,6…の2の倍数、3は3,6,9…の3の倍数で登場する。
ので、これらの登場回数を配列でカウントして、最後に配列のインデックスで掛け算すれば答えになる。

DP

↓見ながらお勉強中。
蛙は飛ばしたよ。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a

コメントを残す

あなたのメールアドレスは公開されません。必須項目には印がついています *