ABC311 （2023/07/22）
〇A問題
Yuto.icon a b cの順に並んでないといけないと誤読していた
yuichang.iconsetのsize
Kaplam.iconA,B,Cそれぞれ出てきたかを記録して全部出てきたらi+1をprint、マウス調子悪くて左右クリック反転させてたらコピペ失敗して少し大変だった 追記：茶色になりました\(*‘ω‘ *)/
CarpDay.iconA問題から辞書使って，A・B・Cの個数をカウント．全て1以上になったら出力．setが正解だね．なるほど．
tako.iconA, B, Cの個数をそれぞれカウント
TK.iconABCの順じゃないといけないと勘違い、サンプルと違う答え出て焦る
まーす.iconset()でA,B,Cがすべて入るまでカウント
おたふく.icon setの長さが3になるまでカウントする. vscodeが動作がおかしく、時間を溶かす.
〇B問題
Yuto.icon 左端と右端を全探索する．左端と右端をrange(n)で回していてバグっていることに気付かず，時間を溶かす．バカ
Yuto.icon 最近マイブームのRustでランレングス圧縮して解いてみた．Rust楽しい．
yuichang.icon縦に見てやる
Kaplam.icon日付を前から見て行って全員休みだったらansnを１足す、ans<ansnだったらans = ansnみたいな
CarpDay.icon日付ごとにsetを取って，×が含まれない集合が何回続くかカウント
tako.icon最初に1からNまでが入ったsetを作っておいてxが出てきたらsetから消去。最後にリストに変換してソートして前後の差が一番大きいところを出力
TK.icon添え字を調整して縦にループを回して、全部oのところをカウント。連続している限り加算して、連続が切れたら候補に追加
まーす.iconKaplam.iconさんと同じ
おたふく.icon シンプルに全探索して、どれだけ暇な日が連続しているか管理するためにoが来るたびにtmpを加算して、xが来るとtmpを0のリセット. そして、毎回ans = max(ans, tmp)で更新する. デバッグ用のprintを消したときに、print以外も間違えて消してしまっておりWA.
〇C問題
Yuto.icon 有向Graphの連結成分なので，脳死で強連結成分分解のライブラリをコピペ．ライブラリ整備してて良かったね．
Yuto.icon 解説に載ってる「Functional Graph」って聞いたことあるけど知らんかった．これのことなんか．
yuichang.icon強連結成分分解してdfsで方向を考慮して色々考えて時間ロス。絶対もっと簡単にできる。Functional Graph すげー
Kaplam.iconwhile文で点1から探索して一度出てきた数字をsetに入れて、2回目の数字が出たらそこから辿りなおす、0オリジンと1オリジンで結構苦戦した...ICPCの反省活かしたいけど0オリジンで慣れてるから難しい...
CarpDay.iconどの点から探索しても必ず閉路ができるので，点1から探索して，経路を保存．探索済みの点が見つかったら探索済みの点から最後の点までの経路を出力．
まーす.iconなるほど。「すべての頂点から少なくとも１つの別の頂点に対して有向辺が出てるというのがミソ」だったのか......。これは良問だ......。
CarpDay.iconどの点からも1点別の点に行くことができて，点の数が有限，なのがミソですね．
tako.icon強連結成分分解してみました。
TK.icondfsで経路を拾いながら進めていく。一度行った点に帰ってきたら閉路になっているからそこから経路をたどるという方法でやっていたが、全然できていない。実装力...
おたふく.icon 強連結成分分解でいけるやんと思い、自身のライブラリを参照. しかし、頂点数を出力し忘れてWA1件. 有向辺の順番を考慮しないとならないことに気付いておらずWA1件. そして、時間が大丈夫か不安だったが、強連結成分をもう一度dfsで元のグラフから探索して、要素の順番を考慮した強連結成分に復元し、無事時間も間に合いAC. SCC(強連結成分分解)のライブラリを改良して、実行時間を半分にすることが出来た.
〇D問題
Yuto.icon 座標と向きでBFSしたけど，なんかバグってる．やりたいことは合ってるはず．デバッグしてたらコンテスト終わった．くやしすぎる
Yuto.icon コンテスト後，頭を冷やしてデバッグしたらAC．無駄にきれいに書こうとして，条件式が間違ってた．．
yuichang.iconbfsした。配列のsizeをn,nにするミス。頂点見たか否かをmapで持ってたらTLE。多次元配列にして終了1分後にAC。悔しすぎる
Yuto.icon std::map（ハッシュテーブル）だと，衝突しないようなハッシュを生成する部分が重いんですかね？
yuichang.iconmapは平衡二分木？？の一種でsorted_setのように保管されるため、値の挿入にlogNかかって通ったマスと止まったマスを別々のmapで管理すると流石に重すぎるみたいです。ハッシュを使ったsortされないunorderd_mapもありますが、そちらはpair<int,int>をキーにできないため、、
Yuto.icon あ、勘違いしてました。std::mapはsortedだから平衡二分木（ 赤黒木）ですね。C++でもlog付くとだめなんか…
Yuto.icon yuichang.icon のTLEコードをunordered_*に変えて見たけどやっぱりTLEだったので，orderedだからというよりは，アルゴリズムが間違ってそう（無駄な探索をしている？）
yuichang.iconnが小さいときにidを作成するテク凄いです。queueに停止位置を追加する瞬間に停止位置のフラグを立てるとTLEがなくなりました。コンテスト中は管理方法を多次元配列に変えるとき無意識にいじってたみたいです。本当にありがとうざいます🙇♂
Kaplam.icon踏んだ氷のマスを入れるlistと探索済みかどうかを管理するlist合わせて3個作って再帰で2,2から上下左右から行ける所まで行って氷を踏んで最後に踏んだマスを数える、2,2をすでに踏んでいる判定にするのを忘れてWA、あと少しでCarpDay.iconに勝てたのに惜しい...(こおりのぬけみちですね)
CarpDay.iconDFSの変形．上下左右が氷ならその方向へ岩にぶつかるまで移動．初めて通過した箇所があればカウント．岩で止まった箇所は記憶しておいて，初めて止まった場所なら，その場所からまた探索を開始．
tako.iconDFSでやってみたけどサンプルすら通りませんでした。
まーす.iconDFSの方針はたったが実装出来ずじまい。
TK.iconCが行き詰って以降の問題も見たが、今回グリッド系の問題多くね？普通に苦手意識あるから逃げ道がなかった。
おたふく.icon BFSで実装. TLE8件に阻まれた. 何故TLEか分からない. visitedをTrueにするタイミングを変更しただけで圧倒的に実行時間が速くなった...。queに取り出してから、止まったことがある判定にしてしまうと、queに複数同じマスが入ってしまうから実行時間が圧倒的に遅いのか.
〇E問題
Yuto.icon 見てない
CarpDay.icon$ (i, j, n)の$ n=1, 2, ..と大きくして，正方形ができる$ (i, j)の集合を保持する方法で実装．穴がある例題には強いけど，サイズが小さく穴が少ない問題では時間かかりすぎ．案の定，例題4がローカルでも答え出ず．記念に提出しておきました．コンテスト翌日まで考えたけど思いつかず，解説の最初の方みたらあれか！あとは自分で考えて実装してAC．左上を動かすことに固執しすぎました．反省．
Kaplam.iconCarpDay.iconさんと大体同じ、こちらも例題4が出ずAC8TLE18
CarpDay.icon茶色コーダー，おめでとう！
Kaplam.iconありがとうございます！！
〇F問題
CarpDay.iconE問題に詰まって覗いたが，もっと難しそうなグリッド問題だったので，E問題に戻る．コンテスト翌日，E問題ACのあとで1日考えるもGiveUp．解説も当初は理解できず．ユーザ解説でやっと意味わかる（←今ここ）