bouzuya.hatenablog.com

ぼうずやのにっき

ARC138 の A を解いた

大和証券プログラミングコンテスト 2022 Spring (ARC138 : AtCoder Regular Contest 138) の A を解いた。

  • A - Larger Score https://atcoder.jp/contests/arc138/tasks/arc138_a
    • 提出: https://atcoder.jp/contests/arc138/submissions/32502350
    • 1..=K と K+1..=N から 1 項ずつ選んで swap する
    • 1 項でも swap すれば s+1 以上になるはずなので 2 項ずつ選ぶ必要はない
    • 操作回数は swap する項のうち 1..=K 側を i K+1..=N 側を j としたとき j-i になる
    • i を走査して A_i < A_j を満たす j のうち最小のものを得たい
    • A を座標圧縮したものを B とし、セグメント木で B_j に j を入れて B_i + 1..=N の範囲の MIN(j) を取って解いた
    • 解説を見ると (A_i, -i) でソートして走査し i > K のときそこまでの i <= K のうち最大のものと交換すれば良いとなっていた

『カールじいさんの空飛ぶ家』を観た。別れの多い映画で悲しい気持ちになった。

crates:termion を使って suiro に UI をつけている (途中) 。

上の子がワッペン付きの服をみて「このふく、けいさつかんみたい！」とはしゃいでいた。

今日のコミット。