yukicoder171 スワップ文字列(Med)
重複するものを並べる順列は、$\displaystyle \frac{sum!}{a!b!c!}$とすれば表現できる。
一方で$sum!$は計算してもc++ではオーバーフローしてしまう。これは式変形をして、combinationで書き直せば良い。
combinationは任意のmodでも計算できるので、問題ない。
計算量:$O(|S|^2)$
Submission
yukicoder172 UFOを捕まえろ
マンハッタン距離が$K$の時、つまり$|x|+|y|=K$である部分を考える。これは正方形を45°回転させた形をしている。
UFOのいる点の円から接する点は、$\displaystyle (x+rcos(\frac{π}{4}),y+rsin(\frac{π}{4}))$と表すことができる。
これの繰り上げを得れば良い。
計算量:$O(1)$
Submission
yukicoder173 カードゲーム(Medium)
要求誤差が精密でないので、シュミレーションをする。
使用したカードはbitで管理すると簡単にかけた気がする。
また、乱数にmt19937を使ったが、これをforループ内に書いたらTLEした。生成に時間がかかるらしい。
計算量:$O(TRY*N^2)$
Submission
yukicoder174 カードゲーム(Hard)
bitdpはできそう。それにしては解いた人数が少なかったので提出一覧だけ除いたら、それより明らかにオーダーが良いものを提出している人がいたので考えた。
最終的に、$t$ターン目に$i$番目のカードを出すという確率がわかれば良い。
この確率は$PA$のみに依存し、数列${A_n}$には依存しないので多項式時間で求められそう。が、$dp(t,i)$のようなものは重複しうるので簡単には求められなさそう。
$P(t,i)$を、ある$k$番目のカードについて求める。
$dp(x):=i$以下に更に小さいカードが$x$枚あるという確率をもとにして、$i$についてのdpを更新していく。
各$i$について$O(N^2)$で計算できるので、確率を求める部分で$O(N^3)$で計算できる。
こういうのをよく求めたいことがあるので、良い経験だった。
計算量:$O(N^3)$
Submission
yukicoder175 simpleDNA
末尾の長さは一緒なので何も考えずに、それより前の文字を$2^N$だけ取れると思えば良い。
計算量:$O(1)$
Submission
yukicoder176 2種類の切手
$Ax+By≧T$を満たすような非負整数$x,y$で、$Ax+By$を最小化したい。
片方の変数$y$を全部調べたいが、間に合わない。
そこで、$y=‘y+A$であった時を考えると、$Ax+By=A(x+B)+B{‘y}$となるので一定の$y$以上は繰り返して同じ結果を得ることになる。
よって$\sqrt T$ぐらいの計算でよくなる。
計算量:$O(\sqrt T)$
Submission
yukicoder177 制作進行の宮森あおいです！
最大流問題でしかない。$S→$原画マン$→$作画監督$→T$へそれぞれ$J(i),INF,C(j)$の辺をはれば良い。
計算量:$O(|最大流|)$
Submission
yukicoder178 美しいWhitespace (1)
偶奇の判定と最大の値を保持する。
計算量:$O(N)$
Submission
yukicoder179 塗り分け
2つの図形の角を決定するのに$O(HW)$だけかかる。正しい一致を見るだけでよい。
結構WAを出した。
計算量:$O(H^2W^2)$
Submission
yukicoder180 美しいWhitespace (2)
$f(x)$は、下に$凸$-上に$凸$なので全体で下に$凸$な関数になっている。
これがわかればあとは三分探索をするだけ。
三分探索の境界でミスらない方法を知らないときは、収束後は近傍を調べると安全。(ずるい)
計算量:$O(NlogN)$
Submission