SRM500 D2H GeometricProgressions

2つの等比数列が与えられる．この中で異なる数の個数を求める

考察

愚直に計算するとオーバーフローする．ここで素因数分解を考える．いつも素因数分解というと

としていたが，(このままではやったらTLEになるので)

とした．

素因数分解は必ず一意に定まるので数が等しければ素因数分解も等しい．後はこれをmapに突っ込んでsizeを取った．
SystemTest落ちまくり．以下の事を全く頭に入れていなかった．
- 初項が0なら必ず0
- 公比が1の場合は，必ず初項
- 初項が0でなく公比が0の場合は，n == 1ならば00 = 1より初項だけ，n != 1ならば初項と0になる．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <queue>
#include <set>
#include <map>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
typedef long long ll;

vector<int> func(int n) {
    vector<int> ret;
    if(n == 0 || n == 1) {
        ret.push_back(n);
        return ret;
    }

    int a = 2;
    while(n >= a*a) {
        if(n%a == 0) {
            n /= a;
            ret.push_back(a);
        }
        else {
            a++;
        }
    }

    if(n > 1) ret.push_back(n);

    return ret;
}

class GeometricProgressions {
  public:
  int count(int b1, int q1, int n1, int b2, int q2, int n2) {
        map<vector<pair<int,int> >,int> m;

        vector<int> B1 = func(b1);
        vector<int> Q1 = func(q1);
        vector<int> B2 = func(b2);
        vector<int> Q2 = func(q2);

        map<int,int> cnt;
        rep(i,B1.size()) {
            cnt[B1[i]]++;
        }

        vector<pair<int,int> > v;
        map<int,int>::iterator ite;
        for(ite = cnt.begin();ite != cnt.end();ite++) {
            v.push_back(make_pair(ite->first,ite->second));
        }

        m[v]++;

        if(q1 == 0) {
            if(b1 != 0 && n1 != 1) {
                vector<pair<int,int> > res;
                res.push_back(make_pair(0,1));
                m[res]++;
            }
        }
        else if(b1 != 0 && q1 != 1) {
            rep(i,n1-1) {
                rep(j,Q1.size()) cnt[Q1[j]]++;

                vector<pair<int,int> > res;
                map<int,int>::iterator ite;
                for(ite = cnt.begin();ite != cnt.end();ite++) {
                    res.push_back(make_pair(ite->first,ite->second));
                }
                m[res]++;
            }
        }

        map<int,int> cnt2;
        rep(i,B2.size()) {
            cnt2[B2[i]]++;
        }

        vector<pair<int,int> > v2;
        for(ite = cnt2.begin();ite != cnt2.end();ite++) {
            v2.push_back(make_pair(ite->first,ite->second));
        }

        m[v2]++;

        if(q2 == 0) {
            if(b2 != 0 && n2 != 1) {
                vector<pair<int,int> > res;
                res.push_back(make_pair(0,1));
                m[res]++;
            }
        }
        else if(b2 != 0 && q2 != 1) {
            rep(i,n2-1) {
                rep(j,Q2.size()) cnt2[Q2[j]]++;

                vector<pair<int,int> > res;
                map<int,int>::iterator ite;
                for(ite = cnt2.begin();ite != cnt2.end();ite++) {
                    res.push_back(make_pair(ite->first,ite->second));
                }

                m[res]++;
            }
        }

        return m.size();
  }
};

場合分けの書き方がやばい．もっとシンプルに書けるようになりたい．

Jul 14th, 2015
srm, topcoder

Codeforces311-div2C Arthur and Table

http://codeforces.com/contest/557/problem/C

足の長さがバラバラなのでこれを安定状態にしたい．安定状態になるには足の最大の長さの本数が全体の本数の半分より多ければよい．その時の最小のコストを求める．

Sampleを考える．長さ1を1マスとし，文字がコストを表す．取り除いた足を赤色で表現する．

Sample1

長さ5を取り除くほうがコストが安い

Sample2

既に安定状態である

Sample3

長さ2に揃える．長さ3は全て取り除き，個数が半分より多くなるように長さ1を1つ取り除く．

考察

