はまやんはまやんはまやん

hamayanhamayan's blog

2019-04-13から1日間の記事一覧

Great Ocean View [AtCoder Beginner Contest 124 B]

https://atcoder.jp/contests/abc124/tasks/abc124_b 解説 https://atcoder.jp/contests/abc124/submissions/4962119今までの最大値よりも小さいなら、海が見られないので、今までの最大値を持ちながら、 答えをカウントしていこう。 int N, H[20]; //------…

Buttons [AtCoder Beginner Contest 124 A]

https://atcoder.jp/contests/abc124/tasks/abc124_a 解説 https://atcoder.jp/contests/abc124/submissions/4962028場合分けをして解くことにする。 A=Bなら、どっちも取るのが最適。 そうでないなら、大きい方を2回取るのが最適。 int A, B; //-----------…

ジジ抜き [yukicoder No.814]

https://yukicoder.me/problems/no/814 前提知識 二分探索 解説 https://yukicoder.me/submissions/338394問題文にもあるように、ジジは奇数枚・他は偶数枚になっている。 使えそうな性質がこれなので、これを使って解法を考えていく。 ある数以下のカードの…

ユキちゃんの冒険 [yukicoder No.813]

https://yukicoder.me/problems/no/813 解説 https://yukicoder.me/submissions/338365公式解説にもあるが、門を1つにまとめ上げることで答えを求めよう。 逃走率p1、通過率q1の門、逃走率p2、通過率q2の門を1つにまとめると、逃走率 p=(p1+q1*q1*p2/(1-p1*p…

Change of Class [yukicoder No.812]

https://yukicoder.me/problems/no/812 前提知識 ダイクストラ 解説 https://yukicoder.me/submissions/3382671日経過するたびに、距離が2の人と友達になる。 次の日もまた、距離が2の人と友達になる。 これで友達になっている人を考えると もともと距離1→も…

競技プログラミングにおけるダブリング問題まとめ

工事中 ダブリング ~~~ 問題

約数の個数の最大化 [yukicoder No.811]

https://yukicoder.me/problems/no/811 前提知識 エラトステネスの篩の計算量 解説 https://yukicoder.me/submissions/338186今回は答えを全探索する。 答えの候補MがNと共通の素因数をK個以上持つかは、2つの数を素因数分解して、同じ数の個数のうち少ない…

割った余りの個数 [yukicoder No.810]

https://yukicoder.me/problems/no/810 解説 https://yukicoder.me/submissions/338175Mで割った余りを並べてみると、 0 1 2 3 ... M-1 0 1 2 3 ... となる。 ここからどこでもいいので、連続してM個取り出すとそれはすべて異なっていることが分かる。 よっ…

かけ算 [yukicoder No.809]

https://yukicoder.me/problems/no/809 解説 https://yukicoder.me/submissions/338172解法を考えるときは、全探索対象を探すという汎用的なテクがあり、 今回はAを全探索して考える。 普通に全探索すると、10^9かかるが、A<Bと考えると、sqrt(10^9)に収ま…