ABC287 (2023/01/28)
〇A問題
Yuto.icon S.count("For") > len(S)//2
TK.iconS.count("For") >= len(S) /2にしていてWAに。こうするならint(len(S)+1/2)だと思い、やってみるとサンプルが通らず。数も少ないのでForとAgainstの数を比較した。後から考えるとint(len(S) + 1/2)になっているのでint((len(S)+1)/2)じゃん...
CarpDay.icon愚直に確実に，両方ともcountしました．
TTT.icon "For"の数cnt > N-cntならYesと出力しました。
〇B問題
Yuto.icon s[-3:] in T
TK.iconSのうち、末尾がTに一致するものの個数でなく、Tのうち、Sの末尾と一致するものの個数を求めていた。その名残をそのまま改良して作成したため、もっと簡単にできた気がする。
CarpDay.icon2重ループで，Sの末尾3つとTのそれぞれを比較．Yuto.iconの方法がいいね．
TTT.icon リストTを重複なしのセットにしてから再度リスト化し、i外j内の2重ループでT( i ) == S( j )(3:)の個数を数えました。
〇C問題
Yuto.icon みんな大好きUnionFindで無向Graphの閉路検出と連結成分数を数えて判定する．問題文二つ目の条件「v[i]とv[i+1]は連結」については，vを任意に並び変えられるので気にしなくて良い．← 次数の判定が足りてない．
TK.iconUnionFindで連結成分の個数１かつ閉路がない場合で判定
Yuto.icon 私とTKの実装では解説に載っている最初のケースで不正解になります．ついに自分も嘘解法で通してしまった．．．
おたふく.iconAfterContestでその解法がはじかれます！！
Yuto.icon 誠に遺憾．．
CarpDay.icon枝数＝点数-1の条件ととグラフの次数の条件だけで判定してWA．．．2週連続，Ｄ・Ｅの後に戻り，やっと反例（非連結のケース）に気付き，UnionFind使って何とかAC．
おたふく.icon絶対UnionFindだと思ったのに、パスグラフであることの言い換えが思いつかず、DFSなど色々模索して沼。問題を飛ばすという思考が頭から消え去り、テンパり祭り。しょぼん
CarpDay.iconわかる！離脱決意直前，かなり焦りました！離脱しても，気になって次の問題集中できないし．．
TTT.icon グラフの連結成分が1個かつ閉路がない, すなわち根が1個でないならパスグラフ？と考えて色々ググりながらコーディングしていましたが、テストケースは1つしか通らず、できませんでした。
〇D問題
Yuto.icon 文字列アルゴリズム？知らない子ですねぇ... CarpDay.iconが本番中にD,Eを通していたところから予想すると両方 #文字列アルゴリズム で解けるのかな？ TK.icon愚直にループすると10^10だからループ一回でうまくできる方法があるのかと考えたが思いつかなかった。Tが固定の文字列であることや？が任意の文字に置き換えられるので？の位置をうまく覚えておくと行けるのかなどいろいろ考えたが思いつかなかった。
CarpDay.icon 例1でハンドシミュレーションして，思いついたアルゴリズムでAC．解説の想定解法でした．
TTT.icon 少し覗いてからCに取り組みました。問題の意味がイマイチ理解できませんでした。
〇E問題
Yuto.icon Dが無理なのでEを見る．君も文字列アルゴリズムか...
TK.iconDを考えているうちに少しのぞいたが、Dにかけていた時間を考えると浮気しないほうが良さそうと思いDに戻った。
CarpDay.icon 例2でハンドシミュレーションして，思いついたシンプルなアルゴリズムで通った．ラッキー．解説見たら，別解1の方法と同じでした．
〇F問題
Yuto.icon DもEも無理だったのでFまで見た．Graphだし行けるかな？と思ったけど普通に難しかった．木DP的な感じで上手いことやればできるのかな？
TK.icon以降未確認
CarpDay.iconDPと踏んで考えるが時間切れ．解説見て木DPを学習．知らない方のACコード見て解法理解しました．
〇G問題
CarpDay.iconコンテスト後に覗く．クエリだからセグ木？解法分からず，早々に解説チラ見して概要理解．理解不足と実装に苦労してやっとAC．
Yuto.icon セグ木ライブラリのverifyで解いてみた．ライブラリを作るところで力尽きたので問題を解く部分は殆どカンニングした．クエリ先読みして座標圧縮してセグ木二つ使って頑張ると解けるけど流石G，とっても難しい．セグメント木を使うと分かっていても，使い方が難しい．まあセグメント木については大分理解が進んだから良しとしよう