ABC282 (2022/12/17)
〇A問題
TTT.icon S="ABC...Z"としてS(:K)を出力しましたが、元のSの並びが...LNMO...と間違えてて1度WA出してしまいました。アルファベットを覚えるところから出直してきます。
Yuto.icon chr(ord(A)+i)を順番に出力する
解説見た．string.ascii_xxというのがあるんですね．便利．たまに欲しい時があるので覚えておきます
sakana.icona=65で置いてchr(a)としてaをｎ回インクリメントした。
CarpDay.icon一番上の方と同じ方法．スペルミスしないように，ゆっくり入力しました．それでもACになるかドキドキでした．
TK.icon文字列を準備して出力した。スペルミスがないか注意深く確認した。
〇B問題
Yuto.icon itertools.combinationsは便利ですね
TTT.icon 前回同様Cの方が問題文の理解が早かったのでこちらを後で解きました。すべてのペアの数からx-xが一つでも含まれているペアの数を引きました。orの否定を見るほうが簡単だと気づいたので。
sakana.iconfor文使い慣れてなくて上手く判定できず、結局whileで回した。比較がほぼ３重ループなので数が多いとできなかったかも。
CarpDay.icon素直に3重ループ．未だitertools.combinations使いこなせていないので，この機に覚えようかな．
TK.icon三重ループになるなぁ。ー＞制約を確認ー＞回せる！ ということで3重ループで条件を満たすか確認していった
〇C問題
Yuto.icon "が閉じているかフラグを持ちつつ前から順に見ていくだけ．Bよりも簡単．若干のICPCっぽさを感じた
sakana.icon読み込んだ時点で「”」の個数が偶数だったら枠外というような判定した。
TTT.icon sakanaさんに同じくです。1度TLEになりましたが、複数のif文をandにしてまとめて、for文の中で随時結果の文字列を1文字ずつ表示したら通りました。
CarpDay.iconやり方は他の方と同じ．プログラムの下の方にB問題の解出力のprint(ans)が残っていたのに気付かず， joinする前のリストが最後に表示され，それがjoinした結果の出力と勘違い．しばらくjoinについて調べたりして手間取る．作業する前には，作業場を綺麗にすること大切．
TK.icon文字列をリストにしてfor文で回して、「"」がくるごとにフラグを更新していった
〇D問題
Yuto.icon 愚直にやるなら$ {}_{n}C_{2} - m本の辺を全て考えないとだめなので$ n=10^5だと$ O(10^{10})くらいになって無理．こういう時は全体から余事象を引くと上手くいく．余事象は各ノードと同じグループに繋ぐ辺の本数と，元から繋がっている辺の本数なので，これを引いたものをansに足していく．二部グラフの判定はやったこと無くてぐぐったらBFS/DFSが出てきたけど，UnionFind使った．
sakana.iconできなかった。dictionaryに登録していって、条件の判定するのかなと思ったけどそもそも二部グラフをあまり理解していなかった。またやってみます。
TTT.icon グラフ理論の授業で見たことあるグラフでした。せっかくとってるので、自力で解けるように頑張ってみます。時間内にはノートに書いて考えただけでコーディングはしていません。
CarpDay.icon連結成分の判定はUnionFindが簡単だけど，二部グラフの判定はBFS/DFSが簡単だなぁ，と少し迷って後者で実装．複数成分のときの解答を誤って考えていてWA．成分数が2のときはACだけど3以上のときはWAだった．連結数3以上に対応する方法は余事象にすれば良いことにやっと気付いてAC．確かに余事象使うなら，最初からUnionFindが正解だね．
TK.icon安直に考えると存在しない辺を追加して二部グラフであるかどうかを判定すると思ったが、ラベル付けしていく判定法や奇数サイクルを持たないなど、自分の知っている判定法だとサイズが大きいとTLEになることがわかりきっていた。グラフ問題も対応できるように頑張りたい。
〇E問題
Yuto.icon dpかな？と思ったけど，二つ引く遷移が上手く設計出来なかった．前回の勉強会でDPやったばかりだったので通したかった(というか本当にDPで解けるのか？)
解説見たら最小全域木とか書いてた．なにがどうなったら全域木が出てくるの．．？
CarpDay.icon2つの球x, yに対して得点が定まるので，点xと点yの距離が得点になるTSP？bitDPで解けるんじゃね？と実装．入力例1はACだったが，入力例2で答えが出力されない．．．bitDPの問題見たら，N<=15程度．今回は500．ダメだ．．きっとDPだから解説見ないで頑張ろう！と思ったら，ネタバレが上に書いてあった．．次からは書き込みは終わった後にします(^^) UnionFindで極大木を実装してAC．UnionFindすごいなぁ．
Yuto.iconネタバレしてしまって申し訳ないです．今後こうならないために，目隠しコマンドをScrapBoxに追加しておきました．角括弧で囲んで先頭に！を付けると目隠しになるので，今後はネタバレ要素は目隠しで記述します
CarpDay.icon新機能の追加，ありがとう．時間が経てばネタバレではないので，どこまでがネタバレか難しいところですね．
〇F問題
Yuto.icon 一応目は通したけど，何をしたらいいのか全く方針が立たない．Nが小さかったら，あり得る閉区間を全て登録しておけば良いかもしれんけど，N=4000とか微妙に大きいので無理そう．というかF問題でそんなに単純なものは無さそう
解説見た．Sparse Tableとか見たことないです
CarpDay.iconコンテスト中は「インタラクティブ」の理解に時間がかかりそうだったので，すぐに却下して終了後にじっくり考察．セグメント木でできそうかと思ったけど，選択する区間が2つのみなので単純には無理なことに気付く．セグメント木の変形で検討するも，汎用的なアルゴリズムにできずギブアップ．解説見て Sparse Tableなるデータ構造を知る．その構造を知っているかどうか，という問題ですね．