ABC191

NISHIO Hirokazu [Translate]
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

塗られるマスの四隅の角について「なければ追加、既にあるなら取り除く」をやる
pythondef 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
pythondef 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になるようにした
普段からこれでいいな
pythondef 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
pythondef 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 = \gcd(S) \iff \gcd(y[x\text{ divides }y] ) = x
ある集合Sについて成り立つなら、そこにxの倍数を追加しても成り立つ
なのですべての部分集合をケアする必要はない
xの倍数であるものを全部含んだ集合だけを考えれば良い
xがAのどの数の約数でもない場合、集合が空になるので考えなくて良い
なのでいずれかの数の約数であるxについて、それと1対1対応する集合のgcdを取れば良い
約数個数は対数オーダーなのでAが10^9でも問題ない
それでも3TLE
約数の数が多いテストケースで落ちるようになる
pythondef 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
pythondef 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^9
定義域より値域が狭い関数
こういう時に値域と定義域の交換をする
Xを像とする元は複数個あり得るのだけど、その中から構成しやすいものを選べば良い
Zのような像にならない元は、何に写しても良い
元々の写像をf、反転した写像をgとするとき、ある元xがfの像に含まれるかどうかは f(g(x)) = xでわかる
これは通常の意味での逆写像ではない
通常はf(x) = y \iff g(y) = xであるような写像f,gを互いにもう片方の逆写像といい、全単射の時だけ存在する
今回は与えられたfに対してg(y) = x \Rightarrow f(x) = yが成り立てば良い、ゆるい逆写像
今回の問題に関しては、x = \gcd(S) のゆるい逆関数が S = \{y|y\in A, x\text{ divides }y \}であることに気付くのが問題変形の第一歩だった




D - Circle Lattice Points
実数に対する大小判定
まずは誤差を考えずに素朴に書いてみる
二次関数の解の公式
これでサンプルは全部通る
pythondef 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)  円の中心がちょうど整数である場合に、その頂点がダブルカウントされてしまわないように注意が必要
pythondef 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)