2021-03-28

ARC116 参加記録

1完13分でした。
B問題高速化できず。。 $O(N^{2})$ から落とすことができませんでした。

A - Odd vs Even

愚直に思いつくのは、各ケースでの整数 $N$ の約数を求め、個数を数え上げることですが、 $N \leq 10^{18}$ と大きく、列挙が間に合いません。
そこで、 $N$ の正の奇数の約数と正の偶数の約数に法則がないか試しにいくつか見てみると、次のようなことがわかります。

$N$ が奇数ならば、奇数の約数の方が多い
が偶数のとき、
- $N$ の約数で、偶数が $2$ だけならば、偶数と奇数の数は同じになる。
- 偶数が $2$ の他にもあるならば、偶数の方が多い

$N$ が奇数のときは、約数も奇数しか存在しません。
$N$ が偶数で、約数の中で偶数が $2$ だけの場合、 $N = (偶数) \times (奇数)$ の形に必ず分解できます。片方が偶数ならもう片方は奇数にならなければいけないので、偶数と奇数の数は同じになります。
$N$ が偶数で、複数の偶数の約数をもつ場合は、 $N = (偶数) \times (偶数)$ の形も作ることができるため、偶数が多くなります。

B - Products of Min-Max

$A$ の部分集合 $B$ の最大値と最小値を考えるにあたって、 $B$ は $A$ の要素の順番によらずとってこれるので、まずは $A$ をソートします。
最小値と最大値だけ考えれば良く、その間に入る値は使っても使わなくても良いことになります。

例として 2 3 5 6 8 という数列を考えてみます。
最小値を固定したとき、求める値は次のようになります。

最小値を 2 として最大値を動かすとき、間に入る値について含む/含まないの $2$ 通りが要素数分あるので、このとき、
$\min{(B)} \times \max{(B)}$ は $2 \times (2 + 3 \times 1 + 5 \times 2^{1} + 6 \times 2^{2} + 8 \times 2^{3})$ と書けます。

同じようにして

最小値 3: $3 \times (3 + 5 \times 1 + 6 \times 2^{1} + 8 \times 2^{2})$
最小値 5: $5 \times (5 + 6 \times 1 + 8 \times 2^{1})$
最小値 6: $6 \times (6 + 8 \times 1)$
最小値 8: $8 \times 8$

これを愚直に書くと正しい答えは出せますが、計算量が $O(N^{2})$ なので、TLE となります。最大値側の計算を高速に行う必要があります。

どうやるかですが、最小値を 8 側から動かしたとき、次の部分に注目します。

最小値 6: $8 \times 1$
最小値 5: $8 \times 2 + 6 = 2 \times 8 + 6$
最小値 3: $8 \times 2^{2} + 6 \times 2^{1} + 5 = 2 \times ( 2 \times 8 + 6) + 5$

後ろ側から漸化式で各値を求めることができます。 $f_n = 2 f_{n-1} + a_n$ という形です。
この形であれば、各最小値での計算を $O(1)$ で行うことができます。

N = int(input())
A = list(map(int, input().split()))
A.sort()

ans = A[-1]*A[-1]
ans %= MOD

# 後ろから作っていく
atmp = 0
for i in range(N-1, 0, -1):
    atmp = (2*atmp + A[i]) % MOD
    ans += (A[i-1]*atmp) % MOD
    ans += A[i-1] * A[i-1]
    ans %= MOD

print(ans)

C - Multiple Sequences

後日がんばります。。

D - I Wanna Win The Game

同じく後日ときます。。

2021-03-28

ABC197 参加記録

AtCoder コンテスト参加記録

4完0ペナ 45分でした
E 解けなかったのが惜しいですね。。

A - Rotate

3文字固定なので、入力で受け取った文字を求められた順で直接出力します。

S = input()
print(S[1]+S[2]+S[0])

B - Visibility

与えられた点から上下左右それぞれ外周か # にぶつかるまで何個 . があったか数えます。入力の際に # で囲ってしまっても良いですね。

H, W, X, Y = map(int, input().split())
X -= 1; Y -= 1
field = []
for _ in range(H):
    tmp = list(input())
    field.append(tmp)

ans = 1
for h, w in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
    i = h; j = w
    res = 0
    while True:
        if not (0 <= X+i < H and 0 <= Y+j < W):
            break
        if field[X+i][Y+j] != '.':
            break
        i += h
        j += w
        res += 1
    ans += res
print(ans)

C - ORXOR

