ABC363 （2024/07/20）
〇A問題
まーす.icon^の説明いる？いらんいらん
まーす.icon現在のレートを^で表せ．的な問題だと勘違いした．
CarpDay.icon緑復活おめでとう！！
まーす.iconいえーい
tako.icon MODでやればよさそうと思いつつ場合分けした。そしてミスりそうになった
Kaplam.iconif 100 > n って感じで4つ書いた
yuichang.icon out((1000-r)%100)にしててrが100の時にペナしそうだった
CarpDay.icon久々の1-liner．嬉しい．
〇B問題
まーす.iconLをsortして，print(max(0, T - L[-P]))．
tako.icon 適当にシミュレーション
Kaplam.icon素直に全部1ずつ足すの
yuichang.icon シミュレーション
CarpDay.icon降順にソートしたこと以外，まーす.iconさんと同じ．
〇C問題
tako.icon 全探索したがpythonでは通らない。やり方が悪いのかもしれんがc++で殴る
tako.iconmore_itertoolsというライブラリのdistinct_permutationsというものを使うと同じものを消した順列を出してくれる。これを使うと普通に通る。pythonにこういうライブラリがないわけがない
CarpDay.icon 情報Thanks！AtCoderでも使えるんやね！
まーす.iconムズイ．制約小さいタイプの問題はたいてい実装げーなので嫌い．
Kaplam.icon手元pypyで10秒ぐらいかかったのでD終わらせてからC++で書いた...ら1TLE出た上に再提出したら2TLEに増えて回数で通せそうになかったので文字の種類全部ばらばらの10文字の場合3628800を出すってちょっとズルして通した(危ういケース両方1msで終わったし確率で通りそう)、最近オーダーでは問題ないのに確率でTLE出るコード書いちゃうこと多いからもう少し制約余裕持つか3,4secぐらい許してほしい
yuichang.iconunorderd_setがハッシュ的に今回の問題と相性悪いらしいのでC++でも1TLEしてるのかも。あとst.countが最悪O(N)
Kaplam.icon確かにset関連の処理抜いて出してみたら上の2ケース600msぐらいで終わりました、なるほど...
yuichang.icon 何も考えずC++で順列全探索。1119ms
CarpDay.icon同じく全列挙したら2件TLE．2件ということは最悪ケースと踏まえ，Kaplam.iconが書いたように，全部バラバラのときに$ N!を返すようにしたらAC．Kaplam.iconのいう通り，C++だと脳筋でPythonだとTLEという問題がときどき目につく．まぁ，yuichang.iconさんに教えてもらえるうちにC++も使えるようにするのが賢明かも．
CarpDay.iconバラバラ対応なしでも通るようにする方法を検証．(1)全パターンを文字列にしてからソート．前回と同じパターンはチェックしない → AC．文字列にせずタプルのままだとTLE．(2)チェック済みのパターンを集合で覚えておいて，各パターンをチェック済みかどうか判断する方法 → TLE．文字列かしてもだめ．(3)同じパターンでも無視して全パターン調べて，最後にS中にある文字数を確認．$ n文字あるなら，$ n!で答えを割る → 余裕でAC．結論：リストやタプルのままより，文字列の方が速い．要素数が大きいリスト・タプルはできるだけ触らない．特に集合のinは意外に時間がかかるのに注意（(1)の方法で$ O(N!logN!)かかっているのにACなのは不思議）．
〇D問題
tako.icon C躓いたから先にこっちと思ったが問題文が短かったので(ルールの範囲内で)GPTに投げてCを考えてた
まーす.icon出力結果が0のときと1桁のときと2桁のときとそれ以外のときで場合分け．もうちょっと綺麗に出来たかもだけど，ACでたので結果オーライ．
Kaplam.icon1桁は0~9の10個、2桁は1~9を2個並べた9個、3桁は10 ~ 99を鏡にした90個って感じで頑張った
yuichang.icon 桁数調べて気合
CarpDay.icon答えの桁数求めるところまで想定通り考えられたのに，$ N番目を求めるところで根本的な勘違いして最後まで解けず．漸化式立てて，数学的に綺麗にとけるんじゃね？という色気が出たのも敗因．猛省します．(1) すぐ解けないと判断したら，次の問題を読む．(2) シンプルに考える．綺麗な解き方にこだわらない．猛省します．
CarpDay.iconレート30ダウンした．．．レート58アップしたyuichang.iconさんと全く同じレート1138！
yuichang.icon ><👍
〇E問題
tako.icon パット見むずそうなのでF考えてた。いけそうな解法思いついたのが5分前で無理でした。
まーす.icon残りの25分はこの問題に捧げてた．海に面してる部分をheapで見てやればいけそうな感じがするけど，実装ダルそう．
Kaplam.iconheapqとBFSで行けるとは思うんだけどどっかバグってる、CのC++書き換えで時間くった_(:3」∠)_
Kaplam.icon重複して探索してたからそこ直して出したんだけどがっつりTLE...浅い所からheapqでとりだして周りで沈んでなくて沈む所をBFSで広げていくだけだからO(H*W)で済んでるはずなんだけど定数倍重すぎるっぽい
yuichang.icon 時間を全探索。次に沈む可能性のあるsorted_multiset、確実に沈む座標のqueueを持ってbfs。1299ms。C++最強～
CarpDay.icon終了後に問題を読む．heapqで解けると判断して実装するも29/48でTLE．Kaplam.iconさんのいう通り，$ O(H*W)で済むから納得いかず，heapqに格納していた3次元（標高，行，列）を2次元（標高，行×W+列）に変更したらAC.なんじゃそりゃ？スポンサーなしABCは意図的にPython使いに嫌がらせしているようにも感じる今日この頃．
CarpDay.icon解説見たら，みんな大好きUnionFindでも解けるとのことで，試しに実装．その方法だと場所を1次元で管理することになるせいか，問題なくAC．接続するタイミングを保持する部分が必要なので，それなら単なるリストでも実装できるため，この方法である必要性は低いかな．
〇F問題
tako.icon 素因数分解とか考えてたけど無理そう
CarpDay.icontako.iconさんと同じくそんな感じかな～ → 考えたけど分からず解説読む．うーん．思いつかないこともない方法だけど，計算量問題ない！って見込める自信はないなぁ．
〇G問題