ferinの競プロ帳

競プロについてのメモ

競技プログラミング

Educational Codeforces Round 60 D. Magic Gems

問題ページ 解法 dp[i]=(i個分スペースを埋める方法が何通りあるか)としたDPを考える。i個スペースを埋めるためにはmagic gemを一つ置くパターンとmagic gemを分割しnormal gemをM個置くパターンがある。したがってこのDPの遷移は dp[i] = dp[i-m] + dp[i-1]…

Educational Codeforces Round 60 C. Magic Ship

問題ページ 解法 i日目に到達可能な場所がどのようになっているのか考える。(x1,y1)=(0,0)、s="UDRL"のときの例を以下に示す。 風が吹く方向と逆方向に移動すればi日目で到達したマスはi+1日目以降でも到達可能なことがわかる。したがってi日目にはi以下の地…

ARC062 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

問題ページ 解法 立方体の上の面と底面を決めると残りの側面に来る面の色配置は一意に定まる。色の配置がvのタイルが何枚あるか?という情報を計算しておけば何通りあるかは求めることができる。C(N,2)通りを全通り試すことで答えが求まる。 ただし、回転等…

ARC084 E - Finite Encyclopedia of Integer Sequences

問題ページ 解法 まずKが偶数ならば(K/2, K, …, K)となる数列が答えになることがわかる。よってKが奇数のものについてのみ考える。 ナイーブな解法として答えの数列でi番目で数列のa番目をつくるにはi番目の数字が一意に定まるとして前から決めていくような…

ARC065 E - へんなコンパス / Manhattan Compass

問題ページ 解法 まずマンハッタン距離なので45度回転しチェビジェフ距離に変換しておく。 コンパスの移動で穴2つの距離が変わることはない。したがって穴aと穴bの距離Dと等しい穴の組が何個あるのかを考えればよい。穴の組O(N^2)個について全て考えるのは不…

みんなのプロコン 2019 F - Pass

問題ページ 解法 dp[i][j] = (結果の列のi+j番目まで見たときに赤をi個、青をj個使っているとき何通りあるか) でDPをする。DPの遷移は dp[i+1][j] += dp[i][j] 次に赤を置くことが可能 dp[i][j+1] += dp[i][j] 次に青を置くことが可能 の2通りになる。次に赤…

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

問題ページ 解法 とりあえず散歩によって作れる列がどのようなものであるのか実験する。ある区間を往復するときに大きく往復するのではなく一つずつ独立に往復していくと考えられるので各要素は独立に値を決められる。いろいろ実験していると数列の取りうる…

CODE THANKS FESTIVAL 2018 F - Coins on the tree

問題ページ 解法 辞書順最小を求めるときは前から貪欲に決めていくのが典型。まずv[1]=1と決めてみたときに残りの木の状態と操作回数とコイン枚数について条件を満たせるのであればv[1]=1と決定してしまってよい。条件を満たさないのであればv[1]=2として同…

第5回 ドワンゴからの挑戦状 本選 C - Interval and MST

問題ページ 解法 boruvka法を使って最小全域木問題を解く。各連結成分から他の連結成分へつなぐ最もコストが小さい辺をO(N)やO(NlogN)程度で求められるときに有効な方法になる。ある区間が他の区間と交差するのは4パターンに分類できる。 その区間の右側と他…

エイシング プログラミング コンテスト 2019 E - Attack to a Tree

問題ページ 解法 木DPをする。dp[v][i][j] = (頂点vを根とする部分木でi回辺を切っていて頂点vの連結成分以外は問題文の条件を満たし、頂点vの連結成分が全てバッテリー(j=0)orそれ以外(j=1)のときの連結成分の頂点の重みの和の最小) とする。不可能な場合は…

TDPC T - フィボナッチ

問題ページ 解法 きたまさ法メモ - よすぽの日記 この記事を自分なりに理解したメモ 問題では1-indexになっているが0-indexで扱うとする。つまり以下の数列Aの第n項を求めろという問題になる。 A[i] = 1 (i<k) A[i] = A[i-1] + A[i-2] + … + A[i-k] (i>=k) 行列累乗を使えばO(K^3N)で解ける(cf. 蟻本p114</k)>…

EDPC Q - Flowers