1つ以上の空でない連続した区間に分ける方法を全探索します。分け方は、下の図のように、配列（黒マル）の要素を並べたときの間(矢印)のどこに仕切りを入れるか、と考えれば良いです。

f:id:Xenous:20210328091127p:plain — 区切り方の全探索

これは bit 全探索で可能です。python では標準ライブラリ itertools.combinations を使っても実装できます。具体的には、仕切りを $k$ 個選んだときの全ての場合を確かめて、 $k$ も $0$ から $N-1$ までループさせれば良いです。

from itertools import combinations

def bitOR(A:list) -> int:
    res = 0
    for a in A:
        res = res | a
    return res


def bitXOR(A:list) -> int:
    res = 0
    for a in A:
        res = res ^ a
    return res


def main():
    N = int(input())
    A = list(map(int, input().split()))
    ORmemo = [[-1] * (N+1) for _ in range(N+1)]
    ans = bitXOR(A)
    for k in range(N-1):
        for iters in combinations(range(1, N), k):
            res = []
            i = 0; rangeiters = list(iters) + [N]
            for j in rangeiters:
                if ORmemo[i][j] != -1:
                    res.append(ORmemo[i][j])
                else:
                    res.append(bitOR(A[i:j]))
                i = j
            ans = min(ans, bitXOR(res))
    print(ans)


if __name__ == "__main__":
    main()

一応、OR をとったときの値をメモ化しています。 $N$ が大きくないのでなくても大丈夫な気がします。

D - Opposite

正 $N$ 角形を構成する頂点は必ず円上にあります。与えられた2点から、その円の中心の座標が求まります。
$x_1, y_1$ は、円の中心から角度 $\theta$ だけ反時計回りに回転させたものと考えることができます。

原点を中心とした回転は回転行列を使えばすぐに求まります。以上より、円の中心の座標を使って原点に平行移動させ、原点周りの回転をして、元の位置に戻せば良いです。

N = int(input())
x0, y0 = map(int, input().split())
xN2, yN2 = map(int, input().split())
theta = 2*pi / N

# 中心を求める
midX, midY = (x0+xN2) / 2, (y0+yN2) / 2

# 原点に戻す
x, y = x0 - midX, y0 - midY

# 回転させる
tox, toy = x*cos(theta) - y*sin(theta), x*sin(theta) + y*cos(theta)

# 戻す
x1, y1 = tox + midX, toy + midY

print(x1, y1)

E - Traveler

本番で解けなかった問題です。
まず、取っていったときの色の番号が広義単調増加という制約があるので、色の番号が小さい方からみていくことになります。
また、結局は同じ番号のボールの最も左側と最も右側の位置だけわかっていれば良いです。同じ色のボールを回収するとき、間にあるボールをあえて取らないで取りに戻ることをしても、端からとったときと同じかそれ以上の移動が必要になってしまいます。

どのように調べるかですが、最初は距離が近い方を選んで探索することを考えていました。これだとサンプル3のように次の色が片側に寄っている場合を取りこぼす可能性があります。

結局のところ、どの色の番号を取得したときでもやることは同じで、次の2択になります。

同じ色のボールについて、左端から右端に向かって回収する
同じ色のボールについて、右端から左端に向かって回収する

直前で回収した色の右端か左端にいるので、もう少し具体的に書くと、次のような遷移になります。

$k$ 番目の色のボールを回収し右端にいて、 $k+1$ 番目の色のボールを左端から回収する。
$k$ 番目の色のボールを回収し右端にいて、 $k+1$ 番目の色のボールを右端から回収する。
$k$ 番目の色のボールを回収し左端にいて、 $k+1$ 番目の色のボールを左端から回収する。
$k$ 番目の色のボールを回収し左端にいて、 $k+1$ 番目の色のボールを右端から回収する。

この遷移を、色の番号が小さい方からDPで埋めていけば良いです。

N = int(input())
minX = dict(); maxX = dict()
colorset = set([])
for _ in range(N):
    X, C = map(int, input().split())
    if C not in minX: minX[C] = X
    else: minX[C] = min(minX[C], X)
    if C not in maxX: maxX[C] = X
    else: maxX[C] = max(maxX[C], X)
    colorset.add(C)
colorlist = list(colorset)
colorlist.sort()
M = len(colorlist)

# 初期化
DP = [[float('inf')] * 2 for _ in range(M + 1)]

# 初期条件
DP[0][0] = 0; DP[0][1] = 0

