yukicoder191 供託金
$\displaystyle \frac{sum}{10}≧a[i]$の数をカウントする。こういう判定は積の形に治すのが良い。
計算量:$O(N)$
Submission
yukicoder192 合成数
素因数分解をする。
計算量:$O(logN)$
Submission
yukicoder193 筒の数式
$S+S$の文字列から、$|S|$だけの式を評価すれば良い。
計算量:$O(|S|^2)$
Submission
yukicoder194 フィボナッチ数列の理解(1)
testcase01-10は、実際にスーパーフィボナッチ数を作れる。愚直に作るのはダメなので、総和に追加する部分と削除する部分だけ見ればよい。
testcase11-20は、$N$が小さいので、行列累乗で$K$番目のスーパーフィボナッチ数を求める。総和も以下のようにして求められる。
$$
\begin{eqnarray}
\left(
\begin{array}{c}
S(n+1) \\
Fib(n+1) \\
Fib(n) \\
Fib(n-1) \\
\vdots \\
Fib(2) \\
\end{array}
\right) =
\left(
\begin{array}{cccccccc}
1 & 1 & 0 & 0 & 0 & \ldots & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & \ldots & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & \ldots & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & \ldots & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & \ldots & 0 & 0 \\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & 0 & 0 & \ldots & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & \ldots & 0 & 0 \\
\end{array}
\right)
\left(
\begin{array}{c}
S(n) \\
Fib(n) \\
Fib(n-1) \\
Fib(n-2) \\
\vdots \\
Fib(1) \\
\end{array}
\right)
\end{eqnarray}
$$
計算量:$O(K),O(N^3logK)$
Submission
yukicoder195 フィボナッチ数列の理解(2)
$F_{A,B}(k)=Afib(k)+Bfib(k+1)$のような形になっている。
$$Afib(i)+Bfib(i+1) = X$$
$$Afib(j)+Bfib(j+1) = Y$$
$$Afib(k)+Bfib(k+1) = Z$$
のような方程式を解けば良い。ただし$X,Y,Z$が全部一致するときは別で考える。
最小の正整数$A$について、$A=1$のとき、$fib(1)=1,fib(2)=1$であるから適当な$B$を取れば良いことになる。
$A=1$は確定したので、$fib(i)$から$B$の値を見つければ良い。
計算量:$O(sz^3)$ ($sz:=50$)
Submission
yukicoder196 典型DP (1)
iwiwiさんの2乗の木DPを見たことがあるので解けた。
$dp(i,k):=$頂点$i$以下の部分木について、$k$個色を塗る塗り方の総数 としてdpする。
積の和のdpだけど、部分機についての$K^2$のループで値が重複するので一時変数に退避させた。
計算量解析よく分からない。$O(NK^2)$っぽいけど$O(NK)$らしい。
計算量:$O(NK)$
Submission
yukicoder197 手品
文字列を一致させられるとして、$N≧2$のときは一致しうる。
$N=0$のときは同じかどうか、$N=1$のときはシュミレーションをすればよい。
計算量:$O(|s|)$
Submission
yukicoder198 キャンディー・ボックス2
三分探索でも解けそう。が、マンハッタン距離の最小化に式が似ているのでこれをやってよい。
計算量:$O(N)$
Submission
yukicoder199 星を描こう
どの3点を選んでも一直線上にない適当な4点を選んで、その中にもう1点があったときは☆をつくることができない。
が、凸包で実現できる。凸多角形が5点の図形だったらOK。
計算量:$O(N)$
Submission
yukicoder200 カードファイト!
0/1の最小費用流はいらない。貪欲で解ける。
Aが何かしらの手段で勝ちうるなら、最小のBに対して、それより大きいAのカードを持ってくる。
Aがどうしても負けるときは、Bの最大手を出してAの最小手を出せば良い。
先にmultisetを作ってやったら速そうと思った。
計算量:$O(NlogN)$
Submission
やっと200まで解けた。たまには解けなかったものをもう一回解く時があっても良さそう。