精進 - 夢追い人

やーーー

1258

Prim

#include <cstdio>
#include <algorithm>
#define INF 1000001
using namespace std;
typedef long long ll;
int cost[100][100];
int mincost[100];
bool used[100];
int V;
ll prim() {
    for (int i=0; i<V; i++) {
        mincost[i]=INF;
        used[i]=false;
    }
    mincost[0]=0;
    ll res=0;
    while (true) {
        int v = -1;
        for (int u=0; u<V; u++) {
            if (!used[u]&&(v==-1||mincost[u]<mincost[v])) v=u;
        }
        if (v==-1) break;
        used[v]=true;
        res+=mincost[v];
        for (int u=0; u<V; u++) {
            mincost[u]=min(mincost[u], cost[v][u]);
        }
    }
    return res;
}
int main() {
    while (scanf("%d",&V)!=EOF) {
        for (int i=0; i<V; i++) for (int j=0; j<V; j++) {
            scanf("%d",&cost[i][j]);
            if (i==j) cost[i][j]=INF;
        }
        printf("%lld\n",prim());
    }
}

3264

Segment-Tree RMQ

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
const int MAX_N = 1 << 17;
int n, dat[2*MAX_N-1], dat2[2*MAX_N-1];
void init(int n_) {
    n=1;
    while (n<n_) n*=2;
    for (int i=0; i<2*n-1; i++) {
        dat[i]=INT_MAX;
        dat2[i]=INT_MIN;
    }
}
void update(int k, int a) {
    k += n-1;
    dat[k]=a;
    dat2[k]=a;
    while (k>0) {
        k=(k-1)/2;
        dat[k]=min(dat[k*2+1],dat[k*2+2]);
        dat2[k]=max(dat2[k*2+1],dat2[k*2+2]);
    }
}
int query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return INT_MAX;
    if (a <= l && r <= b) return dat[k];
    else {
        int vl=query(a,b,k*2+1,l,(l+r)/2);
        int vr=query(a,b,k*2+2,(l+r)/2,r);
        return min(vl, vr);
    }
}
int query2(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return INT_MIN;
    if (a <= l && r <= b) return dat2[k];
    else {
        int vl=query2(a,b,k*2+1,l,(l+r)/2);
        int vr=query2(a,b,k*2+2,(l+r)/2,r);
        return max(vl, vr);
    }
}
int main() {
    int nx,q; scanf("%d%d",&n,&q);
    nx=n;
    init(n);
    for (int i=0; i<nx; i++) {
        int cow; scanf("%d",&cow);
        update(i,cow);
    }
    for (int i=0; i<q; i++) {
        int a, b; scanf("%d%d",&a,&b);
        int r1=query(a-1,b,0,0,n);
        int r2=query2(a-1,b,0,0,n);
        printf("%d\n",r2-r1);
    }
}

2823

deque
アルゴリズム自体は頭にあったけど実装力なくてずっと実装できなかったもの。
ちなみにG++だと通りません。C++で通ります。

#include <cstdio>
const int MAX_N = 1000000;
int n, k;
int a[MAX_N];

int min[MAX_N], max[MAX_N];
int deq1[MAX_N], deq2[MAX_N];
int main() {
    while (scanf("%d%d",&n,&k)!=EOF) {
        for (int i=0; i<n; i++) scanf("%d",&a[i]);
        int s=0, t=0;
        for (int i=0; i<n; i++) {
            while (s < t && a[deq1[t-1]] >= a[i]) t--;
            deq1[t++] = i;
            if (i - k + 1 >= 0) {
                min[i - k + 1] = a[deq1[s]];
                if (deq1[s] == i - k + 1) {
                    s++;
                }
            }
        }
        s=0; t=0;
        for (int i=0; i<n; i++) {
            while (s < t && a[deq2[t-1]] <= a[i]) t--;
            deq2[t++] = i;
            if (i - k + 1 >= 0) {
                max[i - k + 1] = a[deq2[s]];
                if (deq2[s] == i - k + 1) {
                    s++;
                }
            }
        }
        for (int i=0; i<=n-k; i++) printf("%d%c",min[i],i==n-k?'\n':' ');
        for (int i=0; i<=n-k; i++) printf("%d%c",max[i],i==n-k?'\n':' ');
    }
}

2190

やるだけですが、Xが末尾にしか使えないというのを最初知らずにWA

#include <iostream>
using namespace std;
int main() {
    string isbn; cin >> isbn;
    int pos, sum=0;
    for (int i=0; i<10; i++) {
        if (isbn[i]=='?') pos=10-i;
        else {
            if (isbn[i]=='X') {
                sum += 10*(10-i);
            } else {
                sum += (isbn[i]-'0')*(10-i);
            }
        }
    }
    int ans=-1;
    for (int i=0; i<11; i++) {
        if ((sum+i*pos)%11==0) {
            ans=i;
        }
    }
    if ((pos!=1&&ans==10)||ans==-1) {
        cout << -1 << endl;
    } else if (pos==1&&ans==10) {
       cout << "X" << endl;
    } else {
       cout << ans << endl;
    }
}