詰まった問題を覚書程度に記す。
ABC142 D
公約数のうち素数の数を調べればいい。これはでできる。ただし。
AとBの公約数は最大公約数の約数である。Nを素因数分解していけばよい。調べるのはまでで良くて,を超えるような素因数は多くても1個しかない。
はじめ「最大公約数以下の素数をを列挙すればいいのかな~~~」と考えていたらそれだとかかって解けないことに(TLE出してから)気づいた。こうして期せずして(?)充実した素数ライブラリを作成することができたのだ。はあ。
ABC142 E
atcoder.jp
「ハァ~最小重みマッチングかあ知らんなあ解説読んで実装しよ」とeditorialを見たら一番上に「動的計画法」って書いてあったから一目散に閉じた。
結局bitDPを使えば解ける。Nが非常に小さいことから気づきたいなあ。そもそもABCにネットワークフローは出ないのかしら。いずれ勉強しないとなあ。
ABC142 F
atcoder.jp
実装も考察も何一つ追いつかなかった。完敗。
解き方1
editorialのやりかた。いくつか図を書けばわかるが,一つ閉路をもってきたときに,そこにもし余分な辺が入ってあったとすれば,その余分な辺はショートカットになっている。つまり,その余分な辺を使えばより最適な閉路が手に入る。これを繰り返せばいい。
解き方2
辺をひとつ固定して,startをその辺の終点,goalを始点とする。そこからダイクストラ法を用いて,startからgoalまでの最短路が答えとなる。もちろんstartからgoalまでたどり着けなかったら固定する辺を変える。
最近けっこうABCの問題を解いているのだけれど,時間内にA~Fまで解けるようになる気がしない。どうすればいいのかなあ。