ARC036 D問題

AtCoder Regular ContestのD問題を解いた。
問題はこれ
D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder
解説はこれ
AtCoder Regular Contest 036 解説
書いてみたら、最後のテストケースだけREになって、なんでや!ってなって、調べた。
あった。
蟻本初級編攻略 - 2-4 Union Find木 後編 - Arantium Maestum
これによると、union-findで無限ループに陥ることがあるらしい。
この修正は、感覚的には、木treeの辺に向きがあると思って、その向きを数の大きい方が小さい方に揃えるイメージ。
そうすると、サイクルができない。

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):
##    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,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)

    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    A[y] = bx
    A[by] = bx

N, Q = map( int, input().split())
V = [ i for i in range(2*N)]
for _ in range(Q):
    w, x, y, z = map( int, input().split())
    x, y = x-1, y-1
    if w == 1:
        if z%2 == 0:
            union(V,x,y)
            union(V,x+N,y+N)
        else:
            union(V,x,y+N)
            union(V,y,x+N)
    else:
        if find(V,x) == find(V,y):
            print('YES')
        else:
            print('NO')

おまけ

##のsortedを使うより、if文で書いたほうが倍ぐらい速かった。
関数を呼び出さないほうが速いっぽい。
defも然り。

コマンドを作る

自作のコマンドを作成した
これを見ながらやった。

echo $PATH

で、コマンドを実行する際に参照するディレクトリがわかる。
ちなみに、多分

/etc/profile

に書いてある。
ちなみに、設定ファイルの読み込み方は
Linux - bash 設定ファイル(Debian 系)! - mk-mode BLOG
に書いてあった。

というわけで、bashで書いたファイルに適当に名前をつけて、上のディレクトリに置けば、その名前を打てば実行できるようになる。

AGC027 C 問題

pythonでやってる人が全然いない・・・。
トポロジカルソートよくわかんないけど、解けたから解説する。

AGC027のC問題

AtCoder Grand Contest 027のC問題です。
これ
C - ABland Yard

解説

公式の解説はこれ
https://img.atcoder.jp/agc027/editorial.pdf

’A'と’B'のうち、高々1種類しか隣接していない頂点を取り除いていく。

V = [ i for i in range(N)]

で頂点の個数を管理する。

Edges = [ set() for _ in range(N)]

で、各頂点に隣接する頂点を管理する。
同一の頂点を結ぶ辺は無視したいので、setで扱うことにする。

A = [ 0 for _ in range(N)]
B = [ 0 for _ in range(N)]

これで、各頂点に対し、隣接する'A'と'B'の個数を管理する。
ここで、同一の頂点を結ぶ辺は無視するものとする。
同一の頂点を結ぶ辺を無視するために今回はdefalutdictを用いた。便利。

’A'と’B'のうち、高々1種類しか隣接していない頂点を取り除いていくために、
まず、’A'と’B'のうち、高々1種類しか隣接していない頂点のsetをTとする。
そこから、BFSっぽいのかよくわからない、方法を使って、消していく。
これは公式の説明と同じで、高々1種類しか隣接していない頂点を帰納的に取り除いていく。
もし、全ての頂点が消えれば、目的のものは得られないことになり、解答は'No'になる。

'A'と’B'のうち、高々1種類しか隣接していない頂点がなくなるまでループを回す。
Tから1つ、頂点nを取り出して、それと隣接する頂点mと隣接するA'及び'B'の個数が1だけ減少する。
もし、頂点mが'A'と’B'のうち、高々1種類しか隣接していなければ、Tに追加する。

まとめると、次のプログラムになる。

