問題 解法 解答 問題 https://atcoder.jp/contests/abc148/tasks/abc148_d 解法 壊すレンガの数を少なくするには残すレンガの数を増やせばよいので，できる限り 1, 2, 3, ... の列を長くすればよい．これは，次に残したい数字 k（最初は 1）を保持しながら左…

問題 解法 解答 問題 https://atcoder.jp/contests/abc148/tasks/abc148_e 解法 N が奇数のとき，答えは 0．なぜならば，f(N) は素因数に 2 と 5 を持たないから． N が偶数のとき，f(N) が 5 で割れる回数が答えとなる（正確には 2 で割れる回数との min に…

問題 解法 解答 問題 https://atcoder.jp/contests/abc148/tasks/abc148_f 解法 高橋君は木のどこかの葉に逃げるのが適切なので，それぞれの葉に逃げたときの青木君の移動回数を求め，それらの max を答えとすればよい． まず，ある葉（頂点 t）までの距離 d…

問題 解法 解答 問題 https://atcoder.jp/contests/abc144/tasks/abc144_f 解法 M 本の辺それぞれをふさいだときの E を計算していては O(M^2) となり間に合わない．ここで，ある頂点 v から出る辺のうち 1 つを塞ぐとするとき，v とつながる先の頂点から頂…

問題 解法 解答 問題 https://atcoder.jp/contests/abc144/tasks/abc144_e 解法 「チーム全体の成績を k 以下にすることが出来るか」を基準とする二分探索で答えを求める．これは A を昇順，F を降順にソートしておき，この順番で担当する食べ物を割り当て，…

問題 解法 解答 問題 https://atcoder.jp/contests/abc144/tasks/abc144_d 解法 底面の辺を軸として傾けているから，平面で考えてよい．ある角度より傾けると水がこぼれるという単調性があるから，「角度 θ 傾けたとき，水がこぼれるかどうか」を基準とした…

問題 解法 解答 問題 https://atcoder.jp/contests/abc145/tasks/abc145_f 解法 まず，数列 H を扱いやすいように座標圧縮しておく（最小を 1 としなければいけないことに注意）．そうすることで H の要素は高々 N + 1 以下になる．また，H[k] < H[k + 1] と…

問題 解法 解答 問題 https://atcoder.jp/contests/abc145/tasks/abc145_e 解法 まず，食べることにした料理の中では食べるのに必要な時間が短い順に注文するのが最適なので，料理を食べるのに必要な時間が短い順にソートしておく．ここで以下の DP を考える…

問題 解法 解答 問題 https://atcoder.jp/contests/abc145/tasks/abc145_d 解法 各移動で原点から x, y 座標合わせて 3 は増加するから，(X + Y) が 3 で割り切れないとき，答えは 0 通り． そうでないとき，操作の回数 n は (X + Y) / 3 回であると分かる．…

問題 解法 解答 問題 https://atcoder.jp/contests/abc146/tasks/abc146_f 解法 辞書順最小にしたいので，マス N からマス 0 に向かって「ゲームオーバーマス」を避けながら，すごろくの目を最大化しながら進んでいけばよい．途中「ゲームオーバーマス」が M…

問題 解法 解答 問題 https://atcoder.jp/contests/abc146/tasks/abc146_e 解法 K = 1 のとき，答えは 0． そうでないとき，各 A_i から 1 を引き，累積和を求めておくと，「A の空でなく，長さが K 未満である連続する部分列で，要素の和を K で割った余り…

問題 解法 解答 問題 https://atcoder.jp/contests/abc146/tasks/abc146_d 解法 まず，最も多くの辺が繋がっている頂点がもつ辺の数が必要となる色の数になる．また，ある 1 つの頂点を木の根とし，そこから辺を塗っていく DFS をする．具体的には，(今いる…

問題 解法 解答 問題 https://atcoder.jp/contests/abc147/tasks/abc147_e 解法 dp(i, j, k) := マス (0, 0) から マス (i, j) までのパスで「偏り」が（以上でも以下でもなく）k となるかどうか という DP を考えると，遷移は (0, 0, |A[0][0] - B[0][0]|) …

