ABC383 （2024/12/07）
ABC 380 からルールの変更がありました．
・生成AIにコードを生成させる場合、コーディング速度の上昇のみを目的とした補完のみが許可されます。問題やその部分問題を解かせたり、アイデアを得たりする用途に使用してはいけません。
・各言語への翻訳や、他プログラミング言語への翻訳などは、ルール中で指定されたフォーマットでのみ許可されます。
〇A問題
Kaplam.icon用事あったので終わり際から始めてA～Cまで書いて普通に通ると思って出したらBは半分ぐらいWA出てCもTLE5で笑ってた、順位見る限り今回大分難しいみたいねって言ってたけどkakip.iconさんがF通してたの見切れてただけだった(4完で700とかやべえってなってた)
kakip.icon前に追加した時間との差だけ水の量を引いて、0未満になったら0にしてから水増やす。水復帰
まーす.icon３桁＆水復帰おめでとう！
kakip.icon↑↓ありがとうございます！
CarpDay.iconKaplam.iconおめでとう！さすが！！
CarpDay.iconショック大きすぎて，山にこもります．．数日後に戻ります．
まーす.iconいつでも待ってます( ；∀；)
CarpDay.icon思ったより早く戻れました．お気遣いありがとう．．．素直にシミュレーション
まーす.icon(*^_^*)
CarpDay.icon 茶色パフォで，レート -40でした．．．コツコツ＋稼ぐぞ！！
まーす.iconans = max(0, ans - (T[i] - T[i - 1])) + V[i]．
tako.icon 疲労困憊のため問題見て終わり CarpDay.icon たまにはごゆっくり～
yuichang.iconsum(v)-t.front()-t.back()的な嘘解法考えてて7分かかった
〇B問題
kakip.icon2つの加湿器の位置を全探索して各マスから加湿器の距離を求める
まーす.icon加湿器を一つ固定して探索．問題読み間違え＆普通にグダった感じ．
yuichang.icon愚直に6重ループする
CarpDay.icon多分kakip.iconさんと同じ．床の位置保持してcombinationで加湿器位置のペアを列挙．各床との距離求める．
〇C問題
kakip.icon各マスについて、加湿器からの距離が近い順に探索
まーす.icon全然方針立たん......．最高値を記録しておいてBFSする感じでいけそうだけど......．（各加湿器ごとにBFSするのではなくて，全部の加湿器を一気にBFSしちゃえばよくね？っていう案）
yuichang.iconダイクストラっぽいの。今から移動できる距離と加湿器の座標をsorted multisetに入れてwhile(multiset.size())で幅優先っぽく
CarpDay.icon各加湿器からDFS．一度湿ったところは探索しなくていいので，計算量は床の個数のO(HW)で済む．．．と思ったら入力例2でWA．思いつかずにD問題へ（行って二度と戻れず）．コンテスト後に山に籠って唸っていたら神の啓示が来てAC．全加湿器から同時にBFS．「DFSがダメならBFS？」っていう発想がコンテスト中にできず，無念．
〇D問題
kakip.icon素数の8乗のパターンと素数1の2乗×素数2の2乗のパターンをすべて列挙
まーす.icon個人的にB, Cより簡単．$ N ^ {1/2}以下の素数リスト$ Pを作って，$ i,\ j \in P,\ i ^ {2} \times j ^ {2} \leq N をbisect 使って数え挙げる．$ 2 ^ 8といったケースもお忘れなくって感じ．
Kaplam.iconおま環なのかもしれないけどtexと反転合わせたら表示おかしいから非推奨かも
CarpDay.icon確かに最後の伏字，何かおかしいぞ．
まーす.iconありがとう．入れ子にしたらやっぱりダメですね......．$ 2^8が表示されてなかった......
CarpDay.icon「お忘れなく」を忘れて沼りました．．（ｘｘ）
yuichang.iconググるとYahoo知恵袋にほぼ答えが書いてるのでやる
CarpDay.iconまーす.iconさんと同じ方法でも入力例2でWA．実数割り算による誤差と判断して，手動の二分探索バージョンで試すも同じ誤答値でWAで試合終了．山に籠り，今度は$ N以下の素数の2乗リストを作る方法を試すも，また同じ誤答値．．．ここでようやく考え漏れの可能性に気付く．kakip.iconさんの最初のパターン見落とし，というオチ．無念×2．
Kaplam.icon素数の積が√nを超えない組み合わせを意識して8乗のも足してって感じ、sampleが200止まりなのがずるい...8乗中々気付かなかったし1回1000ぐらいまで素直に約数の個数求める関数で全列挙してみて何か考え抜けがないか見た方がよかった感じ
〇E問題
yuichang.iconマッチング？燃やす埋める？
kakip.icon重み小さい順に辺追加してunionfindで…的な？
CarpDay.iconコンテスト後に上の「燃やす埋める」のコメント見て，最大流脳になりながら問題読むが方針つかめず．F問題終わってから入力例を図示してみたら，まさにkakip.iconさんと同じ考えに至る．各点Unionには未処理のA側の点とB側の点が同時に入ることはないので，A側の点数－B側の点数をリストで管理したら綺麗に実装，無事AC．コンテスト後はスムーズにAC取れる．．．
〇F問題
kakip.icon「ある色の商品を1個以上買ったなら満足度がK増える」と言い換えられるので、色でソートして色ごとに分割するとDPできる。変数名に日本語使ってみたけどちょっと便利。英小文字のプレフィックスつけると打ちやすい
CarpDay.icon 日本語変数いいね！
CarpDay.icon翌日にやっと問題確認．1色しかなければあれだよね？あとはkakip.iconと同じ発想で実装．$ O(NX)＝O(25\times 10^6)になるから2.5秒でも無理？と心配したけど1441msでAC．定数倍軽いから？
〇G問題