arrows blog

解いた問題などを適当に書いていきます。

AOJ 0018 Sorting Five Numbers

AOJ ソート

問題概要

5つの整数a, b, c, d, eが与えられるので、これらを降順に並び替えよ。

制約

  • -105 ≤ a, b, c, d, e ≤ 105

解法

基本的な考え方は、これと同じ。
上記のリンク先の別解でやればOK。

別解以外の方法では、ソートアルゴリズムを自分で実装する方法がある。
ソートアルゴリズムは、簡単なものだと、バブルソートや
選択ソートがある。

安定性(ここでは説明は省略)を考慮すると、バブルソートの方がおすすめである。
ただし、どちらのソートアルゴリズムもデータ数が1000位までは高速だが、それを超えてくると他の方法を用いた方が良い。


また、注意点として、AOJでは、空白区切りで1行に出力する際には、
各データ(ここでは整数)の間にのみ空白を入れ、最後のデータの後には空白を入れないことがある。

コード

#include <iostream>

using namespace std;

int main()
{
    int a[5];
    for (int i = 0; i < 5; i++) {
        cin >> a[i];
    }
    for (int i = 4; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[j+1]) {
                swap(a[j], a[j+1]);
            }
        }
    }
    
    for (int i = 0; i < 5; i++) {
        if (i > 0) cout << " ";
        cout << a[i];
    }
    cout << endl;
    return 0;
}

AOJ 0019 Factorial

AOJ 数学

問題概要

n!を求めよ。

制約

  • 1 ≤ n ≤ 20

解法

n! = n × n-1 × ... × 2 × 1
であるので、それを計算すれば良い。

計算方法には、ループで書く方法と再帰関数で書く方法がある。

  • ループ
fact = 1;
for (int i = 1; i <= n; i++) {
    fact *= i;  // fact = fact * i; と同じ
}

fact(i)をiの階乗と定義すると以下のような漸化式が導ける。

  1. fact(i) = 1 (i ≤ 1)
  2. fact(i) = i × fact(i-1) (i > 1)

よって、以下のように再帰関数を書くことができる。

int fact(x)
{
    if (x <= 1) return x;
    return x * fact(x - 1);
}


注意点として、この問題では、最大n = 20であり、20!はint型の範囲を超えてしまうので、long long型などを使用する必要がある。

コード

#include <iostream>

using namespace std;

int main()
{
    int n;
    long long result = 1;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

using namespace std;

long long fact(long long n)
{
    if (n <= 1) return 1;
    return fact(n - 1) * n;
}

int main()
{
    int n;
    cin >> n;
    cout << fact(n) << endl;
    return 0;
}

AOJ 0011 Drawing Lots

AOJ やるだけ

問題概要

w個の縦棒、n個の横棒で構成されるあみだくじがある。
横棒iは、aiとbiをつなぐ。
横棒は、上に存在するものから与えられる。

制約

  • w ≤ 30
  • n ≤ 30

解法

まず、始めに横棒が1本もない場合を考える。
その場合、i番目の縦棒から始めるとi番目の縦棒へと行き着くことは明らかである。

次に、1つの横棒があり、縦棒1と縦棒2をつなぐとすると、縦棒1から始めると縦棒2へと行き着き、縦棒2から始めると縦棒1へと行き着く。
つまり、2つの縦棒の結果を交換することになる。

複数の横棒がある場合でも、これが成り立つので、n個の横棒について、iが小さい順に交換を行うことで最終的な結果が得られる。

コード

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int w, n, a, b;
    char c;
    cin >> w >> n;
    vector<int> v(w);
    for (int i = 0; i < w; i++) {
        v[i] = i+1;
    }
    for (int i = 0; i < n; i++) {
        cin >> a >> c >> b;
        a--; b--;
        swap(v[a], v[b]);
    }
    for (int &x: v) {
        cout << x << endl;
    }
    return 0;
}

AOJ 0010 Circumscribed Circle of a Triangle

AOJ 幾何

問題概要

平面上の3点(x1, y1), (x2, y2), (x3, y3)が与えられたとき、それらを頂点とした三角形の外接円の中心座標と半径を求めよ。

制約

  • -100 ≤ x1, y1, x2, y2, x3, y3 ≤ 100
  • データセットの数 ≤ 20

