ABC196 参加記録 - Xenous の精進記録

3完2ペナ 25分でした

A - Difference Max

与えられた $a, b$ と $c, d$ の範囲で $x-y$ を計算する全探索を行って、その最大値が答えです。

B - Round Down

文字列で入力を受け取ります。 python の場合, string.find('.') で、小数点が含まれていればその位置を、含まれていないなら -1 が返るので、その値を使えば元の数字を簡単に切り取ることができます。

C - Doubled

読み違えて、134431 のように回文になる必要があると思い込んでしまい、2WA。

$N$ が $10^{12}$ までありますが、偶数桁の制限があるので、片側の $1$ 〜 $999999$ を全探索します。片側を作り、もう一回繰り返した数字が $N$ 以下かどうかチェックすれば OK です。

D - Hanjo

探索の仕方が明確にならず、実装に落とせませんでした。 10分ほど考えてスキップし、コンテスト中解くことができませんでした。

コンテスト時の考察では1通りを見つけて回転させるなどすることを考えていましたが、ややこしいですね。なるべくシンプルに考えられるようになりたいものです。

敷き詰める畳は3種類、 $1\times1$ 、 $2\times1$ 、 $1\times2$ です。これらをDFSを使って実際に敷き詰めていくことで、何通りかを求めることができます。

具体的には、次のようなDFSを行います。

入力
今の座標 $h, w$ を受け取ります

処理
$h, w$ がすでに畳のときは次の $h, w+1$ にいきます。
( $w+1$ が外にはみ出る場合は $h+1, 0$ を渡します。)

そうでないときは、順に3種類の畳を敷き詰めます。
ポイントは、DFSが戻ってきたときに、畳を元に戻すことです。

畳を全て使い切ったときに答えのカウンターを増やします。

抜粋ですが、以下のような処理を3種類の畳全てに行います。同じような処理を複数書いているので全体のコードは若干見にくいですが、これでACできます。

# 1*1 を配置する
if B > 0:
    field[h][w] = '#'
    B -= 1
    # はみ出したら次の行に行く
    if w+1 == W:
        if h+1 == H:
            # カウントして何もしない
            ans += 1
        else:
            # 次の行
            dfs(h+1, 0)
    else:
        dfs(h, w+1)
    # 元に戻す
    field[h][w] = '.'
    B += 1

※ 追記関数の最初にはみ出た場合の処理を書いておけば、引数を渡すときにはみ出たまま渡すことができるのでスマートに書けます。

E - Filters

$\min(\max(x, a_1), a_2)$ と $\max(\min(x, a_1), a_2)$ の値を考えてみると、 $a_1, a_2$ の条件によって値が確定する場合があることがわかります。 $\min, \max$ だけであれば状況をまとめられそうだったのですが、加算処理の扱いがわからず本番では解けませんでした。

とっかかりは掴めていたので、あとは加算処理をうまく扱って対応します。

まず、 $\max(x, a)$ と $\min(x, a)$ の図を書いてみると、以下のようになります。

f:id:Xenous:20210416213905p:plain — max (左) と min (右) のグラフ

このグラフからわかる通り、 $\max(x, a)$ は最小値を $a$ にし、 $\min(x, a)$ は最大値を $a$ にします。では、 $\min(\max(x, a_2), a_1)$ などはどうなるんだという話ですが、次のように考えると、求めることができます。

$a_2 \lt a_1$ とすると、

$x \lt a_2$ のとき、 $\min(\max(x, a_2), a_1) = \min(a_2, a_1) = a_2$
$a_2 \leq x \leq a_1$ のとき、 $\min(\max(x, a_2), a_1) = \min(x, a_1) = x$
$a_1 \lt x$ のとき、 $\min(\max(x, a_2), a_1) = \min(x, a_1) = a_1$

$a_1 \leq a_2$ とすると、同じように場合分けして計算してみると、

$\min(\max(x, a_2), a_1) = a_1$

となります。図にすると以下のような二つの形にしかならないことがわかります。

f:id:Xenous:20210416222345p:plain — （左） $a_2 \lt a_1$ の場合と、 $a_1 \leq a_2$ の場合（右）

（左） $a_2 \lt a_1$ の場合と、 $a_1 \leq a_2$ の場合（右）

同様に考えてみると、 $\max(\min(x, a_2), a_1)$ もほぼ同じ挙動をすることがわかります。ゆえに、 $\min$ と $\max$ に関しては、最大の値と最小の値を更新していけばよく、更新の途中で定数関数になったら、それ以降ずっと定数関数になります。

次に加算処理は $y$ 軸方向の平行移動とみなせます。グラフを平行移動させてしまうと先程考えた式から変わってしまうので、今回はグラフを移動させるのではなく、次以降の比較対象 $a_{i+1}$ の値から $a_i$ を引いてしまいます。そして、実際に求めるのは、グラフを平行移動させた方なので、最後に引いた分を元に戻して答えにします。

f:id:Xenous:20210416224004p:plain — （左）グラフを平行移動させる場合と、次の $a_{i+1}$ を平行移動させる場合（右）

（左）グラフを平行移動させる場合と、次の $a_{i+1}$ を平行移動させる場合（右）

最終的なコードは以下になりました。

提出コード

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    # 最大値と最小値
    higha = float('inf'); lowa = -float('inf')
    # 加算処理用
    cost = 0
    # 定数関数になったら flag が True になる
    flag = False
    for _ in range(N):
        a, t = map(int, input().split())
        if t == 1:
            # 加算する処理
            cost += a
        elif t == 2:
            # 最小値側の更新
            lowa = max(a-cost, lowa)
            if lowa > higha or flag:
                higha = lowa
                flag = True
        else:
            # 最大値側の更新
            higha = min(a-cost, higha)
            if lowa > higha or flag:
                lowa = higha
                flag = True
    
    Q = int(input())
    X = list(map(int, input().split()))

    # 加算処理で引いた分を足して答えにする
    for x in X:
        if x < lowa: print(lowa + cost)
        elif lowa <= x <= higha: print(x + cost)
        else: print(higha + cost)


if __name__ == "__main__":
    main()