今日から AtCoder の過去コンテストも Rust 1.70.0 に切り替わったようだ。まだぼくのコードは対応していない。 cargo-compete は v0.10.6 に更新して compete.toml の [submit] を README にあるとおり、↓と変更すれば提出できるようになった。

[submit]
kind = "file"
path = "{{ src_path }}"
language_id = "5054"

cargo-atcoder は最近のコンテストに参加できていることから分かるように設定を変更済み。 PAST 本が終わるまではこのまま進めるつもりでいる。

shapez のためにキーボードとマウスを買った。

• 数列の反転 (第八回 アルゴリズム実技検定:J問題) https://atcoder.jp/contests/past202109-open/tasks/past202109_j
  • https://atcoder.jp/contests/past202109-open/submissions/45246406
  • 解説 AC 以前もおそらく解説 AC
  • 左から k 番目は反転したかしていないかで N + 1 - k か N + k のどちらかにしかならない
  • 反転回数の偶奇が問題になる
  • 反転の方法から k を含む (k 以上の位置) を反転したものの総和の偶奇を判定すれば良い
  • 反転した位置を数えてやれば良い
  • ここまで整理すればセグメント木に落とし込める

use proconio::input;
use segtree::*;

fn main() {
    input! {
        n: usize,
        q: usize,
        tk: [(usize, usize); q],
    }
    let mut segtree = Segtree::<Additive<usize>>::new(n + 1);
    for (t, k) in tk {
        match t {
            1 => {
                let i = if k <= n { n + 1 - k } else { k - n };
                let ans = if (segtree.prod(i - 1..n) + if k > n { 1 } else { 0 }) % 2 == 0 {
                    n + 1 - i
                } else {
                    n + i
                };
                println!("{}", ans);
            }
            2 => {
                segtree.set(k - 1, segtree.get(k - 1) + 1);
            }
            _ => unreachable!(),
        }
    }
}

今日のコミット。

• kireta 1 commit
  • Remove static file handler
• rust-atcoder 1 commit
  • pastbook2 past202109_j