Algoogle

Algorithm for Programming Contest

AOJ 0574 Nails

Category: AOJ Tag: imos-method

Nails

問題概要


1辺に釘をn本使った正三角形を作る.
各行iにはi本の釘が並んでいる.
釘を輪ゴムで正三角形を作るように囲む.
それをm個の輪ゴムで行う.
輪ゴムの囲い方を指定したとき, 輪ゴムで囲われた釘の本数を求めよ.

解法


三角形に対していもす法を使うだけ.

コード


(0574.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> f;


int solve()
{
        int ans = 0;
        for (int i = 0; i < n; i++)
                for (int j = 0; j <= i; j++)
                        f[i][j+1] += f[i][j];
        for (int i = 0; i < n; i++)
                for (int j = 0; j <= i; j++)
                        f[i+1][j] += f[i][j];
        for (int i = 0; i < n; i++)
                for (int j = 0; j <= i; j++)
                        f[i+1][j+1] += f[i][j];

        for (int i = 0; i < n; i++)
                for (int j = 0; j <= i; j++)
                        if(f[i][j]) ans++;

        return ans;
}

void input()
{
        scanf("%d%d", &n, &m);
        f.resize(n+2);
        for (int i = 0; i < n+2; i++) f[i].assign(i+2,0);
        int a, b, x;
        for (int i = 0; i < m; i++) {
                scanf("%d%d%d", &a, &b, &x);
                a--; b--;
                f[a][b] += 1;
                f[a][b+1] -= 1;
                f[a+x+1][b] -=1;
                f[a+x+2][b+1] += 1;
                f[a+x+1][b+x+2] += 1;
                f[a+x+2][b+x+2] -= 1;
        }
}

int main()
{
        input();
        printf("%d\n", solve());
        return 0;
}

Comments