2021-07-22から1日間の記事一覧
何の話かと言うと atcoder.jp上記の問題は、「前のループで事前に計算できる部分を見つける」というちょっとした工夫で高速化ができるよく知られた問題です。「子供に飴を配る」という立て付けですが、端的には、・ という条件の下に、 を満たす の組み合わ…
何の話かと言うと atcoder.jp「区間DP」でうまく解ける問題の例として、こちらを紹介します。 区間DPとは? 「一列にならんだもの(A[1],..., A[N])を操作する系」の問題で、特定範囲 A[i] 〜 A[j] に制限した場合の答えを dp[i][j] とした上で、幅 d = j -…