人権なし

競プロで解いた問題や開発の進捗などの記録です

Codeforces 問題

Codeforces Round #566 (Div. 2):B. Plus from Picture

問題 解法 解答 問題 codeforces.com 解法 十字架の中心部分をまず見つける.中心部分の条件は,自身と上下左右のマスが * であること.このようなマスを 1 つ見つけたら上下左右に連続する * を . に置き換えていく.この操作後,* が残っていれば NO,残っ…

Codeforces Global Round 2:D - Frets On Fire

問題 解法 解答 問題 codeforces.com 解法 まず S をソートしておき,重複しているものは取り除いてよい. ここで,各クエリで与えられる区間の「位置」は答えに影響を与えず,「長さ」が影響を与える.なぜならば,区間が [l, r] としたら,その区間にあっ…

Codeforces Global Round 2:C - Ramesses and Corner Inversion

問題 解法 解答 問題 codeforces.com 解法 問題にある操作は「任意の x1 < x2, y1 < y2 となるような 4 つの値を選び,マス (x1, y1), (x1, y2), (x2, y1), (x2, y2) の値を反転させる」と言い変えることが出来る.また,マス目 A, B で異なっている箇所をマ…

Codeforces Global Round 2:B - Alyona and a Narrow Fridge

問題 解法 解答 問題 codeforces.com 解法 何本までを冷蔵庫に入れるか (k) を固定して考えたとき,a_1, a_2, ... , a_k をソートしたものを b とおく.まず,高さ b_k のものを入れなければならないので,仕切りは必ず b_k の高さが入るような空間が出来る…

Codeforces Global Round 2:A - Ilya and a Colorful Walk

問題 解法 解答 問題 codeforces.com 解法 各色ごとに最も小さい座標と最も大きい座標を求め,それぞれソートしておく.その後,ある色を固定したとき,ほかの色の最大値を求めその差の max を取り答えにする.ほかの色の最大値を求めるのには事前に各色の最…

Codeforces Round #530 (Div. 1):A. Sum in the tree

問題 解法 解答 問題 codeforces.com 解法 b_i を「頂点 i を根とする全て部分木に含まれる s の最小値」とおく.このとき,b_i < s_i であるような頂点が存在したらその木は構成不可能なので -1 を出力すればよい. 木が構成出来る場合,木全体を根から(す…

Codeforces Round #534 (Div. 1):A. Grid game

問題 解法 解答 問題 codeforces.com 解法 縦長のタイルは 4x4 のマスの上半分,横長のタイルは下半分にひたすら敷き詰めていけば永遠に敷き詰められる.なぜなら,上半分に関しては 4 つ設置すると上から 1, 2 行目が消えて,下半分に関しては 2 つ横に並べ…

Hello 2019:C - Yuhao and a Parenthesis

問題 解法 解答 問題 codeforces.com 解法 各括弧列について,( と ) のどちらがどれだけ不足しているのかを調べる.もし,両方不足している括弧列は他のどの括弧列ともペアになれないので考えない.それ以外の括弧列の中で ( の不足分と ) の余剰分が一致す…

Hello 2019:B - Petr and a Combination Lock

問題 解法 解答 問題 codeforces.com 解法 n <= 15 と小さいので,回すそれぞれの動作を時計回りか反時計回りのどちらにするかを全通り試す.針が 0 度のところに戻るかどうかは O(n) で判定できるので,O(2^n * n). 解答 codeforces.com 360 で mod を取る…

Hello 2019:A - Gennady and a Card Game

問題 解法 解答 問題 codeforces.com 解法 問題文の通りに判定すればよい.O(1). 解答 codeforces.com