Pの競プロ記

競技プログラミングに関することを書きます。

AOJ 0574 Nails

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0574

釘にいくつかの輪ゴムをひっかけて三角形を作ります。
1本以上の輪ゴムに囲まれた釘の本数を求める問題です。

2 <= N <= 5 * 103
1 <= M <= 5 * 105


解法


想定解はおそらく動的計画法(DP)でしょうが、今回は別の解法で。

いもす法というものを用いて解きました。私自身この方法を用いるのは初めてだったので、とても勉強になりました。

内容については以下の通りです。
http://imoz.jp/algorithms/imos_method.html

この問題で注意しなければいけないのは、
int nail[5002][5002] で配列を確保するとMLEになってしまうということです。

ですから、下のソースコードのようにmallocやassignなどを用いて動的に配列を確保してやる必要があります。

もしDPで解くのであれば、配列の型をshortにしてやれば通るはずですが、このやり方だとたぶんダメです。


ソースコード

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <complex>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
#include <cstring>
using namespace std;

#define REP(i,x,n) for(int i = x; i < (int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define f first
#define s second
#define mp make_pair
#define pb push_back

typedef pair<int,int> P;
typedef long long ll;

static const int INF = (1 << 29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

int main(){
  int N,M;
  int A,B,X;
  //int *nail[5010];
 
  cin >> N >> M;
  /*
  rep(i, N + 5){
    nail[i] = (int *)malloc((i + 5) * sizeof(int));
    memset(nail[i], 0, sizeof(nail[i]));
  }
  */
  vector< vector<int> > nail(N + 5);
  rep(i, N + 5) nail[i].assign(i + 5, 0);

  // imos method
  
  rep(i,M){
    scanf("%d%d%d",&A,&B,&X);
    nail[A][B]++;
    nail[A][B + 1]--;
    nail[A + X + 1][B]--;
    nail[A + X + 1][B + X + 2]++;
    nail[A + X + 2][B + 1]++;
    nail[A + X + 2][B + X + 2]--;
  }
  
  // from left to right
  for(int i = 0; i <= N + 2; i++){
    for(int j = 0; j <= i + 2; j++){
      if(j != 0) nail[i][j] += nail[i][j - 1];
    }
  }
  
  // from upper right to lower left
  for(int j = 0; j <= N + 2; j++){
    for(int i = j; i <= N + 2; i++){
      if(i != 0) nail[i][j] += nail[i - 1][j];
    }
  }

  // from upper left to lower right
  for(int i = 0; i <= N + 2; i++){
    for(int j = 0; j <= N + 2 - i; j++){
      if(j != 0) nail[i + j][j] += nail[i + j - 1][j - 1];
    }
  }
  
  int ans = 0;
  
  for(int i = 0; i <= N; i++){
    for(int j = 0; j <= i; j++){
      if(nail[i][j] > 0) ans++;
    }
  }
  
  cout << ans << endl;
  
  return 0;
}