問題 解法 解答 問題 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) で知れるように前計算しておく．あとは，受付しなければいけない人が連…

問題 解法 解答 問題 yukicoder.me 解法 P = 1 または N / 2 より大きい素数のとき答えは 1．なぜならば，前者は自明で，後者は 2 * P が N を超えてしまうため，1 ~ N の数の中で 2 と P をかけて合成数を作ることが出来ないから． そうでないとき，家 i（i…

問題 解法 解答 問題 atcoder.jp 解法 答えの E * (M_1 * M_2 * ... * M_N) は読み上げられる数字の総和であるので，確率などを気にする必要はない．ルーレットの番号が小さいものからこの総和を求めていく． dp(i) := ルーレット i までで構成出来る数字の…

問題 解法 解答 問題 atcoder.jp 解法 座標圧縮のアルゴリズムを用いればよい．O(NlogN)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 川と変態仮面の動く線分が交差しているかを判定すればよい．O(1)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 最長共通部分列 (LCS) の長さ + 1 が答えになる．LCS は簡単な DP によって求めることが出来る．O(|S||T|)． 解答 atcoder.jp