スピード勝負だった。Fは結局解けない。。 atcoder.jp 数列が与えられ、特定の数列の値を別の値に書き換える操作を行う。 操作ごとにすべての和を答える。 Dにしてはとても簡単。 初期段階での数列の和を取っておいたとき、 BをCに変化させたとき、Bがb個あ…

Eまで通せたが、もうちょっと早くやりたかった。 atcoder.jp こっちは割と典型問題。素因数分解を行った後で、各素数pにおいて p1, p2, p3.... とzを取っていけばよい。素因数分解の実装がさくっとかけたのは満足。 def factrization(N): k = 2 ret = {} L =…

atcoder.jp イワシは相性によってグルーピングができる。 このグルーピングさえうまく処理できれば、あとは数え上げればよい。 a匹のグループAとb匹のグループBの相性がそれぞれ悪かった時、 各グループの内部での取る取らないで2のa乗、2のb乗通りできる。 …

atcoder.jp 30分ぐらい。もう少し早く解きたかった。 まず、10100のおかげで、K個取るとき、K+1個取るとき、K+2個取るとき、・・・で、和がかぶることはなく独立して考えることができる。 N＝10とし、このうち3個だけを考えてみたとすると以下の11個の中から…

atcoder.jp 上から作ったり、下から作ろうとしたり、dpを考えてみたが、 0の扱いが難しくて、下からは作れなかったし、上から作ると、何番目、の扱いが非常に面倒。 しばらく考えて苦肉の策として、Nがそこまで大きくないこととサンプルテストに最大値が出て…

atcoder.jp もう少し早くできた、、はず。 ワーシャルフロイドの本質をきちんと理解してなかったが故に実装に時間がかかった。 当然、Nの制約からワーシャルフロイドを直接使ったO(N3)はできないが、 それでも、ワーシャルフロイドの考え方がベースになって…

しばらくやめてたがまた再開する。 atcoder.jp 「一つだけ抜く」パターンは全体をあらかじめ求めておいて、その抜かれた影響を考えることで計算量がO(N)になるケースが多い気がする。 今回もそんな感じで、抜かれた数字が元々C個あったとすると、そのうちの2…