POH! Vol.2 C++模範解答

こちらではpaiza事務局側で作成したコードを随時掲載していきます。
更新日:2014年4月30日(水)

C++: paiza事務局作成コード Vol.3 動的計画法

得点:100点
通過テストケース数:7/7

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)

typedef long long ll;


int main() {
  int H, W; cin >> H >> W;
  vector<string> display(H);
  rep(i, H) cin >> display[i];

  int table[310][310] = {}, dp[310][310];
  rep(i, 310) rep(j, 310) dp[i][j] = 100100100;

  rep(k, H) {
    rep(i, H - k) {
      dp[i][0] = display[i + k][0] == '0' ? min(dp[i][0], 1) : 0;
      REP(j, 1, W) dp[i][j] = display[i + k][j] == '0' ? min(dp[i][j], dp[i][j - 1] + 1) : 0;
    }

    int hist[310] = {};
    rep(i, H - k) {
      rep(j, W - 1) if (!dp[i][j + 1] && dp[i][j]) hist[dp[i][j]]++;
      if (dp[i][W - 1]) hist[dp[i][W - 1]]++;
    }

    int sum = 0;
    rep(i, W) sum += hist[i + 1];
    rep(i, W) table[k + 1][1] += (i + 1) * hist[i + 1];
    REP(i, 2, W + 1) {
      table[k + 1][i] = table[k + 1][i - 1] - sum;
      sum -= hist[i - 1];
    }
  }


  int N; cin >> N;
  rep(i, N) {
    int S, T; cin >> S >> T;
    cout << table[S][T] << endl;
  }

  return 0;
}

C++: paiza事務局作成コード Vol.2 O(H^2W^2)

得点:71点
通過テストケース数:5/7

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)

typedef long long ll;


int main() {
  int H, W; cin >> H >> W;
  vector<string> display(H);
  rep(i, H) cin >> display[i];

  int ss[310][310] = {};
  rep(i, H) rep(j, W) ss[i + 1][j + 1] = (display[i][j] == '1' ? 1 : 0);
  rep(i, H) rep(j, W) ss[i + 1][j + 1] += ss[i + 1][j];
  rep(j, W) rep(i, H) ss[i + 1][j + 1] += ss[i][j + 1];


  int N; cin >> N;
  rep(_, N) {
    int S, T; cin >> S >> T;
    int cnt = 0;
    rep(i, H - S + 1) rep(j, W - T + 1) {
      int d = ss[i + S][j + T] - ss[i + S][j] - ss[i][j + T] + ss[i][j];
      if (d == 0) cnt++;
    }

    cout << cnt << endl;
  }

  return 0;
}

C++: paiza事務局作成コード Vol.1 O(H^3W^3)

得点:42点
通過テストケース数:3/7

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)

typedef long long ll;


int main() {
  int H, W; cin >> H >> W;
  vector<string> display(H);
  rep(i, H) cin >> display[i];

  int N; cin >> N;
  rep(_, N) {
    int S, T; cin >> S >> T;
    int cnt = 0;
    rep(y, H - S + 1) rep(x, W - T + 1) {
      rep(i, S) rep(j, T) if (display[y + i][x + j] == '1') goto next;
      cnt++;
next:;
    }

    cout << cnt << endl;
  }

  return 0;
}
ページの先頭へ戻る