2019-02-09

AGC011 B Colorful Creatures

AtCoder Grand Contest 011の B の Colorful Creatures を解いた。
解説と違ってたから、解説を書く。
２分探索を使って解いた。

問題はこれ
B - Colorful Creatures。
解説はこれ
https://img.atcoder.jp/agc011/editorial.pdf。

解説

全ての生き物の色が異なるので、大きさでソートすることで、
$A_1 \leq A_2 \leq \cdots$
としても一般性を失わない。

最終的に、 $i$ 番目の生き物の色になるには、
$\{A_j\}_{j \neq i}$ を小さい方から順番に吸収していくことができればよい。
つまり、次のような条件を考えれば良い。
$\{b_j\}_{i \leq j \leq n}$ を次のように定める。
$b_i = \sum_{j=1}^i A_i$ 、
$b_{j+1} = b_j + A_{j+1}$ 。
$b_i$ が上のように定まるのは、自分より小さい生き物は必ず吸収できるためです。
このとき、任意の $j \leq i$ に対して、
$A_{j+1} \leq b_j \times 2$
を満たせば良い。これが条件。

これを全ての $i$ に関してやればよいが、それでは $O(N^2)$ になってしまう。

ところで、この条件はある $i$ に関して成立すれば、それ以降の添字でも成立する。
これは、実際は $\{b_j\}$ が $i$ に依存しない数列だからです。

というわけで、２分探索を実行できます。

解答

解答では、 $\{b_j\}$ が $i$ に依存しないことを利用して少し短くしています。
別に、毎回計算しても間に合います。
というか、初めはこれで通しました。
コメントアウトに書いておきます。

from itertools import accumulate
N = int( input())
A = list( map( int, input().split()))
A.sort()
l = -1
r = N-1
B = list( accumulate(A))
while r - l > 1:
    m = (l+r)//2
    check = 1
    #now = sum(A[:m+1])
    for i in range(m+1,N):
        if A[i] <= B[i-1]*2:
            pass
        # if A[i] <= now*2:
        #     now += A[i]
        else:
            check = 0
            break
    if check == 1:
        r = m
    else:
        l = m
print(N-r)

おまけ

100msくらい変わる。

ちなみに、解説は $O(N)$ だけど、これは $O(N \log(N))$ です。

2019-01-31

ARC083/ABC074 D Restoring Road Network

atcoder python プログラミング

AtCoder Begginer Contest 083、AtCoder Regular Contest 074 D Restoring Road Network

よくわからなかったので、解説の解説をする。
他の人のコードを見ながら勉強した。
問題がこれ
D - Restoring Road Network。
解説がこれ
https://img.atcoder.jp/arc083/editorial.pdf。

解説

各 $i$ に対して、 $\{A_{i,j} \mid j \neq i\}$ の最小値の長さの辺は必ず存在する。
これで十分では？と思ったけど、そうじゃなさげ。
でも、その時点で最小の重みを持つ辺は確定しそうということが分かる。
それをやってみる。

$WF$ を $N \times N$ のリストで、対角成分が $0$ でそれ以外の全ての成分が $10^9+1$ とする。
ワーシャルフロイドをする。

$\{A_{i,j} \mid i, j\}$ を最小値から順番にとっていく。

その辺の重みを $a$ とし、辺を $(s, g)$ とする。
まず、それを加えるかどうか考えよう。
$d$ でグラフの距離を表すことにする。
全ての $s, g$ 以外の頂点 $i$ に対して、次の3パターンが考えられる。

1. 任意の $i$ に対して、 $WF_{s,i} + WF_{i,g} > a$ :
こういう辺を追加してもよい。
これが最適である。
まず、これより大きい辺との大小比較をする必要はない。
また、この辺の追加により、最短経路が更新される可能性はない。
このとき、 $WF_{s,g} = a = WF_{g,s}$ と更新する。
2. ある $i$ に対して、 $WF_{s,i} + WF_{i,g} = a$ :
同じ距離だから、こういう辺を追加する必要はない。
3. ある $i$ に対して、 $WF_{s,i} + WF_{i,g} < a$ :
このような、グラフは存在しない。

