AOJ Volume0 0092: Square Searching

 動的計画法で解く。
[i][j] = [i-1][j-1]と[i][j-1]と[i-1][j]の最小値
0行目と０列目では[i-1]や[j-1]ができない。
->fieldの左上部分を(1,1)にして0行目と0列目を0で初期化しておく。
 ※[i][j]='*'なら[i][j]=0とする。
/*****************************
* 2012/07/06                 *
* AOJ Volume0 0092           *
* Square Searching           *
* crane                      *
******************************/

#include<iostream>
using namespace std;

#define MAX_N 1000
char field[MAX_N][MAX_N];
int data[MAX_N][MAX_N];
int main(){
   
    int n;
    while(cin >> n, n){
        for(int i=0; i<n; i++){
            data[0][i] = 0;
            data[i][0] = 0;
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                cin >> field[i][j];
                data[i][j] = 0;
            }
        }

        int max = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(field[i][j] ==  '*'){
                    data[i][j] = 0;
                }else{
                    data[i][j]=min(data[i-1][j-1],min(data[i][j-1],data[i-1][j]))+1;
                    if(max < data[i][j])
                        max = data[i][j];
                }
            }
        }
           
        cout << max << endl;

    }
    return 0;
}

AOJ Volume11 1141: Dirichlet's Theorem on Arithmetic Progressions

エラトステネスの篩で素数を求めておく。

/****************************************************
*    2012/06/23                                        *
*    AOJ Volume11 1141                                *
*    Dirichlet's Theorem on Arithmetic Progressions    *
*    ディリクレの算術級数定理                        *
*    crane
*****************************************************/
#include<iostream>
#include<cmath>
using namespace std;

#define MAX_N 1000000

int field[MAX_N];

int main(){
    /*素数テーブル作成*/
    field[0] = 0; field[1] = 0;
    for(int i=2; i<MAX_N; i++)    field[i] = 1;//初期化
    for(int i=2; i<sqrt((double)MAX_N)+1; i++){
        if(field[i] == 1)
            for(int j=i*2; j<MAX_N; j+=i)
                field[j] = 0;
    }

    int a,d,n;    //a->aからはじめる,  dずる増える,　n番目目の素数
    while(cin >> a >> d >> n, (a||d||n)){
        int cnt = 0;
        while(1){
            if(field[a]==1) cnt++;
            if(cnt==n) break;
            a += d;
        }
        cout << a << endl;
    }
    return 0;
}