DPというのは不思議で、ただ適当に配列をループで回しているだけに見えても難しい問題を解決してくれていたりします。 実際に解決できているのだから、間違っていることはないのでしょうが、直感的に正しいとはとても思えません。 最近、DPは効率のいい全探…

全域木とは あるグラフがあったとき、そのグラフの全ての頂点といくつかの辺を使って作られた新たなグラフが連結で閉路を持たないとき、新たなグラフを元のグラフの全域木という。 最小全域木 辺がコストを持つとき、コストの総和が最小の全域木を最小全域木…

問題リンク 考察 数列 の和を最大化したいので、できるだけ全ての を に近づけたい。 として問題なさそう。 については が を上回らないのなら が を上回るのなら とすると辻褄を合わせたまま最大化できそう。 こんな感じで数列 を後ろから見て行って数列 を…

コード vector<uint64_t> prime_factor(uint64_t n) { vector<array<uint64_t, 2>> ret; for (uint64_t i = 2; i * i <= n; ++i) { if (n % i) continue; uint64_t cnt = 0; while (n % i == 0) { n /= i; ++cnt; } ret.push_back({ i, cnt }); } if (n != 1) ret.push_back({ n, 1 }); re</array<uint64_t,></uint64_t>…

問題リンク まず、 を素因数分解し で考えてみます。( はそれぞれ素数) この時 で割り切ることのできる最小の とは です。 これは が必ず素因数として を 個以上もつためであり、 ならば、 は を内包します。( と は互いに異なる素数なので、 は必ず割り切れ…

問題ページ 最近JOI(日本情報オリンピック)の存在を知り、過去問を解いたりしていたのだが、おそらくDP的な考え方を使う問題を解いた。1 DPは前の値を使って次の値を計算できるか、次の値を計算するときにはその前の値がすべて計算終了していなければいけな…

コンテストリンク ABCDの4完。 A問題 よくある算数の問題。 ただ、簡単な問題は凡ミスしやすくて苦手。 B問題 s.size()-t.size()だけ全探索しようとしてs.size()==t.size()のケースでwaを出してしまった。 C問題 普通に計算するとのため紙に書いてみる。 そ…

問題リンク 組み合わせ計算で解こうとして撃沈。 どうしたらいいの...と思いながら解説を読んだ。 発想が足りない。 どうしたらいいのだろう。

問題リンク の範囲に2019の倍数があれば答えは必ず0になる。 ということには早めに気付けた。 しかし、愚かな私は2019を倍数に含まない数列に対して、 が最適解だと思い込み、WAを重ねた。 少し考えればわかることなのに...

問題リンク 解説をみて、 が の制約を無視した時の組み合わせの数。というのが理解できなかった。 があるので、これを利用してうまく求めるんだな、なんて思っていたら全く分からず。 文字列Sの中から、それぞれ違う位置にある文字を3つ取ってきたとき、小さ…

の時、(ただし、q,pなどはすべて素数) の正の約数は となる。 例えば80の約数を見るときに として、80の約数は10個あるのだなと分かる。 素数の組み合わせだけ倍数が存在するため、 までの となるため。