全列挙（4題）

競技プログラミング C++

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本の章末で紹介されている練習問題をひたすら解いている。
競技プログラミングの世界で通用するような人は、最低でも1000題は解いているのがふつうだそうだ（要出典）。修行だな、修行。楽しいけど。

さて、全列挙の問題である。最初の2題は順列の列挙を使う。C++にはnext_permutationという便利な関数があるので、この関数と親しむ練習だった。
3題目は枝刈りしながら探索。枝刈りしながらの探索って、オセロのAI作ったときにやりましたよ。4題目はbitDPみたいに全列挙。

POJ3187: Backward Digit Sums

3187 -- Backward Digit Sums
1からN(1<=N<=10)までの数が1行目に並んでいる。
2行目以降は上の行の隣り合う数の和が書かれている。
例えば、N=4なら以下のとおり。

3 1 2 4
4 3 6
7 9
16

N=4と最終和(この場合は16)から最初の並び(この場合は3 1 2 4)を決定したい。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  // 入力
  int n, sum;
  cin >> n >> sum;

  // 計算
  // 順列を全列挙して調べる
  vector<int> v(n);
  // iota(v.begin(), v.end(), 1);
  for (int i = 0; i < n; i++)
    v[i] = i + 1;
  int a[10];
  do {
    for (int i = 0; i < n; i++)
      a[i] = v[i];
    // 順列vに対して最終和を計算する
    for (int i = n; i > 1; i--) {
      for (int j = 0; j < i; j++) {
        a[j] += a[j+1];
      }
    }
    // a[0]が最終和. sumと等しければ結果を出力
    if (a[0] == sum) {
      cout << v[0];
      for (int i = 1; i < n; i++) {
        cout << " " <<v[i];
      }
      cout << endl;
      return 0;
    }
    // next_permutationの威力
  } while (next_permutation(v.begin(), v.end()));
}

POJ2718: Smallest Difference

2718 -- Smallest Difference
0から9までのいくつかの数字が与えられ、数字を2つのグループに分けて2つの整数を作る。2つの整数の差の絶対値の最小値を求めよ。

#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
const int INF = 1000000000;

int main() {
  // 入力
  int n;
  cin >> n;
  cin.ignore();
  while (n--) {
    int a[10];
    int res = INF;
    string str;
    getline(cin, str);
    stringstream s(str);
    int b, size = 0;
    while (s >> b) {
      a[size++] = b;
    }
    // 計算
    if (size == 2) {
      res = abs(a[0] - a[1]);
    } else {
      int x, y, half;
      half = size / 2;
      // 順列を全列挙して半分のところで分けて2つの整数を作る
      do {
        if (a[0] == 0 || a[half] == 0) continue;
        x = 0;
        y = 0;
        for (int i = 0; i < half; i++) {
          x *= 10;
          x += a[i];
        }
        for (int i = half; i < size; i++) {
          y *= 10;
          y += a[i];
        }
        res = min(res, abs(x - y));
      } while (next_permutation(a, a + size));
    }
    // 出力
    cout << res << endl;
  }
}

POJ3050: Hopscoch

3050 -- Hopscotch
5*5の1桁の数字。縦横に5回移動して6桁の整数を作る。何通りの整数ができるか。
【入力の例】
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1
【出力の例】
15
全列挙すると、
111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121

/*
*/
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
// 5*5の数を格納
int field[5][5];
// 結果となる6桁の数を格納
set<int> nums;
// 枝刈りのため
set<int> done;
// 4方向
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 枝刈りしながら深さ優先探索
void dfs(int x, int y, int n, int cnt) {
  // 5回投げたら
  if (cnt == 6) {
    // numsに要素が見つからなけれあば追加する
    if (nums.find(n) == nums.end()) {
      nums.insert(n);
      // cout << n << endl;
    }
    return;
  }

  // 枝刈り
  int a = 1000 * n + 100 * x + 10 * y + cnt;
  if (done.find(a) != done.end()) {
    return;
  }
  done.insert(a);

  // 4方向
  int nx, ny;
  for (int i = 0; i < 4; i ++) {
    nx = x + dx[i];
    ny = y + dy[i];
    // 外にはみ出ていなければ
    if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
      dfs(nx, ny, 10 * n + field[nx][ny], cnt + 1);
    }
  }
}

int main() {
  // 入力
  for (int x = 0; x < 5; x++) {
    for (int y = 0; y < 5; y++)
      cin >> field[x][y];
  }

  // 計算
  for (int x = 0; x < 5; x++) {
    for (int y = 0; y < 5; y++)
      dfs(x, y, 0, 0);
  }

  // 出力
  cout << nums.size() << endl;
}

AOJ0525: Osenbei

Osenbei | Aizu Online Judge
おせんべいを焼く。
最大で横10行縦1000列なので、横10行のひっくり返し方(2^10=1024通り)を全列挙する。

// おせんべい
/*
  横10行以下なので、すべての裏返し方を全列挙。
  それぞれの場合に、出荷できるせんべいが最大になる縦の裏返し方を考える。
*/
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAX_R = 10;
const int MAX_C = 10000;
bool senbei[MAX_R][MAX_C];

int main() {
  while (true) {
    // 入力
    int r, c;
    cin >> r >> c;
    if (!(r | c))
      return 0;
    int buf;
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        cin >> buf;
        if (buf) {
          senbei[i][j] = true;
        } else {
          senbei[i][j] = false;
        }
      }
    }

    // 計算
    // bitDPみたいに、2進法の数iと横r行のひっくり返し方を対応させる
    int cnt, cnt_r;
    int cnt_max = 0;
    int last = 1 << r;
    bool tate[MAX_R];
    for (int i = 0; i < last; i++) {
      cnt = 0;
      int k = i;
      for (int j = 0; j < r; j++) {
        // tate[j] = 1ならj行目をひっくり返す。0ならひっくり返さない。
        tate[j] = (k % 2 == 1) ? true: false;
        k /= 2;
      }
      for (int j = 0; j < c; j++) {
        cnt_r = 0;
        for (int l = 0; l < r; l++) {
          if (senbei[l][j] ^ tate[l])
            cnt_r++;
        }
        cnt += max(cnt_r, r - cnt_r);
      }
      cnt_max = max(cnt_max, cnt);
    }
    // 出力
    cout << cnt_max << endl;
  }
}

感想

C++の入力で手間取る（いつも通り）。