Atcoderなどで頻出の数学テクニックで、天才要素が強いと思われるありうる全事象についての数え上げについてパターン化できそうなものを纏める。
とりあえず大前提１、２をまとめた。
とりあえず大前提１、２をまとめた。
大前提１
次の条件１を満たす者は、方法１で数え上げられる。
条件１
ある部分に着目した時、数え上げたいすべてのものはそれをただ１つもつ。
方法１
そのある部分(X_iとする)ごとに、X_iを持つもの数え上げる対象を計算して数え上げる。(掛け算するとか)このステップをf(X_i)とかく。
そして、それをsigma(1->N, i)f(X_i)する。
一見すべての事象をカバーできてるか怪しいけど、条件１は必要十分条件であるためできてる。ここが個人的にあまり直感的ではなく天才ポイントが高い。
いくつか例を挙げる
例 ABC127 - E(500)
もうすでに記事が出てるけど、この問題はこの原理でも考えられる。
共通してる部分をとにかく探すと、盤面を固定したときには、特に共通項はない。
しかし、考えるのはありうる盤面すべてなので、これを念頭にいれて考える。すると、「二つの点の座標の差の絶対値」は全部の考えうる置き方での共通部分と考えられる。
あとは、二点の置く今見てない軸で2乗、二点の場所以外のところですべてにおきうるということでコンビネーション、差がXということは、同じ行でありうる置き方をまたかける。これらを全部かけ合わせればとける。(コマを区別はしないので、左と右の入れ替えは考えなくてよい。コマを区別する場合は、答えに最終的にN!をかければよい。)
しかし、考えるのはありうる盤面すべてなので、これを念頭にいれて考える。すると、「二つの点の座標の差の絶対値」は全部の考えうる置き方での共通部分と考えられる。
あとは、二点の置く今見てない軸で2乗、二点の場所以外のところですべてにおきうるということでコンビネーション、差がXということは、同じ行でありうる置き方をまたかける。これらを全部かけ合わせればとける。(コマを区別はしないので、左と右の入れ替えは考えなくてよい。コマを区別する場合は、答えに最終的にN!をかければよい。)
ここからわかるように、大前提１を使った考えうるすべての数え上げは並べる物自体(物を並べるパターンに限るけど)の区別はいったん無視して、同じものと考えると見通しがよい。
例 ABC140 E(500)
この問題はこの記事を書くきっかけにもなった。
すべての連続部分列に対しての、二番目に大きい要素を返す写像fをおき、すべての連続部分列をfに入れた合計をもとめればよい。
すべての連続部分列に対しての、二番目に大きい要素を返す写像fをおき、すべての連続部分列をfに入れた合計をもとめればよい。
この場合、共通部分としては、すべての[L, R]は二番目に小さい値を必ず1つもつので、二番目に小さい値に着目すればいいとわかる。
着目すると、指定した数字が二番目に大きいとなる条件は、その数字の場所よりも大きい数字がある場所が、今見てる数字の場所の前後の二つさえわかれば、かけ算で計算できる。ここらへんは解説放送を見たほうが早い。
大前提２
前から見て、新しく見た場所が末尾となる区間に関する計算が前から累積和的、もしくはセグ木的に一回の操作ごとにO(1), O(log n)くらいで求まるのなら、前から見てその末尾ごとに答えを加えればよい。
ちなみに書いてる途中に気づいたけど、この考え方の問題まだ出会ってないし、もしかしたら大原則１に完全カバーされるかもしれない。
例
ある長さNの数列(2 <= N <= 100000, -10^9 <= A_i <= 10^9)を与えられる。
1 <= L < R <= Nを満たすすべての(L, R)のペアに対して、[L, R]の区間の和を足し合わせたものを求めよ。
1 <= L < R <= Nを満たすすべての(L, R)のペアに対して、[L, R]の区間の和を足し合わせたものを求めよ。
この問題は大原則１で考えると、ある数に着目した時、それを含む区間の数は積で求まるのでそれを合算すればよい。よってとけた。
大原則２で考えようとしたけど無理っぽい。