解答

import heapq
N = int( input())
A = [ list( map( int, input().split())) for _ in range(N)]
Q = []
for i in range(N-1):
    for j in range(i+1,N):
        heapq.heappush(Q, [A[i][j],i,j])
WF = [ [10**9+1]*N for _ in range(N)]
for i in range(N):
    WF[i][i] = 0
cnt = 0
while Q:
    a, s, g = heapq.heappop(Q)
    addcheck = 1
    for i in range(N): #新しく辺(s,g)を追加できるかどうかを判断する。
        #小さい辺から順番にチェックしているので、より大きい辺との大小比較の必要がない。
        #もう一つ、最短経路が更新される可能性があるが、それは今の辺より真に大きい辺のみなので、問題ない。
        if i == s or i == g:
            continue
        else:
            if WF[s][i] + WF[i][g] == a:
                addcheck = 0
            elif WF[s][i] + WF[i][g] < a:
                 break
    else:
        WF[s][g] = a
        WF[g][s] = a
        if addcheck:
            cnt += a
        continue
    print(-1)
    break
else:
    print( cnt)

2019-01-27

Speed keys (org-mode)

emacs org-mode 備忘録

org-mode に speed keys という機能があるらしい。

一般に、emacs のキーバインドは C とか M とかを用いたものです。

そのキーバインドが1文字になるっぽい。

というわけで、参考文献。

org-mode のキーバインド、その先 - Qiita

2018-12-19

行列の計算

python プログラミング備忘録

pythonで行列を高速に計算したい！

numpyを使うと良いのじゃ。

$X$ を $r$ 乗する。

import numpy as np
X = np.matrix([[....],...,[...]])
A = X**r

終わり。速い気がする。

np.array(X)
np.matrix(X)

で互いに行き来できる。

2018-12-19

pythonのsortについて

python atcoder プログラミング

$X$ をリストとすると、

X.sort()

でソートできる。

$X$ を2次元配列のリストとする。

上と同様にソートすると、第1成分がソートされたあと、第2成分がソートされる。

ところで、第2成分についてソートしたくなることがある。
そうするには、

X.sort(key = lambda x:x[1])

とすればよい。

しかし、この場合は第2成分だけをソートしており、第1成分は並べられていないどころがぐちゃぐちゃになっている。

というのも、この場合は第2成分のみに注目して、（おそらく）クイックソートを行っているためである。

クイックソートは不安定なのでぐちゃぐちゃになる。

2018-11-25

Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選 B - Sum AND Subarrays

python プログラミング atcoder

Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選 B - Sum AND Subarrays
B - Sum AND Subarrays
を解いた。
公式解説はこれ
https://img.atcoder.jp/dwacon5th-prelims/editorial.pdf。

bit演算系の問題は苦手だけど、初めてコンテスト中に解けた。
理解の整理のために解説を書くことにした。

解説

bit演算といえば、2進数表示の各桁ごとに見るのがよくある。
一般に、ピッタリの値を求めるよりも以上の値を確認するほうが"楽"らしい。
これを前提に考えると、 $2^n$ を考えるのが良さげに見えてくる。
特に、大きい桁から決めていけばいいことが分かる。
というのも、
$2^n > \sum_{k=1}^{n-1}2^k$
なので、上の桁を確定した後に、それ以下の桁で数の大きさが逆転されることがない。
例えば、

10000  01111

では、10000 の方が大きい。
というわけで、上の桁から決めていこう。
$N \leq 1000$ と $a_i \leq 10^9$ なので、部分列の和は高々 $10^{12}$ である。
ここで、
$\log_2(10^{12}) = 39.86313713864835 \cdots$
なので、 $2^{40}$ くらいまで考えれば良い。

