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