ABC302 (2023/05/20)
〇A問題
TTT.icon A%B==0ならA//B、そうでないならA//B+1を出力しました。
おたふく.icon 以前に解いたユークリッドの互除法同様、何回引いたかは割り算で表現して計算時間の短縮を図る。その後、AをBで割った余りが0ならばもう1回余計に引く必要がある
Yuto.icon a % bならmax(1, a // b)，それ以外ならceil(a / b)を出力したけど2WA．なんで？？？？？？
CarpDay.icon割り算による計算誤差？
Yuto.icon コメントありがとうございます．ご指摘の通り，誤差が原因でした．ceil(a / b)とした時にfloatを経由するのがまずいです．a // bの整数除算のみを使用するか，decimal.Decimalクラスを利用することで解決しました．
tako.iconCarpDay.icon TTT.iconさんと同じです。
yuichang.icon(a+b-1)/bで切り上げができます。pythonだと(a+b-1)//b。CarpDay.iconいいね！
TK.icon商を出力。割り切れてなかったら＋１して出力
〇B問題
TTT.icon 配列外参照に気をつけながら、縦横斜めの末尾がsnukeの"e"であることを確認し、そこからk,u,nの順に合っているか見る、というようにしました。おしりから見る必要もなかったし、プログラムも愚直な探索で冗長になったので反省しています。時間内にACをもらえてよかったです。
おたふく.icon 実装に少し苦戦。まず最初にsを見つけてから、8近傍からnを探す。その後、見つけた向きにu、k、eを探す。配列外参照を起こし、一度だけRE。
Yuto.icon やるだけやんと思いながら実装したら8WA．なんで？？？？？？？？？？？？？？？？？？？？？？？
CarpDay.icon8方向調べる必要がありますよ．
Yuto.icon 本当ですね．なぜか6近傍しか見ていませんでした．．．
yuichang.icondx,dyを持つ。配列外参照に気をつける
tako.icon多分おたふく.iconさんと同じです。
CarpDay.iconsすら見つけない方法で，愚直に実装．多分yuichang.iconと同じ
TK.iconｓを見つけてから愚直に探す。ＨとＷを逆にかいていてＷＡ
〇C問題
Yuto.icon A, B無理だったのでCに来た．itertools.permutations
yuichang.iconC++には順列を列挙してくれるnext_permutationがある。ただ、フラグの挿入位置を間違えて2ペナ。
おたふく.icon 実装にとても苦戦。最初は辞書順にソートするだけで解けるのでは？と思ったが考えが足りないことに気付き、一旦D問題へ進む。解き終えてからもう一度取り組み、1文字だけ変更すれば一致させることのできる文字列同士を無向グラフのようにdictで計算。そこから全点を始点としてDFS。全ての文字列を辿ってDFSを終えられたらYes、終えられなかったらNoと頑張った。
tako.icon文字列の個数が最大でも8個しかないので全探索で1文字違いの文字列のペアを記憶。記憶したペアでグラフを作ってBFSして結果から適当に出力しました。今思えばDFSのほうが良かった気もしますが手元になかったので。
CarpDay.icon 各文字列をノードとし，2つの文字列が1文字違いならエッジを引く無向グラフを考えると，「一筆書きできるか？」という問題になり，グラフ理論の用語でいえば「オイラーグラフかどうか」を判定すれば良い．UnionFindで連結性確認して，各ノードの次数調べて，オイラーグラフの判定して完璧！と思ったらずっと8WAから抜けられず．苦渋ながらD問題へ．ラスト13分で戻り，問題熟読．サイズが異様に小さいのでYuto.iconと同じく itertools.permutationsで実装したら残り3分でAC！何でオイラーだとNGなのか考えます．．．
オイラーグラフではなく，ハミルトングラフの間違いでした．．．中途半端なグラフ理論の知識で自己陶酔したのが原因でした．恥ずかしい．．．
おたふく.iconとtako.iconの方法はグラフの連結性チェックなので，代わりにUnionFindを使った方法でもACでした！でも「グラフが連結ならば，オイラー路が存在する」は証明されていない（はず）だけど，ネットで反例が見つからず．命題成立するのか，しないのか，気になります．
おたふく.icon グラフが連結でも4頂点の完全グラフならばオイラー路は存在しないのでは？
CarpDay.iconごめんなさい！「オイラー路」ではなく「ハミルトン路」でした！
CarpDay.iconグラフが連結でも，ハミルトン路がない例がありました！abc, xbc, ayc, abzでお試しください！After Contestデータも追加されました！！
おたふく.icon せっかくのUnionFindチャンスを気付けなかったのが悔しいです。
TK.iconすべてではなく条件を満たすものが存在すると勘違い。条件を満たすものを整理して、ＤＦＳすれば良かった。後から出します
〇D問題
Yuto.icon 半分全列挙？的な感じでいけるかなと思ってダメ元で提出したらAC．AB解けてないのにCD解けたの意味分からん
yuichang.iconAを決めてBを二分探索。10WAが出た。何故？？イテレーター（pythonにもある？)を後置デクリメントしてたので、入ってほしい値が変数に入っていなかった。auto it2 = it--;だとit2にitの値が入る。
おたふく.icon AとBをソートして、普通にfor文でAの値を回す。そしてAの値がaの時にi = bisect.bisect(B, a+D)として、a + DをBの中に右から見て何番目に挿入できるかを求める。そこでi - 1番目のBの値を見て、aとの差がDより小さいならそれがaの時の価値の最大値となる。そして、最終的に最大値がいくらか求める。追記 : 少し条件をミスしていましたが、たまたま解答が通ってしまっている部分がありました。
tako.iconおそらくおたふく.iconさんと同じです。RatedでDまで解けたの久しぶりなんでうれしいです。
CarpDay.iconおそらくおたふく.iconさんと同じです．C問題より簡単（？）
TK.iconとりあえず愚直に出してみた。尺取り法的な感じでＡとＢのインデックスを進めれば行けそうとか考えてた。Ｃ解くかＤ解くか悩んで結局どっちも中途半端で解けていない。
〇E問題
Yuto.icon 繋げるだけならUnionFindで解けそうだけど，切り離すの無理．クエリ先読みするか，データ構造を工夫するのか，どうしよう．．と思っていたらコンテストが終わりました．
tako.iconYuto.iconさんと同じく、UinonFindで行けるやん！と思って実装してたら切り離しがあって無理でした。愚直(?)に実装したものの9TLEでした。
おたふく.icon 5分程だけ問題を見て、UnionFindやん！...以下同文。後日問題を考えてみると、この実装だと計算時間はそこまで大きくならないような気がするが、計算時間の計算がよく分からないのでとりあえずTLE覚悟で提出すると無事AC。恐らくCarpDay.iconと同様の方針だと思われる。
CarpDay.icon 切り離す処理があるので単純な方法だとO(NQ)で無理，と思い一旦はC問題に戻る．C問題の謎が解けずまた戻る．よく読むとタイプ1のクエリでは1本ずつしか枝が増えないので，タイプ2で削除される枝も対して多くないことに気付き，愚直に実装したらAC.喜びつつ，残り時間13分でC問題に戻る．
〇F問題
Yuto.icon これ以降見てない
CarpDay.icon C問題とE問題が分からず一度覗く．問題Cのように各集合をノードとして，2つの集合が共通集合を持てば枝を張り，始点ノードと1を含む集合ノードに枝，終点ノードと終点を含む集合ノードに枝を張ってできた無向グラフにおいて，始点からBFSして終点までの距離を求めればいいはず．でも，集合が2×10^5存在するので，2つの集合のペアを作る段階でTLEしそう，と思って諦める．翌日試行錯誤してもWAから逃れられず解説を見る．超頂点というアイデア，いろいろ応用効きそう！実は発想おしかった？
おたふく.icon 最初の発想として、CarpDay.icon同様に無向グラフを作成し、BFSでは？と思ったが計算量を減らす工夫が思い付かず、解説を覗き超頂点という発想を知る。また、解法自体は理解できたがTLEに苦しみ、多点BFSというものを発見して無事AC。少し疑問なのが、整数1や整数Mがどの集合にも含まれていない場合の問題を考慮する必要があるのかないのか。
CarpDay.icon整数1を始点，整数Mを終点として例の処理を行うので，例外処理は不要ですよ～