ferinの競プロ帳

競プロについてのメモ

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人を選んだとき…

Codeforces Round #513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2) E. Sergey and Subway

問題ページ 解法 辺を追加する前と後のグラフでの最短経路の変化について考える。距離が2の頂点対が結ばれて距離1になる。したがって元の最短距離がxであればceil(x/2)となる。d[i][j] = (辺を追加する前のグラフの頂点i,j間の最短距離) とする。答えはsum(c…

Codeforces Round #516 (Div. 1) B. Labyrinth

問題ページ 解法 dijkstraを行う。あるマスにたどり着くときに取るべきルートは高々2通りなので右に移動する回数を最小にしたときと左に移動する回数を最小にしたときそれぞれについて考える。d[y][x]=(マス(y,x)にたどり着くまでの(右移動回数,左移動回数))…

Codeforces Round #516 (Div. 1) C. Dwarves, Hats and Extrasensory Abilities

問題ページ 解法 2^30=10^9を使ってうまく二分割できるように構成する。まずx軸上に30点置けるような間隔で順番に置いていく。異なる色がでてきたタイミングで二分割する線のうち1端点が決まる。次にもう片方の端点を決定する。x=0,y=1e9,x=1e9の線上で3e9点…

Codeforces Round #518 (Div. 1) A. Array Without Local Maximums

問題ページ 解法 制約がDPをしろと言っているのでDPを考える。dp[i][j][k]=(i番目まで見ていてa[i]=jで{a[i-1]<a[i], a[i-1]=a[i], a[i-1]>a[i]}のときの組み合わせ数)とする。dp[i]を求めるのにはdp[i-1]さえあれば求められる。よってN個持つのではなく2個もって使い回す。dpの遷移を考</a[i],>…

Codeforces Round #518 (Div. 1) B. Multihedgehog

問題ページ 考えたこと 各頂点を根として判定をするO(N^2)はできそう 全方位木DPかなあとか考える 冷静になると根になりそうなのはグラフの中心しかない 木の直径はdouble-sweepで求められるので直径を構成するパスの端点から距離が等しい頂点が中心 木の中…

2018-2019 ICPC, NEERC, Southern Subregional Contest C. Cloud Computing

問題ページ 解法 i日目に使用するplanはcoreの値段が安い方から順にK個取っていく貪欲で決定できる。 i日目に存在しているplanについて2つのBITを用いて管理する。cnt[i]=値段がiで使えるcoreの個数、sum[i]=値段がiのcoreを使うのにかかる値段の和とする。 …

SoundHound Programming Contest 2018 Masters Tournament 本戦 D - Propagating Edges

問題ページ 考えたこと addとcheckだけなら簡単 completeで辺がO(N^2)本できるので辺を持つとやばい 辺はやばいけど頂点を持てばO(N)個しかない completeで完全グラフになった頂点集合をまとめておけばよさそう checkはaddで追加された辺に該当するものがあ…

Codeforces Round #396 (Div. 2) D. Mahmoud and a Dictionary

問題ページ 考えたこと グラフのつなぎ方が2種類 蟻本の食物連鎖と実質同じ 頂点を2倍したunionfindを使って矛盾がなければつなぐという処理を繰り返す これでYES,NOには答えられる 単語の関係を答えるクエリはufでつながっているか確認すればよい #include <bits/stdc++.h></bits/stdc++.h>…

ARC097 E - Sorted and Sorted

問題ページ 解法 転倒数が答えになるので転倒数の定義を考える。最初の数列をA、最終状態の数列をBとする。(転倒数) = (A[ia]=B[ib]=x,A[ja]=B[jb]=yとしたときにia<jaかつib>jbとなるペア(x,y) (x</jaかつib>

AOJ2401 Equation

問題ページ 解法 変数は高々10種類なので'T'と'F'の割り当ては2^10通りしかない。=で分割しておけばequationを用意する必要はない。構文解析はO(|S|)でできるので割り当てを全通り試して等しくならないものがあれば'NO'、そうでなければ'YES'を出力する。以…

AOJ2613 Unordered Operators

問題ページ 解法 まず演算子の優先順序が*>+>-となっている場合のBNFを書いてみる。左再帰と演算子の優先順序に気をつけつつ書くと以下のようになる。 <expr1> = <expr2> ['-' <expr2>]* <expr2> = <expr3> ['+' <expr3>]* <expr3> = <factor> ['*' <factor>]* <factor> = '(' <expr1> ')' | <number> 他の優先順序の場合についても同様にBNFを書ける。</number></expr1></factor></factor></factor></expr3></expr3></expr3></expr2></expr2></expr2></expr1>…

Tenka1 Programmer Contest E - Equilateral

問題ページ 考えたこと 45度回転 これ以降チェビジェフ距離で考える 距離が等しい点はある正方形上の点になる 2点を固定してその2点のどちらとも距離が等しい点を探す 各点を中心として2点間の距離*2を1辺の長さとする正方形を書く 2点どちらとも距離が等し…