Codeforces 81 D. Polycarp's Picture Gallery

問題

m種類の写真が、それぞれa[i]枚ある。
n枚の写真を環状に並べたいが、隣り合う写真は違うものにしたい。

そのような並びが可能なら、並べ方をどれか一つ出力し、
不可能なら-1を出力せよ。

制約条件

n≦1000
m≦40

方針

fura2さんのソースコードを見て書いてみたのだけど、なんでこの方針が正しいのかよくわからない。
まず偶数番目を埋め、奇数番目を、埋める。

埋め方は、以下のとおり。
まず前処理として枚数の多い順にソートしておく。
次に、今見ている写真が使えるなら使い、使えないなら、次に枚数が多かった写真を見る。
一番少なかった写真が使えなかったら一番多かった写真に戻る。

なぜかこれで必要十分になっているらしい。

komakiのは次のような方針。
0番目に枚数の多い写真を置く。
次からは、置ける写真のうち、0番目に置かれているものをまず優先的におけるか見る。
0番目に置かれているものが置けなかったら、現時点で残ってる枚数の多いものを貪欲に使う。

これは0番目と隣接するのがn-1番目なので、n-1番目に0番目と同じものをなるべく使いたくない、それから、枚数が少ないのを使ってしまうと残りが連続してしまう可能性があるから枚数が多いのから使う、という感じでので理解できるのだけれど……

ソースコード

fura2さん解

int n,m,a[40],ans[1000];
pi in[40];
void run()
{
	cin>>n>>m;
	rep(i,m)cin>>a[i], in[i]=mp(-a[i],i);
	sort(in,in+m);
	int pos=0;
	rep(k,2)for(int i=k;i<n;i+=2){
		int prv=(i+n-1)%n,nxt=(i+1)%n;
		rep(j,m){
			int p=in[pos].second;
			if(a[p]&&ans[prv]!=p+1&&ans[nxt]!=p+1){
				ans[i]=p+1; break;
			}
			pos=(pos+1)%m;
		}
		if(!ans[i]){
			cout<<-1<<endl; return;
		}
		a[ans[i]-1]--;
	}
	rep(i,n)cout<<ans[i]<<(i==n-1?"\n":" ");
}