夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

勢いで埋めてた

DEGwerさんがやるだけ埋めてたせいで、StatusDiffみたいなことしてたら時間をとってしまったんよ〜←
あ、別にDEGwerさんはなんにも悪くないんだけどねっ

ARC C

やった。全ての可能性を単純に調べていく

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool ok=true;
vector<string> mp(8);
int row[8], col[8], dia[2][15];
void dfs(int c) {
    if (ok&&c==8) {
        for (int i=0; i<8; i++) cout<<mp[i]<<endl;
        ok=false;
        return;
    }
    if (col[c]>0) {
        dfs(c+1);
        return;
    }
    col[c]++;
    for (int i=0; i<8; i++) {
        if (row[i]>0||dia[0][c-i+7]>0||dia[1][c+i]>0) continue;
        mp[c][i]='Q';
        row[i]++; dia[0][c-i+7]++; dia[1][c+i]++;
        dfs(c+1);
        mp[c][i]='.';
        row[i]--; dia[0][c-i+7]--; dia[1][c+i]--;
    }
    col[c]--;
    return;
}
int main() {
    for (int i=0; i<8; i++) {
        cin>>mp[i];
        for (int j=0; j<8; j++) if (mp[i][j]=='Q') {
            row[j]++; col[i]++;
            dia[0][i-j+7]++; dia[1][j+i]++;
        }
    }
    for (int i=0; i<8; i++) if (row[i]>1||col[i]>1) {
        puts("No Answer");
        return 0;
    }
    for (int i=0; i<15; i++) if (dia[0][i]>1||dia[1][i]>1) {
        puts("No Answer");
        return 0;
    }
    dfs(0);
    if (ok) puts("No Answer");
}

Dは適度に難しいのでまだです。

AOJ

1085

ループを工夫して実際の計算量をへらす。

#include <cstdio>
#include <algorithm>
using namespace std;
int r[20001];
int main() {
    int n, s;
    while (scanf("%d%d",&n,&s)) {
        if (!n&&!s) break;
        for (int i=0; i<n; i++) scanf("%d",&r[i]);
        sort(r, r+n);
        int cnt=0;
        for (int i=n-1; i>0; i--) {
            if (r[i]>=s) cnt+=i;
            else {
                for (int j=i-1; j>=0; j--) {
                    if (r[i]+r[j]<=s) break;
                    cnt++;
                }
            }
        }
        printf("%d\n",cnt);
    }
}

1084

全探索、何か最初は最大値の計算みすってた

#include <cstdio>
#include <algorithm>
using namespace std;
int c[100];
int calc(int n, int k) {
    int s=0, mt=0;
    for (int i=0; i<=n-k; i++) {
        int temp=1;
        for (int j=0; j<k; j++) temp*=c[i+j];
        mt=max(mt, temp);
    }
    return mt;
}
int main() {
    int n, k;
    while (scanf("%d%d",&n,&k)) {
        if (!n&&!k) break;
        for (int i=0; i<n; i++) scanf("%d",&c[i]);
        int mt=calc(n,k), res=0;
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                swap(c[i],c[j]);
                res=max(res, calc(n,k));
                swap(c[i],c[j]);
            }
        }
        // printf("%d %d\n",res, mt);
        if (res<mt) puts("NO GAME");
        else printf("%d\n",res-mt);
    }
}

1074

時間に名前突っ込んでごにょごにょ

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef pair<int, string> P;
bool comp(const P& a, const P& b) {
    if (a.first!=b.first) return a.first<b.first;
    return a.second<b.second;
}
int main() {
    int n;
    while (scanf("%d",&n)) {
        if (!n) break;
        vector<string> cnt[31];
        map<string, int> mp;
        P po[n];
        for (int i=0; i<n; i++) {
            string name; cin>>name;
            po[i]=P(0,name);
            mp[name]=i;
            int m; scanf("%d",&m);
            for (int j=0; j<m; j++) {
                int d; scanf("%d",&d);
                cnt[d].push_back(name);
            }
        }
        for (int i=0; i<31; i++) {
            int sz=cnt[i].size();
            int x=n-sz+1;
            for (int j=0; j<sz; j++) {
                po[mp[cnt[i][j]]].first+=x;
            }
        }
        sort(po, po+n, comp);
        cout<<po[0].first<<" "<<po[0].second<<endl;
    }
}

以上!!勉強にもどります(しろめ)

広告を非表示にする