haraduka https://blog.hatena.ne.jp/haraduka/ haraduka's diary https://haraduka.hatenadiary.jp/ AtCoder これはできなかったのが悔やまれる…。 N人(身長がバラバラ)が並んでいて、i人目に関して、その人が前を見た時に見える人の数を出力する問題。問題を簡単化する。 普通に考えるとi人目に関して、それより前のj人目を見て、そのiとjの間に二人より大きな人が存在しなければj人目は目視することができ、それの和を取ればいい。しかしこれで考えると、どう頑張ってもO(N^3)なので見方を変える。 i人目から順に見ていくことにすると、i-1番目は見える。i-2番目はi-1番目より大きければ見える。i-3番目はi-1, i-2番目より大きければ見える…というように、実はi-1番目から1番目まで順に見ていき、身長が単… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fharaduka.hatenadiary.jp%2Fentry%2F2015%2F07%2F28%2F172746" title="Donutsプロコンチャレンジ2015 C問題 行列のできるドーナツ屋 - haraduka&#39;s diary" 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 2015-07-28 17:27:46 rich https://haraduka.hatenadiary.jp/entry/2015/07/28/172746 1.0 100%