合宿埋め〜

旅行先で始めました

score

めんどくさい

#include <cstdio>
#include <algorithm>
using namespace std;
struct score {
    int s, r, n;
};
bool comp1(const score& a, const score& b) {
    return a.s>b.s;
}
bool comp2(const score& a, const score& b) {
    return a.n<b.n;
}
score stu[100000];
int main() {
    int n; scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&stu[i].s);
        stu[i].n=i;
    }
    sort(stu, stu+n, comp1);
    int rank=1, cnt=0, bef=-1;
    for (int i=0; i<n; i++) {
        if (bef!=stu[i].s) {
            bef=stu[i].s;
            rank+=cnt;
            stu[i].r=rank;
            cnt=1;
        } else {
            cnt++;
            stu[i].r=rank;
        }
    }
    sort(stu, stu+n, comp2);
    for (int i=0; i<n; i++) {
        printf("%d\n",stu[i].r);
    }
}

factorial

数学ゲーでカンニングした。
n=p1^x1 * p2^x2 * ... * pm^xm
とあらわせたとき
max(pk*xk)が答えになるというもの。
よく考えたら自明だけれどもこんなの無理げー（数学力つけよう）

#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int n; scanf("%d",&n);
    int res, ans=1;
    for (int i=2; i<=n; i++) {
        res=0;
        while (n%i==0) {
            n/=i;
            res+=i;
        }
        ans=max(ans,res);
    }
    printf("%d\n",ans);
}

mall

-1の処理にちょっと手間取りました。
-1をINT_MAXとかにして、もれないように合計をlong longで計算すると、ようするにただの累積和です

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;
int field[1005][1005];
ll sum[1005][1005];
int m,n,a,b;
int main() {
    scanf("%d%d%d%d",&m,&n,&a,&b);
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
        scanf("%d",&field[i][j]);
        if (field[i][j]==-1) field[i][j]=INT_MAX;
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            sum[i][j]=field[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
        }
    }
    ll res=INT_MAX;
    for (int i=b; i<=n; i++) {
        for (int j=a; j<=m; j++) {
            ll s=sum[i][j]-sum[i-b][j]-sum[i][j-a]+sum[i-b][j-a];
            res=min(res, s);
        }
    }
    printf("%lld\n",res);
}

building

いつやったやつだしwww
最長増加部分列ね

#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 20000
int main() {
	int n; scanf("%d",&n);
	int a[n], dp[n];
	for (int i=0; i<n; i++) scanf("%d",&a[i]);
	fill(dp, dp+n, INF);
	for (int i=0; i<n; i++) {
		*lower_bound(dp,dp+n,a[i])=a[i];
	}
	printf("%d\n",lower_bound(dp,dp+n,INF)-dp);
}

route

dijkstra変形だったけど、90点しか取れなかったので最後カンニングした
ポイントは頂点というより各辺を使うまでの最短を確定させていくといった感じ

#include <cstdio>
#include <cmath>
#include <climits>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;
struct edge {
int from,to, cost;
bool flag;
};
struct dg { int x, y; };
typedef pair<int, edge*> P;
vector<edge> G[105];
dg dot[105];
bool isdon(int a, int b, int c) {
    long long ax=dot[a].x-dot[b].x, ay=dot[a].y-dot[b].y;
    long long cx=dot[c].x-dot[b].x, cy=dot[c].y-dot[b].y;
    long long ac=ax*cx+ay*cy;
    if (ac<=0) return true;
    else return false;
}
void dijkstra() {
    priority_queue<P, vector<P>, greater<P> > que;
    for (int i=0; i<G[0].size(); i++) {
        que.push(P(G[0][i].cost,&G[0][i]));
    }
    while (!que.empty()) {
        P p=que.top(); que.pop();
        int dist=p.first;
        edge& e=*p.second;
        if (e.flag) continue;
        e.flag=true;
        if (e.to==1) {
            printf("%d\n",dist);
            return;
        }
        for (int i=0; i<G[e.to].size(); i++) {
            edge& e2=G[e.to][i];
            if (isdon(e.from,e.to,e2.to)) {
                que.push(P(dist+e2.cost,&e2));
            }
        }
    }
    puts("-1");
    return;
}
int main() {
    int n, m; scanf("%d%d",&n,&m);
    for (int i=0; i<n; i++) scanf("%d%d",&dot[i].x,&dot[i].y);
    for (int i=0; i<m; i++) {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        G[a-1].push_back((edge){a-1,b-1,c,false});
        G[b-1].push_back((edge){b-1,a-1,c,false});
    }
    dijkstra();
}

anagram

めんどくさーいってダダこねちゃったやつ(´・ω・｀)
よくある数学の問題でもあるよね、重複を上手く処理しながら数えます

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
map<char, int> cnt;
ll calc[21];
int main() {
    calc[0]=0;
    calc[1]=1;
    for (int i=2; i<=20; i++) calc[i]=calc[i-1]*i;
    string str; cin>>str;
    for (int i=0; i<str.size(); i++) {
        if (cnt.find(str[i])!=cnt.end()) cnt[str[i]]++;
        else cnt[str[i]]=1;
    }
    ll ans=0;
    int sz=str.size()-1;
    for (int i=0; i<str.size()-1; i++) {
        for (map<char,int>::iterator j=cnt.begin(); j!=cnt.end(); j++) {
            if ((*j).first==str[i]) break;
            cnt[(*j).first]--;
            ll res=0;
            if (cnt[(*j).first]>=0) res+=calc[sz-i];
            for (map<char,int>::iterator it=cnt.begin(); it!=cnt.end(); it++) {
                if ((*it).second>=2) res/=calc[(*it).second];
            }
            ans+=res;
//            printf("%d %lld %c\n",i,res,(*j).first);
            cnt[(*j).first]++;
        }
        cnt[str[i]]--;
    }
    printf("%lld\n",ans+1);
}