脳log[20231210]

2023年12月10日 (日) [AtCoder] 今日は ABC332 があった。ではふりかえり。■A 問題「Online Shopping」。言われた通りにやります。■B 問題「Glass and Mug」。K がべらぼうな数だと相当にややこしい問題になる。操作１が最も数が少なくてサイクルの起点になりそうだけど、そのときにマグが空とは限らないのがいやらしくて、操作１から操作１までのサイクルごとに初期状態の変遷を考えないといけない。操作１と操作１のあいだに操作２が何回繰り返されるか、そのあいだ、操作２と操作２のあいだに操作３が何回繰り返されるかは固定だけど(追記：マグの初期状態が違うんだから違うか)、最後の操作３の繰り返しだけは少なくなるかもしれない。二分探索をして最後の１サイクルだけシミュレートするとかかな。でもこれは B 問題なので K(≦100) 回操作をシミュレートします。■C 問題「T-shirts」。休日ごとにリセットされるので split(/0+/) した結果の 12 文字列について考えた。１の数を c1、２の数を c2 として、[c2,c1-M].max の max を答えにしたら WA だった。たぶん c2+[c1-M,0].max の max を答えにすべきだった。今以て確信はもてない。２パスの別方針の解答をでっちあげたらそちらはミスがなかったらしくそれで AC をとったので。■D 問題「Swapping Puzzle」。制約が５以下とささやかなので階乗の２乗に２乗を掛けても大丈夫。たぶん賢く操作を構成しようとすると、同じ値を持つマスの扱いが問題になりやすいと思う。すべての並べ替えを列挙して盤面が一致しているかを確かめるのが確実。■E 問題「Lucky bag」。解けてないよ。15 15／1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 という入力に対して３秒弱かかるのでは TLE が避けられない。勘違いする人がいるみたいだけど、３秒弱っていうのはコードテストで 2778 ms (＜３秒) かかったって意味だよ。俺は勘違いしてないよ。■F 問題「Random Update Query」。区間適用のセグメント木の香りがします。もっとも、仮にそれが手持ちの道具箱に入っていたとしても関数の合成が書けたわけではない。どこかで読んだけど、Ax+B の A と B を覚えておくだけで合成できたのかな。