はじめに 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...はじめに 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...はじめに Codeforces Round #332 Div. 2 Prob. C. Day at the Beach 問題：http://codeforces.com/contest/599/problem/C 解けなかったのでブログに書いておく。 考え方 重複がある数列をソートしたいとき、ある区間でのソートが全体でのソートと一致した数列になるかどうか、という問題はその区間での各数字の出現回数が一致することを調べればよい。 →mapで数えて一致するかどうかを確認する。毎回map…
Read more...はじめに Codeforces Round #330 Div. 2 Prob. B. Pasha and Phone 問題：http://codeforces.com/contest/595/problem/B 解けなかったのでブログに書いておく。 考え方 各ブロックが、biで始まらないかつaiで割り切れる数字で構成される組み合わせの数え上げ（のMOD）。 →各ブロックを条件の通りで数えた後掛け算してmodするだけ 解けなかったのはstlのpowの返り値がdouble…
Read more...はじめに CODE FESTIVAL 2015 予選A D問題 問題：http://code-festival-2015-quala.contest.atcoder.jp/tasks/codefestival_2015_qualA_d 解けなかったのでブログに書いておく。 考え方 Xを決めたとき、「全員がX回移動できるときにすべて埋められるかどうか」は整備士を左からなめていって高速に判定できる。 →二分探索で最大のXを求める。 制約を見てもdp…
Read more...