人権なし

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

AtCoder 400 点問題

square869120Contest #6:C - Infinite Grid

問題 解法 解答 問題 atcoder.jp 解法 スタートからゴールまでの移動は,まずスタートから全てのマスが移動できるマスであるような行まで移動し,ずっと右へ進み続け,その後ゴールのマスまで下がっていくようになる.到達可能である条件は「全てのマスが移…

AtCoder Beginner Contest 124:D - Handstand

問題 解法 解答 問題 atcoder.jp 解法 まず,最も長くなるような 1 の連続する部分列をただ 1 つ作るのが最適になる.なぜならば,わざわざ間に 0 をいくつか挟み複数の 1 が連続する部分を作るのであれば,複数の 1 の部分のうち最も長いものの両端の 0 の…

AtCoder Beginner Contest 123:D - Cake 123

問題 解法 解答 問題 atcoder.jp 解法 XYZ 通り列挙していては当然間に合わないので,まず XY 通り全て列挙する.この XY 通りのうち,K + 1 番目以降は最終的な答えの K 個の中に入らない(これは実験すると明らか).なので XY 通りをソートし,大きいもの…

全国統一プログラミング王決定戦 エキシビジョン:G - 回文スコア

問題 解法 解答 問題 atcoder.jp 解法 最大の長さの回文1つとあまりの文字で長さ 1 の回文をたくさん作るのが最適.O(|S|). 解答 atcoder.jp

「みんなのプロコン 2019」:C - When I hit my pocket...

問題 解法 解答 問題 atcoder.jp 解法 まず,A 枚のクッキーを B 枚のクッキーにするとき,2 枚以上増えなければ得をしない.なぜならば,2 回かかる操作をただクッキーを 1 枚あたらしく得ることに費やした方がよいから.そうでないとき,まずクッキーを A …

AtCoder Beginner Contest 122:D - We Like AGC

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k, l) := 今 i - 1 文字目まで考えて,i - 3 文字目が j,i - 2 文字目が k, i - 1 文字目が l のときの,i 文字目から先の通り数 と DP を定義する.次の1文字(すなわち i 文字目)を決めるとき 'A', 'T', …

AtCoder Grand Contest 032:A - Limited Insertion

問題 解法 解答 問題 atcoder.jp 解法 前から操作を見るのは実は困難なので,後ろから見ていく.このとき,問題は「場所 i で数字 i を消すことができる.この消し方とは?」と言い換えられる.また,消す場所は消せる場所の中で一番右がよい.なぜならば,…

AtCoder Beginner Contest 120:D - Decayed Bridges

問題 解法 解答 問題 atcoder.jp 解法 グラフから辺を取り除いていくのではなく,辺を追加していくと考える.辺を後ろから追加していった時の「不便さ」を逆にしたものが求める答えになる. 辺を1つ追加したときに改善される「不便さ」は辺の両端の頂点それ…

AtCoder Beginner Contest 119:D - Lazy Faith

問題 解法 解答 問題 atcoder.jp 解法 各クエリごとに x_i より左にある最寄りの神社・寺,x_i より右にある最寄りの神社・寺の場所を計算する.これは std::lower_bound() や std::upper_bound() を用いて O(logA), O(logB) で計算できる.あとは,神社と寺…

AtCoder Beginner Contest 121:D - XOR World

問題 解法 解答 問題 atcoder.jp 解法 A, B >= 10^12 と大きいので愚直な計算では TLE となってしまう. ここで,答えとなる数の k bit 目を明らかにすることを考える.0 から順番に数を 2 進数表記で書いて眺めてみると,1 bit 目は 0, 1, 0, 1, ... と 0, …

AtCoder Beginner Contest 118:D - Match Matching

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := マッチ棒を i 本ちょうど使って出来る最大の数 と DP を定義する.このとき,遷移時に A_i を全て試し,その中で最大の数を DP の答えにすればよい.答えとなる数は非常に大きくなるので,文字列として扱う.O…

AtCoder Beginner Contest 117:D - XXOR

