ABC355 （2024/05/25）
〇A問題
まーす.icon差集合．
Kaplam.icon私たちのScrapboxを返せ(2024年5月21日よりサービス名を「Scrapbox」から「Cosense」に変更いたしました。)
tako.icon↑名前変わって草
CarpDay.icon AとBを集合にして，大きさ1なら-1，それ以外は1～3までループして集合に入っていないのを見つける
yuichang.icon a!=bなら6-(a+b)
〇B問題
Kaplam.icon愚直に
tako.icon AだけじゃなくBも連続してたらと思っててペナ。
まーす.iconCという配列作ってCをsortして，Cを順番に見ていく．flagで連続かどうかは管理．
CarpDay.icon (値, リスト名)というタプルをリストAとBに対して作って，連結＋ソート．前から順にチェック．
yuichang.iconやる。iとjでループさせたのにj使わなくてペナ
〇C問題
Kaplam.icon縦と横はdict、斜めは2個のlistで、1個len()でくくり忘れてて1WA
tako.icon全部dictでやった
まーす.icondictとsetでBINGOかどうかを管理．対角成分の集合でやらかし．
CarpDay.icon 行合計，列合計，斜め合計のリスト作って，素直にカウント．「同じ数字が出ない」で助かった．
yuichang.icon どこに貢献するか判定
〇D問題
Kaplam.iconにぶたんして自分より小さく終わってるのと自分より大きく始まってるのの数を引く、こんがらがって時間かかっちゃった
tako.icon lでソート、過去に今見ているlより大きいrがあればその個数を足す
まーす.iconlとrをtupleで受け取りそれのリストlrを考え，lrをsortして後はheapの出番．1ペナは，C問題の内容を間違えてこっちに提出したから...…
CarpDay.icon 制限時間3秒にやられた．変に難しく考えて，座標圧縮したり，セグ木使ったりで迷走．20分ぐらいで諦める．コンテスト終了後，他の皆さんが解いているのを見て落ち着いて考える．多分tako.iconと似た方法をheapqで実装してAC．うーん．
yuichang.icon イベントソート、処理を行う場所、入れるor出すを持って場所に対してソート
〇E問題
Kaplam.iconこの間似たようなのあったみたく2^nで飛ばしていったけどWA,インタラクティブってやり方間違えたら基本全部TLEになるものだと思ってたけどprint(内容,flush = True)してないだけだった(合ってるはずなのに全TLEで不思議に思って過去のABCのインタラクティブの他の人のpythonコード見て気付いた)
tako.icon同上
まーす.iconインタラクティブな問題は食わず嫌いなんよな……
CarpDay.icon D無理でもEが解ければいいや，と挑むもWA地獄から逃れられず時間切れ．確かに似たのあったよね．そのときのkakip.iconさんの方法を思い出して，実装したつもりなのに，どこが悪いんだろう．．レート33ポイントダウン(x x)
CarpDay.icon おっしゃる通りです．ABC349Dと同じパターンで解いたらNG，ということですね．諦めて解説見て，やっと気づきました...
まーす.iconトラップすぎる......
〇F問題
yuichang.icon最小全域木（MST)を最初に作る。クエリが来たらMSTに使っている辺の中で最大のものより小さい重みの辺が来たら採用する。更新の仕方としては現在MSTに使っている辺は全て必要不可欠であるのが前提にある。辺を一本切るとグラフが2個になるので、クエリで来た2つのノードから出てる辺の中で一番重みが大きいものを削除して今来た辺を貼り直せばグラフはMSTになるはず。この方法で良いと思ったがサンプル1しか通らず残りはRE。各ノードに対して｛重み、行く先｝を持ったsorted_multisetを持っている、計算量、メモリ的には問題ないと思うがわからない
CarpDay.icon 点が①～④で，初期MSTを構成する枝が次の3本：①－②（重さ2），②ー③（重さ10），③ー④（重さ2）とします．クエリで①－④（重さ1）が入ったら，削除する枝は何でしょうか！？
yuichang.icon 削除するべきは重さ10の辺ですね、、ありがとうございます🙇♂️