AtCoder Beginner Contest 124に参戦したので、提出時にどのようなことを考えていたのかと実際の提出コードをまとめておきたいと思います。利用した言語はPython3。Python3や競技プログラミングに取り組まれている方の一助になれば幸いです。

基本的には参戦記録のようなものをまとめることはあまりないのですが、今回は総合成績115位と自分にしてはかなりよい結果だったので、浮かれてこんな記事を書いています(´・ω・｀)

A - Buttons

取りうる行動は以下の3通りなので、それぞれの行動で獲得できるコインの数の最大数を求めます。

大きさAのボタンを2回押す
大きさBのボタンを2回押す
大きさAのボタンと大きさBのボタンを1回づつ押す

B - Great Ocean View

すべての旅館について、海を見ることができるかどうかを判定し、見ることができる旅館の数を数えるだけです。$O(n^2)$ですが、旅館の数Nの最大値が20とかなり小さいので、この解法でもACします。Nが大きいと工夫する必要があるかもしれません。

C - Coloring Colorfully

市松模様のパターンは以下の2通りです。

□■□■□■□■□■...
■□■□■□■□■□...

よって「与えられたタイルの並び」から2つの市松模様に変えるためのコストを求め、よりコストが低いほうが答えになります。

D - Handstand

左端のインデックスをi、右端のインデックスをjとすると、S[i:j]に属する人を$K$回の操作で全員逆立ちにできた場合、右端を広げます。つまりj += 1とします。一方、$K$回の操作をしても全員を逆立ちにできなかった場合、左端を狭めます。つまりi -= 1とするわけですね。

ところで「S[i:j]に属する人を$K$回の操作で全員逆立ちにできるか」の判定はどのようにすべきでしょうか? たとえば次のように人が並べられていたとします: 01001000。これは3回の操作で全員を逆立ちにすることができます。

先頭の人を逆立ちにする。
真ん中の2人を一度に逆立ちにする。
最後尾の3人を逆立ちにする。

つまりS[i:j]のうち0が連続する区間の数が$K$以下の場合、「$K$回までの操作で全員逆立ちにできる」といえそうです。すると問題は「S[i:j]のうち0が連続する区間の数」をいかに効率よく求めるかになります。わたしは尺取り法を利用しましたが、累積和でもなんとかなりそう。並んでいる人の数$N$の最大値が$10^5$というかなり微妙なラインではあるので、工夫次第では区間をなめるコードでもなんとかなるかも。

AtCoder Beginner Contest 124 の参戦記録

A - Buttons

B - Great Ocean View

C - Coloring Colorfully

D - Handstand