脳log[20230831]

2023年08月31日 (木) [AtCoder] 精進。ABC191-F「GCD or MIN」(黄 diff)。最初のとっかかりとしてまず gcd を無視して min を考えた。min だけのとき最後に残るのは A 数列の中の最小値。ここに gcd がどう関わってくるか。gcd(a,b) は必ず min(a,b) 以下の数になる。そして最小値は最後まで残すことができる。まとめると……。A 数列の最小値を M とする。M は最後まで残すことができる数のひとつであり、その中では最大のもの。gcd(A[a], A[b], A[c],...) によって作ることができる M 以下の数はすべて最後まで残すことができる。その種類数が答え。■提出 #45084618 (AC / 725 Byte / 1974 ms / 5332 KB)。DP をした。それも頭の良くない DP を。まず A[0] を配列の先頭に配置し、以降 A[1] から A[N-1] について、配列の全要素とのあいだで gcd を計算してそれら gcd と A[i] そのものを配列に追加した。重複がないとすると伸びていく配列のサイズは 0,1,3,7,15,...,2^N-1 という感じで成長していって、N≦2000 だから２の 2000 乗はやばいんだけど、実際は gcd が１になったり重複したりすることが多いのでそれなりに大丈夫。でも Ruby では４から５秒かかって大丈夫ではなかったので C++ の犯罪力に頼りました。実は C++ であっても２秒を数百 ms オーバーしてしまったので、GCC ではなく Clang を選んだり、set ではなく unordered_set を使ったり、２つ使っていた unordered_set を１つに減らしたり、初期にあまり配列を伸ばさないで済むように A 数列をシャッフルしてみたりした(※逆にソートすると悪化した)。それでも２秒を 50 ms ほどオーバーしてしまったのだけど、unordered_set に大きめの初期サイズを与えると 100 ms 弱縮んでようやく AC の目途が立った。Ruby で通してる人は素因数分解をしたりしてるんだろうか。Ruby でも３桁 ms で AC がとれるらしいんだよね。自分にはわからんけども。■ブログを２つほど読んだ。約数を列挙してそれが GCD になりうるかどうかを調べるといいらしい？ さっき書いた素因数分解～云々がそうなんだけど、素因数の指数部分を減らしてみて、共通部分を持つ他の要素を(１つ以上)見つけて、非共通部分の GCD が１になるかどうかで答えの候補になるかどうかがわかる。でも計算量的にそうした方がいいという判断ができなかった。■Ruby で約数を列挙してさっき書いたようにして答えを出してみたら、many_divisors_00.txt というケースが最長で、２秒を 121 ms オーバーした。ましにはなったけどまだ考えが足りないらしい。提出 #45095866 (AC / 628 Byte / 192 ms / 9844 KB)。Ruby では TLE 間違いなしなのでこれも C++ だけど、1974 ms → 192 ms で 10 倍ましにはなってるんだな。このうえさらに Ruby で通すのつらすぎるぜ。■提出 #45096878 (AC / 259 Byte / 1762 ms)。これは Ruby。AC と TLE の分かれ目はまさかの約数列挙ループだった。while b*b<=a; if a%b==0; c = a/b end b+=1 end なら AC で、while b<=c; if a==b*c; end c = a/b+=1 end なら TLE。AC の方では足し算１、掛け算１、剰余演算１が毎回で、約数が見つかったときだけ割り算が１。TLE の方は足し算１、掛け算１、割り算１を毎回やっている。剰余と割り算のコストが同程度なら剰余を求めないで済んでる分得かなと思うんだけど、そういう結果ではない。違うんだ？ ループ回数は同じだと思うし、どこで差がついてるのか本当にわからない。■３桁 ms の２つの提出(#20120433, #20414187)を読んだ。約数列挙に工夫があった。最初に素数を列挙している。たしかに１ずつ加算して割り切れるか確かめるより、素数について指数を調べる方が効率が良さそう。