Integer#prime_division で見つけようとしたけど、最大ケースのサンプルが通らない。200 万回繰り返すには素因数分解のコストは高すぎるらしい。もうちょっと考えてみる。約数の数が９個ということは、素因数分解したあとの形が p1*p1*p2*p2 になるものしかないのではないかと考えた。約数の数っていうのは素数ごとの (指数の値+1) をかけあわせたものなので、９になるのは (2+1)*(2+1) だけなのではないかと。ここでも平方数だ。２乗なのか４乗なのかもうわけがわからないよ。素数の２乗を列挙するだけで済むので時間は間に合うようになったけど、最大ケースのサンプル２が合わない。10 いくつかだけ少なく出る。時間オーバーの素因数分解解法の答えは合っているので、9=(2+1)*(2+1) の部分で漏れがある。9=(8+1) のケースが漏れていた。２乗４乗の次は８乗だってさ。もうわけがわからないよ。こうなるとサンプル１の嫌らしさに気がついてしまう。最初の８乗数が 256 だから、サンプル１の N=200 は絶妙に少ない。そんなこんなで 40 分間たいへんな思いをした。コーディング部分は列挙して二分探索して足すだけで何も難しくない。Ruby で 307 ms の提出があるなか自分のは 1004 ms かかっているあたり、考察がまだ甘いのだけど、もう考えたくないのだ。■F 問題 Diversity。配点が E より 25 点だけ上なのでまずは F 問題を読んだ。DP。パラメータが多い。制約は N が 500 以下な点を除いて甘くない。特に色の種類が N 以下と全く限定されていないので、どの色がすでに選択済みかというビットフラグを状態のキーにはできない。色の扱いが問題だと思った。色ごとに DP をして価格と効用がそろって上昇するように商品グループを列挙しておいて、そののち価格と効用についての DP をするのかと思った。だけど後段の DP で扱う商品群がどれだけの大きさになるのかわからない。商品を組み合わせたものをさらに組み合わせようとしている。ここらで E 問題へ。■E 問題 Sum of Max Matching。頂点数も辺の数も少なくないグラフ。パスに含まれる辺の重みの最大値を考えるということは、回り道をしてでも軽い辺を使うべきだということ。UnionFind で軽い辺から使って徐々にグラフを拡張していくのかな。特に短くない２つの数列 A と B が与えられて、その組み合わせの最小値を答えるという。各頂点は A 数列か B 数列のどちらかに含まれるか全く含まれないかで、どちらかに複数回現れることもある。グラフを拡張しながら連結成分内で A-B ペアを作ろう。具体的なペアを考えるには A,B 数列は長すぎるけど、連結成分ごとに余っている A(B) 数列要素の数を記録しておくだけでよい。A 数列の要素と B 数列の要素を貪欲に消費して損をしない。F 問題に寄り道していた時間を含めても提出まで 21 分だから、D 問題より早い。これは不思議のないことで、UnionFind を使うからクラスカル法を使うからという理由で E 問題に配置されている問題は、のーみそこねこねな D 問題より型にはまっていて解きやすいことがある。今日は得をしたけどこれとは逆に、LazySegTree を使うからという理由で F に配置されている問題は、diff が低い割に配点が高く、だけど Ruby で参加している自分は TLE にならない遅延セグメント木の実装を持っていないので撤退するしかないということで大損をする。くやしいね。■F 問題。色で商品をソートしておいて、色が切り替わるところで DP テーブルを切り替えることにして、あとは普通に DP をするだけだったのだろうか。DP は１回だけで良かったんだろうか。どんだけ考察が早くても残り 20 分で実装できる DP ではなかったけども。■■■たぶんだけど、１アールに関連して覚えている 100 という数字は、掛ける前の数字ではなく掛けたあとの数字ではなかったか。つまり、10M×10M = 100M^2 = １アール なのではなかったか。そうすると１ヘクタールに関連付けて覚えている１万という数字が、100M×100M = 10000M^2 = １ヘクタール ということになっておさまりがいい。自分の生活に一切関わってこなかった知識なのでわざわざ調べませんけども。■C 問題に関連して多始点 BFS というワードを見かけたので調子に乗ったことを書くんだけども、始点の数を区別することに意味がありますか？ 移り変わるキューの中身をのぞいてみる。キューの中に始点(距離ゼロの頂点)が詰まっている状態がスタート。そこから距離ゼロと１の頂点が詰まっている状態、距離１の頂点が詰まっている状態、距離１と２の頂点が詰まっている状態、距離２の頂点が詰まっている状態、距離２と３の……状態が次々と現れる。距離ゼロの頂点だけが唯一でなければいけない理由はどこにもないと思うんだよ。同じ距離の頂点が１個だろうが複数だろうがキューの中で整然と列をなすからプライオリティキューなしで BFS が成立している。■精進。F 問題。昨日「どんだけ考察が早くても残り 20 分で実装できる DP ではなかったけども」と書いたわけなんだけど、ARC189 が終わったあとで書き始めたら 11 分で完成したよ。提出 #60595097 (AC / 253 Byte / 1030 ms)。ひとひねりあっただけで初歩的な DP でしたね。ひとひねりでてきめんにやられてしまうところに応用力のなさが現れている。BFS の始点が複数になってやられるのと同じことだよ(調子に乗ってごめんなさい)。