ferinの競プロ帳

競プロについてのメモ

2018-11-03から1日間の記事一覧

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],>…