AGC 012F Prefix Median - DEGwerのブログ

解説に少し頼りました。

問題概要

http://agc012.contest.atcoder.jp/tasks/agc012_f

思考の道筋

ある操作で作りうる列を数えるときは、同じ列ができる操作列の同値類から代表元を一個取ってきてそれを数える(できた列に対して、何らかのgreedyで操作列を一個対応付けることにするとうまくいくことが多い)のが常套手段。今回も、prefix medianでできる列を一個固定して、それを生成する操作列を考えることにする。まずは与えられた集合の要素がすべて異なる場合を考える。

できた列を前から見ていって、新しいものが出てきたら、それはそのステップで追加されたことにしてよいことが分かる。また、それ以外のものについて、課される条件は「端から距離x以内にある」とかだけなので、実は端から埋めていけばいいことが分かる。

次にこれを数えることを考える。前から見ると区間の情報とかをいちいち持っておかないといけなくて無理そうなので、後ろから見る。後ろから見ると、ソート列の要素を消していく問題になる。列の要素は、「前から見て初出かどうか」で分類できる。

後ろから見ていき、中央値を移動させたとする。移動前のやつが「前から見て初出」だったら、これはそれ以降(本来の時系列では、それ以前)には存在しない。ということで単に消してOK。結局、「まだ残っている、既に中央値として使われたもの」の列を持っておけば、この列を一気に2つ以上中央値が移動することはない。さらに、この列の内部にいるなら、この列の要素以外のものに中央値が移動することもない。中央値を移動させるときに右または左の要素を一緒に消すが、これは消した個数だけ持っておけばOK。

以上に気を付けると、以下のDPが書ける。

DP[n][l][c][r][d][s][t]: n回操作して、中央値として出てきたまだ消されていないものがc個あり、それより左の要素がl個、右の要素がr個残っており、まだ消えていない中央値たちの中で今いる場所が左からd番目であり、中央値として使った一番左がs、一番右がtであるときの、中央値の列としてありうるものの個数

ここで与えられた集合に重複がある場合を考えるのだが、作った列で同じものが連続する場合、新たに加えたものを適切に今見ているところの前または後ろに置くことにすれば、結局中央値が移動しない場合に含められることが分かる。よって、この枠組みで問題なく扱える。

これでO(N^7)となる。遷移を書き下してぐっと睨むと、l+c+rが一回の遷移で2ずつ、l+dが1ずつ小さくなっていくことが分かる。この依存関係で状態が削れて、O(N^5)となる。(l+c+rについては遷移の考え方を見るとそれはそう、l+dについては解説見るまで気付かなかったが、これが見えないと本解みたいなエスパーをしないと厳しくなると思う)

さて、中央値として(後ろから見て)新しいものが出てくるときはd=1もしくはd=cだが、この関係を上の式に突っ込んでみるとl=r=N-n(これ重要)という式が出てくる。ということは、後ろから見て新しいものが出てくるとき、その新しいものとして置けるものは真ん中から距離N-n以下のもの、ということになる。

さて、かなり強めの性質が分かったところで、このDPは(これ以上状態を削れないが)かなり冗長なことをしているように見えてくるので、この方針を捨てる。落ち着いて言い換えなおすと、解説に書いてある条件が出てくる。これをうまいことDPすればよいのだが、「前から見て初出かどうかで消すかどうか決める」みたいなことをしているとどうしても[n][c][d][s][t]あたりを全部持っておかないといけなくなってダメそうなので、中央値を消すタイミングを「その順番を飛ばしたとき」にすることにする。そうすると遷移は重くなるのだが、これまで[c][d][s][t]と持っていたものが、「[N-n,N+n]の中でまだ消えていないものに対する、今の場所の相対位置」みたいなものだけ持っておけばいいことになるので状態数が削れて、O(N^4)となる。

なにか

以上のような思考をすれば、エスパー力がなくても一応常人に思いつきうる解法になる(まあ出来なかったんだけど)。でも一本道にこの思考を辿ってもかなり大変だからコンテスト中にこういう愚直な考察を1ステップずつ積み重ねて通すのは無理だろうなぁ。

今回の場合、結局列が作れる必要十分条件が一番自然な十分条件と一緒になるので、それっぽい十分条件が見えたら地道な考察を始めるより前にそれが必要条件であることを示しに行く方がいいんだと思う。証明自体は別に難しくないので。

コード

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
ll dp[52][101][101];
int main()
{
	int num;
	scanf("%d", &num);
	vector<int>v;
	for (int i = 0; i < num + num - 1; i++)
	{
		int z;
		scanf("%d", &z);
		v.push_back(z);
	}
	sort(v.begin(), v.end());
	dp[1][1][0] = 1;
	for (int i = 1; i < num; i++)
	{
		int a1 = int(v[num - 1 - i] != v[num - i]), a2 = int(v[num - 1 + i] != v[num - 2 + i]);
		for (int j = 1; j <= i + i - 1; j++)
		{
			for (int k = 0; k < j; k++)
			{
				for (int l = 0; l < k + a1; l++)
				{
					dp[i + 1][j + a1 + a2 - (k + a1 - l - 1)][l] += dp[i][j][k];
					dp[i + 1][j + a1 + a2 - (k + a1 - l - 1)][l] %= mod;
				}
				dp[i + 1][j + a1 + a2][k + a1] += dp[i][j][k];
				dp[i + 1][j + a1 + a2][k + a1] %= mod;
				for (int l = k + a1 + 1; l < j + a1 + a2; l++)
				{
					dp[i + 1][j + a1 + a2 - (l - 1 - k - a1)][k + a1 + 1] += dp[i][j][k];
					dp[i + 1][j + a1 + a2 - (l - 1 - k - a1)][k + a1 + 1] %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= num + num - 1; i++)
	{
		for (int j = 0; j < i; j++)
		{
			ans = (ans + dp[num][i][j]) % mod;
		}
	}
	printf("%lld\n", ans);
}