人権なし

競プロで解いた問題や開発の進捗などの記録です

AtCoder 600 点問題

AtCoder Beginner Contest 134:F - Permutation Oddness

問題 解法 解答 問題 https://atcoder.jp/contests/abc134/tasks/abc134_f 解法 元の数列 (1, 2, ... , N) と新しく構成した数列(ここでは〇で示している)を縦に並べて,同じ数字同士を線で結んでみる.すると以下のようになる. *1 問題で問われている奇…

AtCoder Beginner Contest 126:F - XOR Matching

問題 解法 解答 問題 https://atcoder.jp/contests/abc126/tasks/abc126_f 解法 M = 0 のとき,答えは自明に (0, 0). M = 1 のとき,K = 0 のときしか答えは存在しない. それ以外のとき,K < 2^M ならば答えが存在する.なぜならば,K >= 2^M のときには 0…

AtCoder Beginner Contest 130:F - Minimum Bounding Box

問題 解法 解答 問題 atcoder.jp 解法 x_max, x_min, y_max, y_min の座標となる点が変化するタイミングのみ調べればよい.なぜならば,変化するタイミング間では求める面積は広義単調増加・減少になるので,間ではなく両端のタイミングでその区間での面積の…

AtCoder Beginner Contest 131:F - Must Be Rectangular!

問題 解法 解答 問題 atcoder.jp 解法 頂点 X_1, X_2, ... , X_100000, Y_1, Y_2, ... , Y_100000 をおき,(x, y) に点があるとき頂点 x と y に辺を張ることを考える.こうしてできたグラフ上では長さが 3 のパスができる.このパスの始点と終点を新たに結…

diverta 2019 Programming Contest 2:D - Squirrel Merchant

問題 解法 解答 問題 atcoder.jp 解法 取引所 A でいくつかのどんぐりを金属に変え,取引所 B で金属を全てどんぐりに変えていくつかのどんぐりを金属に変え,取引所 A で金属を全てどんぐりに変えるように行動すればよい.途中の取引所 B で金属を全てどん…

AtCoder Grand Contest 034:B - ABC

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

M-SOLUTIONS プロコンオープン:E - Product of Arithmetic Progression

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

CPSCO2019 Session3:F - Flexible Permutation

問題 解法 解答 問題 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 Grand Contest 033:B - LRUD Game

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

いろはちゃんコンテスト Day1:K - ルーレット

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

Tenka1 Programmer Contest 2019:D - Three Colors

問題 解法 解答 問題 atcoder.jp 解法 a の和を sum とすると max({R, G, B}) < sum / 2 が成り立っていれば三角形を構成出来る.なので,R, G, B のどれかが 1 つでも sum / 2 以上の値であるとき,三角形は構成できない. ここで,塗り分ける場合の数全体…

AtCoder Regular Contest 079:E - Decrease (Judge ver.)

問題 解法 解答 問題 atcoder.jp 解法 (解法の証明をせず通してしまった) 数列 a の中の最大値である箇所が何回かの操作によって最小値になるまでにかかる最小の操作の回数を二分探索で求め,操作後の a をソートし,またこの二分探索を繰り返していき,最…

AtCoder Regular Contest 075:E - Meaningful Mean

問題 解法 解答 問題 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 Regular Contest 071:E - TrBBnsformBBtion

問題 解法 解答 問題 atcoder.jp 解法 各クエリで与えられる部分文字列を A だけの最も短い文字列にすることを考える.まず,部分文字列中の B を全て AA に変換し,残った A だけの文字列のうち AAA と 3 つ A が並んでいる箇所は空文字列に出来るので出来…

AtCoder Regular Contest 097:E - Sorted and Sorted

問題 解法 解答 問題 atcoder.jp 解法 次の DP を考える: dp(i, j) := 白いボールを 1 ~ i 番までソートし,黒いボールを 1 ~ j 番までソートしたときの,残っている 2 * N - (i + j) 個のボールをそれぞれの色でソートするのにかかる操作回数の最小値 この…

エクサウィザーズ 2019:D - Modulo Operations

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 今黒板に書かれている数が i で,j 個 S から取り出したとき,これからの操作で考えうる最後に書かれる数の和 と DP をたてる.また,ある数字 x よりも大きい数字 y で mod をとっても x は変わらないので…

