人権なし

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

AtCoder 600 点問題

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かかる。こ…