Codeforces Round #127 (Div. 1)
tourist回嫌い(直球)
色々やってしまい1完でした。
A. 以下の様な条件を満たす行列を考える。
- n*nの正方行列である
- 全ての要素が0または1
- 行列は上下左右対称すなわちAi, j = An - i + 1, j and Ai, j = Ai, n - j + 1が成り立つ
- 上下左右に隣り合う要素同士が同時に1となることはない
そのような行列の内、1をx個要素としてもつものを構成することの出来る最小のnを求めよ。
なんか本当にヤバそうだなあと思いながら適当にやったら6WAぐらいして諦めた。
計算量は問題にならないので、n=1から順に試していけば良い。
そして基本的にまずnが偶数か奇数かで場合分けしないといけない。
nが偶数の時は結構簡単で、最後の条件と対称性から、中央の2行2列は0で埋まる。すると小さい正方形4つに分かれるイメージになって、それらの正方形には最後の条件以外を特に考えないで埋める事ができるから、xが4の倍数であってかつx/4 <= MAX_PLACE( (n-2)/2)であればよい。ここでMAX_PLACE(t)はt*tの正方形に最後の条件を満たすように入れることの出来る1の最大数。
nが奇数の時が辛い。nが奇数の時、nが偶数の時と同様に中央の1行1列以外の場所に1が存在する時は、勝手に対称性から4つ発生するので、4の倍数ずつ増える。
中央の1行1列でかつ、完全な中央でない場所に1が存在する時は、対称性から2つ発生するので2の倍数ずつ増える。
完全に中央に1が存在する時は、対称性を考えなくていいので1個だけ増やせる。
その上で、中央が1かそうでないかによって、置くことの出来る数が変わる。
まず、中央が1である時、すなわちxが奇数の時、他の場所に、1は、0 <= a <= MAX_PLACE( (n-1)/2) ∧ 0 <= b <= ( (n-1)/4) * 2を満たす様な(a, b)で表せる4 * a + 2 * b個であれば置くことが出来る。
中央が1でない時、すなわちxが偶数の時、(n-1)/2が奇数の時、中央に1がないことによって、2 * bのbが2増えるため、これを考慮しないと落ちる。分かってたけど実装しなかったのはカス。
もうちょっと良い方法ないのかなあ。
B. n, m, Cが与えられるので、Σ[i=1..n]Σ[j=1..m] C[i][j] * D{(4X, 4Y), (4j-2, 4i-2)}^2 を最小化するようなX, Yと最小化された値を求めよ。ただしDはユークリッド距離
なんかユークリッド距離とマンハッタン距離を頭の中で取り違えるやらかしが発生したせいでめちゃくちゃ悩んだ。距離に2乗がついてるから次元が分解出来ないンゴねえって感じ。最終的に、定点に対するマンハッタン距離の関数D(X, Y)は2次元で離散な凸関数になっていて、2乗しても凸のままで、凸関数の和は凸関数だから、結局全体として2次元の凸関数だから3分探索すればエエやんけと思って、O(NM * log3/2(N) * log3/2(M))を書いたらTLEして落ちた(概算が10^9なので当たり前、概算しましょう)。でTLEしてオイオイオイとなった時にユークリッド距離であることに気づく。ユークリッド距離の2乗はX, Yの項が分離するから次元が分解できるンゴねえ....
よって適当に上の目的関数をXとYの項に分解して同じように３分探索すると、logが１つ消えて通った。
C. n個の頂点がn-1本の辺によって接続され連結になっていて、このグラフは道である。各辺には人が通れる回数の上限が決まっている。好きな頂点から初めて好きに辺を通って良い時、最大で何回移動することが出来るか。
n-1本の辺の通ることの出来る上限回数を左からE1, E2, ..., En-1とする。
ちょっと考察すると、全体で移動出来る回数は、1 <= a <= b <= c <= d <= n-1を用いて、Σ[i=a..d-1] Ei - |{Ei | Eiが奇数 i=a..b-1)}| - |{Ei | Eiが偶数 i=b..c-1)}| - |{Ei | Eiが奇数 i=c..d)}|と表すことが出来、これの最大を求めれば良いことが分かる。これはどうしてかというと、何度も同じ辺を行き来することが出来るから、とりあえず最大化するためにはi番目の辺を通る時はEi-2回往復してしまうと、残り上限2回をどう通るかによって、行って引き返してきたり、行ったまま帰ってこなかったり、そもそも通らなかったりする(当たり前)。これは何を意味しているかというと、全体の経路はかならず、(1度通って引き返してくる辺たち) (1度通ったきり引き返して来ない辺たち) (1度通って引き返してくる辺たち)という並びになってないとおかしい。要は偶数回通る辺、奇数回通る辺、偶数回通る辺というふうに連続して存在している(もしくはこれらの内存在しない辺の集合があってもいい)。図にするとこんな感じ。まあ自分で書いたら分かると思う。
後は計算量と、初めから上限回数が1の辺の処理が問題になる。
とりあえず後者は一旦無視して考えると、流石にさっきの上の式の4変数を総当りするとO(n^4)になって間に合わないので、自明な変数を削る所から始める。
まずa, dはなくてもいい。これはa, dは左端と右端に設定した方が絶対に通れる回数が大きくなって得だから。
bは流石にないと困るので、これは総当りすることにする(bの総当りでO(n))。
これによって、固定したbに対して、最大の移動回数を与えるようなcを効率良く求めたいと考えられる。
これは結構簡単で、要は「bit列が与えられる。bit列をある場所で分割して、それより左側にあるbitを全て反転させる。この時、立っているbitの数を最小化するにはどの位置で分割すれば良いか。」という問題と同じ。
これは、左から、
diff[idx] := 位置idxまでに出現した1の数と位置idxまでに出現した0の数の差
を累積和的に計算して、segment treeなどに突っ込んでおけば、Range Max Queryによって、maxidx = argmax(diff[idx])が分かって、位置maxidxで反転させると、立っているbitは最小化されて|{Ei | Eiが奇数 i=b..n-1)}| - (diff[maxidx] - diff[b-1])になることが分かる。ちなみに実際には反転させないケースもあるので、|{Ei | Eiが奇数 i=b..n-1)}| - max(diff[maxidx] - diff[b-1], 0)。
さて問題は上限回数が初めから1回であるような辺が含まれている時で、これがかなり罠。なんか上までの考察はすぐ終わったのに本当に嘘&バグらせで辛い思いをした。
さて、上限回数が1回である辺は、当然2回通ることが出来ないから、aからb-1やcからdに含まれては行けない。よって、最も右に存在する1の場所pつまりEp=1となる最大のpを記憶して(1がなければp = 1)、RMQのクエリの区間の左端をpに設定する必要がある(つまり[p, n-1]にクエリを投げる)。これだけだと、RMQを[0, p-2]に飛ばしていないわけだからpより右側の辺を一切通らないケースを考慮していなくて嘘っぽいけど、ある辺iについてそこを通る回数はEi - {0, 1}でこれは常に0以上であるから、さっきも言った通り全ての道を通ったケースが、全ての道を通らないケースに比べて劣ることは絶対にない。
累積和を取ったりindexをいじったりする系の奴、考察が終わっていてもバグりまくるの辛いしどうにかしてくれ。
自分向けメモ： コーナーケースとかヤバそうなケース思いついたらとりあえずメモっとけ。考察もう少し丁寧に。嘘が入らない程度に考察は少しずつ積み重ねる。飛躍出来るだけしない。
