問題 解法 解答 問題 https://atcoder.jp/contests/abc135/tasks/abc135_e 解法 考察をしやすくするため X >= Y >= 0 となるように X, Y を変換してしまう．変換した場合は，答えを出力する際に元の X, Y に当てはまるように再度復元する必要があるので注意…

問題 解法 解答 問題 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/tkppc4-2/tasks/tkppc4_2_a 解法 まず y 座標は 0 以上で偶数でなければならない．ここが一番引っかかるポイントだと思う． y 方向に + の方向にしか移動できないので，移動回数 t が求まる．この移動回数…

結果 A - Harmony B - 0 or 1 Swap C - City Savers D - Digits Parade 結果 6 問中 3 問正解（600 / 2100 点, 6:57），4500 位中 983 位，パフォーマンス 1289，新レート 1462 (-18)．A - C 問題を早く通すことができたのはよかったが，最後まで D 問題を通…

問題 解法 解答 問題 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 問題で問われている奇…

7/21 に選考結果が来ると思いきや，1 日ほど遅れたみたいですね（選考がかなり難航していた？）．去年も参加して今年も通ることができたのでよかったです．例年以上に一般枠での応募が多かったようで，TL の方々でも落ちている方がいらっしゃるようです．も…

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