コンテストへのリンク
A. Add Odd or Subtract Even
x,yの大小や、差の偶奇で場合分けする。
B. WeirdSort
A[i]>A[j](i<j)となっている箇所があれば、i～jは全てスワップ可能でなくてはダメ。
C. Perform the Combo
i番目でミスしたとき、各文字を何回ずつ使っているか？ を累積和を使って前計算。
D. Three Integers
1～$10^5$（もっと小さくても良いと思うが、一応）の範囲で、約数のリストを作っておく。（約数の個数はN=$10^5$として、Nlog(N)程度）
その上で、bの値を1～$10^5$の範囲で全探索。aは、bの約数のうちでaに一番近いものを、cはｂの倍数に一番近いものを取る。
Hackされたのは、bを、cの最大値程度までしか変更しなくて良いと思い、1～$10^4$で全探索したためでした。
E. Construct the Binary Tree
（自分が出ていた頃の）LeetCodeっぽい問題。なんかこういう二分探索木系の問題たくさん出ていたよね……。今も出ているんだろうか。
まず、木の深さの合計が最小になるのは、完全二分木（子ノードが常に二つ）に近いとき。それを基準にして、深さの和が求められたものになるように構築していく。
完全二分木にBFS順にノード番号を振ったようなものを考えると、左端のノードは、1,2,4,8,...と2ベキになっている。これを幹にする。
ノード番号が大きい、葉に近いノードを考えると、その親を入れ替えることにより深さの合計を増やすためには、幹を伸ばすしかない。
そうやって、幹をどんどん伸ばしていき、最後の一個、幹を伸ばすのでは深さの合計が大きくなりすぎてしまうとき、どの幹のノードにくっつければ良いかを調べて調整する。
F. Moving Points
近づいていくなら距離は0になる。離れていくなら、互いの距離が最小になるのは初期値のとき。
左にある点から見ていくとする。
そのとき、今見ている点Aが、Aより左にある（x座標が小さい点）点Bとぶつからないのは、その点よりBの速さよりAの速さが大きいとき。
あとは実装問題。BITで管理して解くことができる。(x, v)の図（グラフ）を描いて考えれば分かると思う。
0 件のコメント:
コメントを投稿