2018-11-02

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)

2018-11-02

最小全域木をpythonで

atcoder 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 する。

具体例

ABC065 D Built? - kamojirobrothersのブログ

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, (辺の重さ, 頂点, 頂点)) する。

具体例

2015 IndeedなうB D Game on a Grid - kamojirobrothersのブログ

2018-10-30

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

python プログラミング atcoder

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

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

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

解説

以下、 $\lceil x \rceil$ により、 $x$ 以上の最小の整数を表す。

$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。
Binary indexed tree(BIT)をやった - kamojirobrothersのブログ。

転倒数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)

2018-10-27

ARC103/ABC111 D Robot Arms

python プログラミング atcoder

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

2018-10-26

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]

2018-10-26

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

C言語書評

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

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

2018-10-26

ヘッダファイルを含めて実行する

shell プログラミング備忘録 C言語

忘れないように。
簡単のため、関数などを書いたソースファイル及びヘッダファイルを

source.c source.h

、この関数を使ったソースファイルを

main.c

とする。

これをコンパイルして、

main.exe

と名付ける。

次をやればよい。

gcc -o main.exe source.c main.c