E: guruguru - AtCoder Regular Contest 077
整数xを一つ決める。ある数a[i]に対して、a[i] + 1 またはxに遷移する、という操作を行い、a[1]～a[n]までの遷移を実現する。この操作の回数が最小になるようにxを決めた時、その最小回数を求めよ。
素直にやるとO(NM)の問題で当然間に合わない。そこでx=kのときの操作回数f_k(x)を考えると、xの不連続点が存在する高々1次関数の組み合わせになっていることがわかる。例えばa[i] < a[i + 1]であれば、a[i] < x <= a[i + 1]のときはxに遷移したほうが操作回数が最小になる。この場合はxの1次関数になる。それ以外のときは+1を繰り返したほうが最小になる。この場合はxの0次関数(定数関数)になる。
そこで、[f_1(x), f_2(x), ... , f_m(x)] という数列を構成することを考えると、この数列に1次関数を一気に足す、という操作がO(1)やO(logN)程度でできれば解決である。
そこでimos法を用いる。具体的には、n次関数の係数ごとにimos法を用いて、最後にx^nを書けながらf_k(x)を復元する、という操作になる。O(N)。
n次関数の和はそれぞれの次数の係数の和をとった関数に等しい、つまり
(ax + b) + (cx + d) = (a + c)x + (b + d)
という当たり前のロジックを使うものだけど慣れてないと思いつくのは難しい気がした。
D: 11 - AtCoder Regular Contest 077
1～nの数で構成された、n+1個の数列が与えられる。この数列の中で、1～nはそれぞれ少なくとも1回以上は登場する。この時、長さ1～n+1の部分列で、異なる個数の総和を求めよ。
要はある数が一つだけダブっており、それ以外は全部1個づつ現れる数列である。これを以下の3パターンに分けてカウントする。(以下、長さkの部分列とする)
- ダブりの数を含まない場合 n-2Ck 通り
- ダブりの数を1個含む場合 n-2Ck-1通り * ダブリの数の選び方2通り
- ダブりの数を2個含む場合 n-2Ck-2 通り
ただし、2番については次のような場合をダブルカウントしている。
xxxxxxxxxx11yyyyyyyyyyyyyy
そこで、この数を引く。これは、ダブっている数の両側にある数列の個数をmとおくとmCk-1通りであり、この数を引けばよい。mは愚直に数えてもO(N)である。
全体で計算量はO(N)になる。
C: pushpush - AtCoder Regular Contest 077
数列a[i]が与えられる。このa[i]とある空の別の数列b[j]について、bの末尾にa[i]を加え、bをreverseする、という操作をすべてのa[i]について繰り返す。最後にできる数列を求めよ。
毎回Reverseするのではなく、Nが偶数なら最後に一回Reverseすればよい。あとはa[i]の要素を順に末尾、先頭、末尾、先頭と追加していく。O(N)。
E: Connected? - AtCoder Regular Contest 076
RxC の平面内に (x1[i], y1[i]) (x2[i], y2[i]) の座標のペアが幾つか与えられる。このペア同士で線を引きたいが、それぞれの線が交差してはならない。そのような引き方が可能かどうか判定せよ。
まず、両方の点のいずれかが周囲を除いた領域RxCの内部にある時、そのペアは無視してもよい。なので、両方の点が領域の周辺にあるものだけを考える。
これはある角から出発して辺を一周するような順序で点をソートし、順番にキューに入れていく。既にキューに入れたものが現れた場合、キューの先頭にもう片方のペアがあるならばキューから出す。そうでない場合は線が引けないのでNOを出力する。これを最後までやればよい。ソートが一番重く、O(N logN)。
D: Built? - AtCoder Regular Contest 076
座標(x[i], y[i])に街がある、街間に道路を引くためにはx座標の差またはy座標の差の小さいほうの距離だけコストがかかる。いくつか道路を引いて全部の街を行き来できるようにするための最小コストはいくつか？
最小全域木を求めれば良いのでKruskal法またはPrim法をする。ただし、全部の街の間にEdgeを引くと計算量がオーバーする。具体的にはO(N^2 logN)になる。
そのため、あらかじめx座標でソートした街、y座標でソートした街を作成しておき、その前後でしかEdgeがないようにしておくと、Edgeの数は(N-1)*2に抑えられる。そのため計算量がO(N logN)で計算できる。
C: Reconciled? - AtCoder Regular Contest 076
犬がN匹、サルがM匹いる。犬同士、サル同士が互いに隣り合わない並びかたは何通りか？
|N - M| > 1 の場合は0通り。
|N - M| == 1 のときは、xoxoxoxox という並び順しかありえないのでN! * M! 通り。
|N - M| == 0 のときは、oxoxoxox と xoxoxoxoいう並び順の2通りがあり、2*N! * M! 通り。
AtCoder Grand Contest 016 C: +/- Rectangle
H行W列の整数値のテーブルで、h行w列の部分区画の和はすべて負、かつテーブル全部の要素の和が正であるようなテーブルは存在するか？するなら具体例を示せ。
具体的な構成を色々試すと、右下の角1マスだけ負、それ以外は正であるようなテーブルを作ることで作れそうである。この時、hがHの約数、かつwがWの約数であると、テーブルをすべて部分区画でダブりなく敷き詰めることができるため、絶対に全区画の和は負になってしまう。それ以外の場合で具体的に構成してみる。
ある数Vを仮定して、右下の角が -V*(w*h - 1) - 1, それ以外のマスがVであるようなh x wの部分区画を考えると、この範囲での合計は-1であり、負になる。これを横方向にw+1, w+2, と伸ばしていった時、範囲内の合計が最も小さいものはw+1のときであり、具体的にはV*h -1になる。一番右上からh x wの区画が合計N個あった時、上のようなとり方をするとその合計値は-Nとなる。これがV*h - 1の値より絶対値で小さければ、全体の合計値は必ず正となる。ここではWもHも500以下であるため、例えばV=1000とすることで目的のテーブルが構成できる。O(WH)。
この手の発想力が求められる問題は結構苦手かもしれない。
