Yukicoder201-210

yukicoder201 yukicoderじゃんけん

rateが非常に大きいので整数の比較はできない。桁の大きさが異なるときはそのまま判定できて、同じ時は一番大きい数字の桁からみていけばよい。
計算量:$O(|S|)$
Submission

yukicoder202 1円玉投げ

愚直だと$O(N^2)$になってしまう。座標の制限から、適当にグリッドを分割してそこに点を配置して愚直に近傍の円に引っかるかを調べれば良い。
分割サイズは適当に50ぐらいで十分な気がする。
計算量:$O(Nk)$ $k$:分割サイズ
Submission

yukicoder203 ゴールデン・ウィーク(1)

実際に調べれば良い。
計算量:$O(|S|)$
Submission

yukicoder204 ゴールデン・ウィーク(2)

問題文をしっかり読めば簡単。与えられた表以外にも平日は存在するので、休日の開始箇所を16箇所決めてその中の最大値を出力すれば良い。
計算量:$O(|S|^2)$
Submission

yukicoder205 マージして辞書順最小

現在選択できるものについて最大の文字列を選択することになる。$N$個の中から最大のものを選択するだけでこれは実現できる。
priority_queueだと実装がかなり楽。
計算量:$O(\sum |s_i| log \sum s_i)$
Submission

yukicoder206 数の積集合を求めるクエリ

Aの列とBの列を準備し、Bの列をシフトさせていく。このときの一致数が各クエリの答えになる。
列の長さは$N$以下であることと、AとBの列をシフトさせていくときの操作はFFTらしさを感じるのでこれを考えてみる。
FFTでは$c[k] = \sum a[i]*b[k-i] $の計算を高速にできたので、今回はa[i+q] = b[i]をこの式に適用できればいいことになる。
これはBの列を反転すれば実現できたことになるので、FFTを終えたら答えはc[N+q]を見て行けば良い。
いいFFTの問題そう。
計算量:$O(NlogN+Q)$
Submission

yukicoder207 世界のなんとか

愚直に見ればよい。
計算量:$O(B-A)$
Submission

yukicoder208 王将

斜めに移動できるので、だいたい$max(X,Y)$で移動できる。
ただし、$y=|x|$上に邪魔な点と目標のマスへ行くときはダメなので$+1$回必要。
計算量:$O(1)$
Submission

yukicoder209 Longest Mountain Subsequence

一番大きい値の左右から愚直に見ていくことを考える。その過程で何度も同じ比較を行うことになる。ここはメモ化できそうなので、前2個の選択を保存した配列を準備して、メモ化再帰を繰り返せば良い。
計算量:$O(N^3)$
Submission

yukicoder210 探し物はどこですか?

回数の期待値を最小化するにあたって、見つけられる確率が高い部屋からみればよい。
最大のものを見つける操作をこうそくにできればよいので、priority_queueで最大確率を持ってこれば良い。
試行回数は$10^6$ぐらいで良いらしい。よくわからない。
計算量:$O(TRYlogN)$ (TRY:試行回数)
Submission

Share Comments
̃Gg[͂ĂȃubN}[Nɒlj
comments powered by Disqus