こんちゅう

エッセイ・小説・ブログ・楽譜置き場。 不定期更新。

AtCoder ABC 142

詰まった問題を覚書程度に記す。

ABC142 D

atcoder.jp

公約数のうち素数の数を調べればいい。これはO(\sqrt{N})でできる。ただしN=gcd(A,B)
AとBの公約数は最大公約数の約数である。Nを素因数分解していけばよい。調べるのは\sqrt{N}までで良くて,\sqrt{N}を超えるような素因数は多くても1個しかない。

はじめ「最大公約数以下の素数をを列挙すればいいのかな~~~」と考えていたらそれだとO(NloglogN)かかって解けないことに(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まで解けるようになる気がしない。どうすればいいのかなあ。