5問でした。Fは思いつくすべてのテストケースが通るのにサンプルの4だけ通らなくて何がおかしいのだろうと悩んでるうちにタイムアップ。
- 単純にループして間に合うので素朴に書く python
def solve(N, AS):
m = max(AS)
count = 0
ret = None
for k in range(2, m + 1):
v = sum(1 for a in AS if a % k == 0)
if v > count:
ret = k
count = v
return ret
- 場合わけ
- 桁数が1桁の時
- 0文字消せる
- 既に3の倍数の時0
- それ以外は達成不能-1
- 桁数が2桁以上の場合
- 1文字消せる
- 全体のあまりと同じあまりの桁が存在すれば1
- なければ-1
- 桁数が3桁以上の時
- 2文字以上消せる
- 1文字では消せないことがわかっている
- あまり1が2枚以上か、あまり2が2枚以上あるなら、あまり0にできる
- 桁数が1桁の時
- ちょっと自信がないが投げる
- ケアレスミスで2WAした python
def solve(N):
total = sum(N) % 3
if total == 0:
return 0
if len(N) == 1:
return -1
from collections import Counter
xs = Counter(x % 3 for x in N)
if xs[total]:
return 1
if len(N) == 2:
return -1
if xs[1] > 1 or xs[2] > 1:
return 2
return -1
-
「なぜ探索ではなく場合わけをしたのか」って話、僕に関しては問題を見た時点でこういう図が脳裏に浮かんで高々2回で済むのが見えてるから探索ではなく場合わけで書き下そうという気持ちになる
-
公式解説
- 2枚消す場合に、全体の余りが1だとすると「1枚消す」で処理されてないことから1がないことはわかっていて、2が1枚だけではあまり1にならないから2枚以上確実にある D - Wandering
-
累積和を2つ重ねれば良い、と実装し始める
-
移動途中に一時的に大きくなるのも最大値の更新に含めるのだということにサンプルが通らなくて気づく
-
移動中に最も大きくなる量がいくらかを別途持つことにした python
def solve(N, AS):
pos = 0
dpos = 0
maxdpos = 0
ret = 0
for a in AS:
dpos += a
if dpos > maxdpos:
maxdpos = dpos
if pos + maxdpos > ret:
ret = pos + maxdpos
pos += dpos
return ret
- 考えたこと
- ランプが5×10
- マップは225万
- 4方向に塗り広げるのが素直
- O(HW)だが、間に合わないのか？間に合いそうだが。
- 追記: 「右方向に進む光」がどこまで塗るかは各マスについて左のマスに「右方向の光」が来てるかどうかさえ知ればOKなのでO(WH)でできて、それを4回やるだけ。
- 素直に実装してみる
- RE
- マップを少し広げたらREが減ってWAが増えた、その辺のバグっぽい
- ランプの位置を配列に書き込む時に縦横逆に入れていた→修正 python
def solve(H, W, mapdata):
maph = mapdata[:]
for y in range(H):
ypos = y * W
for x in range(1, W):
pos = ypos + x
if maph[pos] == 0 and maph[pos - 1] == 1:
maph[pos] = 1
for x in range(W - 2, -1, -1):
pos = ypos + x
if maph[pos] == 0 and maph[pos + 1] == 1:
maph[pos] = 1
mapv = mapdata[:]
for x in range(W):
for y in range(1, H):
pos = y * W + x
if mapv[pos] == 0 and mapv[pos - W] == 1:
mapv[pos] = 1
for y in range(H - 2, -1, -1):
pos = y * W + x
if mapv[pos] == 0 and mapv[pos + W] == 1:
mapv[pos] = 1
ret = 0
for i in range(W * H):
if maph[i] == 1 or mapv[i] == 1:
ret += 1
return ret
- 公式解説
- 無意識だったけどこれXとYにわけるパターンだったな
- 考えたこと
- 追記: この段落の考えは最終的にWA
- まず最適な払い方を求める
- 各コインが何枚で繰り上がるのかも計算しておく
- 上から順に「1枚増やしても繰り上がらないなら1枚増やす」
- 繰り上がる時はその上の桁を増やしたものと区別がつかないので数えない
- ある桁が1増えると、そこ以降の桁は0になれる
- 0は飛び地にはならないことと、既に0のものは場合の数を増やさないことに注意して数え上げる
- 追記: この段落の考えは最終的にWA
- 何が間違っていたか
- 例えば1,2,4,8で5を払うケースで、このアルゴリズムは4を返すが8と2を出して4と1を受け取るのはvalid
- 僕本人もそれが正しいと思い込んでいた
- 1 10 100 1000 10000で101を払うケース、テストケースに7と書いていたが本当は9
