ABC382 （2024/11/30）
ABC 380 からルールの変更がありました．（メモ：ABC 385 まで掲示）
・生成AIにコードを生成させる場合、コーディング速度の上昇のみを目的とした補完のみが許可されます。問題やその部分問題を解かせたり、アイデアを得たりする用途に使用してはいけません。
・各言語への翻訳や、他プログラミング言語への翻訳などは、ルール中で指定されたフォーマットでのみ許可されます。
〇A問題
まーす.icon@をカウントして，print(N - @の数 + D)．
tako.icon 以下同文
Kaplam.icon今日はイベント参加してて、自分の出番終わった後も観てようかな～とunratedでするつもりだったのに運の神様にそっぽ向かれすぎて気まずくなったので予定変更してratedで競プロに逃げてきたら上振れました ようやく入水したので一旦一区切りとします、お疲れ様でした( ˘ω˘)
まーす.icon３桁すごい......&入水おめでとう
CarpDay.iconおめでとう！水色増えて嬉しいです！
yuichang.iconおめでとう！
Kaplam.icon↑↓ありがとうございます(*'ω'*)
kakip.iconおめでとうございます！
CarpDay.iconprint(N - S.count('@') + D)
kakip.iconBを先に解いたのでそれでcount
〇B問題
まーす.icon文字列$ Sの後ろから$ D番目の@を記録して，print(S[ : 後ろからD番目の@のindex] + .から成る文字列)
tako.icon 逆から見る
Kaplam.icon同上
CarpDay.icon素直にリストにして逆から見て置き換えて文字列に戻す．
yuichang.iconやる
kakip.iconstr.replace()の第三引数で置換回数を指定
〇C問題
tako.icon 美食度でソートして二分探索してその範囲のインデックスの最小値。
まーす.icon 寿司の美味しさ$ Bをsortして，尺取り法．
Kaplam.iconそこまでの最低値求めてにぶたん
CarpDay.iconKaplam.iconさんと同じと思われ
yuichang.icon累積min（誰が取る？）でいい
kakip.icon同上
〇D問題
tako.icon 最後頑張ったけど最後の最後で最後のテストケースがTLEして発狂してた
まーす.icon再帰関数を頑張って作る．作れる数列の個数を表示し忘れて，1ペナルティ．もう一つはTLE．
Kaplam.icon再帰するだけ、作れる数列の個数を表示し忘れて，1ペナルティ
CarpDay.icon再帰避けるためdequeで実装しようと思ったけどややこしくて再帰使う．CPythonで投稿するとTLEにならないかドキドキする．
Kaplam.icon気になったので私のとCarpDay.iconさんの提出をそれぞれpypyとCPyで出してみたのですが、私のpypyとCPyが約800msと3000ms,CarpDay.iconさんのpypyとCpyが約500msと1000msでいずれもpypyの方が明確に早く終わりました、今回みたいな浅い所までしか潜らない再帰の場合はpypyで出した方がTLEの危険性低いかもしれません(C++とPythonの両刀してた時期に言語変え忘れたまま出したことが何度もあったので個人的にはCPyで提出した後pypyに戻し忘れるのも怖いかも)
Kaplam.iconAtcoder用の拡張機能色々あるって聞きつつ結局1回も入れた事ないんですがこういうのまであるんですね、すごい
CarpDay.icon調査ありがとうございます！ポイントは再帰の深さですね．
yuichang.icon上限を見積もって再帰
kakip.icon枝刈りしてなくてTLE、水→緑に
〇E問題
まーす.iconパックを剥いたときに，レアカードが$ i枚となる確率$ P_{i}を求めて，期待値DP．この期待値DPのところでつまずいてる感じ......
CarpDay.iconまーす.iconさんと同じく確率$ P_iを求める．$ i=0の場合を除く処理すれば最大$ X回で$ X枚になるので解けると思ったけど，各ループで$ O(N^2)かかる方法しか思いつかず時間切れ．
CarpDay.iconうまくいかず諦めて解説見る．自分の期待値DPの理解の甘さを痛感．以前もすごろくのような類似問題あったし，しっかり理解していれば難しくない問題だった．もったいない．
〇F問題
Kaplam.icon範囲更新のセグ木で初期地点下のやつから落としていく、解法はすぐ思いついたけど範囲更新のセグ木が手持ちに見当たらないし検索して出てきたやつなんかエラー出るしってんで結構ロスしたけどF通ったの確か初めてで嬉しい嬉しい
CarpDay.iconE問題に詰まって覗きに来る．頑張ればできるかも？と思いつつ，E問題を解かねばならない使命感を持って退却．
CarpDay.iconコンテスト終了後，tako.iconさんお好み遅延セグ木使って実装．自信もって投稿するもTLE．本質的部分は改善無理なので，入出力でのロスを除いたらAC．このライブラリはやっぱり重いね．
CarpDay.iconAtCoderのライブラリより，OBが残してくれた自作ライブラリの方が少し速かったよ～． yuichang.iconソートして一番下のやつから決めていける。区間更新、区間minの遅延セグ木を使ってバーで埋まっているマスを保持してシミュレーションできる
〇G問題