ABC204-E「Rush Hour 2」を解きました✅ 辺のコストが出発時刻で変わるグラフの最短時間。待てるので最適な出発時刻は√d付近になり、その5通りだけを全探索してダイクストラ法に組み込みました。ダイクストラ法に工夫を加えるところが面白かったです🚦 https://gist.github.com/maehrm/c8bfbe0ed8507a0837e124b8918743b2 #AtCoder #競技プログラミング

ABC143-E「Travel by Car」を解きました✅ ワーシャルフロイド法を2回使う解法。1回目で最短距離を求め、距離がL以下のペアをコスト1の辺にして、2回目で最小の満タン回数を求めます。解説にはダイクストラ法の解法もありましたが、ワーシャルフロイド法の方がしっくりきました🚗 https://gist.github.com/maehrm/8af14136960b842057e9bd1252df3b2e #AtCoder #競技プログラミング

ABC110-D「Factorization」を解きました✅ スポーツの日とは思えない過ごし方で取り組みました😅 Mを素因数分解し、素因数ごとに重複組み合わせnCrで配分して掛け合わせる解法です。素因数ごとに独立に数えられるのがポイントでした🔢 https://gist.github.com/maehrm/a345e2a30bedbea024e90130571e211c #AtCoder #競技プログラミング

ABC116-D「Various Sushi」を解きました✅ 自分なりに考えたものの、結局drken1215さんのC++の例をPythonに書き直しました。各ネタの代表K個を選び、種類数を減らしながらヒープ内の最大と入れ替える貪欲法。理解できるとなるほどと思います🍣 https://gist.github.com/maehrm/1f3f228fac78eee9f282ecabef7b0a2d #AtCoder #競技プログラミング

ABC197-F「Construct a Palindrome」を解きました✅ 頂点1側とN側の端点のペア(u,v)を状態に、同じ文字の辺を両側から同時にたどるBFS。u==vなら2d、辺でつながれば2d+1が答えの候補。両端から攻める発想がきれいに決まりました🔁 https://gist.github.com/maehrm/835a61862ac6188a28e87d549bf14f63 #AtCoder #競技プログラミング

ABC201-E「Xor Distances」を解きました✅ 根からのXOR d[u]を求めておけば、u-v間のパスのXORは d[u]^d[v]。ビットごとに0の頂点数×1の頂点数×2^iを足すだけで解けました。XORの性質が気持ちよかったです🌳 https://gist.github.com/maehrm/bd67cc8660455822e0ead4c8062fb665 #AtCoder #競技プログラミング

ABC477-F「Count Cells in a Window」を解きました✅ 2次元累積和の包除原理でオフライン処理し、各行のy=ax+bの傾きaとy切片bをBITで管理。かなり苦戦しましたが、とても勉強になりました🪟 https://gist.github.com/maehrm/f53169ed3719f968130ab22da188760d #AtCoder #競技プログラミング

ABC155-D「Pairs」を解きました✅ 正・負・0の3グループに分け、「積がv以下のペア数」を判定関数に二分探索。符号の組み合わせごとに異なる数え方を組み合わせる必要がありました✖️ https://gist.github.com/maehrm/5a187afac3cb809df802e2fc79d2561c #AtCoder #競技プログラミング

ABC149-E「Handshake」を解きました✅ 二分探索でボーダーラインokを求め、ok+1以上の確定ペアは累積和で合計、残りはok×残りペア数で補う解法。境界処理が丁寧さを要求されました🤝 https://gist.github.com/maehrm/6d7dd1e253b639f97928ca8957c0aefc #AtCoder #競技プログラミング

ABC468-F「Chmax」を解きました✅ 左から最大値を更新する回数をカウントし、更新されなかった要素だけでLISを求める。「元の更新回数+LISの長さ」が答えになる発想が面白かったです📈 https://gist.github.com/maehrm/7caba176b66946e634d8f8748624bbf3 #AtCoder #競技プログラミング

ABC146-F「Sugoroku」を解きました✅ ゴールから逆順に辿り、できるだけ遠くへジャンプする貪欲法。逆から構築した経路を反転すると自然と辞書順最小になるのがポイントでした🎲 https://gist.github.com/maehrm/76c63807c689ada4a89145741d0300f6 #AtCoder #競技プログラミング

ABC194-F「Digits Paradise in Hexadecimal」を解きました✅ dp[i][j]（上位i桁・使用j種類）で桁DP。既知の種類を使う/新種類を使うの2遷移に加え、先頭ゼロなどの場合分けも必要でした🔢 https://gist.github.com/maehrm/ce27cde3224076e7b955f9fc97588672 #AtCoder #競技プログラミング

ABC169-F「Knapsack for All Subsets」を解きました✅ dp[i]を管理し、使わない要素は集合Tに含む/含まないの2通りとしてdp[i]を2倍加算。通常のナップサックDPに自由度を乗算で組み込む発想が面白かったです🎒 https://gist.github.com/maehrm/49f6c91904e963665c3232e6b84681e7 #AtCoder #競技プログラミング

ABC151-F「Enclose All」を解きました✅ 自分でmycombi関数を作り、2点直径→3点外接円→EPSと3段階で完成させました。外接円の中心を行列で求めるところで久しぶりに高校数学を思い出しました⭕ https://gist.github.com/maehrm/5ae51b337f1205d5552d99ef93fe9e50 #AtCoder #競技プログラミング

ABC369-G「As far as possible」を解きました✅ 木を「本線」と複数の「支線」に分解し、支線を長い順に往復（×2）で足していく貪欲法。木を主軸と枝に分ける発想が美しい一問でした🌲 https://gist.github.com/maehrm/b40821b7865e7224c36e06b67a1a441b #AtCoder #競技プログラミング