「みんなのプロコン 2019」:D - Ears

問題 解法 解答 問題 atcoder.jp 解法 dpR1(i) := 座標 i にいて,これから右に行き座標 i に戻ってこないとき,i 番目の耳以降操作しなければいけない回数の最小値 dpR2(i) := 座標 i にいて,これから右に行き座標 i に戻ってくるとき,i 番目の耳以降操作…

AtCoder Grand Contest 028:B - Removing Blocks

問題 解法 解答 問題 atcoder.jp 解法 各ブロックについてそのブロックの重さが答えに加算される回数を求めたい.ブロック i の重さが加算される回数を求める.ブロック i とブロック j が連結である場合の数を P(i, j) とおく.P(i, j) (1 <= j <= N) の和…

AtCoder Regular Contest 067:E - Grouping

問題 解法 解答 問題 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 Grand Contest 001:C - Shorten Diameter

問題 解法 解答 問題 atcoder.jp 解法 「直径が K より外の頂点を削除する」と「直径が K 以内の頂点を残す」のは同じなので,後者に置き換えて,残す頂点を最大化することを考える. K が偶数の場合,各頂点から K / 2 以内の頂点を残すことになるので,全…

AtCoder Grand Contest 003:C - BBuBBBlesort!

問題 解法 解答 問題 atcoder.jp 解法 連続する3つの要素を逆順にする操作は真ん中の要素を挟んでいる2つの要素を swap することと同じなので,A の奇数番目の要素と偶数番目の要素それぞれがソートされる.なので,ソートされた後の A で奇数番目の要素で…

AtCoder Grand Contest 029:B - Powers of two

問題 解法 解答 問題 beta.atcoder.jp 解法 まず,A を大きい順に見ていく.このとき,今見ている要素が一番大きいので,もしペアにすることが出来る要素があるならば,それは1つに定まる.ここで,あえてペアにしないことは得にならない(最終的な答えが -…

AtCoder Regular Contest 103:D - Robot Arms

問題 解法 解答 問題 beta.atcoder.jp 解法 まず,それぞれの到達させたい点と原点の距離の偶奇が一致することを確かめる.一致しなければ,どんなに頑張っても不可能. それぞれの到達させたい点と原点の距離の偶奇が一致するとき,ロボットの腕の長さを 2^…

AtCoder Regular Contest 064 : E - Cosmic Rays

問題 解法 解答 問題 E - Cosmic Rays 円が N 個あり、できるだけその円の中に入りながらスタート地点からフィニッシュ地点まで行きたい。この時の最短距離を求める問題。 解法 N <= 10^3 と優しいので、円の中心同士の距離をコストとして辺をつくり、グラフ…

AtCoder Grand Contest 026 : B - rng_10s

問題 解法 解答 問題 B - rng_10s りんごマートはある日の朝に開店し,その時にはジュースの在庫が AA 本ありました。 すぬけ君は毎日昼にりんごマートでジュースを BB 本買います。 りんごマートでは毎日夜にジュースの在庫を確認し,CC 本以下だった場合,…

AtCoder Regular Contest 100 : D - Equal Cut

問題 D - Equal Cut 長さ N の整数列 A を4つの連続する部分列に分けたとき、4つの数列のそれぞれの和の最大値と最小値の差を最小化すると差はどうなるか、という問題。 解法 4つに分けるので半分の半分だと考える。最初に半分に切るところは全通り試すと…

AtCoder Regular Contest 098 : E - Range Minimum Queries

問題 E - Range Minimum Queries 長さ N の数列 A から「長さ K の連続する部分列を1つ選び、その中の最小値を数列から取り除く」動作を Q 回行う。Q 回で取り除いた Q 個の数値の最大値と最小値の差の最小値を求める問題。 解法 最小値を固定させると、ま…

AtCoder Regular Contest 061 : E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip N 個の駅と M 個の路線があり、各路線には運営会社が決められている。同じ運営会社で連結の路線はどれだけ乗ってもコストはかからないが、運営会社をまたいで載る場合はコストがそれごとに1かかる。こ…