夢追い人

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

タイトルの案が思い浮かばない。

よし、じゃあこれからJOI模擬練習でも・・・orz

0121

メモ化もしてるのになんだこのTLEはって思ったら、最初はループ判定、次にマップ判定間違えてて、
最終的に最初に全部計算しなきゃTLEになったので計三回程度TLEした←

#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
const string target="01234567";
struct puzzle {
    string stat;
    int zero;
    puzzle(string _s,int _x) {
        stat=_s;
        zero=_x;
    }
};
int d[4]={-1,1,-4,4};
int n;
int main() {
    queue<puzzle> que;
    map<string, int> done;
    que.push(puzzle(target,0));
    done[target]=0;
    while (!que.empty()) {
        puzzle now = que.front(); que.pop();
        int pos=now.zero;
        for (int i=0; i<4; i++) {
            int nx=pos+d[i];
            if ((nx>=0&&nx<4&&pos>=0&&pos<4)||
                (nx>=4&&nx<8&&pos>=4&&pos<8)||
                (nx>=0&&nx<4&&pos>=4&&pos<8&&abs(nx-pos)==4)||
                (nx>=4&&nx<8&&pos>=0&&pos<4&&abs(nx-pos)==4)) {
                string temp=now.stat;
                swap(temp[pos],temp[nx]);
                if (done.count(temp)==0) {
                    que.push(puzzle(temp,nx));
                    done[temp]=done[now.stat]+1;
                }
            }
        }
    }
    while (scanf("%d",&n)!=EOF) {
        string stats="";
        stats+=(n+'0');
        for (int i=1; i<8; i++) {
            scanf("%d",&n);
            stats+=(n+'0');
        }
        printf("%d\n",done[stats]);
    }
}

0087

やるだけ

#include <iostream>
#include <sstream>
#include <string>
#include <stack>
#include <vector>
#include <cstdio>
using namespace std;
int main() {
    string str;
    while (getline(cin, str)) {
        vector<string> vec;
        stack<double> stc;
        string temp="";
        for (int i=0; i<str.length(); i++) {
            if (str[i]==' ') {
                vec.push_back(temp);
                temp="";
            } else {
                temp+=str[i];
            }
        }
        if (temp.length()!=0) vec.push_back(temp);
        for (int i=0; i<vec.size(); i++) {
            if (vec[i]!="+"&&vec[i]!="-"&&vec[i]!="*"&&vec[i]!="/") {
                stringstream ss;
                ss<<vec[i];
                int n; ss>>n;
                stc.push((double)n);
            } else if (stc.size()>1) {
                double top=stc.top(); stc.pop();
                double top2=stc.top(); stc.pop();
                if (vec[i]=="+") stc.push(top+top2);
                else if (vec[i]=="-") stc.push(top2-top);
                else if (vec[i]=="*") stc.push(top*top2);
                else if (vec[i]=="/") stc.push(top2/top);
            }
        }
        printf("%.6f\n",stc.top());
    }
}

0189

ワーシャルフロイドやるだけ

#include <cstdio>
#include <cstring>
#include <climits>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
ll dist[10][10];
int main() {
    int n;
    while (scanf("%d",&n)!=EOF) {
        if (!n) break;
        for (int i=0; i<10; i++) for (int j=0; j<10; j++) {
            if (i==j) dist[i][j]=0;
            else dist[i][j]=INT_MAX;
        }
        set<int> town;
        int a, b, c;
        for (int i=0; i<n; i++) {
            scanf("%d%d%d",&a,&b,&c);
            dist[a][b]=c;
            dist[b][a]=c;
            town.insert(a); town.insert(b);
        }
        int sz=town.size();
        for (int k=0; k<sz; k++) {
            for (int i=0; i<sz; i++) {
                for (int j=0; j<sz; j++) {
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
        int rpos, res=INT_MAX;
        for (int i=0; i<sz; i++) {
            int sum=0;
            for (int j=0; j<sz; j++) if (dist[i][j]!=INT_MAX) sum+=dist[i][j];
            if (sum<res) {
                rpos=i;
                res=sum;
            }
        }
        printf("%d %d\n",rpos,res);
    }
}

0525

Rが少ないことに着目して横一列を裏返すか裏返さないかのパターンを全列挙。
これはbit使います。
それであとは縦に1の数を数えたとき1と0の数の多いほうを合計したのが答えになる。

#include <cstdio>
#include <algorithm>
using namespace std;
int osen[10][10000];
int main() {
    int r, c;
    while (scanf("%d%d",&r,&c)) {
        if (!r&&!c) break;
        for (int i=0; i<r; i++) for (int j=0; j<c; j++) {
            scanf("%d", &osen[i][j]);
        }
        int res=0;
        for (int S=0; S < 1<<r; S++) {
            for (int i=0; i<r; i++) {
                if (S>>i&1) {
                    for (int j=0; j<c; j++) osen[i][j]^=1;
                }
            }
            int cnt=0;
            for (int i=0; i<c; i++) {
                int one=0;
                for (int j=0; j<r; j++) one+=osen[j][i];
                cnt+=max(one,r-one);
            }
            for (int i=0; i<r; i++) {
                if (S>>i&1) {
                    for (int j=0; j<c; j++) osen[i][j]^=1;
                }
            }
            res=max(res,cnt);
        }
        printf("%d\n",res);
    }
}
広告を非表示にする