ARC022

奇跡が起きて1位。順位表のスクリーンショットは撮った。

• -

A : スーパーICT高校生

• 指定の文字列が部分列として含まれるか調べるだけの簡単なお仕事
• A問題だしと思ってムダにO(n^3)で書いた。反省はしていない。

#include <iostream>
#include <string>

using namespace std;

bool check(string s){
    int n = s.size();
    for(int i=0;i<n;i++){
        if(s[i]!='i'&&s[i]!='I') continue;
        for(int j=i+1;j<n;j++){
            if(s[j]!='c'&&s[j]!='C') continue;
            for(int k=j+1;k<n;k++){
                if(s[k]!='t'&&s[k]!='T') continue;
                return true;
            }
        }
    }
    return false;
}

int main(){
    string s;
    while(cin >> s){
        cout << (check(s) ? "YES" : "NO") << endl;
    }
}

B : 細長いお菓子

• はいはい、尺取り尺取り…と思ってたら2WAだした。これはひどい。
• とはいえ、こういうのはバグらせやすいのでサクッと書ける人々はすごいと思う。

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

int idx[100001];
int A[100000];

int main(){
    int N;
    while(cin >> N){
        for(int i=0;i<N;i++) cin >> A[i];
        memset(idx, -1, sizeof(idx));
        int cur = 0;
        int res = 0;
        for(int i=0;i<N;i++){
            if(idx[A[i]] >= cur){
                res = max(res, i-cur);
                cur = idx[A[i]]+1;
            }
            idx[A[i]] = i;
        }
        res = max(res, N-cur);
        cout << res << endl;
    }
}

C : ロミオとジュリエット

• 恥ずかしながら木の直径を求めるアルゴリズムを知らなくて、調べて書いた(白目)
• アルゴリズムのシンプルさに軽く感動を覚えました。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

typedef vector< vector<int> > Graph;

int getFar(const Graph& g, int start){
    const int INF = 1000000007;
    int n = g.size();
    vector<int> dist(n, INF);
    dist[start] = 0;
    queue<int> qu; qu.push(start);
    int res = start;
    while(!qu.empty()){
        int p = qu.front(); qu.pop();
        res = p;
        for(int i=0;i<g[p].size();i++){
            int next = g[p][i];
            if(dist[next] < dist[p]+1) continue;
            dist[next] = dist[p]+1;
            qu.push(next);
        }
    }
    return res;
}

int main(){
    int N;
    while(cin >> N){
        Graph g(N);
        for(int i=0;i<N-1;i++){
            int a, b; cin >> a >> b;
            g[a-1].push_back(b-1);
            g[b-1].push_back(a-1);
        }
        int s = getFar(g, 0);
        int t = getFar(g, s);
        cout << s+1 << " " << t+1 << endl;
    }
}

D : スプリンクラー

• とりあえずy座標ごとに各スプリンクラーがカバーする区間を計算した。
• その後、区間をマージすることで必要個数を出して、とりあえず30点得た。

• まだ全ての円が原点を通るという性質を使ってない。
• 60点と100点の差が円の存在範囲だけなので、60点は30点の延長な気がしてくる。
• 中心が凸包を構成する円だけ調べたら良いのでは、と思うも正当性に自信がない。
• やること無いし書いてみるか、と書いて投げたら60点取れてしまった。
• ここで残り20分くらい。暫定1位だったのでスクリーンショット撮った。

• 満点解法にするには区間マージを賢くしないといけなさそうな雰囲気。
• やばそう、と思って残り時間はニセコイ12巻を読んでました。ごめんなさい。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>

using namespace std;

const double EPS = 1e-8;

typedef complex<double> P;

double cross(P a, P b){ return imag(conj(a)*b); }
double angle(P a, P b){ return arg(conj(a)*b); }

bool compare(const P &a, const P &b){
    return make_pair(real(a),imag(a)) < make_pair(real(b),imag(b));
}

vector<P> convexHull(vector<P> vp){
    if(vp.size() < 3) return vp;
    sort(vp.begin(), vp.end(), compare);
    vector< pair<double,int> > vi;
    for(int i=1;i<vp.size();i++) vi.push_back(make_pair(angle(P(1,0),vp[i]-vp[0]), i));
    sort(vi.begin(), vi.end());
    vector<P> res(2);
    res[0] = vp[0]; res[1] = vp[vi[0].second];
    for(int i=1;i<vi.size();i++){
        P next = vp[vi[i].second];
        int sz = res.size();
        while(sz>=2&&cross(res[sz-1]-res[sz-2],next-res[sz-1])<EPS){
            res.pop_back(); sz--;
        }
        res.push_back(next);
    }
    return res;
}

int main(){
    int N;
    while(cin >> N){
        vector< pair<int,int> > v[6000];
        vector<P> vp;
        for(int i=0;i<N;i++){
            int x, y; cin >> x >> y;
            vp.push_back(P(x,y));
        }
        vp = convexHull(vp);
        for(int i=0;i<vp.size();i++){
            int x = vp[i].real();
            int y = vp[i].imag();
            int sr = x*x+y*y;
            int r = sqrt(sr)+1e-8;
            for(int j=-r;j<=r;j++){
                int range = sqrt(sr-j*j)+1e-8;
                int yIdx = y+j+3000;
                v[yIdx].push_back(make_pair(x-range,x+range));
            }
        }
        int res = 0;
        for(int i=0;i<6000;i++){
            if(v[i].empty()) continue;
            sort(v[i].begin(), v[i].end());
            int begin = v[i][0].first;
            int end   = v[i][0].second;
            for(int j=1;j<v[i].size();j++){
                if(end < v[i][j].first){
                    res += end-begin+1;
                    begin = v[i][j].first;
                    end   = v[i][j].second;
                } else {
                    end = max(end, v[i][j].second);
                }
            }
            res += end-begin+1;
        }
        cout << res << endl;
    }
}

• -

ついにAtCoderで1800というレーティングを頂きました。黄色くらい？
この後のGCJで使う分の運が残ってるのか、とても不安です。