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

問題 解法 解答 問題 atcoder.jp 解法 各さいころの目ごとに得点を K 以上にするために必要な確率を求め，1 / N と掛け合わせたものを合計したものが答えになる．コインが表が出続けなければならない回数は，得点が 2 倍されていく過程をシミュレーションす…

問題 解法 解答 問題 atcoder.jp 解法 "BC" という文字列は分断されたり "B" と "C" が独立して操作に影響を与えることはないので 1 つの文字に置き換えて考えてしまってよい．"BC" を "X" と置き換えると，問題文中の操作は s の連続した部分文字列であって…

問題 解法 解答 問題 atcoder.jp 解法 公差 d が 0 のとき，求める答えは x * x * ... * x となるので x^n． そうでないときについて考える．まず，各項を d で割る．そうすると，t = x * mod_inverse(d) とおくと， t, t + 1, t + 2, ... , t + n - 1 と初…

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

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

結果 A - Sum of Interior Angles B - Sumo D - Maximum Sum of Minimum 結果 6 問中 3 問正解（800 / 2900 点, 49:19），3283 位中 571 位，パフォーマンス 1632，新レート 1597 (+3)．500 点の D 問題を結果的に通すことができてよかったが，解法ミスに気…

結果 A - Apple Pie B - Guidebook C - Switches D - equeue 結果 6 問中 4 問正解（1000 / 2100点, 27:14），5186 位中 371 位，パフォーマンス 1805，新レート 1594 (+27)．目標であった 5 問正解は達成できなかったが，4 問目までを早く通すことができた…

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

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

問題 解法 解答 問題 atcoder.jp 解法 全ての [L_i, R_i] に含まれるカードの枚数を求めればよい．これは，L_i のうち最も大きいものと R_i のうち最も小さいものの差になる．この２つの位置が逆転するとき，答えは 0 となるので注意．O(N)． 解答 atcoder.j…

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

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

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

問題 解法 解答 問題 atcoder.jp 解法 スイッチの数 N が N <= 10 と小さいので，スイッチが on か off かを 1, 0 と置き換え bit 全探索をする．全スイッチの状態それぞれについて電球がつくかどうか問題文にある通りに調べればよい．O(2^N * M)． 解答 atc…

問題 解法 解答 問題 atcoder.jp 解法 問題文中の操作によって，与えられる木の直径は，木の直径となっている 2 つの頂点のうち 1 つを選ぶことによって 1 減らすか，葉でない頂点を選ぶことによって 2 減らすことが出来る．よって，この問題は「木の直径を …

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

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

問題 解法 解答 問題 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 解法 ユークリッドの互除法で各 A_i, B_i の最大公約数は求まる．O(N * log(max(A, B)))． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 (min(A_i, B_i), max(A_i, B_i)) をペアとし，std::set に追加していく．最終的な set のサイズが答えになる．O(NlogN)． 解答 atcoder.jp

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

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

問題 解法 解答 問題 atcoder.jp 解法 dp(i, a, b) := 1 ~ i までの全ての順列のうち，P_k > k となるような k の個数が a，P_k < k となるような k の個数が b である通り数 を考える．1 ~ i - 1 までの順列に新しく i を追加するとき，1 ~ i - 1 までの順…

結果 A - Darker and Darker B - LRUD Game 結果 6 問中 2 問正解（900 / 6400 点, 22:30），1288 位中 486 位，パフォーマンス 1787，新レート 1567 (+27)．A, B 問題を早解き出来たのはよかったが，C 問題と通せず終わってしまったためパフォーマンスがあ…

問題 解法（嘘） 解答 問題 atcoder.jp 解法（嘘） 上下と左右はそれぞれ独立に考えられる．なので，先手が上下左右のうち 1 方向を決めて，その方向に貪欲に動かしていき，もう一方がその逆の方向に貪欲に動かしていくという操作を各方向シミュレーションす…

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

問題 解法 解答 問題 atcoder.jp 解法 受付しなければいけない人がいる時間帯の区間の数が知りたいので，imos 法を用いて「ある時間 t に受付しなければいけない人がいるか？」を O(1) で知れるように前計算しておく．あとは，受付しなければいけない人が連…