はじめに Codeforces Round #344 Div. 2 Prob. C. Report 問題：http://codeforces.com/contest/631/problem/C 数列が与えられる。先頭からr番目の要素までを、降順または昇順でソートするクエリが順番に与えられる。最後の状態を出力。 考え方 クエリをrでソートして、後ろから確定するかんじ。確定されていない要素の中でのmaxかminの要素が後ろから並んでいく。確定されていない要素はmultisetで管理した。計算量はO…
Read more...はじめに CODE FESTIVAL 2015 予選B D問題 問題：http://code-festival-2015-qualb.contest.atcoder.jp/tasks/codefestival_2015_qualB_d 解けなかったのでブログに書いておく。 考え方 左方向に、すでに黒く塗られたところを飛ばしながら黒く塗っていく。 →黒く塗られた区間をsetで持ってマージしたりしながらシミュレーションするだけ。O(nlogn) これを解いた時は、競プロから離れすぎていてset…
Read more...はじめに Codeforces Round #333 Div. 2 Prob. B. Approximating a Constant Range 問題：http://codeforces.com/contest/602/problem/B 与えられた数列で、minとmaxの差が1になる区間の最大サイズを求める。 解けたけど効率悪い実装していたので書いておく。 考え方 multisetに数字を突っ込んだり削除したりしながらしゃくとりするだけ。計算量はO(nlogn) ACしたけどmultiset…
Read more...