解法

点1と点2の垂直二等分線、点2と点3の垂直二等分線を求め、それぞれl1, l2とする。
l1とl2の交点が外接円の中心座標となる。

また、半径は、中心座標からいずれかの点への距離である。

コード

#include <iostream>
#include <cmath>
 
using namespace std;
 
#define EPS (1e-5)
#define equals(a, b) (fabs(a - b) < EPS)
 
struct Point {
    double x, y;
 
    Point(){}
    Point(double x, double y) : x(x), y(y) {}
 
    Point operator + (const Point &p) const {
        return Point(x + p.x, y + p.y);
    }
 
    Point operator - (const Point &p) const {
        return Point(x - p.x, y - p.y);
    }
     
    Point operator * (const double &k) const {
        return Point(x * k, y * k);
    }
};
 
typedef Point Vector;
 
double dot(const Point &a, const Point &b)
{
    return a.x * b.x + a.y * b.y;
}
 
double cross(const Point &a, const Point &b)
{
    return a.x * b.y - b.x * a.y;
}
 
double norm(const Point &p)
{
    return dot(p, p);
} 
 
double abs(const Point &p)
{
    return sqrt(norm(p));
}
 
struct Line {
    Point s, t;
    Line(){}
    Line(Point s, Point t) : s(s), t(t) {}
};
 
Line getPerpendicularBisector(const Point &a, const Point &b)
{
    double cx = (a.x + b.x) / 2.0;
    double cy = (a.y + b.y) / 2.0;
    Point p = Point(cx + (a.y - b.y), cy + (b.x - a.x));
    return Line(Point(cx, cy),p);
}
 
Point crosspointLL(const Line &a, const Line &b)
{
    Vector va = a.t - a.s, vb = b.t - b.s;
    double d = cross(vb, va);
    if (abs(d) < EPS) return b.s;
    return a.s+va*cross(vb, b.t - a.s) * (1.0 / d);
}
 
int main()
{
    Point p[3];
    int N;
    cin >> N;
    while (N--) {
        for (int i = 0; i < 3; i++) {
            cin >> p[i].x >> p[i].y;
        }
        Line l[2];
        for (int i = 0; i < 2; i++) {
            l[i] = getPerpendicularBisector(p[i], p[i+1]);
        }
        Point c = crosspointLL(l[0], l[1]);
        double r = abs(c - p[0]);
        printf("%.3f %.3f %.3f\n", c.x, c.y, r);
    }
    return 0;
}

AOJ 0009 Prime Number

AOJ 数学 累積和

問題概要

整数nが与えられるので、n以下の素数の数を出力せよ。
なお、素数とは、「1と自分自身でしか割り切れない正の整数のうち1を除いたもの」である。

制約

  • 1 ≤ n ≤ 999999

解法

エラトステネスの篩 + 累積和


エラトステネスの篩については、wikipedia(エラトステネスの篩 - Wikipedia)などを参考。
実装は、以下のようになる。 O(n log log n) である。

#define MAX 1000000

int prime[MAX]; // 全て1で初期化する。
prime[0] = prime[1] = 0;
for (int i = 2; i < MAX; i++) {
    if (prime[i]) {
        for (int j = 2*i; j < MAX; j += i) {
            prime[j] = 0;
        }
    }
}


エラトステネスの篩で埋めた、素数かどうかを判定する配列を用いて累積和を求める。
累積和とは、
0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 .... を
0 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 .... とするイメージ。

prime[i] = prime[i] + prime[i-1] (i > 0)
のようにすると累積和を求めることができる。

後は、与えられたnに対して、prime[n]を出力すれば良いことになる。

コード

#include <iostream>

using namespace std;
 
#define MAX 1000000
 
int main()
{
    int prime[MAX];
    fill(prime, prime + MAX, 1);
    prime[0] = prime[1] = 0;
    for (int i = 2; i < MAX; i++) {
        if (prime[i]) {
            for (int j = 2*i; j < MAX; j += i) {
                prime[j] = 0;
            }
        }
    }
    
    for (int i = 1; i < MAX; i++) {
	prime[i] = prime[i] + prime[i-1];
    }
    
    int N;
    while (cin >> N) {
	cout << prime[N] << endl;
    }
    return 0;
}