問題 解法 解答 問題 https://atcoder.jp/contests/abc147/tasks/abc147_c 解法 N 人それぞれが「正直者」かそうでないかを 2^N 通りすべて試し，与えられた情報に合致する組み合わせの中で最も「正直者」の数が多いものを答えにすればよい．O(2^N * N)． 解…

問題 解法 解答 問題 https://atcoder.jp/contests/abc136/tasks/abc136_c 解法 後ろのマスから見ていき，H_i > H_(i + 1) であるような箇所があったら H_i を 1 削る．それでも H_i が高いままであれば答えは No になる．逆に，このような箇所がなく，全て…

問題 解法 解答 問題 https://atcoder.jp/contests/abc133/tasks/abc133_c 解法 区間 [L, R] に 2019 の倍数が含まれているならば，答えは 0． そうでない場合，この区間の長さは 2019 未満であるから，i と j を全探索して答えを求めればよい． 解答 https:…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_g 解法 N_i <= 1 のとき，答えは N_i になる． そうでないとき，2 と 3 で分解するのが最適になる．具体的には，N_i % 3 == 1 のとき 3^(N_i / 3 - 1) * 4 とし，そうでないとき 3…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_f 解法 現在の時刻を t，今いる島を i とするとき，橋 (i, j) を使ったときに島 i + 1 にいる時刻は ceil(t / A_(i, j)) * A_(i, j) + B_(i, j) となる．各島においてどの橋を使っ…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_e 解法 まず A の和が E 以下であればエナジードリンクは飲まなくてもよい． そうでないとき，エナジードリンクを B_i が大きい順に飲んでいけばよい．B を降順にソートしておき，…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_d 解法 まず，要素が重複している連続する区間は 1 つの要素にまとめてしまってよい．なぜならば，このような区間でどこをスキップしてもスコアは増えないから．こうすることによ…

問題 解法 解答 問題 https://atcoder.jp/contests/agc035/tasks/agc035_a 解法 (a ^ b) == c は (a ^ b ^ c) == 0 と同値より，高々 3 種類の数字しか登場してはならない．3 種類の場合は (a ^ b ^ c) == 0 となる a, b, c がそれぞれ N / 3 個，2 種類の場…

問題 解法 解答 問題 https://atcoder.jp/contests/abc132/tasks/abc132_c 解法 (N / 2 + 1 番目に難しい問題の難易度, N / 2 番目に難しい問題の難易度] のどれかを K と設定するのがよい．ソートすればこれは求まる．O(NlogN)． 解答 https://atcoder.jp/c…

問題 解法 解答 問題 atcoder.jp 解法 与えられた長方形の重心を通るような面積を半分にする直線は，長方形の対角線である 2 本が考えられる．それ以外の点で半分にする直線は 1 本に定まる．O(1)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 A - 1, B 以下の整数で C でも D でも割り切れない整数の数をそれぞれ求め，後者から前者を引けば答えになる．C でも D でも割れる数の扱いに注意する．O(1)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 まず，N^2 個（正確にはもっと少ない）ある (p, q) の組を全列挙する．その後，各 (p, q) の組について必要となるコストの回数を計算する．ある頂点 v から移動量が (p, q) または (-p, -q) であるような頂点 u があれ…

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := i 段目まで登る通り数 として DP を考える．通り数は i が「壊れている床」のとき 0 通り，そうでないときは dp(i - 1) + dp(i - 2) 通りとなる．O(N)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 各さいころの目ごとに得点を K 以上にするために必要な確率を求め，1 / N と掛け合わせたものを合計したものが答えになる．コインが表が出続けなければならない回数は，得点が 2 倍されていく過程をシミュレーションす…

問題 解法 解答 問題 atcoder.jp 解法 全ての [L_i, R_i] に含まれるカードの枚数を求めればよい．これは，L_i のうち最も大きいものと R_i のうち最も小さいものの差になる．この２つの位置が逆転するとき，答えは 0 となるので注意．O(N)． 解答 atcoder.j…

問題 解法 解答 問題 atcoder.jp 解法 スイッチの数 N が N <= 10 と小さいので，スイッチが on か off かを 1, 0 と置き換え bit 全探索をする．全スイッチの状態それぞれについて電球がつくかどうか問題文にある通りに調べればよい．O(2^N * M)． 解答 atc…

問題 解法 解答 問題 atcoder.jp 解法 ユークリッドの互除法で各 A_i, B_i の最大公約数は求まる．O(N * log(max(A, B)))． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 (min(A_i, B_i), max(A_i, B_i)) をペアとし，std::set に追加していく．最終的な set のサイズが答えになる．O(NlogN)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 問題文中の「辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる」は「黒色のマスと辺を共有して隣接する白色のマスが黒色になる」と言い変えられるので，全ての黒色の…

問題 解法 解答 問題 atcoder.jp 解法 受付しなければいけない人がいる時間帯の区間の数が知りたいので，imos 法を用いて「ある時間 t に受付しなければいけない人がいるか？」を O(1) で知れるように前計算しておく．あとは，受付しなければいけない人が連…

問題 解法 解答 問題 atcoder.jp 解法 座標圧縮のアルゴリズムを用いればよい．O(NlogN)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 川と変態仮面の動く線分が交差しているかを判定すればよい．O(1)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 最長共通部分列 (LCS) の長さ + 1 が答えになる．LCS は簡単な DP によって求めることが出来る．O(|S||T|)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 N を素因数分解したときの項数よりも K が大きいとき，条件を満たす解はない． そうでないとき，答えの 1 ~ K - 1 項まで順番に N の素因数を小さい順に当てはめていけばよい．最後に残った素因数を全て掛け合わせたも…

問題 解法 解答 問題 atcoder.jp 解法 デートする日を最小化することを考える．以下，最小のデート回数を考える． B = 0，すなわち，記念日が無いとき，最小のデート回数は N / A． そうでないとき，0 日目と最初の記念日の間，B - 1 箇所ある隣り合う記念日…

問題 解法 解答 問題 atcoder.jp 解法 数列 A のうち 1 つを選び，任意の整数に書き換えられるということは，その選んだ数は A 全体の GCD に影響を与えないということと同値である．なので，ある個所を選んだ時の GCD は，その箇所より左の部分列の GCD と…

問題 解法 解答 問題 atcoder.jp 解法 黒の右には白はないので，操作後の石の列は「白白白白白...」か「黒黒黒黒黒...」か「白白白...黒黒黒...」となる．よって，左から何個かを白にして，そのほかを黒にすればよい．この「何個」を 0 ~ N まで試せばよい．…

問題 解法 解答 問題 atcoder.jp 解法 入口と出口を全てのマスについて試していては TLE となってしまうので，候補を減らすことを考える．すると，それぞれ A_i, B_i の座標全てについて調べれば十分であるので，候補を減らすことが出来た．O(N^3)． 解答 at…

問題 解法 解答 問題 atcoder.jp 解法 タイルを塗り替えた後の S は 01010... か 10101... の 2 通り．つまり，この 2 つと初期状態の S を比べ，違う色の枚数の少ない方を塗り替えたあとの S として採用すればよい．O(|S|)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 A, B, C, D, E のうち最も少ない人数に合わせて人を運ぶという方針でよい．なぜなら，それより多い人数を運んでも，容量の小さい箇所で人が溜まってしまい，結局は同じになってしまうから．よって，容量の小さい箇所を …