ABC352 （2024/05/04）
〇A問題
まーす.iconX <= Z <= YかY <= Z <= Xを満たしていれば，Yes．
Kaplam.icon大きいか小さいかみる
TTT.icon まーす.iconさんと同じです．
tako.icon 以下同文
yuichang.iconswapしてあげる
kakip.icon同じくスワップ
おたふく.icon swapしてrange。
CarpDay.icon Kaplam.iconさんと同じかな？場合分け．
〇B問題
Kaplam.icon前から見ていく、なんかこの間もほぼ同じ問題あった気がする
まーす.icon尺取り法みたいなやつ．
tako.icon 右に同じ
TTT.icon 上に同じくです．
yuichang.icon 今どこまでいったかを持つ
kakip.icon同じです
おたふく.icon Sのindexを別で管理。
CarpDay.icon同じく尺取り法の要領．
〇C問題
Kaplam.icon久しぶりに†zip sort†した(添え字付きソートで首と頭の差が小さい方から積んでいったけどそこまで細かくやらなくてよかったね)
TTT.icon face[i] = B[i] - A[i]として顔の長さを記録していき，print(sum(B) + max(face))としました．
まーす.iconTTT.icon さんと同じ．indexを記録して，そこだけ別処理を行ったので，コードは気持ち悪い．１回目，提出したときにWAケースあると気づき1ペナ．
tako.icon 全探索みたいな
yuichang.icon片側全探索
kakip.iconTTT.icon さんと同じ
おたふく.icon てっぺんより下の順番は高さに影響が無いので、てっぺんの全探索。
CarpDay.icon TTT.icon さんkakip.iconさんと同じ
〇D問題
Kaplam.iconheapq2個作って区間内の最大値と最小値とって引く C++のset推奨なんだろうなーと思いながら解いてたけどPythonにもいつの間にかSorted Setなるものが追加されてたのね、しらそん
tako.icon 久々にセグ木使えてうれしいが細かいミスが目立つ
TTT.icon 長さKの区間を右にシフトしていく際の区間内の最大値と最小値の更新の仕方が分からず実装しきれませんでした．
まーす.iconP_invをPのindexと値を入れ換えたもの(つまり，逆関数のようなもの)として，SortedSetをうまく使って幅がKのP_inv[-1] - P_inv[0]の最小値を求めていった．最初はSegTreeを考えていたがやっぱり慣れていないことをするもんじゃないな......
yuichang.icon index持って尺取った。発想がやばい
kakip.iconC++のset使った
おたふく.icon 連続するK個の正整数列の全探索。SortedSetを利用して、正整数列のそれぞれの値をそのindexでソートしたものを作成する。その際、[a, a + K - 1] -> [a + 1, a + K]のとき、SortedSet内はaが削除され、a + Kが追加されるだけなので、今回の解法では計算量がO(NlogN)で済む。
CarpDay.icon スライド最小値で実装するが，うる覚えで煮詰まる．オーバースペックかな？と思いつつ，min用とmax用のセグ木2本で実装．SortedSet，すっかり忘れていた．反省．
〇E問題
Kaplam.iconUnionFindとクラスカル法、解ける問題だったのに普遍的なWAケースに40分気付かずようやく気付いて残り2分、最近がばすぎ_(:3」∠)_
tako.iconわからん
Yuto.icon |E|がでかすぎるので，Eを陽に持てない．与えられるS_iが完全グラフであることを利用すると，良い感じにできる．RustでUFのライブラリ整備してなかったので頑張って書いて，AC！と思ったらコンテスト10分前に終わってた．悲しい．．．
yuichang.icon 最小全域木を重複なくして作る
まーす.icon問題文をみて，目が痛くなったのでFに逃げる......．そして，Fに撃沈する．
kakip.iconコストが低い順に貪欲に繋げた。unionfindも使う
おたふく.icon クラスカル法。
CarpDay.icon 多分kakip.iconと同じ．２点以上の連結成分間をつなぐケースを失念してWA．
〇F問題
まーす.icon解の候補を絞る問題なんだがなぁ......．こういう問題っていつも指針が立たないから困る．
kakip.iconわかったかもだけど実装できない 解説と違うから間違ってるかも ナンプレみたいに各人のありえない順位を埋めていけばいけるかもO(N^2*2^N)、いけないかも 実装がめんどいのでやらない z3とかいう数独ソルバーを使った提出があったのでたぶんできる
CarpDay.icon 最大流に帰着できないかな？って考えているうちに時間切れ．