bouzuya.hatenablog.com

ぼうずやのにっき

東京出張 / ABC038 D を解いた

今日は仕事で東京へ。約 3 ヶ月に一度の出張。帰りの新幹線でこの記事を書いている。新幹線が値上がりしていた。単に料金の高いときに予約しただけ……かもしれない。

今日は体調不良の人が多かった。あるいは体調不良で人が少なかった。多いけど少ない。気温が下がったもんな。半袖の人も居た。微妙な時期だもんな。

のどが痛いので風邪がうつるとまずいかなと思い、特に飲み会などは参加せずに帰ってきた。……といっても 1h 早くなる程度だ。新大阪で終電を怖がってやきもきしなくて済むのはありがたいけどその程度だ。

新幹線のホームの売店で買った弁当を食べた。柿の葉寿司の。ひさしぶりに食べた気がする。柿の葉寿司は食べるたびにひさしぶりと言っている気がする。普段は同じものばかり食べているのでそういう感想になる食べ物が多いのだけど。

  • プレゼント (AtCoder Beginner Contest 038:D問題) https://atcoder.jp/contests/abc038/tasks/abc038_d
    • 提出: https://atcoder.jp/contests/abc038/submissions/46244510
    • 横の昇順・縦の降順にソートする
    • この順に走査すれば横は必ず入れ子にできることが分かるので縦のみを考えれば良くなる
    • 縦を降順にするのは、同一の横に対して複数の縦を処理してしまい本来はありえない入れ子が発生してしまうため
    • その縦よりも小さいもののうち最大のものに +1 したものをその縦に保存していけば良い
    • セグメント木で管理すれば区間の最大を取得できる
use segtree::*;
use std::cmp::Reverse;

use proconio::input;

fn main() {
    input! {
        n: usize,
        mut wh: [(usize, usize); n]
    }
    wh.sort_by_key(|&(w, h)| (w, Reverse(h)));
    let mut st = Segtree::<Max<usize>>::new(100_000_usize + 1);
    for (_, h) in wh {
        let count = st.prod(0..h);
        st.set(h, count + 1);
    }
    let ans = st.all_prod();
    println!("{}", ans);
}

// segtree

今日のコミット。