ABC421 （2025/08/30）
注意：来週は日曜日の昼からコンテストが始まります
〇A問題
まーす.iconlistで受け取って，X - 1 (0-indexed)の要素がYかどうかで判定．
wataumi.iconまーす.iconに同じく。
Kaplam.icon病みツイでりーと！
N_N.icon $ S_i を配列に入れて，$ S[X- 1] と Y が一致してるかで判定．
CarpDay.icon皆さんと同じく
〇B問題
Kaplam.iconstrでひっくり返してこねこね
wataumi.iconKaplam.iconそんなやり方があるんだね！intのままwhile文で愚直にひっくり返しました。
まーす.icon問題通りに．謎のWA出て，気が気でなかった．
N_N.icon XとYを逆にしてしまって少しタイムロス．Java では StringBuilder を使って文字列を反転．
CarpDay.icon素直に足して，文字列にして，反転して，整数にして代入
〇C問題
Kaplam.icon順位的に解いても得なかったのでDやってた、Cぱっと見めんどそうで先にD見る→実装重くて一旦順位表見たら既にC4000人通しててD400人ぐらいしか通してなくて今からC解いても2完の中だと最上位だからあんまり順位上がらないしD通してから時間あれば～って
まーす.icon有限数列$ \{P_{i}\}_{i = 1} ^ {N},\ \{Q_{i}\}_{i = 1} ^ {N},\ \{R_{i}\}_{i = 1} ^ {N}をそれぞれ，文字列 "AB" * N の"A"のindex，文字列 "BA" * N の"A"のindex，文字列Sの"A"のindexとする．このとき，$ \min \left(\sum_{i = 1} ^ {N} \left| P_{i} - R_{i} \right|, \sum_{i = 1} ^ {N} \left| Q_{i} - R_{i} \right| \right)が答え．
wataumi.iconデータ構造は、fenwick Tree(フェニック木)。実装力ないので、ac-library-python（ALC：競プロライブラリ）使ってます。
N_N.icon 最初，レーベンシュタイン距離でも使うのかなと思って（でもよくは知らないから），先にDに進む．でも，文字がAとBしかないことに気付いてこちらに戻ってくる．解き方はたぶん，まーす.iconさんと同じ？[! i番目のAの出現位置A［i］とi番目のBの出現位置A［i］を覚えておく．最終的にA［i］が偶数番目に来るか，B［i］が偶数番目に来るはずなので，abs(A［i］ - i * 2)の和とabs(B［i］ - i * 2)の和を求めて小さい方を出力．
四角括弧の書き方がわからない．．．
まーす.icon全角の「［」，「］」で代用するのはどうですか？［］
N_N.icon そうします．．．
CarpDay.icon"AB" * Nと"BA" * Nの正解パターン２つ作る．次のＡ，次のＢのindexを記憶しておいて，正解パターンと異なるときに，次の位置の文字と入れ替え，次の文字のindexを更新する．この処理をベタに作成してTLE．２つ先のA，２つ先のBを記憶しておくようにして，やっとAC．C問題でこんなめんどくさいことしなくても解けるんだろうな，こんなに手間かけてWAだったら辛いな，という葛藤の中のコーディングがしんどかった．ACして本当に良かった．．
CarpDay.icon解説見ました．確かにAのインデックス集合を(0, 2, 4...)か(1, 3, 5, ...)にするための手数だ．．C問題なんだから，そういう発想が大切で，発想が思いつかないから跳ばす勇気が必要だ．．反省．
まーす.icon私は文字"A"の気持ちを考えたら，上の発想がでました．問題の条件から，swapは隣同士にしか適用出来ないです．このことは，「swapは"AB"の部分または，"BA"の部分に対してしか意味を為さない」ということを表しています．例えば，"AAABBB"のような文字列に対して，2文字目と3文字目をswapしたとしても，無意味なswapをすることになりますね．
CarpDay.icon他者の気持ちになって考えること，大切ですね．競プロは道徳教育にも役立ちますね！
〇D問題
Kaplam.icon通んなかった！
まーす.iconこの問題はめんどくさいです．私の考えでは$ 4 ^ {2} = 16通りの場合分けをする必要があって，多分そこでミスってる．(6WA)
まーす.iconAC でました．愚直解法です．高橋君と青木君が逆向きに動くケースにて，本来は遠ざかっていくのにすれ違った判定をとっていた．気が付くのに１時間かかった......
wataumi.icon区間分けをして、それぞれ連立方程式を解く。
まーす.icon解説見た後でコードを理解．ある種自然な発想だけれども，高橋君と青木君の相対速度を考えることによって，場合分けを減らせるのか......．頭良すぎ
CarpDay.iconコードを拝見．相対速度って何のこと？と思っていたけど，見方変えれば青木君固定して，高橋君だけ動かすという感じね．確かに分かりやすいわ．
N_N.icon 場合分けがたくさんで，間に合わなかった．尺取り法のようにして高橋君と青木君のどちらが先に移動方向を変えるかをチェックしながら，[! 両名のX座標とY座標が同時に交わるかを判定する．両方が逆方向に動いたときに，移動前の距離の偶奇性に注意する（奇数だとすれ違う）．ただし，まだAC出てません．
まーす.iconWAケース発見しました．
code: WA ケース
1 2 0 0
1 1 1
L 1
D 1
code: 想定解
0
N_N.icon ありがとう！自分の研究で大きな進展があったので（別々に取り組んでいた研究が繋がった），こっちの方はほったらかしてました．落ち着いたら，確認してみます．
まーす.icon<(_ _)>
CarpDay.icon高橋と青木の行動が切り替わるタイミングで区分けして，始点と終点の線分が交わるかで判定．．したかったけど，やり方が分からず時間がないので直感で投稿してやっぱり12WA．終了後に30分かけて丁寧に場合分けしたコードを作るも依然10WA．何か見落としているパターンがあるのか．．
CarpDay.iconベタな場合分けによる解法，コンテスト終了後80分後にやっとAC．このやり方は自分には向いてない．
CarpDay.icon解説読む．karinohitoさんのユーザ解説すばらしい！場合分けぐっと減って，コードがシンプルになりました．こういう発想できるようになりたい．2回頑張ってプラスしたランクアップ分をこの2回で吐き出して，げんなり．．
〇E問題
CarpDay.iconD問題が面倒くさそう ＆ 期待値なのでこちらにしようと思ったものの，方針が思いつかずD問題に戻る．
CarpDay.iconまだ解説見ていないけど，またＥ問題とＦ問題，Difficulty逆転している．．
CarpDay.icon何でタイトルが「ヨット」なのか？と思ったら，そういうゲームがあるみたいです（例 ）．また後で期待値計算してみるので，解説は我慢． まーす.iconチラ見してみたけど，絶対難しいやつ．まず，最適な行動が分からん......
〇F問題
まーす.icon野良（お気に入りにしていた人）でこの問題通している人（緑コーダー）がいてびっくり．
まーす.icon linked list の要領でやってみたら，当然のごとくTLE．
まーす.iconどうやら，タイポのせいだったみたい......
まーす.iconサンプルが悪く，CarpDay.iconさんにバグとりに協力してもらい無事AC．感謝感謝
CarpDay.iconコンテスト後に覗く．合計する部分，累積和でとっておかないとTLEになりそう，でも対応が分からないから無理，と勝手に諦めて解説を見る．結論計算量勘違いで，素直に双方向リストで解ける，とのこと．まーす.iconさんがデバッグ中だったので，ほとんどパクらせてもらってAC．勉強になりました．
〇G問題
まーす.iconこっちもチラ見．先頭から貪欲に見ていったら良さそう．けど，まぁ，そんな甘くはないよね......