https://atcoder.jp/contests/abc144/tasks/abc144_f 前提知識 期待値DP 解説 https://atcoder.jp/contests/abc144/submissions/8180528 グラフ全体はDAGになっているので、期待値DPをすることで答えが求まる。 まずは、通路を塞がないパターンを考えてみよ…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_f 解説 https://atcoder.jp/contests/joi2017yo/submissions/8142007 パット見てダイクストラ感はある。 状態を考えると、(どの部屋にいるか, 寒すぎる・暑すぎるのどっちが最後か, 寒すぎる・暑すぎ…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_e 解説 https://atcoder.jp/contests/joi2017yo/submissions/8141535 まず、順当に考えると、座標を全探索して、シミュレーションをして、その座標が尾根であるかを判定する。 どのようにシミュレー…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_d 解説 https://atcoder.jp/contests/joi2017yo/submissions/8140685 何から始めようかという感じになるかもしれないが、M≦20というところがまずはヒントになりそうだ。 種類について何かうまくやる…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_a 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138403 場合分けをする。 Aが凍っている場合は解凍するまでの時間を追加で計算する。 あとは、凍っていないときにかかる時間を追加で計…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_b 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138857 N≦A[i]であれば、当たりとなり、当たりとなるようにM-1個選んでいく。 どれを当たりカードとすべきか考えたときになるべく、A[i]…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_c 解説 https://atcoder.jp/contests/joi2017yo/submissions/8139896 重複なく数えるために、かぶらないような特徴を見つけることが大切である。 今回で言えば、休憩スペースの左上端とする座標につ…

https://atcoder.jp/contests/abc144/tasks/abc144_e 前提知識 二分探索 解説 https://atcoder.jp/contests/abc144/submissions/8164566 まず、最大値の最小化ということで二分探索かというところ。 最大値が決まっていれば、各メンバーについて何回修行が必…

https://atcoder.jp/contests/abc144/tasks/abc144_c 解説 https://atcoder.jp/contests/abc144/submissions/8157943 まず、制約を見ると、掛け算表を作るのは現実的ではない。 Nが書かれているマスはどんなマスだろうと考えたときに、ij=Nを満たすマスであ…

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_a 解説 https://atcoder.jp/contests/joi2016yo/submissions/8142856 物理、科学、生物、地学から点数が高いものを3つ選んで総和を取るが、 これは、「(総和)-4つのmin」と実は等しい。 こっちのほう…

https://atcoder.jp/contests/abc144/tasks/abc144_d 解説 https://atcoder.jp/contests/abc144/submissions/8169237 数学的な問題のようだ。 0°の状態から傾けていくと、水の形は最初長方形だが、台形の柱となり、三角柱となりと遷移する。 三角柱になる前…

https://atcoder.jp/contests/abc144/tasks/abc144_a 解説 https://atcoder.jp/contests/abc144/submissions/8153919 A,Bのどちらかが10以上なら計算できないので-1 そうでないならできるので、A*Bを答える。 int A, B; //---------------------------------…

https://atcoder.jp/contests/abc144/tasks/abc144_b 解説 https://atcoder.jp/contests/abc144/submissions/8155035 2つの整数の積として表現できるかということなので、その2つの整数を全探索する。 それぞれ9種類なので、全体で81通りなので、間に合う。 …