ABC191

D苦手…WAが解決しない… 飛ばしてEはダイクストラでさっと解いて、残り30分 DをやるかFをやるかでFを考察する方が学びがありそうと判断し「いくつかの数のgcdであってmin以下のものの数」でサンプルは通ったがやっぱりTLE。この時点で残り13分なので残りはDをしてたけど最後まで解決せず4問

あー、そうか。Dは「10000倍して整数で扱おう…って二次関数の解を求めるところで平方根が出てくるじゃん…」となってたけど、そこを二分探索で求めるのか。数学的にはO(1)で解けるのでそれに無意識にこだわってしまったが、O(logR)でも間に合う、と。

Fは「いくつかの数のgcdであってmin以下のものの数」だと看破したのは正解であった。それを効率よく求める方法が思いつけるとよかった。

水色に落ちるかなと思ったが、意外と+3だった

なるほど、DとFがかなり難易度高いのか。

C - Digital Graffiti

塗られるマスの四隅の角について「なければ追加、既にあるなら取り除く」をやる
python

def main():
    H, W = map(int, input().split())
    world = OneDimensionMap(H, W, 0)
    for pos in world.allPosition():
        if world.mapdata[pos] == 35:
            start = pos
            break
    corner = set()
    visited = set()
    DIR4 = world.dir4()

    def visit(pos):
        visited.add(pos)
        x, y = divmod(pos, W)
        for xy in [(x, y), (x + 1, y), (x, y + 1), (x + 1, y + 1)]:
            if xy in corner:
                corner.remove(xy)
            else:
                corner.add(xy)
        for dir in DIR4:
            newpos = pos + dir
            if world.mapdata[newpos] == 35 and newpos not in visited:
                visit(newpos)

    visit(start)
    print(len(corner))

公式解説を見るともっとシンプルに書けることがわかる。
- なければ足して、あれば取る、というのは要するに「処理が行われた回数が奇数回か？」ということと同値
- それが知りたいだけなら、足し算の順序は入れ替えても同じなので隣接順に処理する必要はない
- これでAC python

def main():
    H, W = map(int, input().split())
    world = OneDimensionMap(H, W, 0)
    from collections import defaultdict
    cornerCount = defaultdict(int)
    for pos in world.allPosition():
        if world.mapdata[pos] == 35:
            for d in [0, 1, W, 1 + W]:
                cornerCount[pos + d] += 1

    print(sum(v % 2 for v in cornerCount.values()))

E - Come Back Quickly

自己辺や多重辺があることに注意が必要
多重辺は一番短いものだけ残しておく# (2)
- 辺 edges[i][j]で持ってるので多重辺を持つの面倒だったから
各点からダイクストラ法で他の点への距離を求める(dist) # (3)
edges[i][i]とdist[i][j] + dist[j][i] $(i \neq = j)$ の中で最小のものを見つければ良い
# (1)について
- 辺に重みのあるグラフは普段はdefaultdict(dict)で扱ってる
- のだけど、今回# (4)でアクセスする時に値が存在するかどうかチェックするのめんどいなと思った
- ので、値が存在しない時INFになるようにした
- 普段からこれでいいな python

def main():
    N, M = map(int, input().split())
    from collections import defaultdict
    INF = 9223372036854775807
    edges = defaultdict(lambda: defaultdict(lambda: INF))  # (1)
    for _i in range(M):
        frm, to, cost = map(int, input().split())
        # -1 for 1-origin vertexes
        edges[frm-1][to-1] = min(edges[frm-1][to-1], cost)  # (2)

    dist = []
    for start in range(N):
        dist.append(one_to_all(start, N, edges, INF=INF))  # (3)

    for i in range(N):
        x = INF
        for j in range(N):
            if j == i:
                x = min(x, edges[i][i])  # (4)
            else:
                x = min(x, dist[i][j] + dist[j][i])
        if x == INF:
            print(-1)
        else:
            print(x)

F - GCD or MIN

値はソートされていると考えて一般性を失わない
小さい例を考える
- 値が二つの時、A2がA1の倍数なら1通り、違うなら2通り
- リアルタイムのメモを見るとここからすぐ「A1より小さいgcd(Ai, Aj)の個数を調べれば良い」と結論してるけど、なんでそうなったんだっけ…
- gcdは取る順番によらないから引数は集合として考えてよくて、Aの部分集合のgcdがA1より小さくなった時にはそれを解にする手順が存在する
問題はこれをどうやって効率よく計算するかで、素朴な2^Nは当然無理なので悩ましい
- 4TLE python

def main():
    from math import gcd
    N = int(input())
    AS = list(map(int, input().split()))
    minA = min(AS)
    ALL = set(AS)
    NEW = set(AS)
    while NEW:
        next = set()
        for x in ALL:
            for y in NEW:
                next.add(gcd(x, y))
        ALL.update(NEW)
        NEW = next - ALL
    ret = 1
    for x in ALL:
        if x < minA:
            ret += 1

    print(ret)

公式解説
- $\exists (S \subset A) x = g cd (S) ⟺ g cd (y [x divides y]) = x$
- ある集合Sについて成り立つなら、そこにxの倍数を追加しても成り立つ
  - なのですべての部分集合をケアする必要はない
  - xの倍数であるものを全部含んだ集合だけを考えれば良い