from collections import defaultdict
N, M = map( int, input().split())
S = list( input())
E = [ list( map( int, input().split())) for _ in range(M)]
V = [ 1 for _ in range(N)]
Edges = [set() for _ in range(N)]
A = [0]*N
B = [0]*N
d = defaultdict(int)
for i in range(M):
    a, b = E[i]
    a, b = a-1, b-1
    a, b = min(a,b), max(a,b)
    Edges[a].add(b) #隣接する頂点をメモする
    Edges[b].add(a)
    if d[(a,b)] == 1:#(a,b)という辺を一度入力しれいれば、無視して次のループに進む。
        continue
    else:#一度目の入力をしたことをメモする。
        d[(a,b)] += 1
    if a == b:#ループ(同じ頂点を結ぶ辺)だと、このあとの方法だと、ダブルカウントしてしまうので、別扱い。
        if S[a] == 'A':
            A[a] += 1
        else:
            B[a] += 1
        continue
    if S[a] == 'A':
        A[b] += 1
    else:
        B[b] += 1
    if S[b] == 'B':
        B[a] += 1
    else:
        A[a] += 1
T = set()

for i in range(N):#'A'と’B'のうち、高々1種類しか隣接していない頂点をTに追加する。
    if A[i] == 0 or B[i] == 0:
        T.add(i)

while T:#'A'と’B'のうち、高々1種類しか隣接していない頂点がなくなるまでループを回す。
    n = T.pop()#一つ取り出す。
    V[n] = 0#'A'と’B'のうち、高々1種類しか隣接していない頂点なので、取り除く。
    for m in Edges[n]:#頂点nが消えると、それに隣接する頂点mに隣接する'A'及び'B'の個数が1だけ減少する。
        if V[m] == 1:
            if S[n] == 'A':
                A[m] -= 1
                if A[m] == 0:#隣接する頂点mに隣接する'A'及び'B'の個数が0になると、次に消える頂点になる。
                    T.add(m)
            else:
                B[m] -= 1
                if B[m] == 0:#隣接する頂点mに隣接する'A'及び'B'の個数が0になると、次に消える頂点になる。
                    T.add(m)
                
if sum(V) == 0:
    print('No')
else:
    print('Yes')
おまけ

オーダーはO(N+M)。

unionfindとdefalutdict

unionfindの勉強をしたので。
unionfindはグラフの頂点で互いに繋がっているかどうかを判断するのに便利です。
追加の仕方がややこしくて、まだ全然、体に馴染んでない。
unionfindのプログラムの肝は、繋がっている頂点に対しては、同じ値を返すという関数です。
今回は、findという名前で実装しています。

解いた問題はABC049のD問題。
D: 連結 / Connectivity - AtCoder Beginner Contest 049 | AtCoder
解説はこれ。ほとんど何も書いてない。
https://atcoder.jp/img/arc065/editorial.pdf

この問題をやってるときに、初め、Counterで数え上げを行おうと思っていた。
しかし、全然うまく行かなかった。もちろん、うまく実装してる人もいたが。
なぜうまく行かないか、というと、自分のプログラムでできるunion-find treeが必ずしも最適なものとは限らないからだった。
つまり、複数の再帰を必要とするため、Counterとの相性が良くなかった。

というわけで、defaultdictを用いて、実装した。
参考文献はこれ。
8.3. collections — コンテナデータ型 — Python 3.6.5 ドキュメント
Python defaultdict の使い方

pythonの公式ドキュメントは日本語なので神。

プログラムはこれ。

from collections import defaultdict
def find(x, A): #unionfind
    p = A[x]
    if p == x:#根になっていればよい
        return x
    a = find(p, A)#根はない場合は根に到達するまで再帰的にfindする。この1行で少し最適化される
    A[x] = a
    return a

N, K, L = map( int, input().split())
V = [ i for i in range(N)]#道路
W = [ i for i in range(N)]#鉄道
for _ in range(K):#道路
    p, q = map( int, input().split())
    p, q = p-1, q-1
    bp, bq = find(p,V), find(q,V)
    V[q] = bp#pの根bpにqとqの根bpをくっつける
    V[bq] = bp

for _ in range(L):#鉄道
    r, s = map( int, input().split())
    r, s = r-1, s-1
    br, bs = find(r,W), find(s,W)
    W[s] = br#rの根brにsとsの根bsをくっつける
    W[bs] = br

