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

こんにちは, Shinoryoです.

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

A - Rainy Season

$| S | = 3$ なので, 3連続から順にif文で分類していくことで解けます.

	# 入力
	S = input()

	# 各文字がRかどうかを表すbool型変数を用意
	first = (S[0] == "R")
	second = (S[1] == "R")
	third = (S[2] == "R")

	# 3日連続のパターン
	if first and second and third:
	print(3)
	# 2日連続のパターン
	elif (first and second) or (second and third):
	print(2)
	# 1日連続のパターン
	elif first or second or third:
	print(1)
	# 雨が降らなかったパターン
	else:
	print(0)

もちろん, 3文字に限らないようにコーディングすることもできます.

itertools.combinations()で, リストからある数だけ取り出す組み合わせを列挙します. 今の場合, 配列 $L$ (小さい順にソート済)から3つ $i$ , $j$ , $k$ を選ぶ組み合わせを列挙します. そして, 以下の条件を全て満たすものを数えます.

	import itertools

	# 入力
	N = int(input())
	L = sorted([int(x) for x in input().split()])

	# 答えを格納する変数
	ans = 0

	# 組み合わせを列挙
	for i,j,k in itertools.combinations(L,3):
	if i != j and j != k and k != i and i + j > k:
	ans += 1

	# 答えを出力
	print(ans)

$X$ は絶対値を考えていいので, 始めにabs(X)として絶対値にしてしまいます.

$X$ を $D$ で割った商を $T$ とします.

$K < T$ ならば, $X - D \times K$ が答えです.
$K \geq T$ ならば,
- $K - T$ が偶数ならば, $A = X - D \times T$ が答えです(原点をはさんで往復移動すれば元に戻ってこれます).
- $K - T$ が奇数ならば, $D - A$ が答えです(原点を挟んで1回負に移動した点の座標の絶対値が答えになります).

この問題においては, 上の図のように, 移動は置かれたマスの属するサイクル上でのみ行われます. これを念頭に置いておきます.

各マス始まりということでループをして( $N$ マスに対して), それぞれのマスから始まるサイクルを調べます. そして何回移動するか(最小で $1$ 回, 最大で $K$ 回)でまたループをして, それぞれの場合の得点を調べます.

対称性より, サイクルのマスの総数より大きい回数は調べなくてよいです. サイクルを周回した方が得点合計が大きくなる可能性をまとめて考慮することができます.

	# 入力
	N, K = [int(x) for x in input().split()]
	# Pは配列のindexに揃えて-1する
	P = [int(x) - 1 for x in input().split()]
	C = [int(x) for x in input().split()]

	# 答えを格納する変数
	ans = - 10**9 - 1

	# 最初に置くマスに関してN通りループ
	for i in range(N):
	# 移動したことがあるかのフラグ管理
	flag = [False]*N
	# 移動した結果得られる得点を格納
	score = []
	# 移動の結果今いるマスを格納
	now = i

	# まずは1回移動する
	now = P[now]

	# 移動したことがあるマスに移動したら次のステップへ
	while not(flag[now]):
	# 移動したことがあるフラグを立てる
	flag[now] = True
	# 移動した結果得られる得点を追加
	score.append(C[now])
	# 移動する
	now = P[now]

	# 得点を足していくための変数
	score_temp = 0
	# scoreの合計を格納しておく
	# 負なら0にしておく
	score_sum = max(0, sum(score))
	# scoreの長さを格納しておく
	score_len = len(score)

	# 移動する回数は、最大でK回
	# 対称性より、score_lenより大きい回数は調べなくてよい
	for i in range(min(K, score_len)):
	# 移動した結果のscoreを足していく
	score_temp += score[i]
	# ansを更新
	# 周回した方が得点合計が大きくなる可能性を考慮する
	ans = max(ans, score_temp + score_sum * ((K - i - 1) // score_len))

	# 答えを出力
	print(ans)

ちなみに, Python3.8だとTLEとなってしまいましたが, PyPy3だとACでした. やっぱりよく分からないですね.

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