ferinの競プロ帳

競プロについてのメモ

競技プログラミング

Codeforces Round #539 (Div. 2) F. Sasha and Interesting Fact from Graph Theory

問題ページ 解法 頂点a,bを結ぶパスの辺をe本と固定したときの組み合わせ数を求める。まずn-2個の頂点からパス上のe-1個の頂点を選ぶ方法がP(n-2, e-1)通りである。次にパス上の辺の重みを決定する方法について考える。mをe分割する方法はm個のボールの間(m-…

エクサウィザーズ 2019 E - Black or White

問題ページ 考えたこと i回目までに両方ある/白しかない/黒しかない確率をそれぞれ求めたい これがわかればi回目の答えは (両方ある確率)/2 + (黒しかない確率) になるので解ける 黒しかないを知るには黒がj個あるがわかるとよさそう dp[i番目][黒がj個] = …

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

問題ページ 考えたこと sの順列でX%s_1%s_2%s_3…を求める 制約を見るとDPをしてくださいと言っている dp[i番目][modがj]みたいなの 挿入DP?みたいな感じになりそうだけど遷移がやばそう ここでmodの性質を思い出すとmod xをしたあとにmod y(y >= x)をしても…

エクサウィザーズ 2019 C - Snuke the Wizard

問題ページ 考えたこと i番目にいた人が消える条件は何か?で考えるけどまともな形にならない 方針転換して二分探索をすることにする 消える人数を固定したところで何も嬉しくない i番目が左に消えるときi-1番目も左に消えることに気がつく 単調性があるので…

Codeforces Round #548 (Div. 2) D. Steps to One

問題ページ 考えたこと gcd=gと決め打つと長さの期待値が割と簡単に求まる気がする 長さnの確率は (gの倍数の確率)^(n-1) * (gの倍数以外の確率) っぽい g=2,3 の両方で 6, 6, 6, 6,…, 1みたいなのを重複して数えてる 約数系包除で数えられそう 期待値をちゃ…

FII Code Round #1 Sugarel in Love

問題ページ 解法 dp[i][j] = (頂点i以下の部分木で使用したパスにおいて頂点iの次数がjのときの最大値) としてdpする。(頂点vの部分木において)頂点vを端点とする辺を使用しない場合、子の部分木はどのような選び方をしていたとしても問題ないため遷移は dp[…

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が…