問題 解法 解答 問題 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)． 解…