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

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

問題 解法 解答 問題 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_d 解法 まず，最も多くの辺が繋がっている頂点がもつ辺の数が必要となる色の数になる．また，ある 1 つの頂点を木の根とし，そこから辺を塗っていく DFS をする．具体的には，(今いる…

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

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

問題 解法 解答 問題 https://atcoder.jp/contests/abc133/tasks/abc133_d 解法 各山に降った雨の総和 S は A_1 + A_2 + ... + A_N であり，山 i と i + 1 に降った雨の総和 x_i + x_(i + 1) は A_i * 2 である．よって，山 1 に降った雨の量 x_1 は S - (A_…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i 解法 A と B を昇順にソートしておき，各 A_i よりも真に大きい B_i の個数を調べる．これは std::upper_bound() を用いて各 A_i につき O(logM) で計算することができる．この…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_h 解法 各駅での乗り換え時間は，その駅につく路線の所要時間に加算してしまってよい．こうすることで，辺だけにコストを乗せることができたのでダイクストラ法を適用できる．ダイ…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_e 解法 まず，辺のコストを座標圧縮しておき扱いやすくしておく．また，辺を辺のコストが昇順になるようにソートしておく．その後 L を 0 から増やしていったときにどのように連結…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_d 解法 与えられた条件式を整理すると， 2 * A_x == P + Q 2 * (A_y + A_z) == P - Q となる (x, y, z) の組を見つければよいと分かる．前者は自明に判定できるので，後者を見つけ…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_b 解法 問題を整理すると，写真がある頂点は 1 つの枝分かれしない直線状のパス上にあるかどうかを判定する問題になる． 適当な頂点を根として DFS をする．DFS のときに「今いる…

問題 解法 解答 問題 https://atcoder.jp/contests/abc135/tasks/abc135_d 解法 以下の DP を考える． dp(i, j) := 0 ~ i 桁目まで見て，13 で割った余りが j のとき，i + 1 桁目以降余りが 5 になるような ? の埋め方の通り数 i 桁目が ? であるときは 0 ~ …

問題 解法 解答 問題 https://atcoder.jp/contests/abc134/tasks/abc134_d 解法 i = N, (N - 1), (N - 2), ... の倍数の順番に考えていく．そうすると i 番目の箱にボールを入れるかどうか決める際 i * 2, i * 3, ... 番目の箱にボールを入れるかどうかは既…

問題 解法 解答 問題 https://atcoder.jp/contests/abc132/tasks/abc132_d 解法 i 回操作が必要なとき，青玉が連続している区間が i 個あるということなので，(N - K) 個ある赤玉の間と左端と右端の (N - K + 1) 個の隙間に青玉の区間を i 個当てはめればよ…

問題 解法 解答 問題 atcoder.jp 解法 ある区間 [l, r] の和が K 以上であるとき，区間 [l, r + 1], [l, r + 2], ... , [l, N] のそれぞれの和も当然 K 以上なので，各 l について最初に区間の和が K 以上となる r が分かればよい．この l, r は尺取り法によ…

問題 解法 解答 問題 atcoder.jp 解法 期限 B が小さいものから順に仕事をこなしていくのが最適になる．B を昇順にソートした後の A において，A_1 + A_2 + ... + A_i <= B_i ならば i 番目の仕事はクリアとなるので，この不等式の左辺をできるだけ小さくす…

問題 解法 解答 問題 atcoder.jp 解法 各行・列について障害物がある x, y 座標をソートして配列に持っておく．これを前処理として行っておく． 各マスについて，そのマスから見て上下左右の最も近い障害物の座標は，前処理で求めておいた配列上で二分探索を…

問題 解法 解答 問題 atcoder.jp 解法 ある任意の頂点を 1 つ選び，その選んだ頂点からほかの全頂点との間の距離の偶奇で色を分ければよい．なぜならば，ある頂点 v, u と最初に選んだ頂点 r との距離がそれぞれ偶奇が等しければ， v -> r -> u の距離は当然…

問題 解法 解答 問題 atcoder.jp 解法 まず，それぞれ 2 人がもう一方がいなかった場合にゴールまでたどり着けるかを調べる．これは，[A, C], [B, D] 中に岩が 2 つ以上連続している箇所があったら乗り越えられないので，到達不可能となる．この時点でどちら…

問題 解法 解答 問題 atcoder.jp 解法 M 回の操作は順序を入れ替えても問題ないので，C_i が大きい順に行っていくのがよい．また，A_i を小さい順に操作するかどうかを決めていく．今見ている操作が i 番目で今見ている要素が j 番目のとき，C_i が A_j より…

問題 解法 解答 問題 atcoder.jp 解法 問題文中の４つの操作は以下のように言い換えられる： 操作①：左端の宝石を捨てるが，最後に元に戻す 操作②：左端の宝石を捨てる，一生もとに戻さない 操作③：右端の宝石を捨てるが，最後に元に戻す 操作④：右端の宝石…

問題 解法 解答 問題 atcoder.jp 解法 食べ物を 1 ~ N の順番に見ていく．また，最初の暫定的な「最強の食べ物」を食べ物 1 としておく．今，食べ物 i を見ているとき，どちらが勝つかどうかは簡単な四則演算で求まる．もし，食べ物 i が勝つときは暫定的な…

問題 解法 解答 問題 atcoder.jp 解法 まず，A = B ならば，答えは -1 になる． そうでないとき，答えは abs(A - B) となる．これは，ある 0 以上の整数 p, q, r を使って，A = pX + r, B = qX + r とあらわすことが出来て，これらから A - B = (p - q)X と…

問題 解法 解答 問題 atcoder.jp 解法 まず，各 s_i 中に含まれる "AB" の数を答えに加算する．これは，どういう順番で文字列を結合させても "AB" はそのままになるから． 問題は各 s_i の最初の 1 文字と最後の 1 文字をどう組み合わせていくかになる．よっ…

問題 解法 解答 問題 atcoder.jp 解法 "RB" や "GG" と並ぶことはない．また，R は N - 1, N 文字目，G は 1, N 文字目，B は 1, 2 文字目に来ることはない．これらの条件のうち 1 つでも当てはまれば答えは No, すべてクリアしていれば Yes となる．O(N)． …

問題 解法 解答 問題 atcoder.jp 解法 x99999... とするのが最適．しかし，N が x99999... という形であった場合，問題文にある X != N という条件を満たせない．そこで，例えば X = N = 199999 となってしまったとき，X = 289999 とすることで回避できる．…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k) := i - 1 日目までで，j 回好意をほのめかし，前回のほのめかしから k 日経過しているときの，i 日目以降に得られる機嫌の合計の最大値 と DP をおく．このとき遷移は，i 日目に好意をほのめかすかどうかの…

問題 解法 解答 問題 atcoder.jp 解法 数列 A のある隣り合う 2 つの要素の一方が負の数でもう一方が正の数であるとき，両方に -1 をかけるという操作はマイナスの符号を負の数のものから正の数のものへ移動させることと同値である． これを踏まえると，A に…

問題 解法 解答 問題 atcoder.jp 解法 スタートからゴールまでの移動は，まずスタートから全てのマスが移動できるマスであるような行まで移動し，ずっと右へ進み続け，その後ゴールのマスまで下がっていくようになる．到達可能である条件は「全てのマスが移…