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

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

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

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

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

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

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

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

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

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