AtCoder Beginner Contest 174の感想

100-200-300-400-500-0で0ペナ5完1500点。

A - Air Conditioner

$X$ が $30$ 以上かどうかで条件分岐したいので、if文を用いて実装する。計算量は $O(1)$ 。

B - Distance

$N$ 個ある点それぞれについて、「原点からの距離が $D$ 以下か？」という質問に答える。原点からの距離が $D$ 以下であるような点がいくつあるかを記憶する変数を一つ作ると実装しやすい。今回のA問題のような判定を $N$ 回繰り返すイメージ。
計算量は $O(N)$ 。

C - Repsept

説明のため、問題文で与えられた $7,77, 777, \dots$ というような数列を $A$ 、 $7$ が $i$ 個続く数を $A_i$ とする。このとき $A$ の第 $n$ 項は $A_n$ である。
数列 $A$ について、第 $i$ 項の数から第 $i+1$ 項の数へ遷移する方法を考える。これは、

$A_i$ を $10$ 倍して
それに $7$ を足す

とすれば良いことがわかる。「 $7\times 10^{i}$ を足す」とも解釈できるが、上記の方法は変数 $i$ に寄らず一意に表現できるので何かと都合が良い。
さて、今回は $A_i$ が $K$ の倍数かどうか知りたいが、初項から順番に $K$ で割って行って割り切れるかどうか見る方法をとると、途中で $A_i$ の値がオーバーフローしてしまう可能性がある（Pythonなどでも計算速度が非常に遅くなりTLEする可能性が高い）。ここで、今回は「 $A_i$ を $K$ で割った余り」がいくつなのかわかれば十分であるので、先ほどの遷移式に

$K$ で割った余りをとる

という操作を追加する。この操作を追加しても正しい値が求まることは剰余算の性質よりわかる（わからない場合は検索してみてください）。
あとは、 $K$ で割った余りが $0$ となるような $A_i$ が存在しないとき、第何項まで見れば良いのかという問題がある。ところで、先ほどの遷移方法を見ると、 $A_i$ と $A_j$ をそれぞれ $K$ で割った時の余りが等しければ、 $A_{i+1}$ と $A_{j+1}$ は等しくなることがわかる（ここで「変数に寄らず一意に表現」した恩恵が来る）。よって、ある $A_i$ について計算した余りが今までに登場していたところで探索を打ち切ればよい。もっと言えば、鳩ノ巣原理より、「 $A_i$ を $K$ で割った余り」を鳩、「 $0$ 以上 $K$ 未満の整数」を鳩ノ巣と見れば、高々第 $K$ 項までみれば良いことがわかる。
計算量は $O(K)$ 。

D - Alter Altar

「石を $2$ 個選び、それらを入れ替える」という操作は、「石を $1$ 個選び、石の色を変える」という操作を $2$ 回行ったのと同値なので、できれば石を入れ替える操作を優先して行いたい。最小手数を考えることは一度置いておく。石を入れ替える操作のみで、文字列の中でWRという連続部分文字列が存在しないようにするためには、WRという連続部分文字列を見つけたらそれをRWに置換すればよい。この操作を繰り返すと、最終的にRRR...WWWという文字列に落ち着くことがわかる。逆に、この形式の文字列は問題の条件を満たす。
よって、文字列中のRの個数を $R$ とすると、先頭から $R$ 文字目までの中でWという文字はいくつあるかを数えれば、それがそのまま答えとなる（そのWを後半のRと入れ替える操作を行えばよい）。計算量は $O(N)$ 。

E - Logs

長さ $A_i$ の丸太に対して、切った後の長さがそれぞれ $L$ 以下となるように切るのに必要な切る回数の最小値は $(A_i-1)\div L$ で求められる。もし $L$ が固定されているなら、 $N$ 本の丸太全てに対して上記の計算をすることで丸太の長さを $L$ 以下にするために必要な切る回数の最小値がわかる。あとは $L$ を $1$ 以上 $\max (A_i)$ の範囲で二分探索して解を求めればよい。計算量は $O(N\log \max (A_i))$ 。