http://codeforces.com/contest/792
問題
A. New Bus Route
N点の座標が与えられる。
任意の2つの座標の最短距離とその最短距離となる2つの座標のペアの組合せを求めよ。
B. Counting-out Rhyme
N人が円状に昇順で並んでいる。最初リーダーを1さんとし、以下の操作をK回行う。
1. 現在のリーダーの次のK番目の人を削除する
2. 削除した次の人をリーダーにする
i回目に削除した人をすべて答えよ。
C. Divide by Three
ある数Nが与えられる。
その数の任意の位を削除することでリーディング0でない3の倍数を作る。
削除すべき位を最小化したときの答えは？
3の倍数にできないならば-1
D. Paths in a Complete Binary Tree
N頂点の完全二分木がある。
この木は「左のノードが全てラベル付けされたら自分をラベル付けして右のノードをラベル付けする」
というルールで頂点が割り当てられている。
これに対し、Q個の以下のクエリを答えよ
- 初期頂点uがある
- 操作Sがあり、'U'は親ノードへの移動、'L'は左側の子ノードへの移動、'R'は右側の子ノードへの移動を指す
- 移動後の頂点を答えよ
E. Colored Balls
N種類の色の箱がある。
各箱には同色のボールがA[i]個入っている。
以下の条件をみたすようにボールをグループ分けするときのグループ数の最小値は？
1. 1つのグループには1色のボールしか入らない
2. 任意の2つのグループのサイズの差は1以下である
以下、解説
解説
A. New Bus Route
http://codeforces.com/contest/792/submission/25842825
任意の2点を考えなくても隣接する2点の距離のいずれかが最短距離となるため、
Aを昇順ソートしておき、隣り合う2点の距離と現在までの最短距離を見ながら、
最短距離と組合せを更新していく。
B. Counting-out Rhyme
http://codeforces.com/contest/792/submission/25842471
愚直にシミュレートすればよいのだが、削除という操作が面倒である。
なのでリーダーを指すledは「まだ残っている人の中でled番目がリーダー」と定義しておく。
それに加えて、あと残っている人の合計をnとしておくと、削除する対象は(led + A[i]) % n番目の人と完結に計算できる。
あとは、forで先頭から残っている人の(led + A[i]) % n番目を消して出力すれば良い。
C. Divide by Three
http://codeforces.com/contest/792/submission/25845615
削除すべき位を最小化したいということは最大桁数の数を作りたいということである。
よって、
dp[i][m] = i桁目まで見て、ここまでの選択して作った数のmod3がmのときの桁数最大
を考えればよい。
よいのだが、今回は削除した後の結果を出力する必要があるため、以下のようにdpを少し変える。
dp[i][m] = i桁目まで見て、ここまでの選択して作った数のmod3がmのときの{桁数最大値, {その時の前状態のi, その時の前状態のm}}
これでdpをして、後はdpの結果と前状態への遷移を使って、答えを復元していく。
D. Paths in a Complete Binary Tree
http://codeforces.com/contest/792/submission/25847118
完全二分木の特徴は、
深さd,その深さで左からi番目の頂点の...
- 親頂点は「深さd-1, 左からi/2番目」
- 左の子頂点は「深さd+1, 左からi*2番目」
- 右の子頂点は「深さd+1, 左からi*2+1番目」
である。なので、クエリに対して「uが深さy、左からx番目である」のy,xを求め、上の方式にしたがって、(x,y)を計算していき、結果の(x',y')から「ansが深さy'、左からx'番目である」ことを利用してansを作る。
事前に与えられた完全二分木の深さを計算しておく(pre関数)。
そして深さy, 左からx番目の数は2^y + x * 2^(y+1)であるため、深さで全探索して、どの深さ、左から何番目かを計算していく。
あとは、動かして、「深さy, 左からx番目の数は2^y + x * 2^(y+1)」で戻すと答え。
E. Colored Balls
http://codeforces.com/contest/792/submission/25863307
ほぼLHiCさんの解法。
まず2つの関数を用意しておく。
chk(int x) := 要素数がxかx+1のグループの作れるか
sol(int x) := 要素数がxかx+1のグループを作る時のグループ数
やってる中身はそれほど難しくない。
Naive
全ての要素数についてチェックして最小のものを答える。
まあ、思いつく。O(10^9)なので当然ダメ
Optimized
これをどのように改善するかというと、2つの事実を利用する
- 「候補となる要素数は最も小さいAの要素でその要素数のグループが作れるかを考えれば良い」全てのAについてその要素数で作れないといけないということは、その候補はあるAの要素で作れる要素数となる。どのAの要素でもいいが、最も小さいほうが良いような感じはある。（次の事実を見ると、最も小さくなくてもいいかも）
- 「あるAの要素でグループ化できる要素数の候補数はそんなに多くない」これは予測であるが、以下で述べる候補の候補を考えると多くはなさそう。
つまりは「最小のA[0]についてグループ化できる候補を作って、その候補を全て試す」ことでACする。
候補の作り方であるが、これは実験により規則性を見つけてくるしかない。
makeCandidates関数で候補を作っている。
作り方としては、候補の候補を全探索して、本当の候補を探す感じ。
候補の候補は
- i^2<=A[0]であるi
- A[0]/iとA[0]/i-1(i=1,2,...,sqrt(A[0]))
である。これに対し、A[0]で本当にグループを作れるか判定し作れれば候補とする。
プログラム内では40000としているが、これはsqrt(10^9)を想定している。
意味合いとしては、sqrt(A[0])とした方が正しい。
