ICPC2012 新入生教育編2 全探索

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

本日は新入生に向けて探索のテクニックを伝授した。以下は、その練習問題と解説を記す。
(ここ教えたほうがいいとかフィードバックあったらコメントにお願いします)

部分和探索

24個の正の整数の並び中で連続した5つを取り出した時、最大値を求めなさい
(なお、末尾と先頭は連続しているとする)

input
n
a000 a001 a002 ... a023
a100 a101 a102 ... a123
...
an00 an01 an02 ... an23

0 < axxx < 1000000
0 <  n   < 1000000

output
a0max
a1max
...
anmax

sample input
1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1

sample output 
56


単純に24回ループの中に5回ループを持たせるだけでよい。
ただし、タイプミスや不慮の事故を減らすために定数化はしておくべきである。

新入生に求める解放
#include <iostream>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)

const int MAXN=24; // 数字の配列の最大長
const int LEN=5;   // 連続する数
int a[MAXN];

int main()
{
    int n; cin>>n; REP(x,n) 
    {
        rep(MAXN) cin>>a[i]; // 配列に確保しておく

        int ans=0; REP(i,MAXN)
        {
            int v=0; REP(t,LEN) v+=a[(i+t)%MAXN]; //剰余を使って末尾のループに対応する
            ans=max(ans,v); // 最大値を確保する
        }

        cout<<ans<<endl;
    }

    return 0;
}
もうちょっとまともな回答
#include <iostream>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)

const int MAXN=24;
const int LEN=5;
int a[MAXN];

int main()
{
    int n; cin>>n; REP(x,n) 
    {
        rep(MAXN) cin>>a[i];

        int v=0; rep(LEN){ v+=a[i];}
        int ans=v; // 初期値

        rep(MAXN)
        { 
            v += a[(i+LEN)%MAXN]-a[i]; 
            ans = max(ans,v); 
        }

        cout<<ans<<endl;
    }

    return 0;
}

IO回りなど基本的なところは変わっていませんが、連続した部分和をどう算出するかが異なっています。
int v;を用いて前回の値を利用しています。


例えば、a[0]+a[1]+a[2]+a[3]+a[4]の次の値はa[1]+a[2]+a[3]+a[4]+a[5]です。
つまり、a[0]とa[5]に注目すればよいのです。


今回は5つの連続した値でしたが1000000つの連続した値といったようにオーダーが大きくなったときに対応できるかどうかが肝になってきます。

面積と長さの算出

2次元平面にn個の長方形を貼り付けることを考える。
長方形の左上座標と幅と長さが与えられた時、その面積と辺の長さを出力しなさい。

input
n
x1 y1 w1 h1
x2 y2 w2 h2

1 <= n < 100
0 <= x,y,w,h < 1000

output
a b

sample input
2
1 2 3 4
2 5 6 2

sample output
22 24


与えられた長方形を2次元配列にマッピングしていきましょう。
そしてらforループで2次元配列を見ていくだけでよいですね。

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

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)

const int MAXN=2048;
bool U[MAXN][MAXN];

int main()
{
    int n; while(cin>>n)
    {
        memset(U,0,sizeof(U));

        int xx,yy,ww,hh; rep(n)
        {
            cin>>xx>>yy>>ww>>hh; xx++; yy++; // 0-index => 1-index
            REP(y,hh) REP(x,ww) U[y+yy][x+xx]=true;
        }

        int ans1=0,ans2=0; REP(y,MAXN) REP(x,MAXN)
        {
            if(U[y][x]) ans1++; else continue; // 長方形の内部以外は戻す
            if(!U[y-1][x]) ans2++; // 端っこ判定
            if(!U[y+1][x]) ans2++; // 端っこ判定
            if(!U[y][x-1]) ans2++; // 端っこ判定
            if(!U[y][x+1]) ans2++; // 端っこ判定
        }

        cout<<ans1<<" "<<ans2<<endl;
    }

    return 0;
}