どの長さで揃えるかを探索する．仮に揃える長さをLと決めた場合，全体のコストの和からLを引き，後は長さLの足の個数-1個分残すようにすればよいとわかる．長さでsortし小さい順から見ていけば，その処理ができる．

揃える長さを緑とした時に，赤の部分は全て取り除くことになる．
後は緑より小さい足を緑の個数より少なくすればよい．出来るだけコストを抑えたいのでコストが大きい棒を残すようにする．よって全体のコストの和-揃える長さ-(それより長さが短い足をコストの大きい順に個数が少なくなるまで)で求める．

Code

コストが大きい順に見たいためpriority_queueを用いて大きい順に取った．最初は小さい順からとってしまい．WAを生やした．mapを使っているからidなどを作らずにmap巡回をしたほうがより分かりやすい(?)．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n;
    cin >> n;

    vector<int> L(n),D(n);
    rep(i,n) cin >> L[i];
    rep(i,n) cin >> D[i];

    vector<int> id(L.begin(),L.end());
    sort(id.begin(),id.end());
    id.erase(unique(id.begin(),id.end()),id.end());

    int sum = 0;
    map<int,vector<int> > m;
    rep(i,n) {
        m[L[i]].push_back(D[i]);
        sum += D[i];
    }

    int ans = sum;
    priority_queue<int> que;
    rep(i,id.size()) {
        vector<int> v(m[id[i]].begin(),m[id[i]].end());
        int res = sum;
        int cnt = v.size()-1;

        rep(j,v.size()) res -= v[j];

        vector<int> t;
        while(que.size() && cnt) {
            int q = que.top();
            que.pop();

            res -= q;
            t.push_back(q);
            cnt--;
        }

        ans = min(ans,res);

        rep(j,t.size()) que.push(t[j]);
        rep(j,v.size()) que.push(v[j]);
    }

    cout << ans << endl;

    return 0;
}
Jul 12th, 2015
codeforces

SRM662 Flee

(0,0)から(10100,0)に行きたい．最大3つまで警備員の場所が与えられる．目的地に行くことが出来る最大の距離を求める．

Sample0

右にそのまま行く

Sample1

これ以上大きくすると原点を覆ってしまう.また同じ点が与えられることもある

Sample2

右の道は行けないけど左上を通ればよい

Sample3

これもSample0と同様右でよい

考察

場合分けして考えた.
- n = 1の時は，原点との距離が最大の距離である
- n = 2の時は，原点との距離が小さい方が最大の距離である
- n = 3の時は，その3点で構成される三角形に内包されているかいないかに分ける

内包されていない場合

具体的に内包されていないとは次のような場合である
このような場合は原点を覆わないようにすればよいので，原点との距離が最小となる距離を選べばよい

内包されている場合

Sample0を考える．この場合の原点との距離が最小なのは5.09…である．しかしこの距離を採用すると，これでは目的地に行くことが出来ない．
ここで答えの5は(1,5)と(1,-5)との距離の半分である．つまり原点を覆わずに，円が重ならない場所が1つでもあればよい．

Code

内包されている場合は各頂点と原点との距離の最小値と，各頂点間の距離の半分の中から条件を満たす最大値を返す．また距離を考える場合,ルートを取らずに自乗和を比較した(sampleで死んだ)．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define EPS 1e-9
#define INF 1<<30

using namespace std;
typedef long long ll;

struct Point {
    double x, y;

    Point(double x=0, double y=0) : x(x), y(y) {}

    Point operator+(const Point &o) const { return Point(x+o.x, y+o.y); }

    Point operator-(const Point &o) const { return Point(x-o.x, y-o.y); }

    Point operator*(const double m) const { return Point(x*m, y*m); }

    Point operator/(const double d) const { return Point(x/d, y/d); }

    bool operator<(const Point &o) const { return x != o.x ? x < o.x : y < o.y; }

    bool operator==(const Point &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }

    double cross(const Point &o) const { return x * o.y - y * o.x; }

    double dot(const Point &o) const { return x * o.x + y * o.y; }

    double atan() const { return atan2(y, x); }

    double norm() const { return sqrt(dot(*this)); }

    double distance(const Point &o) const { return (o - (*this)).norm(); }

    double area(const Point &a,const Point &b) {
        Point p = a - (*this), p2 = b - (*this);
        return p.cross(p2);
    }

