2015 IndeedなうB D Game on a Grid

これ
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)

ABC065 D Built?

これ
D - Built?
です。

最小全域木の問題です。Kruskal法で実装しました。
最小全域木をpythonで - kamojirobrothersのブログ
Kruskal法の記事です。

よくある考察のやつです。
気づきませんでした。

プログラムはこれ。

from heapq import *
def find(A,x) -> int:
    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

N = int( input())
X = [(0,0)]*N
Y = [(0,0)]*N
E = [(0,0)]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = (x,i)
    Y[i] = (y,i)
    E[i] = (x,y)
X.sort()
Y.sort()
H = []
heapify(H)
for i in range(N-1):
    x1, j1 = X[i]
    x2, j2 = X[i+1]
    y1, k1 = Y[i]
    y2, k2 = Y[i+1]
    heappush(H,(x2-x1, j1, j2))
    heappush(H, (y2-y1, k1, k2))
ans = 0
V = [ i for i in range(N)]
while H:
    w,s,t = heappop(H)
    if find(V,s) != find(V,t):
        union(V,s,t)
        ans += w
print(ans)

最小全域木をpythonで

最小全域木の勉強をしたので、まとめる。

これ
AtCoder 版!蟻本 (初級編) - Qiita
をやってて、最小全域木の項目があったのでやった。

やり方はwikipedia
全域木 - Wikipedia
を参考にした。

これのKruskal法とPrim法をやった。

Kruskal法

Kruskal法の理論

Kruskal法はだいたい次のような感じ(wikipediaに書いてある)。
ans = 0 とする。

0. Sを全ての辺を格納したものとする。

1. Sにある辺のうち、重みが最小のものを取り出す。

2. その辺の2つの頂点が繋がっていなければ、ans に重みを加算する。

3. 1 と 2 を繰り返す。

Kruskal法の実装

pythonでやると、

0 (1). Sに (辺の重さ, 頂点, 頂点) のようなタプル型を全て格納する。

0 (2). Sを小さい順にソートする。頂点の順番はどうでも良いので、そのままソートすると、辺の重さが小さいものが先頭に来る。
あるいは、優先度付きキューを用いても良い。例えば、python には heapq というモジュールがある。
(私はこちらを使っている。)

(1) と (2) に関しては heapq を使えば、まとめてできる。

1. リストなら、S[i] みたいにすればいいし、heapq なら heapq.heappop(S) とすればよい。

2. union-find を用いて、繋がっているか判断する。

3. 繋がっていなければ、ans に(辺の重さ)を加算し、辺の2つの頂点を union する。

Prim法

Prim法の理論

多分こんな感じ。相変わらず ans = 0 で始める。

0. 適当に一つ頂点を選び、それと隣接する頂点間にある辺の情報(辺の重さ, 頂点, 頂点)をSに入れる。
適当に選んだ頂点を  v_0 とする。

1. Sにある辺のうち、最も重さの小さいものを取り出す。

2. 取り出した辺の頂点2つが、 v_0 と繋がっているか判断する。

3. 繋がっていない場合は、 取り出した辺の重みを ans に加算し、 v_0 と繋がっていなかった頂点を繋げる。
さらに、繋がっていなかった頂点と隣接する辺の情報を S に追加する。

4. 2 と 3 を繰り返す。

Prim方の実装

0. Sとして、優先度付きキュー(heapq)を用いて、適当に選んだ頂点  v_0 と隣接する、辺の情報を heapq.heappush(S, (辺の重さ, 頂点, 頂点))する。

1. heappop(S)

2. 各頂点が初めの頂点と繋がっているか確認する。

3. 繋がっていない場合は、(辺の重さ)を ans に可算し、 v_0 と繋げて、隣接する辺の情報を heapq.heappush(S, (辺の重さ, 頂点, 頂点)) する。

ABC 107 / ARC 101 D Median of Medianを解いた。

ABC 107 / ARC 101 D Median of Median
D - Median of Medians
python(pypy)で解いた。

解説はこれ
https://img.atcoder.jp/arc101/editorial.pdf

ほとんど解説どおりだけど、勉強のため自分の言葉で解説する。

解説

x を長さ M の整数列 b の中央値とする。
すると、次の性質を満たす。

  • x 以上の b の元は \lceil \frac{M}{2} \rceil以上
  • x はこの性質を満たすものの中で最大

つまり、x = \max \{ y \in \mathbb{Z} | \sharp \{i | b_i \geq y\} \geq \lceil \frac{M}{2} \rceil\}となる。

ここで、\sharp \{i | b_i \geq y\} は y に関して、広義単調減少である。

従って、x は2分探索で求めることができる。

与えられた長さ N の整数列を A とする。

y を2分探索における基準値とする。(L+R)//2みたいなやつ。

 0 \leq l < r \leq Nに対して、 m_{l,r}A[l,r]の中央値とする。

すると、上記の性質から、y 以上の要素の個数が\lceil \frac{N(N-1)}{2\cdot 2} \rceil以上であるかにより、

2分探索すればよい。

A[l,r]のうち、x 以上の元を\lceil \frac{r-l}{2\cdot 2} \rceil個以上もつものが\lceil \frac{N(N-1)}{2\cdot 2} \rceil以上かを調べれば良い。

ここで、Aの元のうち x 以上のものを 1 に、x より小さいものを -1 に置き換えれば、

A[l,r] のうち、\sharp (\text{1 の個数}) \geq \sharp (\text{-1 の個数})となるものが\lceil \frac{N(N-1)}{2\cdot 2} \rceil以上かを調べれば良い。

個数の関係は和が 0 以上であることと同値なので、