問題 解法 解答 問題 https://atcoder.jp/contests/abc147/tasks/abc147_d 解法 bit ごとに操作は独立なので，A の中で 2^k 桁目が 1 であるものの数をそれぞれ数えておき，この数を用いて答えを計算する．各 2^k 桁目について（1 の個数）*（0 の個数）* 2^…

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

問題 解法 解答 問題 https://atcoder.jp/contests/joi2020-yo1b/tasks/joi2020_yo1b_c 解法 問題文を言い換えると「数列 A の中で最も多く含まれる数字の含まれる回数」を求めればよいと分かる．これは 1 ~ M それぞれについて A の中で登場する回数を数え…

問題 解法 解答 問題 https://atcoder.jp/contests/joi2020-yo1b/tasks/joi2020_yo1b_b 解法 1 ~ A - 1 文字目と A ~ B 文字目と B + 1 ~ N 文字目をそれぞれ別の文字列に分ける．このうち A ~ B 文字目のものを反転させればよい．これは std::string の sub…

問題 解法 解答 問題 https://atcoder.jp/contests/joi2020-yo1b/tasks/joi2020_yo1b_a 解法 3 つの値のうち大きいもの 2 つの和は 3 つの和から最も小さいもの 1 つを引いたものと等しいから，答えは A + B + C - min({A, B, C}) となる．O(1)． 解答 https…

問題 解法 解答 問題 https://yukicoder.me/problems/no/915 解法 まず C が 1 であるときはクッキーを増やすことが出来ないので，答えは -1 となる．そうでないときは必ず A 枚まで増やすことが出来る． 操作を逆に考え，A 枚あるクッキーを 0 枚まで減らす…

問題 解法 解答 問題 https://yukicoder.me/problems/no/914 解法 国 [1, N / 2) での買い物の仕方と，国 [N / 2, N] での買い物の仕方をそれぞれ全列挙し，前者のそれぞれの金額について，後者との和が最も K に近くなるような後者の買い物の仕方を二分探索…

問題 解法 解答 問題 https://atcoder.jp/contests/abc136/tasks/abc136_e 解法 最終的な答えを g，操作後の A_i の値を a_i とすると，a_i % g == 0 であるから，(a_1 + a_2 + ... + a_N) % g == 0 であり，A 全体の総和は操作によって変化しないから，(A_1…

問題 解法 解答 問題 https://atcoder.jp/contests/abc136/tasks/abc136_d 解法 操作の回数が十分に大きいので，子供たちは "RL" となっているような 2 つの連続するマスを行き来するようになる．子供のいるマスが R であるとき，そのマスより右にある最も近…

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

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/mad-time-traveler 解法 行先の候補にコスト 0 の有向辺を張ったグラフを考える．そして，各頂点に世界線変動率を 7 で割った余りごとに状態を持たせる拡張ダイクス…

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/lets-shoot/problem 解法 以下の DP を考える． dp(i, a, b, c) := i - 1 番目まで見て Type 1 に a 回，Type 2 に b 回，Type 3 に c 回トレーニングしたとき，i 番…

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/k-customers-2 解法 一つ目のクエリは，各お客さんの入店・出店時刻を独立に考えることが出来るから，X と Y を昇順にソートしておき，std::upper_bound() を用いる…

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/2-82 解法 まず，仕事を開始時刻が早い順にソートしておく．次に，以下の DP を考える． dp(i) := 次に i 番目の仕事をすることが可能な時，i 番目以降の仕事で得ら…

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/i-is-this-tournament-correct 解法 チームを試合数の少ない順にソートしておく．試合数が 1 であるもの（同率が複数ある場合は適当な 1 チーム）をその次に試合数の…

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/osmium1008-and-timetravel 解法 年数が負の値になりうるので，全て 2*10^5 を加算して考える．ここで以下の DP を考える． dp(i, j) := i - 1 個目までの飴を使い，…

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/disastrous-gemini 解法 A_i - B_i の差が大きい問題の時にクーラーを使うのが最適．初めに A_i の和と A_i - B_i の値を降順にソートしておき，A_i の和から A_i - …