ABC308 (2023/07/01)
CarpDay.iconC++が有利な回ですね！
〇A問題
おたふく.icon 条件を満たしていないものを全てあらかじめ除く。
TTT.icon for文の中で条件3つに従いふるいにかけました。
TK.icon条件を満たしていない時点でNo すべてクリアでYes
yuichang.icon慎重にやる。
Yuto.icon 場合分け
Kaplam.iconTK.iconさんと同じ、ちょっとC++勉強して使いたくなったせいで少し手間取ったyuichang.iconいいね！
tako.iconやるだけ
CarpDay.iconTK.iconさんと同じ．普段あまり使わなかったany使ってみました．
〇B問題
おたふく.icon DとPの対応をdictで管理して、含まれていない場合はP[0]を含まれているなら素直に結びついたPを足す。
yuichang.icon添字に気をつけて慎重にやる
TK.icon文章の理解が最初できなかった。変数に説明文を丁寧につけつつ言われた通りの条件で加算
TTT.icon defaultdictで値段と料理名を登録しました。ICPC前にdefaultdictを使う練習ができて良かったです。
Yuto.icon collections.defaultdict(lambda: P[0])
Kaplam.icon入力全部listに突っ込んで、色名あったらその値段、なかったら0番目、日本語難しくて時間かかった
tako.icon辞書を使ってやりました
CarpDay.icon完全におたふく.iconさんと同じ
〇C問題
おたふく.icon 成功確率を素直に求めた後、その成功確率とそのindexを[成功確率, ~i]として2次元配列を管理。その後、降順にsorted。後はそのindexの~を外して全て空白区切りで出力。解法自体は合っていると思うがWA4件...。
yuichang.icon小数絡む計算なので誤差が恐かったが普通に通ったので驚き。long doubelのおかげ？indexと計算した値を持つpair型を配列に入れてソート。ラムダ式で比較関数を自作。
TK.iconおそらく成功確率をそのまま求めてしまったため、大きい値で誤差ができたのか？そのままソートするとTLEになりそうかなと思い、同じ確率を持つ人を辞書の値をリストにして管理。キーをheapqで取り出してやっていた。後は、A_i = 0の時にheapqの扱いがバグるため、修正したがWAが増えて発狂。
Yuto.icon やるだけ．計算誤差のせいで5ペナも出してしまった（4WAの人たぶん全員これ）．decimal使ってPyPyで出したら謎のTLE．Pythonで出したらやっとAC．計算誤差，以前も同じミスをしたのに．．．ばかです．
おたふく.icon 計算誤差だって..........!?
Yuto.icon decimal.Decimalを使おう！！！！！！！！！！！！
Yuto.icon PyPyだとdecimal遅い件，内部的にstrを経由してて，文字列結合的な処理が入ってるのかな？
CarpDay.iconPyPyが弱い例が増えましたね！
TTT.icon 愚直に実装するとTLEするだろうから何か工夫しようと考えましたが思いつかなかったので残りの1時間はDに費やしました。
Kaplam.icon素直に計算して素直にリストに突っ込んで素直にソートして予想通りTLE16、多分知らない知識がいるやつ。
tako.icon4WAの一人です...Decimalを使う前にB/(A+B)にして適当に出力すると1WAに減ってコーナーケースと思っていろいろ探してました。最終的にDecimalを使って解決。
CarpDay.icon同じく4WAでした．割り算による計算誤差であることはすぐに理解して，A1/(A1+B1)<A2/(A2+B2)を割り算使わないように式変形してA1(A2+B2)<A2(A1+B1)が成立するかどうかをソート時に考慮すればよい，と考えてマージソートを独自に作成．（バチャコンだったので）「ソートの実装なんて懐かしいなぁ」って感傷に浸りながら実装してAC．コンテスト後，Pythonでソートの比較関数を定義できないか調べたらありました．https://qiita.com/norioc/items/cb533d009aa63453df40 ．でもdecimal.Decimal使う方が絶対にいいね． yan.icon見たところ簡単そうじゃん。C問題楽勝とかいってたら4WA。簡単とか言ってごめんなさい。
〇D問題
yuichang.icon 見るからにDFSだが時間かかった。再帰で書いてたらバグらせたのでstackで実装。見たか否かではなく、その頂点にたどり着けるか否かをbool値の配列で管理して計算量削減
おたふく.icon 再帰でDFS。TLE 4件...。非再帰でDFS。TLE 1件...。bfsで作り直してみるとあっという間にAC。解せぬ...。DFSで解けている人のコードを見てみて、再度DFSで実装し直してみて、帰りがけの処理を無くすとACが出たが、何故帰りがけが必要が無いのか分からない。
CarpDay.icon探索の目的が「ある点までの到着可能性」だからでしょう．帰りがけにvisited = Falseとするのは，全ての枝を走査する必要があるときじゃないかな？
おたふく.icon 確かに、どういうルートを辿ってその点に辿り着いたとしても、一度その点の先を進んで行き止まりと分かっていれば、探索をやめてしまっても良いよねって考えると腑に落ちました。
TTT.icon BFSで実装中です。深さの情報もいらないですしDFSでいいのですね。あまり使い分けが分からないですがこのまま解いてみます。(追記：コンテスト後1時間かけて自力でBFSでAC出ました！！初めて全探索以外で自力でAC出せたのでとても嬉しいです！)
Yuto.icon DFSしたらTLEした．一応，行けるとこにしか行かない（snuke...にならない移動はしない）枝刈りはしたんだけど，無理でした．非再帰に書き直してたらコンテスト終了．非再帰のDFS書き慣れてなくて時間かかりすぎ
Yuto.icon コンテスト後，非再帰のDFSにしたら（Python:625ms，PyPy:294msで）通った．．悔しい．Python/PyPyの再帰遅すぎるやろ
TK.icondfsだと思いやってみたが、Cからシフトしてくるのが遅すぎた。
Kaplam.icon再帰で順番にsnukeを繋げていく、再帰の最大回数設定し忘れてRE、他の処理の事考えず最大回数500*500に設定したら足りてなくて2回目のRE、その10倍にしてAC、追記：コメントでPyPyが再帰苦手って聞いたのを思い出して試してみたらPython:420ms,PyPy:966ms...なるほど 再追記：0の数打ち間違えてて500*500で足りてた、とはいえ多すぎない程度に余裕持って設定するのがよさそう
tako.icondfs嫌いなのでbfsで実装しました。不要なインポートとカンニングペーパーを消すのを忘れてました。
tako.icon（追記：bfsだと思ったらもしかしてdfsになってる？あと、dequeインポートしているのに使っていなかった？自分でもよくわからない感じになっています。）
CarpDay.iconどっちでも良いので何となくBFSで実装するも2RE．原因が分からず（バチャコンなのでレートダウンも気にせず）コード半分を消してバグの位置を探すという荒業によって原因追求して（しょうもない）バグを発見．10ペナの末のAC．
〇E問題
Yuto.icon 問題は読んだけど，Dが解けそうで解けなかったので，Eまでたどり着けなかった．
TK.icon覗いただけ、これ以降見ていない
Kaplam.iconC無理そうだったので少し書いてみたものの100%TLEになると思ってやめた。
CarpDay.iconコンテスト中に方針考えたが実装時間足りず．実装に時間かかったがAC．考え方は難しくない．
〇F問題
yuichang.iconEより簡単そう。multiset + lowerboundでいけそう（安直？）Dで時間を使いすぎた
yuichang.icon（追記 multiset+lowerboundでいけた
CarpDay.iconDP？最大マッチングからの最大流？と考えたが，よく考えるとyuichang.iconさん同様，集合管理＋二分探索でできそうと判断．multiset使えるC++なら解けそうだなぁ，と思ってPython用のmultisetを作っている人のサイトからライブラリ拝借して実装したらAC．Python泣かせだの問題だ！．．．と思って解説見たら，単なるheapqでも実装できそう．実装したらコード長も処理時間も短くACできました．