そまちょブログのそまちょ（@somachob）です。
この記事は、AtCoder Beginner Contest 320 の C問題についての解説です。
C – Slot Strategy 2 (Easy)
文字列の長さが100なので、全探索で解いていきます。
各リールの文字の場所を全探索
各リールの文字の場所について全探索してみます。
1つ目のリールの文字の場所を i
2つ目のリールの文字の場所を j
3つ目のリールの文字の場所を k
として全探索し、文字が同じときに、何秒かかったかを求めます。
次のようなコードで全探索することができます。
# 入力
M = int(input())
S1 = input()
S2 = input()
S3 = input()
# 各リールの文字の場所を全探索
for i in range(M):
for j in range(M):
for k in range(M):
# S1のi番目の文字とS2のj番目の文字とS3のk番目の文字についての処理この問題では、表示されている文字がすべて同じときの秒数を求めるので、すべてのリールの文字が同じときだけ処理をします。
# 入力
M = int(input())
S1 = input()
S2 = input()
S3 = input()
# 各リールの文字の場所を全探索
for i in range(M):
for j in range(M):
for k in range(M):
# すべてのリールの文字が同じとき
if S1[i] == S2[j] == S3[k]:
# 同じときの処理インデントが深くなるので、関数に書き出すことで見やすくなります。
また、条件式を反転し、早期リターンすることで見通しがよくなります。
# 入力
M = int(input())
S1 = input()
S2 = input()
S3 = input()
# i, j, kについての処理を関数に
def solve(i, j, k):
# 条件式を反転して早期リターン
# リールの文字が違うとき
if not(S1[i] == S2[j] == S3[k]):
return
# 文字が同じときの処理
# 各リールの文字の場所を全探索
for i in range(M):
for j in range(M):
for k in range(M):
solve(i, j, k)文字が同じときは、i, j, k のうち一番大きい数字を表示させれば良さそうです。
入力例１では、0秒後に2番目のリールを止めて、2秒後に3番目のリールを止めて、6秒後に1番目のリールを止めています。
これは、i = 6, j = 0, k = 2 です。そのため、i, j, kの中で一番大きい6が答えになります。
Pythonでは、max()を使えば簡単に一番大きい数字を求めることができます。
答え用の変数を準備して、十分大きい数字に初期化しておき、文字が同じときの秒数のうち、一番小さい数字が答えになります。
# 入力
M = int(input())
S1 = input()
S2 = input()
S3 = input()
def solve(i, j, k):
# リールの文字が違うとき
if not(S1[i] == S2[j] == S3[k]):
return 10 ** 10
# i,j,kの一番大きいものを返す
return max(i, j, k)
# 答え用の変数。大きい数字で初期化しておく。
answer = 10 ** 10
# 各リールの文字の場所を全探索
for i in range(M):
for j in range(M):
for k in range(M):
answer = min(answer, solve(i, j, k))
if answer == 10 ** 10:
print(-1)
else:
print(answer)実はこれでは、正解になりません。
入力例２のように各リールの同じ場所に同じ文字があるとき、同時にリールを止めることができないからです。
たとえば、次のような入力のとき、答えは20になります。
10
0123456789
0123456789
0123456789各リールを0で止めるとき、1番目のリールを0秒後に止めます。
リールが1周してきた後に、2番目のリールを止めます。このときは、10秒後になります。
さらにリールが1周してきた後、3番目のリールを止めます。このときは、20秒後になります。
このように、同じ場所に同じ文字があったときには、その場所にMを足すことで時間を求めることができます。
次の入力のときは、答えは23になります。3番目の位置にあるので3+M+Mです。
10
1110111111
2220222222
3330333333次の入力のときは、3番目のリールは1周目に止めることができるので、3+Mである13が答えになります。
10
1110111111
2220222222
3333033333このように、i, j, k が同じときについての場合分けをすることで答えを求めることができます。
次のコードで、ACできます。
# 入力
M = int(input())
S1 = input()
S2 = input()
S3 = input()
def solve(i, j, k):
# リールの文字が違うとき
if not(S1[i] == S2[j] == S3[k]):
return 10 ** 10
if i == j == k:
return i + M + M
elif i == j:
return i + M
elif j == k:
return j + M
elif k == i:
return k + M
else:
return max(i, j, k) # i, j, kがすべて違うとき
# 答え用の変数。大きい数字で初期化しておく。
answer = 10 ** 10
# 各リールの文字の場所を全探索
for i in range(M):
for j in range(M):
for k in range(M):
answer = min(answer, solve(i, j, k))
if answer == 10 ** 10:
print(-1)
else:
print(answer)【別解】止める文字と止めるリールの順番を全探索
止める文字と止めるリールの順番について全探索する方法で解いてみましょう。
すべてのリールを同じ文字にできるときは、最大で3周すればそろえることができます。
入力で受け取る各リールの文字列を3つつなげれば、管理しやすくなります。
次のように、入力を受け取ります。出力結果は、入力例１のときのものです。
# 入力
M = int(input())
S = []
for _ in range(3):
s = input()
S.append(s * 3)
print(S)
"""出力結果
['193745806219374580621937458062',
'812469035781246903578124690357',
'238576014923857601492385760149']
"""０から９までの文字について、それぞれについて止めるときの秒数を求め、そのうちの一番小さいものを出力することで、解くことができます。
次の2つについて全探索します。
- 止める文字
- 止めるリールの順番
止めるリールの順番については、順列全探索を使うことで全探索できます。
順列全探索については以下の記事で解説しています。
【Python】順列全探索入門！リストの要素を並べ替えて答えを探す
次のコードで、全探索をすることができます。
from itertools import permutations
# 止める文字について全探索
for num in range(10):
# 止めるリールの順番について全探索
for p in permutations(range(3)):
# 処理止める文字は、すべてのリールに含まれている必要があります。
止める文字を決めたら、その文字がすべてのリールに含まれているかチェックして、含まれていないときは、次の文字に進みます。
Sは文字列で受け取っているので比較するときに num を文字列に変換しておきます。
from itertools import permutations
# 入力
M = int(input())
S = []
for _ in range(3):
s = input()
S.append(s * 3)
# 止める文字について全探索
for num in range(10):
# 止める文字を文字列に変換
number = str(num)
# 止める文字がすべてのリールに含まれていないときはスキップ
if number not in S[0] or number not in S[1] or number not in S[2]:
continue
# 止めるリールの順番について全探索
for p in permutations(range(3)):
# 処理1番目に止めるリールは、その文字の初めの場所で止めることができます。
2番目以降のリールについては、それまでのリールが同じ場所で止めているときは、それ以降の場所で止める必要があります。
変数 t で、今までに止めた場所を管理します。
from itertools import permutations
# 入力
M = int(input())
S = []
for _ in range(3):
s = input()
S.append(s * 3)
def solve(number, p):
t = []
# 各リールについて順番に処理
for i in p:
# 3周分の文字列について1文字ずつ確認
for j in range(3 * M):
# リールのj番目の文字が止める文字のとき
if S[i][j] == number:
# その場所で別のリールを止めているときはスキップ
if j in t:
continue
# 止める場所を追加して次のリールに
t.append(j)
break
# 止める場所の最大値を返す
return max(t)
answer = 10 ** 10
# 止める文字について全探索
for num in range(10):
# 止める文字を文字列に変換
number = str(num)
# 止める文字がすべてのリールに含まれていないときはスキップ
if number not in S[0] or number not in S[1] or number not in S[2]:
continue
# 止めるリールの順番について全探索
for p in permutations(range(3)):
answer = min(answer, solve(number, p))
if answer == 10 ** 10:
print(-1)
else:
print(answer)止める場所については、index() を使うことで求めることもできます。
list.index(x[, start[, end]])x と等しい最初の要素のインデックスを取得します。start は探索する開始位置です。
2番目のリールは1番目の止めた場所以降で、3番目のリールは2番目に止めた場所以降で見つけます。
from itertools import permutations
# 入力
M = int(input())
S = []
for _ in range(3):
s = input()
S.append(s * 3)
answer = 10 ** 10
# そろえる文字について全探索
for num in range(10):
number = str(num)
# 止める文字がすべてのリールに含まれていないときはスキップ
if number not in S[0] or number not in S[1] or number not in S[2]:
continue
# リールの押す順番について全探索
for p in permutations(range(3)):
t1 = S[p[0]].index(number)
t2 = S[p[1]].index(number, t1 + 1)
t3 = S[p[2]].index(number, t2 + 1)
answer = min(answer, t3)
if answer == 10 ** 10:
print(-1)
else:
print(answer)