問題 解法 解答 問題 atcoder.jp 解法 K の i bit 目を K_i,K より小さい数 X の i bit 目を X_i とすると, K_40 = X_40 K_39 = X_39 ... K_i > X_i (0 <= i <= 40) となる.ここで,X_(i - 1), X_(i - 2), ... , X_0 は 0 でも 1 でもよい(K との大小に…

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019:C - Different Strokes

問題 解法 解答 問題 atcoder.jp 解法 自分と相手にとって幸福度の高いものを食べたいと考えると,(a_i + b_i) が大きいものから食べていけば最適だと気付く.言い方を変えると,最初に求める答えが -(b_1 + b_2 + ... + b_N) だった場合,ここに最大の (a_i…

AtCoder Beginner Contest 116:D - Various Sushi

問題 解法 解答 問題 atcoder.jp 解法 まず,N 個の寿司を「おいしさ」が大きい順にソートし,大きいものから K 個選び答えの候補にする.このとき選んだ寿司のネタの種類数が k だとしたとき,1 ~ (k - 1) 種類のネタだけで K 個選ぶことは不可能 or 最適で…

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:C - Exam and Wizard

問題 解法 解答 問題 atcoder.jp 解法 まず,A_i < B_i の状況であるものは必ず A_i を B_i まで上げる必要があるのでこれらは答えの個数に加わる. 上げる必要がある準備度の総和を sum とし,準備度が十分であるものの余剰分(B_i - A_i)を降順ソートした…

CODE THANKS FESTIVAL 2018:F - Coins on the tree

問題 解法 解答 問題 atcoder.jp 解法 問題文の条件より,i 枚目のコインをある頂点 v に置くと決めた場合,(i + 1) 枚目以降のコインを頂点 v とその子孫の頂点に置くことが出来なくなる.よって,1 枚目のコインから順に置く場所を決めていく. (i - 1) 枚…

CODE THANKS FESTIVAL 2018:E - Union

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 整数 i が j 個あるとき,これから黒板に書かれている数を1つにする通り数 と DP を定義する.このとき, dp(i, j) = dp(i + 1, (j + k) / 2) (k は 0 <= k <= a_i で (j + k) % 2 == 0 を満たす整数) …

AtCoder Beginner Contest 061:D - Score Attack

問題 解法 解答 問題 atcoder.jp 解法 頂点 1 から N へのスコアを最大化するパス上に閉路があるならば,スコアを無限に大きくできる.これをベルマンフォード法を用いて調べればよい.辺のコストの符号を逆にすることでスコアを最大化できる.O(NM). 解答 …

AtCoder Beginner Contest 057:D - Maximum Average Sets

問題 解法 解答 問題 atcoder.jp 解法 v を降順にソートし,前から A ~ B 個を平均値が小さくならない間通り数を求め,その合計を答えにする.前から i 個取った時の通り数は C( (v の中にある v[i] の個数), (今まで取った中にある v[i] の個数) ) になる.…

AtCoder Beginner Contest 054:D - Mixing Experiment

問題 解法 解答 問題 atcoder.jp 解法 「dp(i, j, k) := 薬品 i まででタイプ A を j タイプ B を k 集めるときの最小コスト」で DP をする.O(N^3). 解答 atcoder.jp

AtCoder Beginner Contest 051:D - Candidates of No Shortest Paths

問題 解法 解答 問題 atcoder.jp 解法 N <= 100 と小さいので,ワーシャルフロイド法を用いて全頂点間の最短コストを更新していく.もし,dist[i][j] > dist[i][k] + dist[k][j] であるならば,辺 (i -> j) はどの最短経路にも含まれない.これを数えていき…

AtCoder Beginner Contest 114:D - 756

問題 解法 解答 問題 beta.atcoder.jp 解法 自然数 k を素因数分解した式を p^a * q^b * r^c とすると,k の約数の個数は (a + 1) * (b + 1) * (c + 1) であるので,これを利用して,75 は 1 * 75, 3 * 25, 3 * 5 * 5, 5 * 15 なので,p, q, r を素数とする…

Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選:B - Sum AND Subarrays

問題 解法 解答 問題 beta.atcoder.jp 解法 2^31 の位から 2^0 の位の順に答えを決定していくことを考える.なぜならば,2^k の位が 1 にすることが可能であるならば,2^k の位をパスしより小さい位で 1 としたとしても答えを 2^k の位を 1 としたときよりも…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選:C - チップ・ストーリー ~白銀編~

問題 解法 解答 問題 beta.atcoder.jp 解法 P_i の最大値を maxP,Q_i の最大値を maxQ とおく.この時,maxP を 1 ~ N で動かすとき,maxQ は [ N / maxP ] になる.P の通り数は maxP^10 - (maxP - 1)^10 になる(なぜならば,最終的な通り数を求める段階…

AtCoder Beginner Contest 113:D - Number of Amidakuji

問題 解法 解答 問題 beta.atcoder.jp 解法 ぱっと見 DP をしたい気持ちになるので,以下のように DP を定義する: dp(h, w) := スタートから h 行 w 列に行くまでのあみだくじの通り数の合計 後は,DP の遷移を考える.この時,今いる行の次(すなわち h + …

Mujin Programming Challenge 2018:D - うほょじご

問題 解法 解答 問題 beta.atcoder.jp 解法 (x, y) の組をグラフ上の1つの頂点に対応させて考える.(x, y) に1回操作してなる数の組 (tx, ty) から (x, y) に辺を張る.そうすると,(x, 0) と (0, y) から到達できる組はいつか操作が終了する組だと分かる…

SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open):B - Neutralize

問題 解法 解答 問題 beta.atcoder.jp 解法 問題を読むと DP という気持ちになるので,以下のように DP を定義する: dp(i, f) := i 番目の要素まで見たときの最大値(f が true の時,効用を0にすることが可能で,f が false の時,効用を0に出来ない) f…

技術室奥プログラミングコンテスト #3:D - 巨大チェスボード

問題 解法 解答 問題 beta.atcoder.jp 解法 偶数行・列の長さの累積和と奇数行・列の長さの累積和の2つを計算しておく.そうすれば,各クエリにおいて座標が (偶数,偶数) と (奇数,奇数) の黒マスの面積の合計が O(1) で計算でき,この2つを足し合わせれ…

Tenka1 Programmer Beginner Contest:C - Align

問題 解法 解答 問題 beta.atcoder.jp 解法 小さい数,大きい数,小さい数,... のように並べていくのが最適だと分かるので,隣り合う要素の差の合計の式を書くと, (a_2 - a_1) + (a_2 - a_1) + ... + (a_(n-1) - a_n) になる.ここで,両端の要素を除いた …

square869120Contest #4:B - Buildings are Colorful!

問題 解法 解答 問題 beta.atcoder.jp 解法 N 個の建物から K 個選び,それらを左から高さが増加していくようにすることを考える.制約より,選び方を bit 全探索する.i 番目の建物の前までの max を前計算で求めて置き,K 個選んだあとは,前計算の結果も…