kira000 https://blog.hatena.ne.jp/kira000/ kira924ageの雑記帳 https://kira000.hatenadiary.jp/ 競プロ C言語 はじめに 尺取法というものを知った。 尺取法の概要 JOI用語集によると、 配列に対して二つのインデックスを持ち、条件に応じて片方を進める操作を繰り返すことで答えを得る方法のこと。尺取虫の動きにちなんで名付けられた。DPの一種ともとれる。またキューの実装も尺取法の一種である。 とのこと。例えば、AtCoder Regular Contest 022のB問題はこの尺取法を使って解くことができる。 問題の概要 問題文 高橋君は細長いお菓子を持っています。このお菓子は Ncm の長さのお菓子で、 1cm ごとにブロックに分かれています。それぞれのブロックには 種類の味うちのいずれかの味がついていて、… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkira000.hatenadiary.jp%2Fentry%2F2014%2F05%2F06%2F070102" title="尺取法についてのあれこれ - kira924ageの雑記帳" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=N%5C%5C%0AA_1%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20A_2%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20.%5C%20%5C%20%5C%20%5C%20%5C%20.%5C%20%5C%20%5C%20%5C%20%5C%20.%5C%20%5C%20%5C%20%5C%20%5C%20A_N Hatena Blog https://hatena.blog 2014-05-06 07:01:02 rich https://kira000.hatenadiary.jp/entry/2014/05/06/070102 1.0 100%