脳log[20220720]

2022年07月20日 (水) [AtCoder] 精進。第２回PAST-M「食堂」。周期にそって数を数える問題。しかし問題文の長さパラメータの多さからわかるように間違えずに数えるのが非常に難しい。制約が厳しいので素直で間違えにくいが遅いやり方をすることもできない。■提出 #33368195 (AC / 550 Byte / 423 ms)。４、５時間がかりの力作ですよ。初日から最初に好物が食べられる日までのあいだに好物でないものを何皿食べるかを数え、最初に好物を食べたら D 日のサイクルのあいだに何皿の好物とそうでないものを食べるかを数え、余った１サイクル未満の皿数に何皿の好物が含まれているかを数える。前半で累積和を作り、後半で数える。累積和では好物と好物のあいだに何皿の好物でないものを食べるかを記録した。■サンプルしか通らなかった提出 #13619835 (RE×1/WA×3/TLE×24) を書いた２年前より確実に前進しているね。たとえこの前の ABC が３完であり下手をすると AtCoder を始めたばかりの数年前に劣るパフォーマンスだとしてもね。■この手の問題はこれまでに少なくとも３問解いている。ABC175-D「Moving Piece」と ABC241-E「Putting Candies」と ABC258-E「Packing Potatoes」。どれも水 diff。