- やった回: ARC167
- 成績: AB2完🎉 / 0ペナ / 78:17(ペナ込み)
- パフォーマンス(推定): 1579
ダメもとでやったB問題が一発で通ったのがめっちゃうれしすぎる。初水色パフォ(推定)！
そろそろARCもRatedでやってもよいかなぁという欲が出始めているけれど、それよりまずは緑復帰したい……*1
出来たり出来なかったりの幅が激しすぎるのは経験不足ってことで納得するしかないかなぁ。今回は言うまでもなくできた方。
A問題: ARC167-A Toasts for Breakfast Party
貪欲じゃなきゃどう組み合わせたもんか分からんなぁと思って解いたら、どうやら貪欲でよいらしい。
トースト1枚になる皿の数(Xとする)、2枚になる皿の数(Yとする)は固定になって計算で求められるのでまずはそれを求めてしまう。
おいしさ順にトーストをソートして、美味しい順にX枚を1枚の皿としてB_jを求めてしまい、残りの皿Y枚分は残りのトーストから一番美味しいものと一番美味しくないものを順に合わせていく。
(追記) 解説を読んだら全体が2M個になるまで美味しさ0のトーストで埋めていくというやり方が書いてありました。すごく分かりやすい。そういうのサッと思いつける頭が欲しい。
B問題: ARC167-B Product of Divisors
素因数分解とか約数とかべき乗とかそこらへんの性質を使って解く問題。わりとがっつり高校数学みがある。
(0. Bが0の場合はそもそもABが1になるので0を返して終わり)
- Aの素因数分解をする
- ↑のそれぞれの素因数の係数をB倍する
- B倍した係数*2同士の積を出す⇒この結果がABの約数の数になる
A^Bの素因数の係数の三角数 * 3.の値 / (素因数の係数+1)を求める ⇒この値がそれぞれの素因数に対する積の係数の合計になる- 私の実力では説明むずい… A=6、B=2くらいで実際に組み合わせの真理値表みたいなの書くと分かるんだけど、1～係数までの合計×他の素因数の組み合わせの数がABの約数の席に含まれるそれぞれの素因数の個数になる
- ↑で求めた値をAの同じ素因数の係数で割る
約数は基本ペアになっていて掛けると必ずABになる*3ので、割り切れない心配はしなくてよい。 コードでは4.くらいの操作まで全部の素因数に対してやってるんだけど、実は4以降は適当な1個の素因数に対して計算すればよかったりすることにACしてから気付きました。無事にACしてよかったです。
素因数の数というか種類というか、素数を小さい方から掛けていって12個も使うと1012を超えるので、素因数分解した後は素直に配列ぶん回しても十分間に合います。いつもいくつくらいが目安か忘れるのでこれもスニペットに追記。
というわけで、今回も対ありでした～