- xがAのどの数の約数でもない場合、集合が空になるので考えなくて良い
  - なのでいずれかの数の約数であるxについて、それと1対1対応する集合のgcdを取れば良い
  - 約数個数は対数オーダーなのでAが10^9でも問題ない
- それでも3TLE
  - 約数の数が多いテストケースで落ちるようになる python

def main():
    from math import gcd
    from functools import reduce
    N = int(input())
    AS = list(map(int, input().split()))
    minA = min(AS)
    S = set(AS)
    divisors = set()
    for x in S:
        divisors.update(get_divisors(x))
    ret = 1
    for d in sorted(divisors):
        if d == minA:
            break
        targets = [x for x in S if x % d == 0]
        if reduce(gcd, targets) == d:
            ret += 1
    print(ret)

- 約数列挙のタイミングでgcdまで計算すればAC

python

def main():
    from math import gcd
    from collections import defaultdict
    N = int(input())
    AS = list(map(int, input().split()))
    minA = min(AS)
    S = set(AS)
    gcds = defaultdict(int)
    for x in S:
        for d in get_divisors(x):
            gcds[d] = gcd(gcds[d], x)

    ret = 1
    for d in sorted(gcds):
        if d == minA:
            break
        if gcds[d] == d:
            ret += 1
    print(ret)

- 前者がダメで後者ならOKなの、自明ではない気がする
- gcd
    - 前者$\sum_i \sum_x [x < \min(A)][x \text{ divides } A_i]$
    - 後者$\sum_i \sum_x [x \text{ divides } A_i]$
    - 前者の方が小さいよな…

考察
- 部分集合の個数は2^2000、それに対して値の範囲は10
- 定義域より値域が狭い関数
- こういう時に値域と定義域の交換をする
- Xを像とする元は複数個あり得るのだけど、その中から構成しやすいものを選べば良い
- Zのような像にならない元は、何に写しても良い
  - 元々の写像をf、反転した写像をgとするとき、ある元xがfの像に含まれるかどうかは $f (g (x)) = x$ でわかる
- これは通常の意味での逆写像ではない
  - 通常は $f (x) = y ⟺ g (y) = x$ であるような写像f,gを互いにもう片方の逆写像といい、全単射の時だけ存在する
  - 今回は与えられたfに対して $g (y) = x \Rightarrow f (x) = y$ が成り立てば良い、ゆるい逆写像
- 今回の問題に関しては、 $x = g cd (S)$ のゆるい逆関数が $S = {y ∣ y \in A, x divides y}$ であることに気付くのが問題変形の第一歩だった

D - Circle Lattice Points

実数に対する大小判定
まずは誤差を考えずに素朴に書いてみる
- 二次関数の解の公式
- これでサンプルは全部通る python

def main_simple():
    from math import floor, ceil, sqrt
    X, Y, R = map(float, input().split())

    ret = 0
    for y in range(floor(Y - R), ceil(Y + R) + 1):
        xcep = R ** 2 - (y - Y) ** 2
        a = 1
        b = -2 * X
        c = X ** 2 - xcep
        e = b * b - 4 * a * c
        if e < 0:
            continue
        s = sqrt(e)  # (1)
        r1 = (-b + s) / (2 * a)
        r2 = (-b - s) / (2 * a)
        ret += floor(r1) - ceil(r2) + 1

    print(ret)

さてこれの整数版を作ろう…と思ったが# (1)の平方根の計算が厄介
- コンテスト中は平方根を使ったままなんとかしようとしてダメだった
コンテスト後、これは二分探索で求めれば良いと気づいた
二分探索チェックリストを見ながらバグらせないように注意して書く
AC
- # (2) これは確実に円の外である必要がある。 # (4)も同じ
  - floor(fX - fR)だとちょうどピッタリ円周上になるケースがある
- # (3) 円の中心がちょうど整数である場合に、その頂点がダブルカウントされてしまわないように注意が必要 python

def main():
    from math import floor, ceil, sqrt
    fX, fY, fR = map(float, input().split())
    X, Y, R = [round(x * 10000) for x in [fX, fY, fR]]
    ret = 0

    def isIn(x, y):
        ret = (X - x * 10000) ** 2 + (Y - y * 10000) ** 2 <= R ** 2
        return ret

    for y in range(floor(fY - fR), ceil(fY + fR) + 1):
        # find start
        left = floor(fX - fR - 1)  # (2)
        init_right = right = floor(fX)
        if isIn(right, y):
            while left < right - 1:
                x = (left + right) // 2
                if isIn(x, y):
                    right = x
                else:
                    left = x
            ret += init_right - left

        # find end
        init_left = left = init_right + 1  # (3)
        right = ceil(fX + fR + 1)  # (4)
        if isIn(left, y):
            while left < right - 1:
                x = (left + right) // 2
                if isIn(x, y):
                    left = x
                else:
                    right = x
            ret += right - init_left

    print(ret)

🪴 Quartz 4.0

ABC191

Graph View

Backlinks