数列から等差数列を引いていって [0]*n にできるかを答える問題 n = 5 の場合、引く候補は [1,2,3,4,5], [2,3,4,5,1], [3,4,5,1,2], [4,5,1,2,3], [5,1,2,3,4] の 5 つあるが、 どれも総和は 15 であり、引ける回数 k は sum(a) // 15 になる 引いた後の遷移…

"「ある頂点の子孫でない頂点に xを足す」は、 「根の子孫に xを足す」と「ある頂点の子孫に -xを足す」に分けることができるので、 全てのクエリを「ある頂点の子孫に x を足す」の形に帰着することができます。"かしこい。は？となりながら解説の言うとお…

連続する部分列→累積和を取る 累積和をとって、差を考える 余りの種類は m 個あるけど、数列の長さから高々 n 個に座圧できる。 基本テクの詰め合わせ。 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.std…

結局注目する点は、隣り合う2数を足したときに、繰り上がって桁数が変化しない時は、全体の数の和が9減るということのみ。桁数が減る時は繰り上がりがないため、全体の和は変化しない。 なので求める回数は、全体の和を S, 桁数を T とすると、T-1 + (S-1)//…

直観的に一回の動作で、１と１との間にある０を全て１にする、 次の動作では、前１にしたところより１つ右にある０の塊を全て１にする… という動作をｋ回繰り返したものの中から連続して１が並ぶ最大値が作れるとわかる Sのなかに０が連続していくつあるか、…

一組ずつ条件に照らし合わせると当然TLEする Rがa個、Bがb個、Gがｃ個あるとすると、最大a*b*c個ある。 そこから条件２に当てはらないものを引いていくという方針。 条件２ではじかれるものは s[i] != s[i+m+1] and s[i+m] != s[i+2*m+2] and s[i+2*m+2] != …