今日のPKU

1. PKU 3070 Fibonacci
2. PKU 3660 Cow Contest

PKU 3070 Fibonacci

累乗の高速化(x^yでyが偶数のとき、整数kについて y = 2k とおくと x^y = (x²)^k)を実装する。O(log n)。

PKU 3660 Cow Contest

基本方針としては、ある子が誰に負けて誰に勝つかという情報をsetで持っておいて、最終的に負けることが確定している人数 + 勝つことが確定している人数 = N-1 ならば順位が決定できる、ということを利用する。例えば10人の中で3人に勝って6人に負けることが分かっていればその子は4位だと決定できる。3人に勝つことが分かっていても5人に負けることしか分かっていない場合は4位なのか5位なのか決定できない。

そこでまず、入力される情報だけをsetに入れて行く。入力される情報から他の情報を類推することもできるが、それは一旦後回しにして、とりあえず入力の情報のみ読んでおく。

それが終わったら今度は類推に入る。i番目の子がj番目の子に勝つならば、j番目の子が勝つことの出来るすべての子にi番目の子も勝つことができる。つまり、3が4より強くて、2が3より強いなら、2は4より強いということがわかる。同じように、i番目の子がj番目の子に負けるならば、j番目の子が勝つことの出来ないすべての子にi番目の子も勝つことができない。つまり、3が4より弱くて、2が3より弱いなら、2は4より弱いということがわかる。

この類推を1からNまでの全ての子について行う。これだけだと、1番目の子の類推を行っている際に2〜N番目の子の情報は不確定なので、できる類推が行えない。よって2回、1からNまでの全ての子についてこの類推を行うことによって出来るところまでの類推は全て行える。

これで多分 O(N³logN) ぐらいかな？実際はもっと少ないとは思う。