きままにものづくり

日々の気付いたことなんかを書いてます。

SRM645Div1Medium

問題

二次元平面上にN個の点が(x1,y1)と(x2,y2)が与えられる。平面上には3つの塔があり、ひとつの塔を指定し魔法を唱えると、その塔を中心に点対象に点を移動できる。(x1,y1)の点を(x2,y2)に移動できるかを判別せよ。

解法

kmjp.hatenablog.jp
上の記事の回答を使用した。
魔法をいくら使用しても点どうしの相対的な位置は変更することができないので、点集合のソートの差分は一意に決まる。その差分をdx,dyとする。
二つの塔を用いて魔法を唱えると、その塔同士の差分ベクトルの2倍分移動することができる。
塔は3つあるので移動できるパターンは以下になる。

  • ±2*(xt[2]-xt[0], yt[2]-yt[0])
  • ±2*(xt[2]-xt[1], yt[2]-yt[1])
  • ±2*(xt[1]-xt[0], yt[1]-yt[0])

3つのベクトルは線形従属の関係にあるので、2つのベクトルを用いることでもうひとつのベクトルを作成することができる。
塔2と塔0を使用した場合の移動をwx0,xy0とし、塔1と塔0を使用した場合の移動をwx1,wy2とする。
wx0 = xt[2]-xt[0], wy0 = yt[2]-yt[0]
wx1 = xt[1]-xt[0], wy1 = yt[1]-yt[0]
塔2と塔0を使用する移動の回数をp、塔1と塔0を使用する移動の回数をqとした時、以下の式が成り立つ。
\left( \begin{array}{cc} wx0 & wx1 \\ wy0 & wy1 \end{array} \right) \left( \begin{array}{c} p \\ q \end{array} \right) = \left( \begin{array}{c} dx \\ dy \end{array} \right)
この式の行列式が0でないならば、逆行列が存在する。p,qが整数解になるかを判別することで答えがもとまる。
行列式が0の場合は、p,qが存在しないか、無数に存在するかのどちらかになる。

計算量

O(N log N)

コード

SRM643Div1Medium

問題

2行N列の行列が与えられる。各要素はHかSである。以下の3つの操作を行い、すべての要素をHにするための最小の操作回数を求めよ。

  • どれか一つの要素を選びXとし、それと隣り合っている要素を一つ選びYとする。Xの要素をYの要素に書き換える。
  • 連続する列の要素を選び、隣合う列に書き換える。
  • 任意の行を選び、隣り合う片方の行に書き換える。

解法

列のパターンはHH、HS、SH、SSの4パターンとなる。HHしかない場合は0を、SSしかない場合は-1を返す。HHとSSしかない場合は、SSの数が答えとなる。
HSとSHが変化する回数を数える。SH、SHをHHに変えるためには、 \lceil \frac{c}{2} \rceil + 1回の操作が必要となる。SH、HSをすべてSHまたはHSに変えるために必要な操作回数が \lceil \frac{c}{2} \rceil となり、SHまたはHSをHHに変えるために1回の操作が必要になる。最後にSSの数を加えることで答えが求まる。

計算量

O(N)

コード

SRM642Div1Medium

問題

H個の木がある。各木のはじめの高さは h_iで与えられ、 add_iの高さだけ毎日成長する。木を切るためのデバイスがD個与えられる。これは、高さが D_j以上の木を高さ D_jに切ることができる。その日の最後にデバイスを使用することができる。各デバイスは1日に一度しか使えず、各木は1日に一度しか切れない。以上の操作を行ったときのT日目の木の高さの総和の最小値を求めよ。

解法

最小費用流を用いる。以下のようにエッジを張る。ノードには木、デバイス、日とsource、sink、noneがある。noneはデバイスを全く使用しないための頂点である。

  • sourceと各木を、容量1、コスト0で結ぶ
  • 各木とnoneを、容量1、コストh_i + add_i*Tで結ぶ。
  • noneとsinkを、容量H、コスト0で結ぶ。
  • 各木と各日を、容量1、コスト(T-k)で結ぶ。kはデバイスを使用する

