SRM 611 div1 easy LCMSet
問題
集合$A,B(a,b≦10^9,|A|≦50)$が与えられる。それぞれの集合の部分集合のLCMで生み出される値は一致するか?
解説
いやこれ難しくないか..N時間かかった。
しばらく考えた
結局、LCMで生み出される値は集合の元(げん)が元(もと)になっている。
集合$A$を使って、集合$B$の要素を作成できないとすると、$B$には$A$に含まれない元が存在することになる。
あとは元の一致を確認をすれば良い。
これは、$b(i) = p1^{k1} * p2^{k2} * … * px^{kx}$となるような値を$A$の要素のLCMで作成可能か?という問いに答えればよく、
$A$のうち、$b(i)$の約数を持つ値のLCMを取っていけば良い。←ここに気づくのに時間がかかった…
これを$A$からみたときと$B$からみたときの両方を見ればよい。
計算量:$O(N^2)$
SRM 612 div1 easy EmoticonsDiv1
問題
文字列を今$smiles(≦1000)$個画面に表示したい。
今画面に1つだけ表示されているとして、行える動作を
- clipboardから貼り付ける
- 表示されている文字列を全部clipboardにコピーする
- 表示されている文字列を1つ消す とし、それぞれのコストを1とする。 $smiles$個表示するときの最小コストは?
解説
ダイクストラ法をしたい気持ちになる。
区別するのはclipboardの状態。
$dist(x,y):=$ 文字列が$x$個書かれており、いまclipboradに長さ$y$の文字列がかかれている際の行動の最小値
とすればよい。
計算量:$O(smiles^2log \ smiles^2)$
SRM 613 div1 easy TaroFriends
問題
$N(≦50)$匹の猫が位置$coordinates(i) (-10^9≦coordinates(i)≦10^9)$にいる。
今合図をすると、全員が独立して$±X$だけ移動する。
一番端の猫の距離差が最小となるときの距離は?
解説
ある軸を決めてあげて、そのときの移動をシミュレーションすれば良い。
軸を決めるとその左右は軸側に移動するのが良い。(そうで無いとすると距離を最小化できないので)
工夫すると$O(N)$でできそう。?
計算量:$O(N^2)$
SRM 614 div1 easy MinimumSquare
問題
二次元座標上に点が$N(≦100)$点ある。
境界より真に内側に$K(≦N)$点以上含まれるような長方形の選択のうち、最小の長方形面積は?
|座標|$≦10^9$
解説
幅を二分探索する。
幅$W$に対して適当な座標を決めた時の内側の点を数えればよく、これは$O(N^3)$でできる。
計算量:$O(N^3log \ Max)$
SRM 615 div1 easy AmebaDiv1
問題
任意整数のサイズのアメーバがいる。今$X(i)$のサイズのアメーバに順に出会う。
今のサイズと$X(i)$が等しければ、これと合体し2倍のサイズになる。
最終的なサイズに含まれない数は何個あるか?
$X(i)≦10^9,|X|≦200$
解説
まず、$X(i)$に含まれないサイズは最終的なサイズが同じままである。
$X(i)$から始めて、必ず1回は合体した最終的な値が$X$に含まれる数であれば、$X(i)$は最終的なサイズにならない。
したがって$X(i)$から始めて、そこからたどり着く数に含まれない数を見れば良い。
ちょっと英語に戸惑った。
計算量:$O(|X|^2)$