ABC432 （2025/11/15）
Good luck !
今回むずくね......
〇A問題
まーす.icon listで受け取って，降順sortして文字連結．
Kaplam.icon対戦ありがとうございました(*'ω'*)
まーす.icon 景品Get おめでとう
tako.icon おめでとう
CarpDay.icon さすが！横浜も頑張れー！
N_N.icon 強いですね！でもMBはみんな強くなった！！
wataumi.iconKaplam.icon強すぎるんだよな！
まーす.icon 景品Get おめでとう
tako.icon おめでとう。見ない間に強くなったなぁ
N_N.icon おめでとう！いい勝負でした．
CarpDay.iconおめでとう！横浜楽しみだ！！
tako.icon そーと
CarpDay.icon やった！1-liner！！
N_N.icon 同じくソート
〇B問題
Kaplam.icon0を含んでない場合はsort,含んでいる場合は抜いてsortしてから2番目に0を挿入する
tako.icon いろいろ迷走して結局文字列結合にした
まーす.icon 0をカウント＆0以外の数字のlist$ Lを作成して昇順にsort．そして，Lの先頭 + "00...0" + Lの先頭以外の順に連結．
wataumi.icon0も含めて数字のlist$ Lを作成して昇順にsort．そして，for文で0をカウントして、0以外の数字がでてきたら、その数字 + "00...0" 、その後に続く数字をひたすら足す。
CarpDay.icon Kaplam.iconさんと同じっぽい．tako.iconさんと同じく文字列．まーす.iconさんと完全に同じっぽい．
N_N.icon 誰かと一緒かどうかわからないけど，とりあえずソートして解いた．
〇C問題
Kaplam.iconこれかなり難しい気がしたんだけどやたら通っててびっくりしてた 飴玉2個の重さでlcmとって、飴玉の変換の最小単位を求めて、それで変換できない個数だったり、最後まで変換するのに個数が足りなかったりしたら落とすみたいな、正攻法にしては分岐とか実装重いので多分もっと上手にできる気がする
tako.icon むずい。数式の変形とかするんだろーなーと眺めたがわからんので飛ばす
まーす.icon Cは未解決問題なんじゃないの？（適当）sortしたら都合がいいことが起きそう．まぁ，めんどくさそうなんですが......
CarpDay.icon wataumi.iconさんがニヤニヤしている顔が浮かびつつ，不定方程式とにらめっこ．10分以上式変形してD問題へ．ラスト7分で戻って，落ちついて数値例を見たら，あれ？解けそう！数の小さい順にソートして，最小個数をすべて大きな飴にして，以降の個数は大きい飴を小さい飴に交換して実現できるか確認．終了後6分後に無事AC．
wataumi.iconニヤニヤ
wataumi.icon全員の総重量 W が同じなので$ X A_i + (Y-X) b_i = W ( b_i=大きい飴の個数 ) 。$ W が一定なので$ X A_1 + D b_1 = X A_j + D b_j ( D=Y-X )
N_N.icon 一番配る飴が少ない人にはすべて重い方の飴を配る．後は，配る飴が一つ増えるたびに，軽い方の飴を$ Y/(Y-x)個増やして，重い方の飴を$ Y/(Y-x) - 1個減らして配るようにしていけばよい．$ Y/(Y-x)が整数になるとは限らないので，軽い方（重い方）の飴を配る数が整数になるかどうかに注意しながら，重い飴の数の合計を求める．変数を long で宣言し忘れたので，WAを一回食らう．
kakip.iconまず全部大きい飴にしてそれで小さい飴に変えていくかんじ
〇D問題
Kaplam.icon黒長方形を左下-右上の座標で持って、ズレ方によって座標をずらしたり分割したりして最終盤面に、それぞれでくっつくかどうか判定してUFで繋げてそれを元に面積計算、うちが通した時まだ3桁人も通ってなかったのにEを400人ぐらい通してて何事かと
まーす.icon Ｃから現実逃避をしたが，Dもめんどくさそうだった泣
CarpDay.icon 実装ゲーと踏んで頑張るが，実装力＆幾何力弱くて涙目．やっと長方形分割したけど連結処理に手間取る．X方向にソートして隣り合う長方形をチェックする方法で入力例1は通ったけど入力例2がWA．長方形数が思ったより少なかったので，UnionFind使って連結性をチェックして何とかAC．もう残り時間8分未満．．
CarpDay.icon D問題青ランクで，E問題緑ランクでした．．．結果として，自分はE問題多分WAだったからラッキーでした．
wataumi.iconDSU (Union Find)を使用してAC。x座標, y座標が重なるか, x座標, y座標が接するかでくっつけるかを決める。
kakip.icon正解数見てとばした
N_N.icon やはり矩形領域を分割していってUnionFind ね．多くても$ 2^{14}個にしか分割されないので，それでいけるとは思ってたけど，実装がしんどくて途中で戦意喪失．
〇E問題
tako.icon 個数と和をBITで持つ
Kaplam.icon個数をsortedlistで、和をBITで持って、l以下の個数*l + r以上の個数*r + (l+1からr-1までの要素の和)、最初遅延セグで書いてTLEしたのでそこからsortedlistとBITに修正するのに15分かかった
まーす.icon C, Dよりも個人的には簡単（知識ゲー）．使ったアルゴリズム：SegTree
まーす.icon 考えたこと：クエリタイプ2のときのみ記述します．(i) $ l \geq rのときと，(ii) $ l < rのときで場合分けをする． (i) の場合は，$ \maxの定義から，$ N \times lが答え．(ii) の場合は，$ (l より小さい要素数) \times l + (r 以上の要素数) \times r + (l 以上かつ r より小さい要素の総和)が答え．
まーす.icon Lazyの方で試行錯誤しているが，ずっとTLE．スクラップボックスの中にあるやつでやると，AC の数がひとつ増えた．Python でAC出している人のコードをざっと見したけれど，私が見た範囲ではLazyでAC出している人はいなかった．
CarpDay.icon 区間更新しないから，Lazyを使う必要ないのでは？
まーす.icon おっしゃる通りです．方針は簡単にたったけれど，SegTreeの経験値が少なすぎて実装時に混乱していたのと，計算量的にいけるんじゃね？と思ってたので突っ込みました（TLE × 2）．
CarpDay.icon見ることもできず．まーす.iconさん曰く簡単とのことなので，ちょっと見てきます．（見てきた．）全然分からん．セグメント木かな？と思うも，実装思いつかない．また明日考えます．
CarpDay.icon寝る前に考えたら，すっと思いついて実装．方針はtako.iconさんと同じ．タイプ1のときに，元の値と同じ値を入れる場合にWA（理由が分からずGPTに聞いた）．修正してAC．本番で挑んでもWAの理由が分からず撃沈したパターンっぽい．
kakip.iconSegTree使ったけどTLE。これC++だったら通りそう？翻訳させてくれ
まーす.icon 私の場合は，LazySegTreeの場合はTLEで，アルゴリズムを変えずにSegTree使ったらAC出ました．（謎）
CarpDay.icon 後者に比べて，前者はかなり遅いよ～．
まーす.icon SegTreeの認識が甘いことが分かったので実践積まなきゃですね......．これが使いこなせたら水行くんじゃね（適当）
wataumi.iconFenwickTreeを使用してTLE。方針はあってそうなので、悔しい。
〇F問題
wataumi.iconKaplam.icon以降見てない
〇G問題