abc182

NISHIO Hirokazu [Translate]
ABC182
5問でした。Fは思いつくすべてのテストケースが通るのにサンプルの4だけ通らなくて何がおかしいのだろうと悩んでるうちにタイムアップ。

B - Almost GCD
単純にループして間に合うので素朴に書く
pythondef 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

C - To 3
場合わけ
桁数が1桁の時
0文字消せる
既に3の倍数の時0
それ以外は達成不能-1
桁数が2桁以上の場合
1文字消せる
全体のあまりと同じあまりの桁が存在すれば1
なければ-1
桁数が3桁以上の時
2文字以上消せる
1文字では消せないことがわかっている
あまり1が2枚以上か、あまり2が2枚以上あるなら、あまり0にできる
ちょっと自信がないが投げる
ケアレスミスで2WAした
pythondef 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つ重ねれば良い、と実装し始める
移動途中に一時的に大きくなるのも最大値の更新に含めるのだということにサンプルが通らなくて気づく
移動中に最も大きくなる量がいくらかを別途持つことにした
pythondef 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

E - Akari
考えたこと
ランプが5×10^5
マップは225万
4方向に塗り広げるのが素直
O(HW)だが、間に合わないのか？間に合いそうだが。
追記: 「右方向に進む光」がどこまで塗るかは各マスについて左のマスに「右方向の光」が来てるかどうかさえ知ればOKなのでO(WH)でできて、それを4回やるだけ。
素直に実装してみる
RE
マップを少し広げたらREが減ってWAが増えた、その辺のバグっぽい
ランプの位置を配列に書き込む時に縦横逆に入れていた→修正
pythondef 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にわけるパターンだったな

F - Valid payments
考えたこと
追記: この段落の考えは最終的にWA
まず最適な払い方を求める
各コインが何枚で繰り上がるのかも計算しておく
上から順に「1枚増やしても繰り上がらないなら1枚増やす」
繰り上がる時はその上の桁を増やしたものと区別がつかないので数えない
ある桁が1増えると、そこ以降の桁は0になれる
0は飛び地にはならないことと、既に0のものは場合の数を増やさないことに注意して数え上げる
何が間違っていたか
例えば1,2,4,8で5を払うケースで、このアルゴリズムは4を返すが8と2を出して4と1を受け取るのはvalid
僕本人もそれが正しいと思い込んでいた
1 10 100 1000 10000で101を払うケース、テストケースに7と書いていたが本当は9
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 5:17:17 PM[Edit]
Related Pages
