VKCupとJAG参加してきました

JAGの方はウォームアップだからみんな一問しか通してなかったので、普通に一発ACで22位
VKCupはオーダー・ナメナメをしていたので３つ落として1084位でした

VKCup

A

なんか友達のペアを探せってやつ。
適当にhashもどき実装してやった。
プレテストで0の場合分けを忘れていて-100

#include <cstdio>
#include <vector>
#include <iostream>
#include <cmath>
#include <cstring>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<string, string> P;
vector<string> name;
set<P> res;
int hash(string s) {
    int sz=name.size();
    for (int i=0; i<sz; i++) if (name[i]==s) return i;
    name.push_back(s);
    return sz;
}
string tos(int h) {
    return name[h];
}
vector<int> ts[2000][2000];   // ts[i][j]:=hash値iからhash値jへのコンタクトの時間
int main() {
    int n, d, t; scanf("%d%d",&n,&d);
    string a, b;
    for (int i=0; i<n; i++) {
        cin>>a>>b>>t;
        int ah=hash(a), bh=hash(b);
        ts[ah][bh].push_back(t);
    }
    int sz=name.size();
    for (int i=0; i<sz; i++) {
        for (int j=i+1; j<sz; j++) {
            int s1=ts[i][j].size(), s2=ts[j][i].size();
            if (s1==0||s2==0) continue;
            for (int k=0; k<s1; k++) {
                bool flag=false;
                for (int l=0; l<s2; l++) {
                    int dist=abs(ts[i][j][k]-ts[j][i][l]);
                    if (dist>0&&dist<=d) {
                        res.insert(P(tos(i),tos(j)));
                        flag=true;
                        break;
                    }
                }
                if (flag) break;
            }
        }
    }
    printf("%d\n",res.size());
    for (set<P>::iterator i=res.begin(); i!=res.end(); i++) {
        cout << (*i).first << " " << (*i).second << endl;
    }
}

B

オーダー・ナメナメ第一弾
普通に数え上げるだけらしいんですが、なんかオーダーを無駄に増やしてしまったよう。
1000色すべて調べてたのがだめだったのかな？
僕の解法は色番号をループしてその色番号での被りと半径かぶりを順次調べていってた
O(1000*ms*cs) : msはその色のマークの数、csはその色のキャップの数
となってTLE

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> mark[1000], cap[1000];
int main() {
    int n, m; scanf("%d%d",&n,&m);
    for (int i=0; i<n; i++) {
        int x, y; scanf("%d%d",&x,&y);
        mark[y-1].push_back(x);
    }
    for (int i=0; i<m; i++) {
        int a, b; scanf("%d%d",&a,&b);
        cap[b-1].push_back(a);
    }
    int cnt=0, bres=0;
    for (int i=0; i<1000; i++) {
        int ms=mark[i].size(), cs=cap[i].size();
        if (ms==0) continue;
        cnt+=min(ms,cs);
        for (int j=0; j<ms; j++) {
            for (int k=0; k<cs; k++) {
                if (mark[i][j]==cap[i][k]) {
                    cap[i][k]+=1000;
                    bres++;
                    break;
                }
            }
        }
    }
    printf("%d %d\n",cnt,bres);
}

C

オーダー・ナメナメ第二弾
同じ文字がめちゃくちゃ並んでるケースに当然対応できない愚直解でTLE
BITとか使うといいらしい（BITうまく使えないｗ）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef vector<int> vi;
map<char, vi> hash;
bool use[100][2000];
int main() {
    int k; scanf("%d",&k);
    string str; cin>>str;
    string res="";
    int n; scanf("%d",&n);
    int len=str.length();
    for (int i=0; i<len; i++) hash[str[i]].push_back(i);
    for (int i=0; i<len; i++) for (int j=0; j<k; j++) use[i][j]=true;
    for (int i=0; i<n; i++) {
        int p; char c; scanf("%d",&p); cin>>c;
        int sz=hash[c].size();
        int cnt=0;
        for (int j=0; j<k; j++) {
            bool flag=false;
            for (int l=0; l<sz; l++) {
                int h=hash[c][l];
                if (use[h][j]) cnt++;
                if (cnt==p) {
                    use[h][j]=false;
                    flag=true;
                    break;
                }
            }
            if (flag) break;
        }
    }
    for (int j=0; j<k; j++) {
        for (int i=0; i<len; i++) {
            if (use[i][j]) res+=str[i];
//            printf("%c%c",use[i][j]?'*':'-',str[i]);
        }
    }
    cout<<res<<endl;
}

D

