2019-06-17から1日間の記事一覧
https://atcoder.jp/contests/abc130/tasks/abc130_e 動的計画法 動的計画法 解説 https://atcoder.jp/contests/abc130/submissions/6001273mod10^9+7で制約が10^3くらいなので、dp[10^3][10^3]かなーと経験則的に思う。 2つの数列があって、dp[s][t]である…
![はてなブックマーク - Common Subsequence [AtCoder Beginner Contest 130 E]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/223516)
https://atcoder.jp/contests/abc130/tasks/abc130_d しゃくとり法 解説 https://atcoder.jp/contests/abc130/submissions/6000372微妙に何から手を付ければいいか分からない。 こんなときは全探索対象を探す訳だが、ここにも典型テクがある。 条件を満たす…
![はてなブックマーク - Enough Array [AtCoder Beginner Contest 130 D]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/211704)
https://atcoder.jp/contests/abc130/tasks/abc130_c 解説 https://atcoder.jp/contests/abc130/submissions/6000248ABC300点問題なので、なるべく単純に考えることにする。 この問題はある種の構築問題である。 構築問題の典型テクとして「理論値の最大値を…
![はてなブックマーク - Rectangle Cutting [AtCoder Beginner Contest 130 C]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/210553)
https://atcoder.jp/contests/abc130/tasks/abc130_b 解説 https://atcoder.jp/contests/abc130/submissions/6000104跳ねる動きをシミュレートする。 N≦100なので、シミュレートしても間に合う。 int N, X, L[101]; //-------------------------------------…
![はてなブックマーク - Bounding [AtCoder Beginner Contest 130 B]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/205556)
https://atcoder.jp/contests/abc130/tasks/abc130_a 解説 https://atcoder.jp/contests/abc130/submissions/6000049問題文の通りに分岐して解く。 int X, A; //-----------------------------------------------------------------------------------------…
![はてなブックマーク - Rounding [AtCoder Beginner Contest 130 A]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/205121)
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b 前提知識 UnionFind 解説 https://atcoder.jp/contests/diverta2019-2/submissions/5943792なにか全探索対象を探す。 どこを全探索しようかなと色々考える。 1つ目を全探索すると、自由度…
![はてなブックマーク - Picking Up [diverta 2019 Programming Contest 2 B]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/204330)
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_a 解説 https://atcoder.jp/contests/diverta2019-2/submissions/5943412まず、みんなボールは1個以上受け取るので、先に渡しておこう。 最大-最小を最大化したいのだが、最小は0にすればい…
![はてなブックマーク - Ball Distribution [diverta 2019 Programming Contest 2 A]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/204314)
https://yukicoder.me/problems/no/840 前提知識 行列累乗によるDP高速化 DPテク11「文字列の部分列の個数を添え字に持つ典型」 解説 https://yukicoder.me/submissions/352662Nが大きい、かつ、数え上げということなので、まずは行列累乗路線で考える。 「…
![はてなブックマーク - ほむほむほむら [yukicoder No.840]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/203023)
https://yukicoder.me/problems/no/838 前提知識 DPテク17「遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる」 解説 https://yukicoder.me/submissions/352656まず、前の問題が解けないと解けないので、こちらを理解する。 get(L, R)…
![はてなブックマーク - Noelちゃんと星々3 [yukicoder No.838]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/200139)
https://yukicoder.me/problems/no/837 前提知識 「マンハッタン距離の差の和の最小値は中央値に集めるとき」 解説 https://yukicoder.me/submissions/352655マンハッタン距離の総和の最小値の地点は中央値であるというテクを使う。 高さの変更先は2つあると…
![はてなブックマーク - Noelちゃんと星々2 [yukicoder No.837]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/195336)
https://yukicoder.me/problems/no/836 解説 https://yukicoder.me/submissions/352484自分はライブラリにしてあるので、貼るだけ。 countMultiple(L, R, div, mod) := [L,R]の間の数でdivで割ったときの剰余がmodである個数 これを作るが、区間の数を[L,R] …
![はてなブックマーク - じょうよ [yukicoder No.836]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/195118)
https://yukicoder.me/problems/no/835 解説 https://yukicoder.me/submissions/352483小数はちょっと扱いにくいので、ジュースを2本で3Lと考えよう。 すると、N/2の切り捨て分だけ3L手に入るので、N/2*3本はある。 あとは、Nが奇数であれば、+1.5L分なので…
![はてなブックマーク - ジュース [yukicoder No.835]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2019/06/17/194812)
