AtCoder Beginner Contest 174をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 174を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - Air Conditioner

入力値が $30$ 以上かどうかをif文で判定します.

問題文にある条件を順に確かめていきます.

$7$ , $77$ , $777$ , ……の数列を ${a_{i}}$ とすると, これは漸化式で以下のように表されます.

\begin{aligned} (1) & a_{i} & = {\begin{aligned} 7 & (i = 1) \\ 10 \times a_{i - 1} + 7 & (i \geq 2) \end{aligned} \end{aligned}

$K$ で割り切れるかが重要なので, $\mod K$ を考えることにします.

漸化式より, ある $i$ で以前に出てきた値が再度出現すると, それ以降は繰り返しになります. $\mod K$ としてとれる値は $0$ から $K - 1$ までの $K$ 通りしかありませんので, (鳩の巣原理より)高々 $i = K$ までの調査でよいことになります.

	# 入力
	K = int(input())

	# 7, 77, 777, ……を順番に格納していく変数aの初期化
	a = 0

	# 高々K回確認すればよい
	for i in range(K):
	# aの末尾に7を追加
	# 数字が大きくなりすぎるのを防ぐために, ここで7で割った剰余にしておく
	a = (10*a + 7) % K
	# 7で割った剰余が0かどうかを確認
	if a == 0:
	# 答えの出力
	print(i + 1)
	exit()

	# 存在しなければ-1を出力
	print(-1)

「赤い石の左隣に置かれた白い石は災いを招く」というのは, すなわち左側に"R",　右側に"W"がまとまって存在するようにしなければならないことになります. イメージとしては, 右の方にある"R"を左の方にある"W"と入れ替えればよいことになります.

そのためには, まずは文字列に存在する"R"の個数を調べます. 最終的には左端からその個数だけ"R"が並ぶことになりますので, その部分文字列に"W"が何個あるかを調べます. その個数だけ, "R"と"W"の入れ替えを行えばよいことになります.

	N = int(input())
	c = input()

	# 左側に"R",　右側に"W"がまとまって存在するようにしなければならない
	# R...R \| W .. W
	# まず, cに存在する"R"の個数(=Rcount)を調べる
	# 左からRcount個だけ"R"が並ぶ状態にすればよい
	# 実際には, cから左からRcount個だけ抽出し,
	# そのうち"W"の個数だけ, "W"と"R"の入れ替えを行うことになる

	print(c[:c.count("R")].count("W"))

E以降は私の能力不足故に省略いたします.