列の構成 (AOJ 2274)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2274

問題

略

解法

validな列になるまで列をランダムで構成する。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n, k;
int seq[1010];
int card[1010][1010];

int main() {
  srand(time(NULL));
  while (scanf("%d %d", &n, &k) > 0) {
    REP(i, k) {
      REP(j, n / 2) {
        scanf("%d", &card[i][j]);
        card[i][j]--;
      }
    }
    while (true) {
      REP(i, n) { seq[i] = rand() & 1; }
      REP(i, k) {
        int sum = 0;
        REP(j, n) {
          sum += seq[card[i][j]];
        }
        if (sum < n / 8 || sum > 3 * n / 8) { goto next; }
      }
      break;
next:;
    }
    REP(i, n) {
      printf("%d", seq[i]);
    }
    puts("");
  }
}