問題 解法 解答 問題 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_f 解法 元の数列 (1, 2, ... , N) と新しく構成した数列（ここでは〇で示している）を縦に並べて，同じ数字同士を線で結んでみる．すると以下のようになる． *1 問題で問われている奇…

問題 解法 解答 問題 https://atcoder.jp/contests/abc134/tasks/abc134_e 解法 単調増加列の数を最小化すればよい．既に色を塗った整数以外で新しく単調増加列を構成することを考える．ここで，残っている数字の中で最も大きいもののうち一番左にあるものは…

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

問題 解法 解答 問題 https://atcoder.jp/contests/abc126/tasks/abc126_f 解法 M = 0 のとき，答えは自明に (0, 0)． M = 1 のとき，K = 0 のときしか答えは存在しない． それ以外のとき，K < 2^M ならば答えが存在する．なぜならば，K >= 2^M のときには 0…

問題 解法 解答 問題 https://atcoder.jp/contests/abc126/tasks/abc126_e 解法 (X_i, Y_i) のカードは他方が分かればもう片方もわかる関係である．なので，(a, b), (b, c) とあったとき a が分かれば b も c も同時にわかる．このようなカードの連結成分内…

問題 解法 解答 問題 https://atcoder.jp/contests/agc035/tasks/agc035_c 解法 N = 2^k であるときは No．なぜならば，N - (2 * N) のパス間で k bit 目が 1 であるものはないため，xor を N にすることは不可能だから．そうでないときは全て Yes となる．…

問題 解法 解答 問題 https://atcoder.jp/contests/agc035/tasks/agc035_b 解法 まず，辺の数が奇数の時は答えは No になる．偶数の時は答えを構成することができる． 簡単な場合として根付き木を考える．このとき各頂点の出次数の偶奇は葉から各辺の向きを…

問題 解法 解答 問題 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_e 解法 各頂点についてけんけんぱの k 歩目 (0 <= k <= 2) で到達するために辺を通る回数の最小値を求めることを考える．これは，各頂点について 3 つの状態（けんけんぱの歩数）をも…

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

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

問題 解法 解答 問題 atcoder.jp 解法 x_max, x_min, y_max, y_min の座標となる点が変化するタイミングのみ調べればよい．なぜならば，変化するタイミング間では求める面積は広義単調増加・減少になるので，間ではなく両端のタイミングでその区間での面積の…

問題 解法 解答 問題 atcoder.jp 解法 まず，問題文の解釈から．選んだ部分列の数字を文字列を連結させて読むのではなく，数列としてみたときに等しいものの個数を求める．例えば {1, 3, 3, 3} と {1333} は，各項を文字列としてみて連結させると同じものに…

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

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

問題 解法 解答 問題 atcoder.jp 解法 広義単調増加となっている部分列の個数が答えになる．無駄に最初から全体に +min(A) してから・・・などと考えると反例が出てくるので注意する（1 WA した）． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 頂点 X_1, X_2, ... , X_100000, Y_1, Y_2, ... , Y_100000 をおき，(x, y) に点があるとき頂点 x と y に辺を張ることを考える．こうしてできたグラフ上では長さが 3 のパスができる．このパスの始点と終点を新たに結…

問題 解法 解答 問題 atcoder.jp 解法 完全グラフにおいては最短距離が 2 であるような頂点の組み合わせは 0 通りになる．ここから辺を 1 本ずつ取っていくと，この頂点の組み合わせは 1 つずつ増えていく．よって，まず最初に完全グラフを作り，その後 K 本…

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

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

問題 解法 解答 問題 atcoder.jp 解法 取引所 A でいくつかのどんぐりを金属に変え，取引所 B で金属を全てどんぐりに変えていくつかのどんぐりを金属に変え，取引所 A で金属を全てどんぐりに変えるように行動すればよい．途中の取引所 B で金属を全てどん…

結果 A - Ball Distribution B - Picking Up C - Successive Subtraction 結果 6 問中 2 問正解（400 / 3200 点, 185:44），3470 位中 1820 位，パフォーマンス 904，新レート 1544 (-53)．A, B 問題で深刻な誤読をしてしまい，ペナルティーも時間も多くなっ…

問題 解法 解答 問題 atcoder.jp 解法 A の各要素の正負を反転させることを考える．全ての要素の正負を反転させたり，1 つも反転させないことは不可能．なぜならば，1 回以上の操作によって選ばれた 2 つの要素は x - y という形になり，最低 1 つは反転させ…

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

問題 解法 解答 問題 atcoder.jp 解法 a + b == a XOR b となるためには，a と b で任意の bit の桁が 1 と 1 になってはいけない．1 XOR 1 は 0 となるが，1 + 1 は 10 と繰り上がりが発生し a + b != a XOR b となってしまう． L の中で bit が立っている…

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

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

結果 A. Filling Shapes B. Plus from Picture C. Beautiful Lyrics 結果 ６問中２問正解（1070 点），5543 位中 1070 位，新レート 1620 (+33, Highest)．B 問題が Systest で落ちてしまったが，何とかレートをあげることができ，青コーダーになれたのでよ…

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