d = defaultdict(int) #デフォルトで0を返すdict。
for i in range(N):
    d[(find(i,V), find(i, W))] += 1
ANS = [0]*N

for i in range(N):
    ANS[i] = d[(find(i,V), find(i, W))]

print(' '.join( map( str, ANS)))
おまけ

unionfindは逐次的な操作との相性が良い。
というか、そうでない操作との相性が悪い。
例えば、defalutdictとの相性は良いが、Counterとの相性はよくない。

優先度付きキュー

優先度付きキュー(priority_queue)の勉強をしたので。
heap型を使えば良い。
heapはリストに比べて最小値の取り出しがはやく、新たな数の追加もはやい。
pythonにはheapqというmoduleがある。
heapqのheapには、基準となる数以外に別の数をtupleの形で持つことができる。
参考文献はこれ
8.5. heapq --- ヒープキューアルゴリズム — Python 3.7.0 ドキュメント
今回解いた問題はcode festival2017のC問題です。
問題はこれ
C: Factory - CODE THANKS FESTIVAL 2017(Parallel) | AtCoder
解説はこれ
https://img.atcoder.jp/code-thanks-festival-2017-open/editorial.pdf
解答はこれ。

import heapq
N, K = map( int, input().split())
H = [tuple( map( int, input().split())) for _ in range(N)]
ans = 0
heapq.heapify(H) #heap型にする
for _ in range(K):
    M = heapq.heappop(H) #最小のものを取り出す
    a, b = M[0], M[1]
    ans += a
    heapq.heappush(H,(a+b,b)) #加算したものをheapに追加する
print(ans)
おまけ

ずっと

    H = heapq.heappush(H,(a+b,b))

ってやっててエラーが出続けていた。

Binary indexed tree(BIT)をやった

これhttp://hos.ac/slides/20140319_bit.pdfを見ながら、これの基本問題をやった。
やり方はこれを見れば十分です。
問題設定はこちら。
N個の変数v_1, ..., v_n。
Q個のクエリ。
各クエリはv_a_jにw_jを加えるという操作。
answerは各クエリに対してv_1 + ... + v_aを求める。
クエリごとにどんどんv_1, ..., v_nは更新される。
入力は

N Q
v_1 v_2 … v_N
v_a_1 w_1
v_a_2 w_2
 ... 
v_a_Q w_Q

という形で与えられるとする。
次のようなプログラムになる。

#x-1となっているのは、リストが0番目からになっているから。
#x&(-x)で2進数で表した場合の最も下位にある1の位置を取り出すことができる。
#例えば,10 = 1010なら10を返し、7 = 111なら1を返す。
N, Q = map( int, input().split())
V = list( map( int, input().split()))
def add(A,a,w):#リストに値を追加する関数
    x = a
    while x <= N:
        A[x-1] += w
        x += x&(-x)

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

A = [0]*N
for i in range(1,N+1):
    add(A,i,V[i-1])
#for i in range(1,N+1): #確認用
#    print(suma(A,i))
for _ in range(Q):
    v, w = map( int, input().split())
    add(A,v,w)
    print(sums(A,v))

プログラムで気をつけることは、2進数で見たときの動きを意識すること。

2分探索

atcoderで2分探索に気づけないので、覚えるために、書き残しておく。
問題はABC063のD問題。
D - Widespread
解説はこれ。
https://atcoder.jp/img/arc075/editorial.pdf
大事なのは中のコメントのみ(##以下)。
ついでだけど、遅かったので、少し修正した。#以下は改善前。

N, A, B = map( int, input().split())
hmax = 0
H = [ int( input()) for _ in range(N)]
hmax = max(H)
L = 0
R = hmax//B + 1
add = A-B
#以下よりも早い
while R-L != 1:#L != R:
    now = (L+R)//2
    need = 0
    for i in range(N):
        r = H[i] - now*B
        if r > 0:
            need += (r-1)//add+1
    if need <= now:##うまくいくとき
        R = now
    else:##うまくいかないとき
        L = now#+1 ##うまく行かないので+1している.これがないと無限ループが発生する。
print(R)