2023-01-18 ABC038 の A, B, C, D を解いた
ABC038 : AtCoder Beginner Contest 038 の A, B, C, D を解いた。
- A - お茶
https://atcoder.jp/contests/abc038/tasks/abc038_a
- 提出: https://atcoder.jp/contests/abc038/submissions/38137464
s.ends_with('T')
- B - ディスプレイ
https://atcoder.jp/contests/abc038/tasks/abc038_b
- 提出: https://atcoder.jp/contests/abc038/submissions/38137514
h1 == h2 || h1 == w2 || w1 == h2 || w1 == w2
- C - 単調増加
https://atcoder.jp/contests/abc038/tasks/abc038_c
- 提出: https://atcoder.jp/contests/abc038/submissions/38137664
l == rで各要素に 1 通りずつl < rは単調増加する箇所ごとに x choose 2 通りずつ。 x は単調増加する箇所の長さ- 足したものが答えになる
- D - プレゼント
https://atcoder.jp/contests/abc038/tasks/abc038_d
- 提出: https://atcoder.jp/contests/abc038/submissions/38138352
- ひとまずすべての w, h が異なるものとして考える
- とりあえず w の昇順に並べる
- 先頭から走査して、ある箱を使う場合は、それまでの結果のうち h 未満で最大の個数 + 1 になる
dp[h] := 高さ h における最大の個数として順に更新していく- 区間の最大を求めるためにセグメント木 or BIT (FenwickTree) を使う
- 最後に全体で最大を求めれば答えになる
- 次に w, h に同じものが含まれる状況を考える
- w が同じ場合は h が昇順になってしまうと、同じ w に対して複数の h を使ってしまうことになる (dp で同じ範囲を対象に更新をかけてしまう)
- w の昇順 h の降順にしておけば問題ない
use std::cmp::Reverse;
use proconio::input;
use segtree::*;
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 + 1);
for (_, h) in wh.into_iter() {
st.set(h, st.prod(0, h) + 1);
}
let ans = st.all_prod();
println!("{}", ans);
}
// segtree
今日のコミット。