https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_g 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5215078ダイクストラをやる。 (到達している駅, 手にしている花)を状態として、コストは使ったお…

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_e 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5214793数えやすい方を数えよう。 AAAを連続する部分文字列に持つ組み合わせではなく、持たない方の組み合わせを考えてみ…

N個の真珠がある。 i番目の真珠の色はpearls[i]であり、1～Mである。 ある真珠を抜き出して、ある箇所に差し込むという操作を行う。 同色の真珠は連続して並んでいる状態にしたい。 操作の最小回数は？1≦N≦50 1≦M≦15 解説 問題を少し読み替える。 今回の問題…

N個の山がある。 高さは順にH[i]である。 ある山からスタートして、左か右かにスキーで降りていく。 高さが同じか低いなら降りられる。 途中で方向は変えられないとき、一回の滑降で最高何個の山を通れるか。1≦N≦50 1≦高さ≦1000 解説 全探索する。 自分は+1…

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_d 前提知識 最小全域木 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5214486これは一般的な話だが、ある問題を見たときに今まで解いた類題が思い出せれば、 そこから似…

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_c 前提知識 座標圧縮 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5214368大小関係を維持したまま、配列の数字を変えて総和を最小化する問題。 これは座標圧縮をすれば…

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_a 前提知識 動的計画法 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5214346問題を読み替えよう。 どの長さqの部分列も、他の歌の部分列でない。 つまり、最長の共通部…

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_l 前提知識 二分探索 SparseTable 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5197060ソートしてK番目の数がなんであるかという問題なので、いつもの二分探索をやる。 …

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_k 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5196729まず、各円盤では独立に確率が決められている。 真面目に計算するのではなく、線形性などをうまく利用するのだろ…

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_j 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5198838回分なので、半分が確定すれば、もう半分も確定する。 簡単のために、Nが偶数のときを考えてみよう。 N/2個の01列…