脳log[20240919]

2024年09月19日 (木) [AtCoder] 精進。CodeQUEEN 2024 決勝の FG。E までしか解けなかった 20240823 の続き。時間をおくと勝手に解けるメソッド。なお、その時間が余命より短いか長いかはわかりません。■F 問題「Divide the Cake」。円環に切れ目ということで前々回の ABC370-F Cake Division を思い出す。ダブリングで解けるかなと考えてみるけど、解けない。どういう問題か。切れ目を１つ選んだとき、その切れ目から１切れ、２切れ、……、N-1 切れのまとまりのいずれもが、１切れあたりの平均において全体の平均を下回らないような、そういう切れ目を見つける。問題には選ばれなかった残りのピースの平均との比較が書いてあるけど、全体の平均と比較するのと同じことでしょう。平均をどう扱うか。累積和を１で割ってみたり２で割ってみたり３で割ってみたりするようでは O(N^2) になってしまう。濃度の二分探索では必要な溶質の質量との差分で考える。平均との差分の累積和を考えてみる。１切れの和、２切れの和、……、N-1 切れの和までの N-1 項の累積和のいずれもが０以上なら、どういう切り方をしても平均を下回ることがない。２周分の累積和をセグメント木に乗せて、N 回、N-1 幅の区間最小値を尋ねた。平均を考えるのに小数は使いたくないから、N で割る代わりに乗ってる数を N 倍した。そうすると全体の平均は元々の数の総和になる。それとの差分の累積和を考える。提出 #57894314 (AC / 636 Byte / 596 ms)。■G 問題「Quintuple Scoop Ice Cream」。二分探索っぽさがあるよね。衝撃の青 diff だった ABC227-D Project Planning みたいに、うまく判定する方法があるのではないか。わからないけど。あるフレーバーを選べる上限は 3K 個まで(１段目と３段目と５段目に)。１つのフレーバーを 3K 選んでしまったら、他のフレーバーは 2K までしか選べない。どのフレーバーも 2K 個までは何も考えずに使えるとも言える。2K を超えるフレーバーが１種類だけだったら、追加で K 個まで使える。２種類以上あったら……全部合わせて K 個まで追加できる。あとは使えるだけ使い切って 5K に足りているかどうかで判定する。提出 #57906057 (AC / 723 Byte / 351 ms)。判定するだけではなかった。トッピング例を構成しなければいけない。ABC362-F Perfect Matching on a Tree の解答を構成するのにプライオリティキューみたいな道具が必要ないように(20240713)、K 個ずつ５段にうまく並べたいと思ったけど、すっきりきれいにはできなかった。５段目を置くときに同じトッピングが最大で３個になるんだけど、必ずしも (A,B,A,C,A) にはならなくて、(A,B,C,A,A) とか (B,A,C,A,A) みたいなケースが考えられる。K 行に渡って泥臭く並べ替えた。■最後の H 問題はまだ。