yutas213 https://blog.hatena.ne.jp/yutas213/ yutasの競技プログラミング勉強帖 https://yutas.hatenadiary.com/ PAST13 AtCoder C++ アルゴリズム実技検定 PAST DP 区間和 競技プログラミング 問題 長さ の整数列 が与えられる。 を満たす整数組 を任意に選ぶときの、 の値としてありえる最大値を求めよ。 入力 まず最初の1行目に整数 が与えられる。 その次の1行に 個の整数 が順に与えられる。 条件 入力はすべて整数 出力 最大値を1行で出力すること。 解法 まず単純な方法として、 となる値を から まで順に探索し、和を求めていくという方法が着想できます。 この方法では、ループを行うだけでも の計算量が必要になり、 は最大で であるので、実行時間制限には間に合いません。 そのため、別の方法を考える必要があります。 そこで、以下のような値 を考えます。 : としたときの の最大値 : … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyutas.hatenadiary.com%2Fentry%2F2023%2F12%2F07%2F141750" title="G - 区間和 / 第13回 アルゴリズム実技検定 (PAST13) - yutasの競技プログラミング勉強帖" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2023-12-07 14:17:50 rich https://yutas.hatenadiary.com/entry/2023/12/07/141750 1.0 100%