AB二完。
コンテスト後のツイート
AtCoder Regular Contest 163 Cが分からず終了……。
— titia (@titia_til) July 2, 2023
A 全探索
B 尺取り法
C 「2 3 6」のそれぞれにxをかけると1/xが作れることを利用しようとしてもがいていた。解説の方法は全く思いつかなかったのでどうしようもない……。
C - Harmonic Mean
解説AC。
部分分数分解を利用するというのを見て実装しようとしたら、全体二倍にするというのを思いつかず苦戦してしまった。
部分分数分解を利用する方針は全く思いつかなかったので解けなくても仕方なかった……とも思うが、他の方針で（やや強引に）通している人も結構いる模様。それを見るとどうにかして通したかったという気持ちになるが、どうすれば良かったかね。
コンテスト中は、和が1になるものx個を使って、それらをx倍したものを合併させる。もしくは、3個を2, 3, 6倍したものを合併させる……というような方針を考えていたが、Nが100～150あたりまでしか作れなかった。
D - Sum of SCC
解説AC。
問題を見て、主客転倒的なテクニックを使いそう、とは思ったが、グラフを二つに分けて考えるという発想はなかなか難しい。
SCCをs0→s1→s2→……のように表してみて、この矢印をどこで区切れば良いか？ と考えれば思いつけるのかなぁ。
また、解説通りのDPをしたつもりが答えが合わずに苦労した。
解説の一行目の「以下の値-1に等しいです」というのは、A側が空の場合とB側が空の場合をダブルカウントしているため、ということなのですね。
これを踏まえて、最終的な答えを求めるときも、i（解説のdp内の添え字）の範囲を[0, N)もしくは(0,N]にしなくてはいけなかった。
類題だと話題になっていたこの問題も解いておいた。
が、今回の問題の解法に引っ張られて二乗のDPで解く方法しか思いつかず、oeisを使ってなんとかAC、としてしまった。
解説（のコード）を見ると、簡単に立式できましたね……。
0 件のコメント:
コメントを投稿