A[l,r]のうち、sum(A[l:r])\geq 0となるものが\lceil \frac{N(N-1)}{2\cdot 2} \rceil以上かを調べれば良い。

 0 \leq i \leq Nに対して、S_i = \sum_{j = 1}^i A[i]とする。
ただし、S[0]=0とする。

以上をまとめると、

 \sharp \{(l,r) \in \{0, 1, \cdots, N\}^2 |\  l < r \text{ and } S_l \leq S_r\} \geq \lceil \frac{N(N-1)}{2\cdot 2} \rceilを調べれば良い。

これは、転倒数という名前らしい。

今回はBITを使って求めた。
次の文献を参考にした。

BITはこれ
http://hos.ac/slides/20140319_bit.pdf

転倒数BITはこれ
BITで転倒数を求める - Qiita

プログラムはこれ。

def add(B,a,n):#リストに値を追加する関数
    x = a
    while x <= n:
        B[x] += 1
        x += x&(-x)

def sums(B,a):#a番目までの和
    x = a
    S = 0
    while x != 0:
        S += B[x]
        x -= x&(-x)
    return S


def invnumber(n, S):# #{(i,j)| i<j and S[i]<=S[j]}
    B = [0]*(n*2 + 1)
    invs = 0
    for i in range(n):
        s = S[i] + n #BITで扱えるようにするために、nを加算した
        invs += sums(B, s) #i<j
        add(B, s, n*2)
    return invs

N = int( input())
A = list( map( int, input().split()))
R = max(A)+1
L = 0
c = (N*(N+1)//2 + 1)//2
while R - L > 1:
    M = (R+L)//2
    S = [0]*(N+1)
    for i in range(1,N+1):
        if A[i-1] >= M:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(N+1,S) >= c:
        L = M
    else:
        R = M
print(L)

ARC103/ABC111 D Robot Arms

これ
D - Robot Arms
を解いた。
解説はこれ
https://img.atcoder.jp/arc103/editorial.pdf
参考にしたのはこれ
AtCoder ARC 103 D - Robot Arms (600 点) - けんちょんの競プロ精進記録

2^0, 2^1, 2^2, \cdots, 2^nという長さのアームがあれば、各格子点のx座標とy座標の和が奇数であり、2^{n+1}-1以下の部分に色がついた、市松模様ができる。
いくつか実験すると、成り立つことが分かる。
あとは、マンハッタンマンハッタンした感じにすると、x軸とy軸を独立に処理できるので、なんとかなる。

というわけで、pythonでの実装はこれ。

def solution(x,y):
    ans = ''
    nowx, nowy = 0,0
    preX = [0]*31
    preY = [0]*31
    for i in range(31):
        if nowx < x:
            nowx += 2**(30-i)
            preX[i] = 1
        else:
            nowx -= 2**(30-i)
            preX[i] = -1
        if nowy < y:
            nowy += 2**(30-i)
            preY[i] = 1
        else:
            nowy -= 2**(30-i)
            preY[i] = -1
    for i in range(31):
        if preX[i] == -1 and preY[i] == -1:
            ans += 'L'
        elif preX[i] == 1 and preY[i] == 1:
            ans += 'R'
        elif preX[i] == -1 and preY[i] == 1:
            ans += 'D'
        else:
            ans += 'U'
    return ans
N = int( input())
X = [0]*N
Y = [0]*N
x, y = map( int, input().split())
X[0] = x
Y[0] = y
evod = (x+y)%2
Flag = True
for i in range(1,N):
    x, y = map( int, input().split())
    X[i] = x
    Y[i] = y
    if (x+y)%2 != evod:
        Flag = False

if Flag:
    D = [2**i for i in range(30,-1,-1)]
    if evod == 1:
        print(31)
        print(' '.join(map(str,D)))
        for i in range(N):
            print( solution(X[i]+Y[i],X[i]-Y[i]))
    else:
        print(32)
        D.append(1)
        print(' '.join(map(str,D)))
        for i in range(N):
            print( solution(X[i]+Y[i]-1,X[i]-1-Y[i]) + 'R')
else:
    print(-1)

pythonの「=」について

pythonの「=」がよくわからなかったが、教えてもらったり、先述の「苦しんで覚えるC言語」でメモリとかポインタとかを勉強してちょっと分かったので、まとめる。

pythonのインタラクションモードで次をやってみる。

a = 1
b = a
a = 2
a
b

すると、次のようになる。

2
1

これは当然。

で、次にリストの一部を変更してみる。

a = [1,2,3]
b = a
a[0] = 1000
a
b

すると、次のようになる。

[1000,2,3]
[1000,2,3]

私はここでaだけが更新できると思ったけど、bも更新された。
混乱した。
これは、C言語でいうと、配列は配列の先頭のメモリを指定しているものであるため、
pythonのリストは確保したメモリの先頭を指定している。
従って、同じメモリ領域を使っているため、aとbが等しくなってしまうのです。

ちなみに、メモリ領域を確保しなおせば良いので、次はうまくいく。

a = [1,2,3]
b = a
a = [1000,2,3]
a
b

で、こうなる。

[1000,2,3]
[1,2,3]

「苦しんで覚えるC言語」を読んだ。

「苦しんで覚えるC言語」を読んだ。
9cguide.appspot.com

筆者が私達の代わりに苦しんでくれている感じ。
読む上で苦しくなることはなく、行間0で読める本だった。
今までpythonしかプログラミング言語は知らなかったので、メモリやポインタなど新しい概念(基本的な概念)を知ることができた。
ポインタはポインタ変数の宣言とポインタの通常変数モードの切り替えが違っててややこしくて、混乱した。
基本情報技術者試験C言語の問題は感覚で乗り切ったので、これを読んだ後に改めて見ると、スッキリした。