ferinの競プロ帳

競プロについてのメモ

Codeforces

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本選べばよい>…

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を使うのにかかる値段の和とする。 …

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

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

Codeforces Round #499 (Div. 2) E. Border

問題ページ Problem - E - Codeforces 考えたこと k進数の下一桁はkで割った余りに等しい a[i] mod k を取っておいてよさそう dp[i番目][金額]=(bool)とかしたいけど10^10なので無理 a[i]がkと互いに素なら0~k-1まで全て取りうる a[i]がkと互いに素でない場…

Codeforces Round #499 (Div. 2) D. Rocket

問題ページ Problem - D - Codeforces 考えたこと p[i]を把握しないといけない y=INFを出力しようと思ったけどだめなのでy=1を出力して確認する p[i]さえわかれば二分探索すればよい m<=10^9ならクエリ回数30回あれば足りる 二分探索を実装して出すと通る y=…

Codeforces Round #499 (Div. 2) C. Fly

問題ページ Problem - C - Codeforces 考えたこと 燃料xを積んだときに旅行を達成できるか?を考えると単調性がある 判定O(N)でできそうなのでにぶたんできそう 燃料を10^9までしか使わないことが保証されている -1の判定はこれを使えばできそう 不等号に=を…

Codeforces Round #500 (Div. 2) D. Chemical table

問題ページ Problem - D - Codeforces 考えたこと sampleを眺める 1列を埋めたあと1つもない列に1個ずつ配置すると最適な置き方な気がした 列iに要素がa[i]個あるときh-max(a[i])個で1列埋めたくなる 列iと列jに同じ行の要素があるとき、この2つの列はマージ…

codeforces #212 div2 D. Fools and Foolproof Roads

問題ページ Problem - D - Codeforces 概要 n頂点m辺の重み付き無向グラフが与えられる。このグラフに辺を張る操作をp回行うことで連結成分数がq個になるようにしたい。 辺を張るときは 同じ連結成分内の頂点なら1000 違う連結成分の頂点ならばmin(10^9, 連…

codeforces #212 div2 C. Insertion Sort

問題ページ Problem - C - Codeforces 概要 n要素の順列が与えられる。この順列に挿入ソートを行う。 この順列のどこか2要素をswapすることで挿入ソートでの交換回数を最小化しろ。 考えたこと ようするに転倒数を最小化すればいい i,j (i

codeforces #469 div2-C div1-A Zebras

問題ページ Problem - C - Codeforces 考えたこと 0と1の数からつくる01列の数特定できない?みたいになるけどできない 色々試してると前から貪欲に取ればいい気持ちになる 前から貪欲するのになぜかO(n^2)の方法しか思いつかない 括弧列みたいに+1/-1で累積…

codeforces #469 div2-D div1-B A Leapfrog in the Array

問題ページ Problem - D - Codeforces 本番中は誤読で時間溶かして終了 解法 操作を逆順にして考える n=5のとき以下のようになる 15243 1 2435 1 2 354 1 2 3 45 1 2 3 4 5 もし最終状態で存在する位置から初期状態の位置を復元できれば答えが求められる 移…

codeforces #433 div2 D. Jury Meeting

問題ページ Problem - D - Codeforces 考えたこと 頂点iに住んでいる人が2往復以上したほうがいいことはない 日付について区間[l,l+k]で議論をすると考える lより前の最も安いチケットで頂点0へ行き、l+kよりもあとの最も安いチケットで頂点0から出発する 各…

codeforces #433 div2 C. Planning

問題ページ Problem - C - Codeforces 考えたこと 順列を全部試すのが無理なのはそれはそう 制約がだいぶでかいのでdpはつらそう 隣同士をswapするとコストがどう変化するかを考える i,i+1をswapするとコストが +c[i]-c[i+1] 変化する sortするような感じで…

codeforces #361 div2 D. Friends and Subsequences

問題ページ Problem - D - Codeforces sparseTableのverifyとして解いた。 解法 区間の左端lを固定して考えてみる 区間[l,r]についてmax(a) - min(b)を考えると単調に増えていく max(a) - min(b) の数列は [-2, -1, -1, 0, 0, 0, 0, 1, 2, 3] みたいな単調増…

codeforces #428 div2 D

問題ページ Problem - D - Codeforces 考えたこと 部分列を全列挙とかそういう方向は不可能そうなので各要素が含まれる部分列の回数とかそういう方向で考える gcdがiとなるような部分列について考える (部分列の長さの和)*i がこんな部分列のスコアになる m…

codeforces #428 div2 C. Journey

問題ページ Problem - C - Codeforces 考えたこと s8pcで見た D - Driving on a Tree 1頂点から求めればいいだけなのでもっと簡単 頂点1を根とした木について考える 止まる頂点は葉以外ありえない 葉までの距離とその葉にたどりつく確率を求めれば期待値が求…