Particle

競技プログラミングについての雑記

2018-02-08から1日間の記事一覧

SRM 657 Div1 Medium PolynomialGCD

各素数ごとに独立になっているので、それぞれ解いて解を掛け合わせればよい。 素数 p の出現回数が一番多くなる場所を決めると、全体で何回 p が出現するかを O(NlogN/p) 程度で計算でき、場所の個数は、Nなので、各素数ごとに、O(N^2logN/p) で計算できる。…

SRM 654 Div1 Medium SuccessiveSubtraction2

区間を 2 つ選んで符号を反転させることができるので、区間和の最小値が計算できれば、あとは簡単に計算できる。 これは、O(N) でやってよいので、配列が更新される度に最初から計算し直せば良い。(解いているときは何も考えずに、StarrySky Tree を貼ってし…