ferinの競プロ帳

競プロについてのメモ

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 W - Intervals

問題ページ 解法 dp[i] = (i文字目までを考え、i文字目を'1'にしたときのスコアの最大) としてDPする。dp[i] = (区間[0,i)に内包される区間で得られるスコア, 全部'0'で0以上にはなる) + (i文字目を'1'にしたことで得られるスコア) = max(0, max(dp[j], j

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 47 E. Intercity Travelling

問題ページ 解法 部分集合全通りを求めるのは無理なので見方を変えてi-1km~ikmの区間を難易度a[j]で通過する確率を求めるとしてみる。n=4で試してみると以下の図のようになる。 図を辺ごとに縦に区切るのではなく、難易度a[i]ごとに横で区切ってみる。すると…

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…

ARC086 E - Smuggling Marbles

問題ページ 解法 木DPを行う。dp[i][j][k]=(j回動かしたときに頂点iにk個(=0,1か2個以上)ビー玉が存在するような初期配置の数) と定義してDPをする。頂点iの子をc_0とc_1とする。これらの子の情報dp[c_0]とdp[c_1]をマージする方法について考える。j=0~d(頂…

Mail.Ru Cup 2018 Round 2 C. Lucky Days

問題ページ 解法 g=gcd(ta,tb)とする。各区間についてgずらすことが可能である。la, lbを両方0に近づけるあたりに最適な区間がある。なので0に近づけた辺りをある程度探索すれば答えが求まる。 [la, ra] と [lb, rb] の共通部分はmax(0, min(ra,rb)-max(la,l…

Codeforces Round #523 (Div. 2)

問題ページ 考えたこと 区間スケジューリングっぽい DPができる気がしないので貪欲を考える 区間スケジューリングでは最後に仕事をした時刻を1つ持てばいいが今回は複数ある あるTV番組[l,r]があったとき、前に見たTV番組のうち終端がl未満で最大の区間につ…

Codeforces Round #520 (Div. 2) D. Fun with Integers

問題ページ 問題概要 次の条件を満たすとき整数aから整数b(2<=|a|,|b|<=n)に変換することができる。 (条件) |x| > 1 となる整数xについてax = b もしくは bx = a を満たすものが存在する。a->b、b->aの変換を以前に行っていない。 この変換をすると|x|点の得…

Technocup 2019 - Elimination Round 2 D. Minimum path

問題ページ 考えたこと 辞書順最小なので前から貪欲に取ることを考える 文字列の最初の方で交換可能でaでないものがあったらaに変えたほうが確実に良い 答えの文字列はaa…aabcdaefのように接頭辞にaが連続している 接頭辞のaが何個か考える 二次元グリッド上…

Educational Codeforces Round 50 (Rated for Div. 2) C. Classy Numbers

問題ページ 解法 桁DPをする。dp[i][j][k] = (i桁目まででA未満が確定しているか(=j)、0以外の数がk個のときの数の個数)とする。jの更新はj or d < (Aのi桁目)とするいつもの、kの更新は0以外なら1足すとすればよい。桁DPの計算量がO(logR)なので全体でO(Tl…

Codeforces Round #509 (Div. 2) E. Tree Reconstruction

問題ページ 考えたこと よくわからないので試しに4頂点のグラフを色々書いてみる 全部の辺に4が出てくる それはそうで最大の頂点番号を取ってくるのだからNは全ての辺に現れる Nが現れない辺があればNOで断定できる Nを中心としたウニを基本に考える 入力にN…

Codeforces Round #519 E. Train Hard, Win Easy

問題ページ 考えたこと 頑張って問題文を読む ペアを組んじゃだめな二人組についてはとりあえず無視する i番目の人のスコアは ans[i] = sum(min(a[i]+b[j],b[i]+a[j])) (i!=j) となる a[i]+b[j] < b[i]+a[j] ⇔ a[i]-b[i] < a[j]-b[j] となる 2人を選んだとき…