読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces #399 ABCDE

A. Oath of the Night's Watch

数列aiが与えられる。aiより真に小さい要素が存在し、かつaiより真に大きい要素が存在するような i はいくつあるかという問題。

ai が最小値でも最大値でもないようなものを数えればそれが答えである。


B. Code For 1

たとえば 10 の変形過程は以下のような木になる。

f:id:pekempey:20170221071658p:plain

[l,r]に含まれる 1 の個数を数えるかわりに[1,k]に含まれる 1 の個数を数えることにしよう。[l,r]の答えが欲しいなら [1,r]-[1,l-1] で計算できる。二分探索木に慣れている人ならすぐに分かると思うが、灰色で塗った頂点より下に 1 が何個あるかを数えればいい。

count(x,k) を x を変形して作られる配列の先頭 k 個に含まれる 1 の個数と定義する。f(x) を x を変形して作った配列のサイズとする。

f(x/2)≦kのとき、真ん中と右側の部分木は無視できるので count(x,k)=count(x/2,k) である。

f(x/2)>k のとき、左部分木はすべて取れるので count(x,k)=count(x/2)+(x%2)+count(x/2,k-f(x/2)-1) である。ここで count(x) は x によって作られる配列にいくつ 1 があるかを意味する。

count の再帰の深さは log x にしかならなくて、f も log x 回の再帰で計算できるため、O(log^2 x) で計算できる。


C. Jon Snow and his Favrourite Number

数列 ai が与えられる。数列をソートし 0-indexed で偶数番目の要素全てに x を xor するという操作を K 回行う。最終的な数列の最大値と最小値を求める問題。

ai<1024 なので 1024×100000 回程度のループでシミュレーション可能である。余計なことをするとプロの餌食になる。


D. Jon and Orbs

N種類のガチャがある。どの種類も等確率で引ける。全種類揃う確率が (p-ε)/2000 をはじめて超えるのは何回引いたときかを求める問題。

N種類のガチャを全種類揃えるのに必要な回数の期待値が NlogN 程度になるのは有名だろう。10000 回引けば当たる確率はかなり高そうである。

i 回引いたときに j 種類揃う確率を DP で求めよう。10000 回くらいなら普通に計算できる。本番では誤差を気にしすぎて手が止まっていたが、そんなに際どいケースはないらしい。


E. Game of Stones

石の個数とすでに使った数のビットマスクを状態として grundy 数を計算する。自明な解析をすると状態数が 60×260 程度になるのだが、実際にはそんなに多くはならない。

念のために計算結果を埋め込んだが、普通に計算しても 3sec には収まるだろう。