日を示す。

  • 各日と各デバイスを、容量1、コストD_jで結ぶ。
  • 各デバイスとsinkを容量T、コスト0で結ぶ。

この処理では、木の高さが D_j以下でもデバイスを使用してしまっている。しかし、求めたいの木の総和の最小値であるため、この時が最小値となることはないため、正しく答えを計算できる。

計算量

O(H * (H + D + T) * min(HT, TD) ) = O(N^4)
N: max(H, D, T)
H: 木の数
D: デバイスの数
T: time

コード

SRM656Div1Easy

問題

サイズNの配列が与えられる。i番目の要素はパンケーキの美味しさを示し、サイズはi+1とする。
以下の操作を行ったあとの美味しさの総和の期待値を求めよ。

  • 選択されていないパンケーキを一様ランダムに選ぶ
  • 選んだパンケーキのサイズがスタックの上にあるパンケーキより大きい場合は、パンケーキをスタックに積まずに終了する
  • 選んだパンケーキをスタックに積み、処理を終了する

解法

dp[T][S]とし、動的計画法を用いる。Tはスタックに積むことができるパンケーキの数、Sはスタックのサイズを示す。
dp[T][S] = \displaystyle{ \frac{1}{N-S}\sum^{T}_{i=0}(d[i] + dp[i][s+1] ) }
という式が成り立つので計算をする。

計算量

O(N^3)

コード

SRM655Div1Easy

問題

サイズX、Yの二次元配列が与えられる。各要素はWかBである。同じサイズの全ての要素がWの二次元配列から以下の操作を行い、与えられた配列にすることができるかを判定せよ。
操作は二次元配列と共に与えられるkを用いて行う。サイズkの正方形を二次元配列内から選択し、すべての要素をWかBにとりかえる。

解法

サイズkのすべてが同じ要素である正方形を見つける。この要素はWでもBであっても最後にまとめて変更することができる要素である。この要素を?で置き換える。W,Bのどちらかと?を保持する正方形を探索し、?に置換する。この処理を更新がなくなるまで行う。すべての要素が?になっている場合は、与えられた配列にすることができる。

計算量

O((XYk)^2)

コード

SRM654Div1Easy

問題

サイズNの配列が与えられる。各要素は小文字のアルファベット(a-z)か?である。?は小文字のアルファベットに変更することができ、各アルファベットへの変換確率はpで与えられる。
全ての要素が同じ部分配列の数がその配列のスコアとする。与えられた配列のスコアの期待値を求めよ。

解法

?を含む部分配列を全列挙し、各部分配列のスコアを数え上げることで答えが求まる。毎回部分配列の分布を計算すると O(N^3 log N)になる。最初と最後の要素以外の変更はないので、使い回すことができる。このことを利用すれば O(N^2 log N)に削減できる。

計算量

O(N^2 log N)
log(N)は指数計算

コード

SRM653Div1Easy

問題

様々な国から来たN人が一列に並んでいる。その内の何人かにどこの国から来たのかを聞いた。同じ国から来た人は隣合っている。
現状の調査結果を表す配列Aが与えられる。この結果から、全ての解答を一意に予測できるか求めよ。

解法

Coding is fun: SRM 653 DIV1 Easy - CountryGroupHard
ここの解答を使用した。

i番目の要素に注目し、それより前の要素jを使用して[j,i]の部分配列を考える。この配列の中の0以外の要素の全てが len = (j - i + 1)に等しい場合、その部分配列は一意に決まる。その結果をdp[i]に保存する。複数のjで条件を満たす場合、dp[i]の値は1より大きくなり、[0,i]での予測できる解答は複数あることを示す。問題は[0,N]で、解答が一意に定まるかどうかを問いているので、dp[N]が1かどうかを調べれば良い。

計算量

O(N^2)

コード