ABC334 （2023/12/23）
〇A問題
Yuto.icon 場合分け
TK.iconスペルミスがないか注意しながら場合わけ
まーす.icon同上．TK.iconさん，コピペしたらその心配は無用！
tako.iconやる
TTT.iconCarpDay.iconおたふく.icon TK.iconさんと同じです.
Kaplam.icon眠すぎたのでコンテスト後にブラゲやりながらC++練習
〇B問題
Yuto.icon むずい．L以上で最初にAとの差のMOD Mが0になる場所と，R以下で最初にAとの差のMOD Mが0になる場所を探したかったんだけど，無理だった．何も分からんかったので，全探索コードをC++で提出したら1ケースだけTLE．高速化テク試しても無理だった．
ユーザー解説の$ \frac{L-A}{M} \leq k \leq \frac{R-A}{M} より，kの個数=\left\lfloor\frac{R-A}{M}\right\rfloor - \left\lceil\frac{L-A}{M}\right\rceil +1 としたら5WAでした．$ kの個数=\left\lfloor\frac{R-A}{M}\right\rfloor - \left\lfloor\frac{L-A - 1}{M}\right\rfloor だとACするけど，なにがダメなんでしょうか．よく分かりません．
Yuto.icon 原因判明．前者だと，浮動小数点数を経由するため，誤差が発生します．decimal.Decilalを使用することで，どちらの方法でもACできました．
CarpDay.icon割り算怖い((((；ﾟДﾟ))))
TK.icon範囲が決まっているタイプの倍数が何個あるか数える問題のノリ。範囲の境目に置くときだけ注意
まーす.icon一生BとCで沼ってた．WAケースはわかってたけど，全然思いつかなかった．
tako.iconちょっと難しかった。一番近い内側の木を考える
TTT.icon WA2つ消せなかったので飛ばしました. Ringoametanさんの解法が個人的にすごくスマートに感じました.
CarpDay.iconLとRからAを引いて単純化．LとRの符号によってややこしくなりそうなので，愚直に場合分け．境目の処理でよくWAするので，サンプル以外に自分で数値例作って確認してから投稿してAC．それでもドキドキした．
yan.icon本番中は細かいことはあまり考えずノートに図を描いてそれっぽい解法を見つけたからやってみたらAC. 本番の後 (R-L)//M+1 でも行けそうと思い実行したらWA. 考えてみると, これではAの位置によってはL~Rの間にない場合が存在するためだと気づいた.
Kaplam.iconLとRをAずつずらしてmで割ってってやると割り算の結果が負の数になった場合c++とpythonで切り捨て切り上げ処理が違うらしくてWA,正攻法じゃないと思いつつLとRにmod mの結果が変わらないように2 * 10^18ぐらい足して割り算の結果を正にしてAC
おたふく.icon TK.icon同様に範囲内に含まれるMの倍数の個数が何個で判定。
〇C問題
Yuto.icon むずい２．飛ばした
TK.icon前から順番に見ていく感じでいけそうな予感がしたため、とりあえずそれで提出。WAが６ぐらいだから反対からやったら行けるかと思い出すもWA4。捨てるタイミングを探索する必要がありそう。
tako.icon33-4(書きたいだけ)
Yuto.icon な阪関無(言いたいだけ)
まーす.iconKの偶奇で分けて実装したが，TK.iconさんと同じくWA4から改善出来ん．WAケースが全く思いつかないんだよな......．コンテスト後，D問題に飛ばした方がよかったと後悔．クリスマス前にレートが一気に下がる恐怖と戦わなければ......
まーす.iconレート マイナス25．耐えや耐え．CarpDay.iconお互い頑張ろう！
まーす.iconCarpDay.iconさん，Thank you!．結局，無くした靴下が奇数のときの処理だけを考えたらよくて，Aのどの要素を"はぶる"かがミソ！結論，"はぶる"Aの要素は，偶数番目(0-index)だから，CarpDay.iconさんの方法が使えるんですよね．勿論，ペアが作れるものは考えなくてよいということはコンテスト中に気づいていたので，そこは前提ね．
CarpDay.icon跳ばすべきだったが，数学の香りにつられて長居．入力例3でペアがあるものはペアにして，ペアがないものだけ考えればよい ことに気付く．2点間の距離の最大を削除すればよい，と考えて実装するも6WA．37分無駄にした．．コンテスト後，数直線上の点をつなぐ問題と考えることができることに気付き，前からつなぐパターンと後ろからつなぐパターンを記憶する方法を実装してAC．難しかった．
yan.icon偶数, 奇数に分けて考えた. 偶数の場合は隣り合う数同士の差をとる. 奇数は左右両方向で見ていき, 偶数でやったように差を見て, 片方がもう片方より小さければ小さい方をもう片方に近づけていき, 最終的には値の差が一番大きい位置を把握し, その値だけ取り除いた. WAだった.
Kaplam.iconkが偶数個の場合はなくなったのを前から2個ずつくっつける、奇数個の場合はどれを使わないかを決めて累積でどん
おたふく.icon コンテスト中では、片方失くした靴下の内隣り合う靴下しか選ぶ必要が無いことと失くしていない靴下をあえて分解して片方失くした靴下と合流させる必要が無いことまでは調べるも、なにか考え漏らしていることがありそうなので解説を見ずに考察してみる。揃っていない靴下の奇数番目のみ除外すれば良いと考察したが4WA...。偶数番目の靴下を除外すれば良い反例があるのか...?
〇D問題
Yuto.icon B, Cが無理過ぎて，見に来た．めっちゃ簡単．prefix_sum + bisect_rightやるだけ
TK.icontako.iconおたふく.icon同上。簡単
TTT.icon コンテスト終了15分後にACでした. 自力で解法思いついて二分探索のプログラム書けたので個人的には良しです.
CarpDay.iconC問題スキップして到着．簡単すぎて「実はC問題，簡単なのでは？」という疑念に付きまとわれる．
Kaplam.iconsortして累積して二分探索、lower/upper_boundてっきりpythonのbisectみたく添え字返すと思ってライブラリに入れてたのにアドレス出すのね
〇E問題
Yuto.icon 連結成分を数えて，MOD 998するだけ．UnionFindと逆元を知っていれば解ける．B, Cよりも簡単．コンテスト終了の3分前くらいにぎりぎりで通せて，めっちゃ気持良かった．
tako.icon同上。僕は34秒前でした。最後サンプルが全部1足りなかったので1足したら通った。ぎりぎりで通すの気持ち―！
TK.iconグラフとか盤面系が苦手意識あるから飛ばしたけど、最後の方に覗いて、UnionFind探索する点の個数分作れば行けるくねと思った。残り3分とかだったから実装まではしてない。
CarpDay.icon UnionFindで解ける！と頑張って残り5分ギリギリでAC！（と思ったら，もっとギリギリが2名いて ^^ ）
おたふく.icon 解法自体は思い付いていたがTLEになり大焦り。探索の必要が無い枝を丁寧に削り、無事AC。
〇F問題
TK.icon「CVRPだ！...C問題に帰ろ」て感じで見るだけ見た。
CarpDay.icon この問題は，巡回する順番決まっているよ～
Yuto.icon 問題だけ見に来た．ヒューリスティクスやりたくなるけど，TL2secで頂点数10^5だから厳しそう．
CarpDay.icon上のコメント見て問題確認．DPだと思ったけど，O(NK)が10^10になるから単純な方法では無理だね．．翌日，DPの推移を考えたらリスト中の最小値の計算と，リスト中の最古要素の削除ができれば実装できることに気付き，SortedListで実装してAC．kyopro_friendsさんの解説とほぼ同じやり方でした．その解説内にスライド最小値なる用語を発見．蟻本に載っているらしい．シンプルだけど知っていたら便利なテクニック．このサイト が分かりやすいです．