# 遷移
l0 = 0; r1 = 0
for i, c in enumerate(colorlist):
    # 右端から進んで左端に行くパターン
    DP[i+1][0] = min(DP[i][0] + abs(l0 - maxX[c]), DP[i][1] + abs(r1 - maxX[c])) + abs(maxX[c] - minX[c])
    # 左端から進んで右端に行くパターン
    DP[i+1][1] = min(DP[i][0] + abs(l0 - minX[c]), DP[i][1] + abs(r1 - minX[c])) + abs(minX[c] - maxX[c])
    l0 = minX[c]; r1 = maxX[c]

# 答え
ans = min(DP[M][0] + abs(l0), DP[M][1] + abs(r1))
print(ans)

2021-03-22

ARC115 参加記録

AtCoder コンテスト参加記録

3完0ペナ 67分でした。
体感的には B < C < A <<< D でした。

A - Two Choices

最初は $1 \leq M \leq 20$ の制約を見て、正解列を bit 全探索して固定させ、各生徒の正解数をチェックするのかと思いましたが、計算量が $O(2^{M}N)$ となり間に合いません。
他の解き方を考えようとしましたが何も思い浮かばなかったので 5分くらいで B問題へ。

戻ってきてから再度考え直して AC することができました。どのような回答状況だと正解数を同じにすることができるか？を考えます。
サンプル1でも提示されていますが、二人の回答状況が00と11、01と10、10と01、00と11 のときに正解をうまく選ぶことで正解数を同じにすることができます。
ここから、例えば 10101 と 00100 の正解数を同じにすることができるかを考えてみると、1問目と5問目は 11 と 00 で、2問目と4問目は同じ 00 であり、残りの3問目が1で共通なため、正解数を同じにすることができます。
サンプルベースでの考察ですが、このように 1 が含まれる数の偶奇が等しい場合に正解数を同じにできるので、あとは組み合わせの計算を行うことで答えを求めることができます。

B - Plus Matrix

行列の要素が $C _ {ij} = A_i + B_j$ で作られるので、列 $j$ を固定して適当な値 $b$ を決めると、 $A_i = C _ {ij} - b$ として各 $A_i$ を求めることができます。
$A_i, B_j$ は非負整数なので、 $B_j$ の中で最も小さな値を $0$ として計算し始めると問題なさそうです。
あとは求めた $A_i, B_j$ を使って、全ての $i, j$ で $C _ {ij} = A_i + B_j$ が成り立っていることを確かめて答えとしました。成り立たない場合は No を出します。

C - NColoring

$i$ が $j$ の約数ならば、 $A_i \neq A_j$ が成り立つように数列を構成します。またその数列に現れる値の最大値が最小になるように作ります。
$1$ から順に小さい値を振っていくことを考えます。例えば $N = 12$ の場合を考えてみると、 $1$ は $2$ 以上全ての整数の約数になっているので、

1 2 2 2 2 2 2 2 2 2 2 2

のような数列が作れます。 $2$ は、「 $4$ 以上の全ての2の倍数」の約数に(当然)なっているので、

1 2 2 3 2 3 2 3 2 3 2 3

となります。
同じ要領で続けていくと、以下のように数列が変化していきます。

1 2 2 3 2 3 3 3 2 3 2 3   # 3番目は2.   6, 9, 12 番目を 3 にする
1 2 2 3 2 3 3 4 3 3 3 4   # 4番目は3.   8, 12番目を 4 にする
1 2 2 3 2 3 3 4 3 3 3 4   # 5番目は2.   10番目を 3 にする
1 2 2 3 2 3 3 4 3 3 3 4   # 6番目は3.   12番目を 4 にする
:
:

このような方針で埋めていくと数列に現れる値の最大値が最小となるように作ることができます。
この作り方は、素因数分解を高速に行うエラトステネスの篩のアルゴリズムに似てるので、そちらも参考になるかと思います。

2021-03-20

ABC196 参加記録

AtCoder コンテスト参加記録

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()

Xenous の精進記録

AtCoder関連他、学習したことの記録です。

ARC116 参加記録

A - Odd vs Even

B - Products of Min-Max

C - Multiple Sequences

D - I Wanna Win The Game

ABC197 参加記録

A - Rotate

B - Visibility

C - ORXOR

D - Opposite

E - Traveler

ARC115 参加記録

A - Two Choices

B - Plus Matrix

C - NColoring

ABC196 参加記録

A - Difference Max

B - Round Down

C - Doubled

D - Hanjo

E - Filters