はじめに Codeforces Round #344 Div. 2 Prob. A. Interview 問題：http://codeforces.com/contest/631/problem/A ある配列xについて、lからrまでの区間ですべての要素のorをとったものを、f(x,l,r)と定義する。 与えられた２つの配列a,bについて、max f(a,l,r)+f(b,l,r)を求める。 考え方 lとrについて全探索するだけ。計算量はO(n^2)。Div2のA…
Read more...はじめに Codeforces Round #344 Div. 2 Prob. B. Print Check 問題：http://codeforces.com/contest/631/problem/B 行か列を一気に色（数字で表現）で塗る。最後の状態を出力する。 考え方 各行、各列で最後に塗られた色と、塗られた時間を記録する。各要素は属する行と列の遅く塗られたほうの色になる。計算量はO(n*m + k)。 解法
Read more...はじめに 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. A. Two Bases 問題：http://codeforces.com/contest/602/problem/A 解けなかったのでブログに書いておく。 考え方 やるだけ 全部mainに書いていたら、入力を受け取るvectorの初期化時に、サイズを添えるコンストラクタ呼び出しで変数を間違えた。vector<int> x(n),y(n);とかしていた。 x用のvectorの宣言時に、m…
Read more...はじめに Codeforces Round #333 Div. 1 Prob. A. The Two Routes 問題:http://codeforces.com/contest/601/problem/A Codeforces Round #333 Div. 2 Prob. C. The Two Routes 問題：http://codeforces.com/contest/602/problem/C…
Read more...