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

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

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

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

問題 解法 解答 問題 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/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/abc133/tasks/abc133_e 解法 適当な頂点を根とする根付き木を考える．根から DFS をしていく．頂点 v にいるとき，その頂点の子の配色の通り数を考える．子は頂点 v の親と頂点 v の色それぞれと互いに異な…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_l 解法 以下の DP を考える． dp(i, j) := 頂点 i にいて，今 j 回まで操作が終わった時の，これから得られるスコアの総和の最大値 遷移は今いる頂点 i に留まるか，頂点 i につな…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_k 解法 最終日には必ず写させてもらう必要がある．なぜならば，最終日分の宿題は N - 1 日までで写すことができないから．最終日で写せるページ数 (a_N) 日分は写すことができるの…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_j 解法 N, M <= 20 と小さいので，両校とも考えられる全てのチームの編成を列挙することができる．ここで，各校全ての生徒がどちらかのチームに入るので，A チームのレートの総和…

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

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

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

問題 解法 解答 問題 https://atcoder.jp/contests/abc132/tasks/abc132_e 解法 各頂点についてけんけんぱの k 歩目 (0 <= k <= 2) で到達するために辺を通る回数の最小値を求めることを考える．これは，各頂点について 3 つの状態（けんけんぱの歩数）をも…

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

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

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

問題 解法 解答 問題 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 解法 引き分けがない（勝ち負けが必ずつく）として考えると，ゲームが行われる回数 M は N <= M <= 2 * N - 1 の値を取りうる．それぞれの M に対する決着がつくまでの確率は，a = A / 100, b = B / 100 とおくと， C(M - 1,…

問題 解法 解答 問題 atcoder.jp 解法 まず，求める答えは x 方向の差の絶対値の合計と y 方向の差の絶対値の合計に分解できる．まず x 方向の差の合計について考える．ここで「差が k となるような 2 つの駒の置き方」を求める．これは x 方向の長さは M で…

問題 解法 解答 問題 atcoder.jp 解法 まず c を降順にソートする．ある頂点に c_1 を置いたとき，この頂点に隣り合う頂点に書く数字は c_2, c_3, ... とするのがよい．なぜならば，あえて小さい整数を最初に選んだ頂点に近づけても (c_1 - (小さい整数)) だ…

問題 解法 解答 問題 atcoder.jp 解法 工事期間を [S_i - X_i, T_i - X_i) とすることで，座標 0 を出発する時間から行き止まりになる座標が分かる形に情報を変形することが出来る．このもとで考える．ここで，今工事中である座標をソートした形で持っておく…

問題 解法 解答 問題 atcoder.jp 解法 最初のペア (A_0, B_0) のどちらかを選ぶかによって作れる GCD の最大値は一意に定まる．具体的には，A_0 を選んだ場合，その次のペアにおいては gcd(A_0, A_1) と gcd(A_0, B_1) のうち大きくなる方を選んだ方が自明に…

問題 解法 解答 問題 atcoder.jp 解法 問題文中の条件を式にあらわすと，N = k(m + 1) となる．よって，k を 1 <= k <= √N の範囲で動かし，条件を満たすような m を探せばよい．O(√N)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 各 k ごとに考える． A_1 ~ A_k までの XOR は累積和的に計算できる．この XOR を bit の桁ごとに見ていく．XOR の i bit 目が 1 のとき，A_1 ~ A_k それぞれの i bit 目が反転される．よって，A_1 ~ A_k それぞれの i …

問題 解法 解答 問題 atcoder.jp 解法 木を頂点，枝を辺として無向グラフを考える．このとき，前に移動した枝の隙間の大きさを状態として加えたダイクストラ法を用いて，頂点 1 から各頂点まで休まなければいけない最小の回数が求まる．よって，答えは (dist…

問題 解法 解答 問題 atcoder.jp 解法 答えとして知りたいのは，各ゴーレムがどこのマスにいるかではなく，マスから落ちるかどうか．また，各ゴーレムが最初の位置関係から逆転することはない（一緒の位置になることはある）．これを踏まえると，左のマスか…

問題 解法 解答 問題 atcoder.jp 解法 (a_i, b_i) というカードに対して a_i, b_i を頂点として間に辺を張ることを考える．そうすると，いくつかの輪の関係になる．ここでそれぞれの輪は共通の頂点を持ったりしない． それぞれの輪ごとに数字の種類を決めた…

問題 解法 解答 問題 atcoder.jp 解法 竹を切るとき，最後に切った時刻が分かれば得点が分かる．なので，竹 L_i から竹 R_i の最後に切った時刻の総和を求められれば，各イベントの得点がわかる．最後に切った時刻は区間 [L_i, R_i] ごとに更新されるので，…

問題 解法 解答 問題 atcoder.jp 解法 問題文中に 書き足された各辺 u→vu→v は、ある頂点 uu からその子孫であるような頂点 vv に向かって伸びています とあるので答えは一意に定まる（これを見落としていて複数答えがあるのでないかとちょっと悩んでいた）…