Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1978-a0e4aaa4
この記事にトラックバックする(FC2ブログユーザー)

Yandex Open 2011 Qualification 1 D問題 - Polycarps Picture Gallery (この記事を編集する[管理者用])

Source

Yandex Open 2011 Qualification 1 D問題 (2000pt)
Problem description
Yandex Open 2011 Qualification 1の自分の参加記録

問題概要

m個 (40以下) の整数a[k]が与えられる.
n要素 (1000以下) の数列Xで,以下の条件をみたすものを1つ求める問題.
 (1) Xに含まれる各要素は1~mの整数
 (2) Xに含まれるkの数はa[k]以下
 (3) Xは隣り合う要素が等しくない (X[1]とX[n]も隣り合うとみなす)

解法

適当に1つおきに数字を置いていく.
ただし,
 1 3 2 4
のように,1-2はOKだが2-3はダメ,という風に,連続するm/2個はOKの場合とダメな場合に分かれる.
なので,m/2個置きたいものは置く場所に注意する.
後は適当にOK.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

int br;

void out(int x){
  if(br) putchar(' '); else br = 1;
  printf("%d",x+1);
}

int main(){
  int i,j,k,l,m,n,now;
  int in[50], ind[50], res[1100], sum;

  while(scanf("%d%d",&n,&m)==2){
    rep(i,m) scanf("%d",in+i);
    rep(i,m) ind[i] = i;

    rep(i,m) in[i]*=-1;
    intIntSort(in,ind,m);
    rep(i,m) in[i]*=-1;

    now = 0;
    rep(i,n) res[i] = -1;
    rep(i,m){
      while(in[i]>0){
        if(res[(now+1)%n]==ind[i] || res[(now+n-1)%n]==ind[i]) break;
        res[now] = ind[i]; in[i]--;
        now += 2;
        if(now >= n && now%2) break;
        if(now >= n) now = 1;
      }
      if(now >= n && now%2) break;
    }

    rep(i,n) if(res[i]==res[(i+1)%n] || res[i]==-1) break;
    if(i!=n){puts("-1"); continue;}
    br = 0;
    rep(i,n) out(res[i]);
    puts("");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1978-a0e4aaa4
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。