明日から・・・

旅委関連でWinにしばらく移ることになりそう。。。

というわけで多分精進もしばらく…いや、できるかな？

3617

蟻本に掲載されてる問題。
貪欲法での解き方が紹介されてます。

僕はよんでしばらくおいてから復習的なかんじでコーディングしてみました。

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    int N;
    scanf("%d",&N);
    string cows="";
    for (int i=0; i<N; i++) {
        char tmp;
        cin>>tmp;
        cows+=tmp;
    }
    int cnt=0;
    while (!cows.empty()) {
        if (cnt!=0&&cnt%80==0) printf("\n");
        string rev=cows;
        reverse(rev.begin(),rev.end());
        if (cows<=rev) {
            putchar(cows[0]);
            cows.erase(0,1);
        }
        else {
            putchar(rev[0]);
            rev.erase(0,1);
            cows=rev;
        }
        cnt++;
    }
    printf("\n");
}

2386

これもアリ本掲載。
DFSの問題です。
こちらも復習として

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;
vector<string> map;
int N,M;
void dfs(int x, int y) 
{
    map[x][y]='.';
    for (int i=-1; i<=1; i++) {
        for (int j=-1; j<=1; j++) {
            if (x+i>=0&&x+i<N&&y+j>=0&&y+j<M&&map[x+i][j+y]=='W') {
                    dfs(x+i,j+y);
            }
        }
    }
    return ;   
}

int main()
{
    scanf("%d%d",&N,&M);
    for (int i=0; i<N; i++) {
        string tmp;
        cin>>tmp;
        map.push_back(tmp);
    }
    int res=0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (map[i][j]=='W') {
                dfs(i,j);
                res++;
            }
        }
    }
    printf("%d\n",res);
}

1852

アリ本の名前の由来だと思われる最初に掲載されていた問題。
おなじみなので解法はおぼえてましたorz

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    for (int ix=0; ix<t; ix++) {
        int pole,n;
        scanf("%d%d",&pole,&n);
        int ants[n];
        for (int i=0; i<n; i++) scanf("%d",&ants[i]);
        int MAX=0,MIN=0;
        for (int i=0; i<n; i++) {
            int maxdis=max(pole-ants[i],ants[i]);
            int mindis=min(pole-ants[i],ants[i]);
            if (MAX<maxdis) MAX=maxdis;
            if (MIN<mindis) MIN=mindis;
        }
        printf("%d %d\n",MIN,MAX);
    }
}

1014

DP問題として
しばらくやって個数制限付きナップザック問題に帰結したけど漸化式が考えつかなかったので蟻本で参照復習。

#include <cstdio>
#include <cstring>
using namespace std;
int main() 
{
    int n[6];
    int k=1;
    while(scanf("%d%d%d%d%d%d",&n[0],&n[1],&n[2],&n[3],&n[4],&n[5])) {
        if (n[0]==0&&n[1]==0&&n[2]==0&&n[3]==0&&n[4]==0&&n[5]==0) break;
        int sum=0;
        for (int i=0; i<6; i++) sum+=n[i]*(i+1);
        if (sum%2!=0) {
            printf("Collection #%d:\n",k);
            printf("Can't be divided.\n\n");
            k++;
            continue;
        }
        sum/=2;
        int dp[sum*2+1];
        memset(dp,-1,sizeof(dp));
        dp[0]=0;
        for (int i=0; i<6; i++) {
            if (n[i]==0) continue;
            for (int j=0; j<=sum*2; j++) {
                if (dp[j]>=0) {
                    dp[j]=n[i];
                }
                else if (j<i+1||dp[j-(i+1)]<0) {
                    dp[j]=-1;
                }
                else {
                    dp[j]=dp[j-(i+1)]-1;
                }
            }
        }
        printf("Collection #%d:\n",k);
        if (dp[sum]>=0) {
            printf("Can be divided.\n\n");
        }
        else {
            printf("Can't be divided.\n\n");
        }
        k++;
    }
}