回文だからマネーチャー（？発音しらないけど）とかいろいろ調べたんですが、どーせ判定は愚直にやってもいいんじゃね？ってやったら通ってしまいました。
１.まずi文字目からj文字が回文であるかどうかを判定
2.そのデータをつかってDP的な要領でi文字目以降の回文の出現個数を求めていく
3.最後にすべての回文に対してi+j文字目以降の回文の個数をたす
で出来ました。

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
string s;
bool ispal(int a, int b) {
    int len=s.length();
    for (int i=a, j=a+b-1; i<a+b; i++, j--) {
        if (s[i]!=s[j]) return false;
    }
    return true;
}
ll pals[2000][2001];
ll dp[2000];
int main() {
    cin>>s;
    int len=s.length();
    for (int i=0; i<len; i++) {
        for (int j=1; j<=len-i; j++) {
            if (j==1||ispal(i,j)) pals[i][j]=1;
        }
    }
    pals[0][len]=0;
    dp[len-1]=1;
    for (int i=len-2; i>=0; i--) {
        ll sum=0;
        for (int j=1; j<=len-i; j++) {
            sum+=pals[i][j];
        }
        dp[i]=dp[i+1]+sum;
    }
    ll res=0;
    for (int i=0; i<len; i++) {
        for (int j=1; j<=len-i; j++) {
            if (pals[i][j]) {
                res+=dp[i+j];
            }
        }
    }
    cout<<res<<endl;
}

E

オーダー・ナメナメ第三弾
多分イテレーターの扱いが微妙で枝刈できてなかったのが原因かなとか思いつつ単純にTLE解だったりするのかも。
すべての色の組み合わせに対してそれぞれの最高の組み合わせをしらべてたら終わりました

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef map<ll,vector<P> > M;
M stack;
int main() {
    int n; scanf("%d",&n);
    for (int i=0; i<n; i++) {
        ll c,s; cin>>c>>s;
        stack[c].push_back(P(s,i+1));
    }
    M::iterator it;
    for (it=stack.begin(); it!=stack.end(); it++) {
        sort((*it).second.rbegin(),(*it).second.rend());
    }
    ll mh=0, c1=0, c2=0, cnt=0;
    for (it=stack.begin(); it!=stack.end(); it++) {
        for (M::iterator it2=stack.begin(); it2!=stack.end(); it2++) {
            if ((*it).first!=(*it2).first) {
                int s1=(*it).second.size(), s2=(*it2).second.size();
                if (s1<s2) {
                    ll h=0;
                    for (int i=0; i<s1; i++) {
                        h+=(*it).second[i].first+(*it2).second[i].first;
                    }
                    h+=(*it2).second[s1].first;
                    if (mh<h) {
                        mh=h;
                        c1=(*it).first;
                        c2=(*it2).first;
                        cnt=s1*2+1;
                    }
                } else if (s1>s2) {
                    ll h=0;
                    for (int i=0; i<s2; i++) {
                        h+=(*it).second[i].first+(*it2).second[i].first;
                    }
                    h+=(*it).second[s2].first;
                    if (mh<h) {
                        mh=h;
                        c1=(*it).first;
                        c2=(*it2).first;
                        cnt=s2*2+1;
                    }
                } else {
                    ll h=0;
                    for (int i=0; i<s1; i++) {
                        h+=(*it).second[i].first+(*it2).second[i].first;
                    }
                    if (mh<h) {
                        mh=h;
                        c1=(*it).first;
                        c2=(*it2).first;
                        cnt=s1*2;
                    }
                }
            }
        }
    }
    cout<<mh<<endl; cout<<cnt<<endl;
//    cout<<c1<<" "<<c2<<endl;
    int rs1=stack[c1].size(), rs2=stack[c2].size();
    if (rs1<rs2) {
        for (int i=0; i<rs1; i++) {
            cout<<stack[c2][i].second<<" "<<stack[c1][i].second<<" ";
        }
        cout<<stack[c2][rs1].second<<endl;
    } else if (rs2<rs1) {
        for (int i=0; i<rs2; i++) {
            cout<<stack[c1][i].second<<" "<<stack[c2][i].second<<" ";
        }
        cout<<stack[c1][rs2].second<<endl;
    } else {
        for (int i=0; i<rs1; i++) {
            cout<<stack[c2][i].second<<" ";
            if (i!=rs1-1) cout<<stack[c1][i].second<<" ";
            else cout<<stack[c1][i].second<<endl;
        }
    }
}

JAG

A

ただその前に出現したことのあるパターンかを調べればよいので、一行読み込みで文字列として扱う卑劣な技をつかった

#include <iostream>
#include <cstdio>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    int n; scanf("%d",&n);
    string str; getline(cin,str);
    set<string> log;
    for (int i=0; i<n; i++) {
        getline(cin,str);
        if (log.find(str)!=log.end()) puts("Yes");
        else {
            log.insert(str);
            puts("No");
        }
    }
}