問題ページ 解法 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)の数を…

問題ページ 考えたこと 上のbitから順番に決めていく 2^i > 2^i-1 + … + 2^0 より上のbitから貪欲に決めてよいはず 2^i の位が1となっている区間がk個以上存在した場合、2^iを1とできる 一旦1と決めた位が合った場合、その下の位で使える区間が限定される i…

問題ページ 解法 木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(頂…

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

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

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

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

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

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

問題ページ 考えたこと 頑張って問題文を読む ペアを組んじゃだめな二人組についてはとりあえず無視する 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人を選んだとき…

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

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

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

問題ページ 解法 制約が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],>…

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

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