ABC423 （2025/09/14）
〇A問題
まーす.iconfor文で，$ i \cdot \frac{C}{1000} + i > Xとなる$ iの最小値（1000 刻みで$ iを増やしていく）を求めて，$ i - 1000が答え．
Kaplam.iconちょっと水戻れる気がしなくなってきた_(:3」∠)_
CarpDay.iconfor文で，$ i\cdot (1000 + c) i > xとなる$ iの最小値（$ iは1000単位）を求めて，$ 1000(i-1)が答え．
wataumi.icon 数学回だったね。print(X//(1000+C)*1000)
N_N.icon wataumi.iconさんと同じ．
〇B問題
Kaplam.icon素直に左と右から開ける
まーす.icon Kaplam.iconさんと同じ．サンプル3を確認するまで，”2人のどちらかが到達可能な部屋の数”を出力するものだと勘違いしていた．
wataumi.icon みなさんに同じだけど、全部のドアが開いているとき、倍数えちゃっててWA.
CarpDay.iconみなさんと同じだけど，部屋とドアの関係，0-indexと1-indexが混乱して結構苦労した．
N_N.icon 今日はバグの日．Dまで難しくはなかったけど，WAの連続．閉じてる扉の一番左端の位置と一番右端の位置を求めてその間の範囲を計算．
〇C問題
Kaplam.icon左全部開けてから右全部開ける、実装方針がまずかったのか早解きも出来てねえんだよな
まーす.icon$ l := \min\{ i \mid i = 0, 1,\dots , N,\ L_{i} = 0 \},\quad r := \max\{ i \mid i = 0, 1,\dots , N,\ L_{i} = 0 \}と定める．また，$ \operatorname{close} := \{c \mid l < c < r, L_{c} = 1 \}と定める．このとき，$ 2 \cdot \operatorname{Card}(\operatorname{close}) + N + 1 - \sum_{i = 1} ^ {N} L_{i}が答え．実際は，こんなことはしていません-
wataumi.icon高橋さんから左右に<開> cnt0 += 1（閉めるだけ）, <閉>cnt1 += 2（開けてから閉める）で、開いてた時だけ、ansL（ansR）をcnt0+cnt1に更新。print(ansL+ansR)
CarpDay.icon左右の端から閉まっている範囲求めて，残り部分の部屋数＋残り部分の閉まっている部屋数
wataumi.iconエレガント！
N_N.icon 開いてる扉の一番左端の位置と一番右端の位置を求めて，その間の閉じてる扉を全部開け，次に開いている扉を全部閉める．もしかしたら，CarpDay.icon さんと似てる？スタート位置の場合分けでミスってWA．
〇D問題
Kaplam.iconheapqで入店管理するだけのはずなんだけどなぜかTLE,色々かなり高速化したんだけどTLEの数変わらないからどこかでwhileに嵌まってるんだろうけど見つからず_(:3」∠)_
Kaplam.iconバグってるわけじゃなくてやたら遅いっぽい、heapqの値intにしてるしそれ以外も色々高速化試みたんだけどなんでだろ
Kaplam.icon計算量的には問題ないけど辞書とかheapqとか要素数増えたら妙に重くなるの複数使ってるからってことで結論付けてみなかったことにした
CarpDay.iconC問題終わった段階で全体見たらE問題の方が緑以下の正答率高かったからE問題へ移動（これが敗因）．E問題に詰まって戻って確認したら要は待ち行列．素直にheapqで実装（当初dequeで実装して間違いに気付かなかった）．
まーす.iconheapqを使って，入店＆退店の管理を行う．団体$ iが入店を行うときに，$ iの前に入店していた団体が退店するときのカウント漏れがあった．
wataumi.iconheapqでイベント管理、dequeで入店管理。
N_N.icon WA×6なので，偉そうなこと言えないんだけど皆，優先度付きキューを使うんだね．うちの子も Java で優先度付きキューを使ってた．自分は，「データは1つ漏らさず残す」という競プロ的には間違った主義（システム開発では正しい姿勢）なので，写像（TreeMap，キーでソートされた写像）で無駄に詳細な情報を残すようにした．計算量的には問題ないと思うけど，データが複雑になるので，バグが入りやすい．．．(TT)
〇E問題
CarpDay.iconずっと考えていたのに最後まで分からず悔しい．各クエリをO(1)で処理したいから，累積和の要領だろうな，と考えてLを1に固定した値はO(N)で求めることはできたけど，(L,R)=(2,4)のようなパターンに対応できず．あと10分だけ考えてみる．
CarpDay.icon10分考えて，神が降ってきたか？もしかして 確率でいう加法定理？まだ下のヒントみてないよ．実装してみよう．
CarpDay.icon実装したらうまくいかないケースが見つかった（ｘｘ）神じゃなかった．．．もう諦めるか．
wataumi.iconヒント：展開
CarpDay.iconヒント見たけど，分からんな．各項の寄与率（合計に対して何回カウントされるか）を考える（俗に言う主客転倒）をして考えたけど，良い方法思いつかなかった．
CarpDay.icon解説見てきました．上の考えは合っていたけど，数学的な考えで進めることができなかった．残念．
まーす.icon累積和の累積和をとったりしてた．というか，これくらいしか思いつかなかった．多分，級数の計算を上手いことすれば，いい感じの式がでてくるはず．って思って，解説とかwataumi.iconさんの伏字みたけれど，全然違った．
wataumi.icon公式解説と同じ考え方。L≤l≤Rかつl≤r≤Rかつl≤j≤rなので、L ≤ l ≤ j ≤ r ≤ R。よって、S(L, R) = Aj(j - L + 1)(R - j + 1)。これを展開すると、S(L, R) = -j*j*Aj+(L+R)*j*Aj-(L-1)*(R+1)*Aj。
CarpDay.icon よく思いつきました！素晴らしい！
Kaplam.iconDが何やってもTLE減らないから諦めてa{i}*(j-x+1)*(y-j+1)まで立て(て制約誤読して出してTLEした後C++で書き直してTLE出して誤読に気付い)て時間切れ
〇F問題
CarpDay.iconE問題に詰まって少し覗く．単純にエラトステネスは使えないだろうし，N個中のM個の組合せ列挙も数が多すぎるので無理．
まーす.iconEと同時進行．問題文に”ちょうどOO個”という文言があったら，たいてい難しい......
CarpDay.iconさすがまーす.iconさん．解説見てきたらまさに「ちょうど」に関すること書いてありました．ゼータ変換の逆変換ってときどき見るから，そろそろ勉強会で勉強するタイミングなのかも．
まーす.icon伏字について，ごりっごりの代数学ですね......．時間が出てきたら，また勉強してみようかしら．
まーす.iconと思って，ググったら，想像していたもの（リーマンゼータ関数）と違った．関数解析で出てくるのか．しかも，線形作用素のあたりの話．
〇G問題