練習メモ2-7
だんだん雑になってるけど、一応。
CF 400
回避した。
インドコン印象悪いので……。
CF 401div2
全体的に簡単だったけど解くの遅かった。
950位&-50で今のレートは1780くらい。
3月中に紫が目標なんだけど苦手セット続くと意外と険しいなあ。
Cは区間を持つという発想にとらわれすぎて、普通に左をここまで見たときの右の最大みたいのをもてばいい、というのが中々思いつかなかった。反省。
Dは……
なんというか、なんとも言いようがないなあ。貪欲法を信じろ、みたいなとこだろうか?
Yukicoder 157
簡単回だった。これも感想は特に……。
489はまんまスライド最小値だけどRMQかセットで十分だよね、というのはまあそれはそうなんだけどインデックス持たせるなら普通にデックでスライド最小値が一番楽なのでは(今更)
インデックス出力しろっていう条件最初読み飛ばしてたのでBTreeSetで書いてしまった。
しかもBTreeSetで最大値返す関数がよくわからなかったので-1倍して持たせるという……。
fn exec() { let mut sc = Scanner::new(); let n: usize = sc.ne(); let d: usize = sc.ne(); let k: i64 = sc.ne(); let a: Vec<i64> = (0..n).map(|_| sc.ne()).collect(); let mut s = BTreeSet::new(); for i in 0..d { s.insert((a[i] * -1, i)); } let mut ma = 0; let mut id = (0, 0); for i in 0..n { let nxt = i + d; if nxt < n { s.insert((a[nxt] * -1, nxt)); } let rem = a[i] * -1; s.remove(&(rem, i)); if let Some(x) = s.iter().next() { let tmp = (x.0 * -1) - a[i]; if ma < tmp { ma = tmp; id = (i, x.1); } } } println!("{}", ma * k); if ma != 0 { println!("{} {}", id.0, id.1); } }
はてな記法でRust使えるのしらなかった。
[追記]
普通にiter().rev()して逆順イテレータ取得すれば最大値もらえるっぽい。
こんなん。
fn exec() { let mut sc = Scanner::new(); let n: usize = sc.ne(); let d: usize = sc.ne(); let k: i64 = sc.ne(); let a: Vec<i64> = (0..n).map(|_| sc.ne()).collect(); let mut s = BTreeSet::new(); for i in 0..d { s.insert((a[i], i as i32 * -1)); } let mut ma = 0; let mut id = (0, 0); for i in 0..n { let nxt = i + d; if nxt < n { s.insert((a[nxt], nxt as i32 * -1)); } s.remove(&(a[i], i as i32 * -1)); if let Some(x) = s.iter().rev().next() { let tmp = x.0 - a[i]; if ma < tmp { ma = tmp; id = (i, (x.1 * -1) as usize); } } } println!("{}", ma * k); if ma != 0 { println!("{} {}", id.0, id.1); } }
RustのこのへんのAPI統一感あって好き。
ただこの問題の場合辞書順最小なので今度はインデックスを-1倍しないといけなくなる。
MUJINプロコン
用事で出れない。かなc