今回から参加したコンテストの記録を残して行くことにします。ほぼ自分用メモ。
公式の解説を見る前に記述しています。

AtCoder Beginner Contest 142

A - Odds of Oddness

OddsofOddness.cpp

int main(void) {

    int N;

    cin >> N;

    cout << ((N + 1) / 2) / (double)N << endl;

    return 0;
}

奇数はN/2個あるのでそれを全体の個数Nで割ってやればよいのだが、Nが奇数のときは2で割るとC++では切り捨てされてしまうため、
(N+1)/2にすることで切り上げを実装。Nが偶数のときは切り捨てられるので問題なし。

B - Roller Coaster

RollerCoaster.cpp

int main(void) {

    int N, K;

    cin >> N >> K;

    int height, count = 0;

    REP(i, N) {
        cin >> height;
        if (height >= K) count++;
    }

    cout << count << endl;

    return 0;
}

与えられた身長を線形に探索しK以上の値を数えるだけ。
問題文の形式を見るとcinで受け取るときに一旦配列に格納したくなったのだが、保持する必要がないので思いとどまる。

C - Go to School

GotoSchool.cpp

int main(void) {

    int N;

    cin >> N;

    vector<pair<int, int>> A(N);
    int num;

    REP(i, N) {
        cin >> num;
        A[i] = make_pair(num, i + 1);
    }

    sort(A.begin(), A.end());

    REP(i, N - 1) cout << A[i].second << ' ';
    cout << A.back().second << endl;

    return 0;
}

登校したときにいた教室の人数=登校した順番なので与えられた配列を昇順に並び替えればOK。
受け取った配列の添字=出席番号なので、配列をそのまま並び替えると出席番号の情報が失われてしまうため、pairで出席番号を保持したまま並び替える。std::sortはO（NlogN)らしいので十分に間に合う。

D - Disjoint Set of Common Divisors

ACできるコードがかけなかったのでコードは省略。

実装した内容

実際に扱う値はAとBの公約数で、公約数の数は素因数の数に依存しているが、素因数の個数の上限を調べようとしてWikipediaを調べたがn=10^12を計算する気にはなれなかった。このときはとりあえずなんとなく10^6個よりは少ないとして考えることに。

AとBの値が何であれ、求まった数がAとBの公約数であることは考えずに、与えられた自然数の集合のから全ての数同士が互いに素な組み合わせを作ることを考える。

組み合わせを作るにあたって一番簡単なのは、
全通りの組み合わせを作って、それぞれの組み合わせで全ての値が素かどうかを調べる。互いに素だった組み合わせのうち個数が最も多かったものを出力。

となるが、公約数の数をMとすると全組み合わせの数が2^M個あり、各組み合わせの各数が互いに素かを調べるのに計算上O(M^2)かかってしまい現実的な時間で終わらない。
そこで思いついた工夫は、個数の少ない組合せから作り、素でないと判断された時点で残りの公約数を追加することをやめ、計算の候補から外すことで作る組み合わせを減らすというもの。
例えばA=12, B=18のときに公約数1,2,3,6から{1}, {1,2}, {1,2,3}, {2,3}, {3}...を作り、{1,2}を作ったあともし次の3を追加して条件を満たさなくなるのであれば、6の入った{1,2,3,6}の判定は行わないということ。
さらにxとyが素であるかどうかを計算しておいたmemo[x][y]を用意しておいて素であるかの判定を省略できるようにする。

しかし、(今考えれば当たり前だが)これでも計算時間が大きすぎたのでTLEで間に合わず。

ACできなかったので考え直した結果

前述した方法は、そもそも素であるものすべてを含んでいない組み合わせ({1,2}や{2,3})は作る必要がないので、
ある公約数xを基準にしてその値と素である公約数y1, y2, y3...自体を組み合わせにして問題なかった。(xが1なら{1,2,3}だけでよい)

AとBの公約数を求めるのに、√nまでの数で割りAB両方割り切れる数を列挙する→ O(√min(A,B)) (最悪でO(√(N)))
公約数同士を素か比較する回数は、xとyのペアを作る回数→ O(M(M+1)/2) ≒ O(M^2)
xがyと素であるかは、xの約数を求めyが含まれているかを計算する→ O(√max(x, y)) (最悪でO(√(N/2)))

まとめると最悪の場合でも O(√(N)) + ( O((M^2)*√(N/2)) )
公約数の個数Mが10^3個程度なら間に合いそうな計算時間である。

~~10^12までの値の素因数の個数の上限をさきほどのWikipedia通りに計算したところ12.86636と出てきたが本当にこんなに少ないのだろうか。~~
19/10/02(追記)
公約数は素因数の組み合わせからも求められるが、約数の個数でいいので最大で√N個以下ということでよかった

ABC142 参加記録