問題ページ 解法 花を削除するのではなく条件を満たしつつ追加していくと考える。高さが低い花から順番に挿入していくと考える。dp[i] = (高さがiの花を挿入したときの美しさの最大)としてDPをする。dp[i] = max(dp[j], j

EDPC J - Sushi

問題ページ 解法 寿司がa[i]個乗っている皿がどこにあったとしても選ばれる確率に影響はない。したがってN要素の数列a[i]ではなくcnt[i]=(i個乗っている皿の数)と情報を持つことができる。 dfs(x, y, z) = (1個乗っている皿がx枚、2個乗っている皿がy枚、3個…

AGC030 D - Inversion Sum

問題ページ 考えたこと 全パターンについて数え上げなので確率で考える ペア(A[i], A[j])について反転している確率を求めてこれを足して2^Qを掛ければよさそう A[i]>A[j],i

AGC030 B - Tree Burning

問題ページ 考えたこと まず部分点を取りに行く 木を燃やすときにi番目が燃えているがi-1番目を燃やさずに飛ばすような方法はない 状態がN^2個で収まりそう dp[反時計回りにi個燃やした][時計回りにj個燃やした] = (かかる最大の時間) みたいなDPをしたい 遷…

Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix

問題ページ 解法 bitwise xorなのでbitごとに独立に考えられる。したがってbitごとに考えればa,bは0/1の数列に帰着でき、答えの行列も0/1要素しか持たないと考えてよい。1が書かれている行・列には1を奇数個、0が書かれている行・列には1を偶数個置くような…

Xmas Contest 2018 B - Bit Smaller

問題ページ 解法 入力が与えられないので条件を満たす数を予め全列挙するプログラムをローカルで実行しておきその答えをtextで提出すればよい。数nをa1,b1,a2,b2,…,ak,bk,cと切れ目を入れたときに条件を満たしているような切り方があれば数nを答えに追加すれ…

yukicoder No.776 A Simple RMQ Problem

問題ページ 解法 この記事(Maximum Subarray Sum in a given Range - GeeksforGeeks)のセグメント木を使って解いた。このセグ木では区間[l,r)の連続した部分列の区間和のmaxを求めることができる。セグ木の各頂点に「区間和」「maximum prefix sum」「maximu…

CADDi 2018 E - Negative Doubling

問題ページ 解法 最終的な列はマイナスとプラスが ----/++++ のように並ぶはずである。したがってマイナスとプラスの区切り位置を決めると、+の列/-の列についてそれぞれ考えられる。符号が全て同じであれば4倍する操作を繰り返すと考えればよく、符号を無視…

Codeforces Round #525 (Div. 2) D. Ehab and another another xor problem

問題ページ 解法 xorなのでbitごとに見ていくのが基本的なパターンになる。クエリ回数の上限が62回なので30bit分について2回ずつクエリを飛ばして決めていけばよさそう。大小関係について見ていくので上のbitから順番に決めていくとよさそう。 c=d=0のクエリ…

AGC006 D - Median Pyramid Hard

問題ページ 解法 K番目の値を求めるときは二分探索がよくあるパターンである。二分探索を使うことでK番目の値がX以上か?という判定問題に置き換える。K番目の値がA以上であればA以下の数Bについても判定が真となるので単調性はある。数列をX以上とX未満の2…

AGC029 D - Grid game

問題ページ 解法 高橋くんが動かなかった場合、青木くんも動かなければゲームが終了するので高橋くんは動けるならば動くべきである。各行について駒がたどりつける最大の列txが求まっていたとする。このときtx以下の地点に障害物が存在していればその障害物…

AGC029 B - Powers of two

問題ページ 解法 各値を頂点に持ち、値を足すと2べきになる頂点間に辺を張るとする。このグラフで最大マッチングが求められればいいが、N<=10^5だと二部マッチングでもTLEしそうなので貪欲なりDPなりでマッチングを高速に求められる構造がなければできなさそ…

AGC029 A - Irreversible operation

問題ページ 解法 操作を終えたあとの最終的な文字列がどうなっているか考えます。BWと並んでいるところがあればまだ操作が続くはずなので一度Bが出てきた後にWがでてくることはありません。したがって最終的な文字列はWW…WWBB…BBとなるはずです。Wの前にBが…

天下一プログラマーコンテスト2015本戦 E - 天下一コップ

問題ページ 解法 順列全てや部分列それぞれについて計算しろといった問題で与えられた通りに数えるのはTLEしてしまうので別の視点から数え上げるのが有効な場合が多い。今回の問題ではi番目の長方形が底でj番目の長方形の高さまで水が入っているような並び方…

Educational Codeforces Round 55 (Rated for Div. 2) E. Increasing Frequency

問題ページ 解法 ある区間[l,r]を選択したときに最適なkの値について考える。[l,r]の中で最も出現頻度が多い値がcになるようにkを設定すればよい。したがって区間[l,r]に操作をしたときの答えは([l,r]以外のcの数) + ([l,r]で出現頻度が最も多い回数) - ([l,…

Technocup 2019 - Elimination Round 3 D. Barcelonian Distance

問題ページ 解法 最短経路としてあり得るのは直線ax+by+c=0に高々1回乗るような経路しかありえない。x=sxかy=sy上を移動したあと直線上を移動しx=gxかy=gy上を移動するパターンか直線上を移動せずに距離abs(sx-gx)+abs(sy-gy)を移動するようなパターンをすべ…

Educational Codeforces Round 54 D. Edge Deletion

問題ページ 考えたこと 最短路DAGを考えると無向グラフで最短路に使われる辺だけを抽出すると木になるはず dijkstraの途中で遷移に使った辺を覚えておけば最短路に使われる辺はわかる k>=n-1であれば使われた辺すべてを出力すればよい k<n-1であれば頂点1に連結になるような辺をk本選べばよい 最短経路長が短い頂点の遷移に使った辺から取っていけば非連結な辺を取ることはないはず 最短路に使う辺を列挙して最短経路長が短いものからmin(n-1,k)本の辺を取ればよさそう #include <bits/stdc++.h> using namespace std</n-1であれば頂点1に連結になるような辺をk本選べばよい>…

第5回 ドワンゴからの挑戦状 予選 C - k-DMC

問題ページ 解法 3つ組のうちaとcを動かしていくことを考える aがcを追い抜かすことはない [a, c]についてs[a]=='D'であれば答えに sum(区間[l,i]のMの数) (a<=i<=c, s[i]=='C') を加算する 現在の区間についてMの数(=mnum)、Cの数(=cnum)、DMC(=now)の数を…

第5回 ドワンゴからの挑戦状 予選 B - Sum AND Subarrays

問題ページ 考えたこと 上のbitから順番に決めていく 2^i > 2^i-1 + … + 2^0 より上のbitから貪欲に決めてよいはず 2^i の位が1となっている区間がk個以上存在した場合、2^iを1とできる 一旦1と決めた位が合った場合、その下の位で使える区間が限定される i…