ARC#1＝バーチャルコンテスト

バーチャルコンテストで15位でした

PKU 2001

トライ使いました(-^〇^-)
仕組み理解

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct Trie {
    int val;
    Trie *next[0x100];
    Trie(int n) {
        val=n;
        fill(next, next+0x100, (Trie*)0);
    }
};
void insert(Trie *t, char *s) {
    if (*s=='\0') return;
    if (t->next[*s]==NULL) {
        t->next[*s]=new Trie(1);
    } else {
        t->next[*s]->val++;
    }
    insert(t->next[*s], s+1);
}
int solve(Trie *t, char *s, int sz) {
    if (*(s+sz)=='\0') return sz;
    if (t->next[*(s+sz)]->val<2) return sz+1;
    return solve(t->next[*(s+sz)],s,sz+1);
}
int main() {
    char s[1020][30];
    int n=0;
    Trie t(1);
    while (scanf("%s",s[n])!=EOF) {
        insert(&t,s[n]); n++;
    }
    for (int i=0; i<n; i++) {
        int cnt=solve(&t,s[i],0);
        printf("%s ",s[i]);
        for (int j=0; j<cnt; j++) cout<<s[i][j];
        cout<<endl;
    }
}

GCJ A

注意力の問題
注意力不足を露呈して７WA

#include <iostream>
#include <map>
using namespace std;
map<char, char> mp;
int main() {
    mp['a']='y'; mp['b']='h'; mp['c']='e'; mp['d']='s'; mp['e']='o';
    mp['f']='c'; mp['g']='v'; mp['h']='x'; mp['i']='d'; mp['j']='u';
    mp['k']='i'; mp['l']='g'; mp['n']='b'; mp['m']='l'; mp['o']='k';
    mp['p']='r'; mp['q']='z'; mp['r']='t'; mp['s']='n'; mp['t']='w';
    mp['u']='j'; mp['v']='p'; mp['w']='f'; mp['x']='m'; mp['y']='a';
    mp['z']='q';
    int t; scanf("%d",&t);
    string str;
    getline(cin, str);
    for (int ix=1; ix<=t; ix++) {
        getline(cin, str);
        for (int i=0; i<str.length(); i++) {
            if (str[i]==' ') continue;
            str[i]=mp[str[i]];
        }
        cout<<"Case #"<<ix<<": "<<str<<endl;
    }
}

GCJ B

貪欲

#include <cstdio>
int list[100];
int main() {
    int t; scanf("%d",&t);
    for (int ix=1; ix<=t; ix++) {
        int n, s, p; scanf("%d%d%d",&n,&s,&p);
        for (int i=0; i<n; i++) scanf("%d",&list[i]);
        int res=0;
        for (int i=0; i<n; i++) {
            int x=(list[i]+2)/3;
            if (list[i]==0&&p!=0) continue;
            if (x>=p) {
                res++;
            } else if (s>0&&p*3-list[i]<=4) {
                res++;
                s--;
            }
        }
        printf("Case #%d: %d\n",ix,res);
    }
}

GCJ C-small

largeわかんねぇ〜とか言ってたらどうやらこれをSTLで回転させたりすると普通にできるらしい

#include <cstdio>
#include <set>
#include <map>
#include <sstream>
using namespace std;
typedef pair<int, int> P;
int main() {
    int t; scanf("%d",&t);
    for (int ix=1; ix<=t; ix++) {
        int a, b; scanf("%d%d",&a,&b);
        int x;
        string st, st2;
        set<P> res;
        for (int i=a; i<=b; i++) {
            stringstream s1; s1<<i; s1>>st;
            int len=st.length();
            if (len==1) continue;
            for (int j=0; j<len-1; j++) {
                char temp=st[0];
                for (int k=0; k<len-1; k++) st[k]=st[k+1];
                st[len-1]=temp;
                stringstream s2; s2<<st; s2>>x;
                if (i<x&&x<=b) {
                    res.insert(P(i,x));
                }
            }
        }
        printf("Case #%d: %d\n",ix,res.size());
    }
}

ARC A

やるだけ

#include <cstdio>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
int main() {
    int n; scanf("%d",&n);
    string c; cin>>c;
    P cnt[4];
    for (int i=0; i<4; i++) cnt[i]=P(0,i+1);
    int len=c.length();
    for (int i=0; i<len; i++) {
        cnt[c[i]-'1'].first++;
    }
    sort(cnt, cnt+4);
    printf("%d %d\n",cnt[3].first,cnt[0].first);
}

ARC B

やるだけ

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
    int a, b; scanf("%d%d",&a,&b);
    if (a>b) swap(a,b);
    int res=0, diff=b-a;
    if (diff%10>=8) {
        res+=(diff+9)/10;
        diff-=(diff+9)/10*10;
    } else {
        res+=diff/10;
        diff-=diff/10*10;
    }
    if (diff%5>=4) {
        res+=(diff+4)/5;
        diff-=(diff+4)/5*5;
    } else {
        res+=diff/5;
        diff-=diff/5*5;
    }
    res+=abs(diff);
    printf("%d\n",res);
}