はじめに
C問題が解けなかったため、まとめようと思います。
C問題
|0|~|9|のリールを持つスロットがある。
経過時間をt秒とすると、以下に対応する秒数でボタンを押すことができる。
下の例では0秒時点で|1|-|8|-|2|が並ぶ。
1列目 2列目 3列目
|1| |8| |2| < (t % 10) == 0
|9| |1| |3| < (t % 10) == 1
|3| |2| |8| .
|7| |4| |5| .
|4| |6| |7| .
|5| |9| |6| < (t % 10) == 5
|8| |0| |0| .
|0| |3| |1| .
|6| |5| |4| .
|2| |7| |9| < (t % 10) == 9
例えば|1|で揃えたい場合は
- 0秒後に1列目のボタンを押す
- 1秒後に2列目のボタンを押す
- 7秒後に3列目のボタンを押す
つまりこのケースでは|1|を揃えたい場合は最低7秒必要である。(★ここの求め方は後述)
|0|~|9|で同様の計算をするとそれぞれを揃えるために必要な最低秒数を求めることができる。
この中の最低値が答えとなる。
★各数値を揃えるための最低秒数を求めるアルゴリズム
上のケースで0を揃えるための最低秒数を計算する。
重要な前提として、
同時に複数の列のボタンは同時に押せない
を意識する。
|0|を揃えたい場合、6秒後に2列目と3列目に同時に出てくる。
したがって、6秒後に2列目を押し、16秒後に3列目を押さなければいけない。
同じ列に同じ値が何個あるかを求めれば、その数が多いほどリールを揃える時間がかかる。
一つの列に現れた同じ数の回数をk、それが最初に現れる秒数をtとすると
t + 10 × (k - 1)
となる。ただし同じ数現れる秒数が複数あった場合は、より後ろのt(秒数)を使用する。
2秒後に2回現れる場合は12秒で必要だが、5秒後に2回現れる場合は15秒必要になるから。
これを前提に|0|~|9|を揃えるのに何秒かかるか求める関数を実装してみる
from collections import defaultdict
def time(num):
d = defaultdict(lambda: 0)
for i in range(10):
for j in range(N):
s = int(S[j][i])
if s == num:
d[i] += 1 # 同じ値が何個あったかをインクリメントする
mk = 0
mv = 0
for i in range(10):
if d[i] >= mv:
mk = i
mv = d[i]
v = d[mk]
return mk + 10 * (v - 1)
# -------------------------
print(time(0)) # 0を揃えるための最低秒数
print(time(1)) # 1を揃えるための最低秒数
あとは各秒数の最低値が求める答えとなる。
def answer():
ans = 10 ** 7 + 1
for i in range(10):
m = time(i)
ans = min(ans, m)
print(ans)
最終的な回答は以下となります。
N = int(input())
S = [input() for _ in range(N)]
from collections import defaultdict
def time(num):
d = defaultdict(lambda: 0)
for i in range(10):
for j in range(N):
s = int(S[j][i])
if s == num:
d[i] += 1
mk = 0
mv = 0
for i in range(10):
if d[i] >= mv:
mk = i
mv = d[i]
v = d[mk]
return mk + 10 * (v - 1)
def answer():
ans = 10 ** 7 + 1
for i in range(10):
m = time(i)
ans = min(ans, m)
print(ans)
answer()
解けなかった理由
|0|~|9|を揃えるためにそれぞれ何秒かかるか、その最低値が答えとなる方針は持っていた。
しかし一回のforループで行おうとしたため、コードが複雑になってしまいACとWAが半分くらいのサンプルケースは通るけど、、の状態になってしまった。
上記でコードとして示したように、「0を揃えるためには何秒かかるか」をまず考える。それを一般化し関数にする。
問題の条件を把握して、|0|~|9|をそれぞれ別ループで確認しても実行時間は問題ないことを確認するべきだった。。