drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder300点 ABC-C 灰色diff for文 for文:ある状態がどこまで続くかを求める 一次元グリッド データ構造テク：差分更新 順序の工夫：後ろから見る 各kに対して バケット for文:前回求めた値を活用する NoviSteps5Q for 文を回していくときに「前回の値を活用する」というテクが登場する問題。このテクは、後に「累積和」や「DP」を学ぶ際の大切な基礎となる。 問題へのリンク 問題概要 日間のうち、 日目には花火が上がる。 各日について、何日後に最初の花火が上がるかを答えよ。 制約 考えたこと 二重ループを書いて TLE にならないなら簡単。実際には TLE になるので少し工夫する。 まず、 日間を マスに見立てることにする。そして、花火のない日は白色マス、花火のある日は黒色マスとする。なお、このように、 日間という設定を マスという設定にして可視化するのは、地味ながらも結構使えるテク。 そして、下図のように、… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F10%2F02%2F140500" title="AtCoder ABC 322 C - Festival (5Q, 灰色, 300 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20231002/20231002135919.png Hatena Blog https://hatena.blog 2023-10-02 14:05:00 rich https://drken1215.hatenablog.com/entry/2023/10/02/140500 1.0 100%