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

hamayanhamayan's blog

2019-08-18から1日間の記事一覧

ハイパー部分和問題 [yukicoder 868]

https://yukicoder.me/problems/no/868 前提知識 戻すDP 解説 https://yukicoder.me/submissions/370474 戻すDPを知っている人は、適用するだけである。 まずは、普通にDPを作ろう。 dp[i][k] := 配列Aのi番目まで使って、総和がkである組み合わせ 戻すDPを…

避難経路 [yukicoder 867]

https://yukicoder.me/problems/no/867 解説 https://yukicoder.me/submissions/370451 まず、やはり気になるのは、制約である。 K2がついているし、かつ、A[i][j]の値がとても小さい。 これはKが増えれば増えるほど、K2による影響が増えていきそう。 なので…

レベルKの正方形 [yukicoder 866]

https://yukicoder.me/problems/no/866 解説 https://yukicoder.me/submissions/370328 結構計算量が厳しいらしいので、ゴリゴリ計算系であろうと思う。 全探索で考えると、左上をHW通り試し、正方形の一片を試してmin(W,H)通り試す。 これだと間に合わない…

24時間降水量 [yukicoder 865]

https://yukicoder.me/problems/no/865 解説 https://yukicoder.me/submissions/370121 クエリ計算を行っていくが、降水量が減ることはないため、 変化する分を計算すればいい。 ある個所が変更されたときに影響を受けるのは24区間である。 なので、その24区…

四方演算 [yukicoder 864]

https://yukicoder.me/problems/no/864 解説 https://yukicoder.me/submissions/370113 ab + bc + cd + da = Kを変形していく (ab + da) + (bc + cd) = K a(b + d) + c(b + d) = K (a + c)(b + d) = K となるので、a+c, b+dはKの倍数になる。 なので、Kを2つ…

計算量 [yukicoder 863]

https://yukicoder.me/problems/no/863 解説 https://yukicoder.me/submissions/369283 計算量が線形時間であれば、Nが40倍になれば、かかる時間も40倍になっているはずである。 小数点切り捨てでAミリ秒なので、実際には、A.0~A.9999であるので、40倍する…

Dividing a String [AtCoder Grand Contest 037 A]

https://atcoder.jp/contests/agc037/tasks/agc037_a 前提知識 DP 解説 https://atcoder.jp/contests/agc037/submissions/6964393 AGCの頭ということで貪欲で解きたい気持ちをこらえて解法を考える。 順位賞を見ると爆速で解いている人もいるが、結構落ちて…