Educational Codeforces Round 47
B問題思いつかなかった 悲しい
A. Game Shopping
問題文を読むと、cのindexを増やしながら対応するaがあるときだけカウントをすれば良いことが分かる。
計算量:$O(N+M)$
Submission
B. Minimum Ternary String
解けなかった。
021->012みたいな遷移を脳死で書いているとわからないけど、1は一番左に持っていくことができる。
したがって(000…)111…22…00…22..00のような形に持っていけばよい。
計算量:$O(N)$
Submission
C. Annoying Present
結局、$x$は全体に加算されて $d*dist(i,j)$は凸な加算がされることが分かる。
最終的な数列の和を最大にしたいので、凸の和を最大にしたい。dが正のときは端にその軸を寄せて、負のときは軸を中央に寄せれば良い。
計算量:$O(N)$
Submission
D. Relatively Prime Graph
$gcd(a,b)==1$になる辺の数を数える。ただし$M$を超えたときに中断する。
すると辺の上限を$M$で抑えることができるので、あとは辺が少ないときに連結でなくなるものの判定をすれば良い。
計算量:$O(M)$
Submission
E. Intercity Travelling
手で実験すると最大の数の方から謎の一定な数列が生まれる。OEISで検索すると出てくるので(http://oeis.org/A001792)
これと$a[i]$をかけ合わせれば良い。(良くないんですが…)
計算量:$O(N)$
Submission
F. Dominant Indices
葉から上の頂点に情報を渡す方法で$O(N^2)$になる。
dsu on treeを学習すると、今回はHL分解で言うところのHeavyPathを保存すれば良いことになる。
葉からHeavyPathのtopに情報をもっていくとして、HeavyPath上のある頂点についてその頂点の部分木の情報を渡し終えている時を考える。
topを見たときにこの情報だけでその頂点の欲しい情報が求められているので条件を満たす最大値のindexを返せるようにしておけば計算量が軽くなって解ける。
LightPathからは、その接続先のHeavyPathのtopに情報を伝搬すれば良い。伝搬回数は$logN$回ほど。
これすごい、応用が効きまくりそう
mapを使ってしまったのでlogが一個増えたけど上手にできそう。
計算量:$O(Nlog^2N)$
Submission