ferinの競プロ帳

競プロについてのメモ

Codeforces

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を根とした木について考える 止まる頂点は葉以外ありえない 葉までの距離とその葉にたどりつく確率を求めれば期待値が求…

codeforces #428 div2 B. Game of the Rows

問題ページ Problem - B - Codeforces 考えたこと 二人席が2n個、四人席がn個あると考えればよさそう ぴったり座れるときに座らない方がいいことはなさそう 二人席と四人席のどちらを先に埋めるべきか 四人席*1より二人席*2の方があとあとぴったり埋められる…

Codeforces Round #438 F. Yet Another Minimization Problem

問題ページ Problem - F - Codeforces 解法 dp[i][j] = (i個目の部分列でj番目までをカバーしたときの最小コスト) としたDPを考える。DPの漸化式は dp[i][j] = min_{k

Codeforces Round #190 (Div. 1) E. Ciel and Gondolas

問題ページ Problem - E - Codeforces 解法 dp[i][j] = (i番目のゴンドラでj人目までを乗せたときの最小値) としたDPを考える。漸化式はdp[i][j] = min_{k

Codeforces Round #189 (Div. 1) C. Kalila and Dimna in the Logging Industry

問題ページ Problem - C - Codeforces 解法 n本目の木を切ったあとはチャージし放題なのでコスト0で全ての木を切れる。したがってn本目の木を切るのに必要なコストを求めればよい。また、j本目の木を切った後にj本目より前の木を切ったとしてもチャージに使…

Codeforces Round #185 (Div. 1) B. Cats Transport

問題ページ Problem - B - Codeforces 解法 猫が止まる時間や丘までの距離など色々あって扱いにくいのでまずは処理しやすいように言い換える。丘に到達してから猫が待つ時間は猫と飼育員が丘0を出発する時間の差に等しい。したがって各猫が丘0を出発する時間…

Codeforces Round #462 (Div. 2) D. A Determined Cleanup

問題ページ Problem - D - Codeforces 考えたこと ax2+bx+c を x+k で割るみたいなので何個か実験すると何か規則がありそう コンテスト中はこの計算をミスってて別の規則を生み出してた(は?) 終わったあとに冷静になって計算すると a_1 + a_2x + a_3x^2 +…

Codeforces Round #462 (Div. 2) C. A Twisty Movement

問題ページ Problem - C - Codeforces 考えたこと 非減少列の判定が連続でなくてもいいことに気付かずに時間を溶かす 反転するのは1→2に移るところ~2→1に移るところ以外考えなくてよさそう [0,l) [l,r] (r,n-1] に分けると[l,r]に1から2に移るところがある…