Codeforces Round #176 (Div. 1)

codeforces.com

はいサイアクの1完。

Bが分からない時は本当に辛いンゴねえ

A. nが与えられる。1~nの順列P[1]~P[n]が「∀i(1 <= i <= n) P[P[i]] = n+1-i」を満たす。このようなPを1つ出力せよ。そのようなPがなければ-1と出力すること。

順列なのでグラフではdirected "cycle"(cyclicではない) graphの集合と対応する。グラフにおいては、上の条件は、頂点iから有向辺を2本辿った先の頂点が常にn+1-iであることを表している。頂点n+1-iから2本辿った先が頂点iにならないといけないから、そのような条件を満たす順列は、大きさ1または4のdirected cycle graphのみで構成されている(ただしnが奇数でかつ頂点(n+1)/2についてのみ大きさ1は許される)。

よって与えられたnをまず4で割って、剰余が2, 3であればそのようなPはない。

後は適当にやればよくて、nが奇数であれば、ans[(n+1)/2] = (n+1)/2にだけ気をつけて、(k)→(k+1)→(n+1-k)→(n-k)→(k)みたいな閉路を考えて答えを構成してやればよい。

なんかめっちゃバグった。アホ。

B. 1~nの順列P[1]..P[n]と自然数kをとって、P[2]P[3]...P[k]P[1], P[k+2]P[K+3]...P[2k]P[k+1], ...を新しい順列として返す写像f(P, k)を定義する(つまり順列をk個ごとで区切って、区切った中で先頭の数を最後に移動させる)。L[1] = [1, 2, 3, ..., n]として、L[k] = f(L[k-1], k)と置く。L[n]を求めよ。

まず最後に移動させる操作の回数は、Σ[i=2..N]ceil(N/i) = O(NlogN)であるから、L[1][1] ~ L[n][n]のn^2個の数の内、いい感じに最後に移動させる数だけを処理することが出来れば、つまり1つの区間内のシフトをO(1)で出来ればO(NlogN)が達成できることはわかる。

ここからが問題で、僕はL[n]におけるi番目の数がL[1]においてどこにあったかというのを独立に考えようとしたのでドツボにハマった。つまり、L[1] ~ L[n]を正方形に並んだn^2個の数だというイメージで見た時、僕は縦に区切って処理しようとしてしまったんだけど、横に区切らないといけなかった。横に区切る、つまりL[k]からL[k+1]を一度に求めようという気持ちでいくとちゃんと出来て、これは、最後に移動させられる数を無視してみると、左に1個ずつズレていくだけだから、このズレを実際にはズラさずに固定してやると良い。どういうことかというと、配列L[k]から配列L[k+1]を作る時、本来ならL[k+1][i-1] = L[k][i]とやるわけだけど、定数1分ずつ全てがズレるのだから、i' = i-1と置いてやれば、L[k+1][i'] = L[k][i]と出来て、L[k+1]を新しく生成するのではなく、L[k]をinplaceに置き換えることにすると(dpのメモリ削減みたいなもん)、1ズレる数に関しては値を参照したりコピーする必要がなくなる。後は、最後に移動させる必要のある数だけ、L[k+1][i+k-1] = L[k][i]みたいな感じにする必要があるから、i'とinplaceを考えると、後ろからL[i'+k] = L[i]で更新していくだけでよく、上の評価式からこの更新の回数はO(NlogN)であるから解ける。

ちなみにL[n][i]がL[1]においてどこにあるかという考え方だと、O(NlogN(logN+loglogN))は達成できるんだけど、N=10^6でしかも旧版の問題に対する処置としてTLEが1/2の1秒だから普通に間に合わない。

自分用メモ: 流石にどっちで対処するかぐらいちょっと考えましょう、というか結構dpの変数置き換えはよくやるし好きなんだからこれぐらい思いつくべき