コマンドを作る
自作のコマンドを作成した - Qiita
これを見ながらやった。
echo $PATH
で、コマンドを実行する際に参照するディレクトリがわかる。
ちなみに、多分
/etc/profile
に書いてある。
ちなみに、設定ファイルの読み込み方は
Linux - bash 設定ファイル（Debian 系）！ - mk-mode BLOG
に書いてあった。
というわけで、bashで書いたファイルに適当に名前をつけて、上のディレクトリに置けば、その名前を打てば実行できるようになる。
追記
bash の man に書いてる。
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進数で見たときの動きを意識すること。
２分探索
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)
