こんにちは。論文を読みすすめられなくて困っていたのところ、音読してみると読み進められることがわかってちょっとやる気が出てきた綿谷雫です。 GWということで今日も解説記事*1を書いていこうと思います。

今回やっていくのはARC024 B - 赤と黒の木です。 AtCoder ProblemsのRecommendationに出てきました。問題のリンクは下に貼っておきます。

問題概要

問題をまとめると

両隣の木と自分の色が3つとも同じだと次の日色が変わる木が環状に並んでいる。
何日目に色が変わらなくなるかを答える
色が変わり続ける場合は-1を出力してね

という感じです。

なぜ赤と黒なのかはよくわかりませんが、赤黒木というデータ構造があるからでしょうか。赤黒木は今回関係ないと思います。

解法にいたるまで

まずはどんな時に色が変わるのが止まるかを考えました。両隣の木と自分の色が3つとも同じときに色が変わる木、なので3つ以上同じ色の木が並んでいるところは両端を除いた真ん中の木の色が全て変わることになります。両端の色は変わりません。そう考えると一日ごとに同じ色の木が並んでいるところが2ずつ短くなっていくことがわかります。 2ずつ短くなっていった末3つ以上同じ色の木が並んでいるところがなくなったら色が変わるのが止まるでしょう。これを考えていけば解けそうです

しかし永遠に色が変わる場合がサンプル3で示されています。永遠に色が変わる場合があるのはなぜでしょうか。これは全てが同じ色の木なので両端がない、という場合があるからです。というわけでこの場合を除外しないといけないですね。

さて全ての木が同じ色という場合を除外したとして、同じ色の木が一番続いているところがどれだけ続いているかを求めます。環状ではなく直線状に並んでいるのであれば、始点から終点まで調べればいいですが、環状だとうまくいきません。というのも6,1,2番目の木が同じ色で並んでいた場合に少なく数えてしまうからです。これを回避するためには2周して数えればいいです。 2倍の長さの配列を用意しました

allocate(color(2*N))
do i=1,N
    read*,color(i)
    color(i+N)=color(i)
end do
 
REN=0
pre=1
do i=2,N*2
    if(color(i-1)/=color(i))then
        REN=max(REN,pre)
        pre=0
    endif
    pre=pre+1
end do
REN=max(REN,pre)

こうしてRENぞくして同じ色の木が並ぶ最長の部分の長さが求められました。

これを使った全体のコードはこんな感じです

program bm
implicit none
integer::N
integer,allocatable,dimension(:)::color
integer::pre
integer::REN

integer::i
read*,N
allocate(color(2*N))
do i=1,N
    read*,color(i)
    color(i+N)=color(i)
end do

REN=0
pre=1
do i=2,N*2
    if(color(i-1)/=color(i))then
        REN=max(REN,pre)
        pre=0
    endif
    pre=pre+1
end do
REN=max(REN,pre)

if(REN==2*N)then
    print"(i0)",-1
    stop
endif

print"(i0)",(REN-1)/2 +1

end program bm

おしまい

*1:もう少しいい表現を探していきたいところ

しずくぶろぐ

競技ぷろぐらみんぐしたり、なんかしたりします

不定期解説記事企画 ARC024B #雫ぷよ

問題概要

解法にいたるまで