ABC369 （2024/08/31）
〇A問題
まーす.iconA = Bと(A - B) % 2 == 1と(A - B) % 2 == 0の３つの場合で条件分岐．vキーと3キーの反応が悪い......
kakip.icon適当に範囲とってソートして判定
CarpDay.iconまーす.iconと同じ．場合分けしたら，3パターンしかなかった．kakip.iconさんの発想，すごいなぁ．．B問題・A問題解いた後で順位表見たら，kakip.iconさんがD問題まで終わっててビビった！
yuichang.icon 場合分け。absつけてなくてペナ。overflow対策で#define int long longをテンプレートに追加した（闇落ち
CarpDay.iconC++とPythonだと剰余残の仕様が異なるから要注意だね．
Kaplam.icon a<=bにして適当な範囲で等差数列なってるか確認(昨日は徹夜明けだったので参加せず、8月のあれこれ片付いたので次回から久しぶりにratedに出来るかも)
〇B問題
kakip.icon左手、右手ごとに差とるだけ
まーす.iconkakip.iconさんと同じ．最初，問題を読み間違えてた．
CarpDay.icon同じく問題読み間違えて，どちらの手でもよいのかと思った．初期状態を全列挙してDP？と思ってよく問題見たら，左右指定されてるじゃん！
yuichang.icon 両手の位置を全探索。シミュレーション
Kaplam.iconやるだけ、この人人差し指だけで演奏してるのかしら、手の場所から左右2マスまでは手動かさなくても演奏できる～とかにしたら面白い問題作れそう
〇C問題
kakip.iconA[i], A[i+1]の差とったやつを連長圧縮して計算
CarpDay.icon run_length（more-itertools）使いこなしている！すごい！
まーす.icon尺取りと似たやつ．
CarpDay.icon長さ１と２は確定なので，長さ3以上の等差数列をチェック．最大どの長さがいくつあるかカウントする．長さk（≧3）の等差数列の部分数列で，長さ3以上となるのは(k-2)(k-1)//2個存在することを計算で示す．
yuichang.icon 何回等差数列が連続しているのかを記録、連続しなくなったらansに組み合わせ数を足す
Kaplam.icon多分みんなと一緒
〇D問題
kakip.icon偶奇ごとに分けてdpやる
まーす.icon簡単なDP．初心者におすすめ．indexのミスで時間食った-
CarpDay.iconお二人と同様．いい勉強になる問題．
yuichang.icon dp -> i番目まで見た。勝数のmod2が0,1の時のmax経験値
Kaplam.iconやるだけ、早解き回だったのかな
〇E問題
まーす.iconむずそう...….．以降，F問題へ．
kakip.iconワーシャルフロイド法で各島間の最短距離を求めておいて、クエリごとに順列全探索。辺が指定されているので、その両側を考慮するのがめんどい
CarpDay.icon各クエリでO(M)でも無理そう．全ての橋通る？もうさっぱりわからず，その後は解けそう（勘違いでしたが）だったF問題に注力．
CarpDay.iconコンテスト終了後に考えるも方法がさっぱり思いつかず，最適化問題として定式化してpulpで解くが，部分巡回路が発生してWA．諦めてお二人の伏字を見てやっと理解してAC．Kが小さいのがヒントだろうな，とは思ったけど，全く思いつきませんでした．
yuichang.icon 全頂点対最短経路をワーシャルフロイドで求めて使う橋の順番を順列全探索して、u側から使うかv側から使うかをbit全探索する。デバッグが終わらず、、
Kaplam.icon気が向いたら見る、前回のEやたらわかりにくいと思ったらdif2140とかだったのね
〇F問題
まーす.iconR成分とC成分に分けてカウント．説明がむずいが，defaultdict(list)使って，R[r]:r行目にあるコインの座標を記録するlist (sort済み), C[c]:c列目にあるコインの座標を記録するlist (sort済み) として，bisect使って条件分岐すれば出来そう．私はAC出してないが......-
まーす.iconTLE出てたから無理っぽい......
CarpDay.icon飲み会中止？
まーす.icon残念ながら......お酒入っていないので，ratedにしました笑
CarpDay.icon(^^)v
まーす.icon帰宅してすぐに準備して，ABCしたので腹ペコです......
kakip.icon遅延セグ木とかdpとか考えたけどわからない。r+cの昇順にソートしていい感じのデータ構造でなんかすればできそう、と思ったけど解説見る限り無理そう
CarpDay.icon$ N\leq 2\times 10^5を$ HW\leq 2\times 10^5と読み間違える．単純にDPで解けると判断するもTLE（当たり前だけど気付かず）．順路の保持に時間がかかると判断して，DP終了後に順路を復元する方法に変えるもTLE．コンテスト終了後に読み間違いに気付く
CarpDay.icon入力例3の図をExcelで作って思案．各コインiに対してv(i): コインiの左上方向にあるコインの個数+1なるvを考えたら求まりそう．SortedListではうまくできず，セグ木で実装し，順路は復元することでAC．セグ木は要素を3次元ぐらいまででもそんなに遅くならないね．解説見たら，LISを使う方法でした．このサイトでも少し触れていますので，良ければどうぞ（（ネタばれ）こちら）． yuichang.icon コインのマスの数が少ないので、グリッド全部を見ずにマスをrでソートしてマスだけ見た平面走査っぽくやれそう。マスを見た時、そこに辿り着ける時のmx取得数をセグ木とか使って高速に求める？？今解いてる。解けた。
〇G問題
CarpDay.iconコンテスト終了後に解説読んで取り組む．理解すれば難しくない問題．考える上でのポイントは，(1)青木君が選択する点は葉．葉がなくなったらそれ以外の点だけど，それ以降は点は上がらない．(2)貪欲法で解ける．K=kのときに選ぶk点は，K=k-1のときに選んだk-1点に新たな1点を追加したk点になる．この2点を理解すれば，単純なDFSで解ける．良い問題．