    double area_abs(const Point &a,const Point &b) const {
        Point p = a - (*this), p2 = b - (*this);
        return fabs(p.cross(p2)) / 2.0;
    }  

    // //線分abが自身に含まれているのかどうか判断する
    // int between(const Point &a,const Point &b) {
    //     if(area(a,b) != 0) return 0;
    //
    //     if(a.x != b.x)  return ((a.x <= x) && (x <= b.x) || (a.x >= x) && (x >= b.x));
    //     else return ((a.y <= y) && (y <= b.y) || (a.y >= y) && (y >= b.y));
    // }      

    double distance_seg(const Point& a,const Point& b) {
        if((b-a).dot(*this-a) < EPS) {
            return (*this-a).norm();
        }
        if((a-b).dot(*this-b) < EPS) {
            return (*this-b).norm();
        }
        return abs((b-a).cross(*this-a)) / (b-a).norm();
    }

    bool hitPolygon(const Point& a,const Point& b,const Point& c) {
        double t = (b-a).cross(*this-b);
        double t2 = (c-b).cross(*this-c);
        double t3 = (a-c).cross(*this-a);   

        if((t > 0 && t2 > 0 && t3 > 0) || ( t < 0 && t2 < 0 && t3 < 0)) {
            return true;
        }

        return false;
    }
};

class Flee {
  public:
  double maximalSafetyLevel(vector <int> x, vector <int> y) {
        int n = x.size();

        vector<Point> v;
        map<pair<int,int>,bool > m;
        rep(i,n) {
            pair<int,int> p = make_pair(x[i],y[i]);
            if(m[p]) continue;

            v.push_back(Point(x[i],y[i]));
            m[p] = true;
        }

        double ans = 0;

        if(v.size() == 1) {
            ans = v[0].norm();
        }
        else if(v.size() == 2) {
            ans = min(v[0].norm(),v[1].norm());
        }else {
            vector<int> d;
            int res = INF;
            rep(i,v.size()) {
                res = min(res,(int)(v[i]*2).dot(v[i]*2));
            }

            d.push_back(res);

            Point p(0,0);
            if(p.hitPolygon(v[0],v[1],v[2])) {
                rep(i,v.size()) {
                    rep(j,v.size()) {
                        if(i == j) continue;

                        Point p(v[i]-v[j]);
                        if(p.dot(p) < res) {
                            d.push_back(p.dot(p));
                        }
                    }
                }

                sort(d.begin(),d.end(),greater<double>());
                d.erase(unique(d.begin(),d.end()),d.end());

                rep(k,d.size()) {
                    int len = d[k];
                    bool flag = false;
                    Point p1(v[0].x-v[1].x, v[0].y-v[1].y);
                    Point p2(v[0].x-v[2].x, v[0].y-v[2].y);
                    Point p3(v[1].x-v[2].x, v[1].y-v[2].y);

                    int r = (int)p1.x*p1.x + p1.y*p1.y;
                    int r2 = (int)p2.x*p2.x + p2.y*p2.y;
                    int r3 = (int)p3.x*p3.x + p3.y*p3.y;

                    if(r >= len) {
                        flag = true;
                    }
                    if(r2 >= len) {
                        flag = true;
                    }
                    if(r3 >= len) {
                        flag = true;
                    }

                    if(flag) {
                        ans = sqrt(d[k])/2.0;
                        break;
                    }
                }
            }else {
                sort(d.begin(),d.end());
                ans = sqrt(d[0])/2.0;
            }
        }

        return ans;
  }
};

内包判定は外積を見れば良い．何かbetweenはコンパイル通らなくてコメントアウトが原因がよく分からない．とりあえずSystemTestは通ったけど，Pointを使わなくても，更に言えば場合分けをしなくても上手く書けそう．
今回は3点しかないが，これがn点になっても凸包を作って同じことをすれば良さそうに思える．

Jul 11th, 2015
srm, topcoder, 幾何

Codetest

競プロのtemplate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <queue>
#include <set>
#include <map>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30

using namespace std;
typedef long long ll;

int main() {
    return 0;
}
Jul 11th, 2015

Testpage

Octopressを用いた

  • テスト中
Jul 11th, 2015