AtCoder 600 点問題
問題 解法 解答 問題 https://atcoder.jp/contests/abc151/tasks/abc151_f 解法 求める半径を二分探索で求める． 半径を r に決めたとき，任意の 2 点を円の中心，半径を r とした円の交点は 2 つに定まる．そして，この 2 点それぞれを円の中心，半径を r …
問題 解法 解答 問題 https://atcoder.jp/contests/abc148/tasks/abc148_f 解法 高橋君は木のどこかの葉に逃げるのが適切なので，それぞれの葉に逃げたときの青木君の移動回数を求め，それらの max を答えとすればよい． まず，ある葉（頂点 t）までの距離 d…
問題 解法 解答 問題 https://atcoder.jp/contests/abc144/tasks/abc144_f 解法 M 本の辺それぞれをふさいだときの E を計算していては O(M^2) となり間に合わない．ここで，ある頂点 v から出る辺のうち 1 つを塞ぐとするとき，v とつながる先の頂点から頂…
問題 解法 解答 問題 https://atcoder.jp/contests/abc145/tasks/abc145_f 解法 まず，数列 H を扱いやすいように座標圧縮しておく（最小を 1 としなければいけないことに注意）．そうすることで H の要素は高々 N + 1 以下になる．また，H[k] < H[k + 1] と…
問題 解法 解答 問題 https://atcoder.jp/contests/abc146/tasks/abc146_f 解法 辞書順最小にしたいので，マス N からマス 0 に向かって「ゲームオーバーマス」を避けながら，すごろくの目を最大化しながら進んでいけばよい．途中「ゲームオーバーマス」が M…
問題 解法 解答 問題 https://atcoder.jp/contests/abc134/tasks/abc134_f 解法 元の数列 (1, 2, ... , N) と新しく構成した数列（ここでは〇で示している）を縦に並べて，同じ数字同士を線で結んでみる．すると以下のようになる． *1 問題で問われている奇…
問題 解法 解答 問題 https://atcoder.jp/contests/abc126/tasks/abc126_f 解法 M = 0 のとき，答えは自明に (0, 0)． M = 1 のとき，K = 0 のときしか答えは存在しない． それ以外のとき，K < 2^M ならば答えが存在する．なぜならば，K >= 2^M のときには 0…
問題 解法 解答 問題 atcoder.jp 解法 x_max, x_min, y_max, y_min の座標となる点が変化するタイミングのみ調べればよい．なぜならば，変化するタイミング間では求める面積は広義単調増加・減少になるので，間ではなく両端のタイミングでその区間での面積の…
問題 解法 解答 問題 atcoder.jp 解法 頂点 X_1, X_2, ... , X_100000, Y_1, Y_2, ... , Y_100000 をおき，(x, y) に点があるとき頂点 x と y に辺を張ることを考える．こうしてできたグラフ上では長さが 3 のパスができる．このパスの始点と終点を新たに結…
問題 解法 解答 問題 atcoder.jp 解法 取引所 A でいくつかのどんぐりを金属に変え，取引所 B で金属を全てどんぐりに変えていくつかのどんぐりを金属に変え，取引所 A で金属を全てどんぐりに変えるように行動すればよい．途中の取引所 B で金属を全てどん…
問題 解法 解答 問題 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 解法 dp(i, a, b) := 1 ~ i までの全ての順列のうち，P_k > k となるような k の個数が a，P_k < k となるような k の個数が b である通り数 を考える．1 ~ i - 1 までの順列に新しく i を追加するとき，1 ~ i - 1 までの順…
問題 解法（嘘） 解答 問題 atcoder.jp 解法（嘘） 上下と左右はそれぞれ独立に考えられる．なので，先手が上下左右のうち 1 方向を決めて，その方向に貪欲に動かしていき，もう一方がその逆の方向に貪欲に動かしていくという操作を各方向シミュレーションす…
問題 解法 解答 問題 atcoder.jp 解法 答えの E * (M_1 * M_2 * ... * M_N) は読み上げられる数字の総和であるので，確率などを気にする必要はない．ルーレットの番号が小さいものからこの総和を求めていく． dp(i) := ルーレット i までで構成出来る数字の…
問題 解法 解答 問題 atcoder.jp 解法 a の和を sum とすると max({R, G, B}) < sum / 2 が成り立っていれば三角形を構成出来る．なので，R, G, B のどれかが 1 つでも sum / 2 以上の値であるとき，三角形は構成できない． ここで，塗り分ける場合の数全体…
問題 解法 解答 問題 atcoder.jp 解法 （解法の証明をせず通してしまった） 数列 a の中の最大値である箇所が何回かの操作によって最小値になるまでにかかる最小の操作の回数を二分探索で求め，操作後の a をソートし，またこの二分探索を繰り返していき，最…
問題 解法 解答 問題 atcoder.jp 解法 a_l, a_(l + 1), ... , a_r の平均が K 以上であるには (a_l - K) + (a_(l + 1) - K) + ... + (a_r - K) が 0 以上であればよいので，a_i から K を引いた値で考える．また，a の累積和 a_imos を考えると，a_l ~ a_r …
問題 解法 解答 問題 atcoder.jp 解法 各クエリで与えられる部分文字列を A だけの最も短い文字列にすることを考える．まず，部分文字列中の B を全て AA に変換し，残った A だけの文字列のうち AAA と 3 つ A が並んでいる箇所は空文字列に出来るので出来…
問題 解法 解答 問題 atcoder.jp 解法 次の DP を考える： dp(i, j) := 白いボールを 1 ~ i 番までソートし，黒いボールを 1 ~ j 番までソートしたときの，残っている 2 * N - (i + j) 個のボールをそれぞれの色でソートするのにかかる操作回数の最小値 この…
問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 今黒板に書かれている数が i で，j 個 S から取り出したとき，これからの操作で考えうる最後に書かれる数の和 と DP をたてる．また，ある数字 x よりも大きい数字 y で mod をとっても x は変わらないので…
問題 解法 解答 問題 atcoder.jp 解法 dpR1(i) := 座標 i にいて，これから右に行き座標 i に戻ってこないとき，i 番目の耳以降操作しなければいけない回数の最小値 dpR2(i) := 座標 i にいて，これから右に行き座標 i に戻ってくるとき，i 番目の耳以降操作…
問題 解法 解答 問題 atcoder.jp 解法 各ブロックについてそのブロックの重さが答えに加算される回数を求めたい．ブロック i の重さが加算される回数を求める．ブロック i とブロック j が連結である場合の数を P(i, j) とおく．P(i, j) (1 <= j <= N) の和…
問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 人をグループ人数 j 以上のグループに分けるときの通り数 と DP を定義する．このとき， dp(i, j) = dp(i - j * k, j + 1) * c / k! (C <= k <= D, c = C(i, j) * C(i - j, j) * ... * C(i - j * (k - 1)…
問題 解法 解答 問題 atcoder.jp 解法 「直径が K より外の頂点を削除する」と「直径が K 以内の頂点を残す」のは同じなので，後者に置き換えて，残す頂点を最大化することを考える． K が偶数の場合，各頂点から K / 2 以内の頂点を残すことになるので，全…
問題 解法 解答 問題 atcoder.jp 解法 連続する３つの要素を逆順にする操作は真ん中の要素を挟んでいる２つの要素を swap することと同じなので，A の奇数番目の要素と偶数番目の要素それぞれがソートされる．なので，ソートされた後の A で奇数番目の要素で…
問題 解法 解答 問題 beta.atcoder.jp 解法 まず，A を大きい順に見ていく．このとき，今見ている要素が一番大きいので，もしペアにすることが出来る要素があるならば，それは１つに定まる．ここで，あえてペアにしないことは得にならない（最終的な答えが -…
問題 解法 解答 問題 beta.atcoder.jp 解法 まず，それぞれの到達させたい点と原点の距離の偶奇が一致することを確かめる．一致しなければ，どんなに頑張っても不可能． それぞれの到達させたい点と原点の距離の偶奇が一致するとき，ロボットの腕の長さを 2^…
問題 解法 解答 問題 E - Cosmic Rays 円が N 個あり、できるだけその円の中に入りながらスタート地点からフィニッシュ地点まで行きたい。この時の最短距離を求める問題。 解法 N <= 10^3 と優しいので、円の中心同士の距離をコストとして辺をつくり、グラフ…
問題 解法 解答 問題 B - rng_10s りんごマートはある日の朝に開店し，その時にはジュースの在庫が AA 本ありました。 すぬけ君は毎日昼にりんごマートでジュースを BB 本買います。 りんごマートでは毎日夜にジュースの在庫を確認し，CC 本以下だった場合，…
