—2025/05/02
今日は雨が降り、昨日ほど気温が上がりません。
昨日のAtcoder問題について、引き続き書きたいと思います。
問題の詳細を昨日の記事にご参照ください。「誰がリーダーになる」
賢いの方もう既に分かったと思いますが、この問題の解き方がそんなに難しくありません。
以下の図をご覧ください。
図のように、2番目と３番目の人に注目してください。この二人それぞれリーダーになれば、全員の立つ方向を変える必要がありません、皆が彼に向いているからです。
２番目の人と３番目の人の共通点があります、それは
自分より前に立つ人は東に向いている、自分より後ろに立つ人は西に向いているということです。
それを見つければ、解決方法が決められます。
自分より前に立つ人は東向きでなければ、回転する必要があるので、カウントする、
自分より後ろに立つ人は西向きでなければ、回転する必要があるので、カウントする。
以上の合計数値は、全員の回転回数になります。
ここでは、実装する際、ちょっと気をつけなくちゃいけないところがありまして、最大回数10⁵あるので、２重ループ処理を避けるため、累積和知識を用いて、1重ループ処理で実装することです。