次に、 $2^k$ 桁目を確定する方法を解説する。
非負整数 $x$ が与えられたとき、 $x$ の 2進数表示において、 $2^k$ が $1$ であることは、
$x \, mod \, 2^{k+1} \geq 2^k$
と同値です。
というわけで、 $K$ 個以上の部分列に対して、上記の条件が満たされることを確かめれば良い。
あとは、プログラムの中に説明をかく。

from itertools import accumulate
N, K = map( int, input().split())
A = list( map( int, input().split()))
accA = [0] + list( accumulate(A))
V = [1]*(N*(N+1)//2)
ans = 0
check = False
for i in range(40,-1,-1):
    W = [0]*(N*(N+1)//2)
    for l in range(N):
        for r in range(l+1,N+1):
            if V[l*(2*N+1-l)//2+r-l-1] == 0:#Vは現時点で採用されている部分列を示している
                #l*(2*N+1-l)//2+r-l-1はVの大きさに合わせて何番目を更新するか決定した。(時間節約のため)
                continue
            if (accA[r]-accA[l])%(2**(i+1)) >= 2**i:
                W[l*(2*N+1-l)//2+r-l-1] = 1
    if check == False:#初めに並ぶ 0 を無視するため
        if sum(W) >= K:
            check == True
        else:#無視して次のloopに遷移する
            continue
    if sum( V and W) >= K:#すでに確定している部分列と合わせて、K個以上あれば2**i桁目を採用する
        #V and W はlistの各成分のbool値の論理積を取っている
        ans += 2**i
        V = V and W
print(ans)

2018-11-02

2015 IndeedなうB D Game on a Grid

python atcoder プログラミング

これ
D: Game on a Grid - Indeedなう（オープンコンテストB） | AtCoder
です。

最小全域木の問題です。
Prim法で解きました。
Kruskal法の、やり方がわからなかった。
解説曰く、できるらしい。

Prim法の解説記事です。
最小全域木をpythonで - kamojirobrothersのブログ。

行列の向きが AtCoder のいつものやつと違って、混乱した。

プログラムはこれ。

from heapq import *
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

H, W = map( int, input().split())
sx, sy = map( int, input().split())
gx, gy = map( int, input().split())
P = [ list( map( int, input().split())) for _ in range(H)]
V = [ i for i in range(H*W)]
sx, sy = sx-1, sy-1
gx, gy = gx-1, gy-1
ans = P[sy][sx]
K = []
heapify(K)
if sx !=  max(sx-1,0):
    heappush(K, ( -P[sy][sx-1]*P[sy][sx] , sx-1, sy))
if sx != min(sx+1,W-1):
    heappush(K, ( -P[sy][sx+1]*P[sy][sx] , sx+1, sy))
if sy != max(sy-1, 0):
    heappush(K,  ( -P[sy-1][sx]*P[sy][sx], sx, sy-1))
if sy != min(sy+1,H-1):
    heappush(K,  ( -P[sy+1][sx]*P[sy][sx], sx, sy+1))
s = sx*H+sy
while K:
    p, x, y = heappop(K)
    if find(V, sx*H + sy) != find(V, x*H+y):
        union(V, sx*H + sy,  x*H+y)
        ans += P[y][x]
        ans += -p
        if x !=  max(x-1,0):
            if find(V, (x-1)*H+y) != find(V, s):
                heappush(K, ( -P[y][x-1]*P[y][x] , x-1, y))
        if x != min(x+1,W-1):
            if find(V, (x+1)*H + y) != find(V,s):
                heappush(K, ( -P[y][x+1]*P[y][x] , x+1, y))
        if y != max(y-1, 0):
            if find(V, x*H+y-1) != find( V, s):
                heappush(K,  ( -P[y-1][x]*P[y][x], x, y-1))
        if y != min(y+1,H-1):
            if find(V, x*H+y+1) != find(V,s):
                heappush(K,  ( -P[y+1][x]*P[y][x], x, y+1))
print(ans)