9/1 PKU

ひさしぶりのPKU。

1619 EKG Sequence

「最初の2項が1,2で、それ以降は前の要素と互いに素でなく、今までに現れたことのない最小の要素とする」という規則で作られるEKG Sequenceというものがある。
300,000以下のnが与えられるので、nがEKG Sequenceに現れる場所を求めよ、という問題。
ヒントとして、答えは1,000,000以下であること、解答に必要な範囲のEKG Sequenceに1,000,000を超える数は含まれないこと、が書かれている。

まず、1,000,000ぐらいまでの数について「ある数の最小の素因数」を並べた配列を作る。この処理は、エラトステネスの篩を行うときに同時に行うと、O(N log N)でできる。
EKG Sequenceを作るときには、各素因数について未登場の最小の数と、各数が何番目に現れたか（もしくは現れてないか）を記録した配列を持っておく。
あとは、各項について、前の項をみて各素因数について最も小さい候補を見て、候補たちの中で最小のものを採用する。素因数についての候補を探すときに、すでに使われていて候補を更新する必要があるかもしれないことに注意。
N項まで処理するとき、O(N log N)の計算時間でできる（はず）。
トータルの計算時間はO(N log N)で解ける。

1628 Deduction

「ABC => DE」のような式がたくさん与えられる。これは、もし左側に含まれる条件をすべて満たしているなら、右側の条件も成り立つ、ということを意味している。
初期条件が与えられるので、真とわかるすべての条件を求めよ、という問題。

条件は52種類。これはlong longに収まる。ある初期状態について解くときは、すべての条件式を見て、更新できるなら更新する、ということを繰り返す。更新できなくなったら終了する。これはO(52 * M)ぐらい。初期条件はN個あるので、O(52 * M * N)。