ABC299 (2023/04/22)
CarpDay.icon 2週連続で，DDOS攻撃でUnrated．．．orz
〇A問題
CarpDay.icon |の回数カウントして，1回のときにoがでたらin．
Yuto.icon 前々回？に知ったrfind使ってみた
おたふく.icon |の登場回数をカウント
まーす.iconおたふく.iconさんと同じ
TTT.icon findとrfindを使いました。
tako.iconいつだったか、どなたかがやっていた"|*|"を使ってみました。
yuichang.icon前回のB問題と同じ、|の回数をカウント
TK.icon前にやってた、対象文字を回収して”｜＊｜”と比較
〇B問題
CarpDay.icon set(C)の中にTがあればCの最大値，そうでなければC[0]と同じ色の中の最大値を表示
Yuto.icon やることは簡単なのに，めちゃくちゃバグらせてしまった．．．
おたふく.icon Tの時の最大値とプレイヤー1の出した色と同色の時の最大値を同時に求め、Tの最大値が無い時に条件分岐。
まーす.iconまずはset(C)でTが集合Cの要素であるかを判断。TがCの要素であるならば、CがTであるものの最大値を出力。TがCの要素でないならば、プレイヤー１と同じ色の者内で比較(後者を勘違いしてWA)。
TTT.icon プレイヤー1の色と同じ色のカードの番号のリスト、Tと同じ色のカードの番号のリスト、プレイヤー1の色と同じ色のカードのプレイヤー番号のリスト、Tと同じ色のカードのプレイヤー番号のリストの計4つのリストにそれぞれ格納しました。
tako.icon前回学んだdefaultdictを使ってみました。キーを色にして、値を番号のリストにしました。
yuichang.iconTの色のカードがあるかないかで場合分け、最大値が更新されたらindexも更新
TK.icon色のセットの中にTがあればその色の人の中の最大値を回収、ないなら１Pの色の人の中での最大値を回収。どちらも最大値を別変数で持ち、更新したときの人を覚えておいた
〇C問題
CarpDay.icon特別な条件を最初に済ませる．最後に-を付け，-の直前に存在する連続したoの個数の最大値．
Yuto.icon 最初，二分探索実装したら4WA．境界の処理に手間取り，にぶたんを尺取りに変えてみるなど紆余曲折を経て無事にAC．7ペナ．．．コンテスト後に落ち着いて考えてみると簡単なのに，コンテスト中にこの冷静さを取り戻したかった．
おたふく.icon 簡単な問題なのに...解法もすぐに思いついていたのに...あまりにもしょうもないミス。デバッグを上手になりたい。
tako.icon-の場所をリストに入れて前後の差が一番大きい物を出力するようにしたら、最後や最初に-がないものに対応できませんでした。-がないものを先に処理してSの両端に-をつけて対処しました。
TTT.icon "o" in S and "-" in Sを満たすときに連続するoの数の最大値を返す関数を呼び出しました。
まーす.icon何回もWA出た方は多分忘れものが多かったハズ(自分がそうだったWA×8回)。「-」が先頭にくる場合と「-」が後ろにくる場合、「-」のみ或いは「o」のみの場合にわけた。最後の条件に手こずったのと最初の方では「-ooo」のパターンしか考えていなかった。 4/26 12:00頃追記↓ まず最初に-或いはo のみで表される文字列Sを-1として出力し、あとは連続するoの数の最大値を出力
yuichang.icon指定された2つの文字がある場合はoが最大で何個連続したか。-が来た時に解を更新してたので-oooみたいな時にペナ。
TK.iconフラグを駆使して解いた。しかし、一回目にooo-はできるが-oooに対応できないかつ、重複カウントするプログラムでWA。同じ処理を逆順で行い、2回目で重複カウントしないように初期化とif文をelifにしてAC。
〇D問題
CarpDay.icon例のあのアルゴリズムのインタラクティブ版
Yuto.icon Cを通した時点で残り5分，問題を理解して少ししたらコンテスト終わった．全く方針が立たない．
Yuto.icon コンテスト後，解答見ずに解きなおしてみたら5分くらいで通せた．悔しい
tako.iconインタラクティブって何？ってなりましたが何とかなりました。二分探索で1と0の境目を探す感じでやりました。Dまで解けたのにUnrated悲しいです。
TTT.icon AC8個、WA13個でした。新しい出題形式でしたがジャッジを見る限り入力出力自体は上手くいっているようでよかったです。数字を愚直に1から順に聞いていました。N=2*10^5のとき聞く数字はどうやって決めていこうかなぁと考えたとき二分探索が頭に浮かびましたが、時間内に実装できませんでした。
まーす.icon見た感じむずそう(小並感)。私には無理そうなので触らないかな......。
yuichang.icon二分探索、それっぽく頑張ったがWA6。rightとleft逆だった><
おたふく.icon お風呂に入ってからD問題を見る。20回のアクセスのみで2*10^5の中から探し出すのは二分探索だろうと思い実装。思ったより簡単に実装できたので、CにこだわらずにDを見ておけば良かった。
TK.icon20回という回数で二分探索に気づき、実装。WAが数件出て結局何が原因かわからなかった
〇E問題
CarpDay.icon白を決めて他は黒という方針で実装したら，2/47だけWA！数値例1を基に反例考えて5分ぐらいで発見．確実性重視してコピペコードだけど無事AC．
Yuto.icon ぱっと見はDより簡単そう．
まーす.iconDとばしてEをメモろうとしたが、条件が意味不(焦ってるいたのもあるかも)だったので諦め。これも勉強会まで触らない......。
おたふく.icon 最短経路の問題なのでBFSだろうなと思い、実装してみた。白にしないと駄目な頂点の集合と、黒にしないと駄目な頂点の集合を管理し、条件を満たすかどうかを判定。コーナーケース? 的な感じでどういう時に条件を満たさないかを考えるのが難しかった。
TK.iconダイクストラとか使えそうかな？とか考えていました。Dを考えていたのであまり深く考察していません。
〇F問題
CarpDay.icon考えても方針すら分からず．Unrated確定して，モチベ↓↓ コンテスト終了前にGive Up．
Yuto.icon これ以降見てない
まーす.iconD,Eより希望あるかもと思ったのも束の間、これも条件ちゃんと理解していない。(今はGやってる)
〇G問題
まーす.iconとりあえずサンプルは全部ACでた。自分でサンプル作ってやってるが、どのパターンがWAなのかわからん泣......(見えざる敵(WA)との戦い)。
CarpDay.iconコンテスト後，貪欲法を思いついて（久しぶりに双方向リストなんぞを）実装する．サンプルはACだけど，他は半分ぐらいWAで諦める．ユーザ解説が分かりやすく，F問題より簡単．