ABC057 D問題を解いた。
AtCoder Beginner ContestのD問題を解いた。
問題はこれ
D - Maximum Average Sets。
解説はこれ
https://atcoder.jp/img/abc057/editorial.pdf。
今回は問題自体の話ではなく、Counterのfor文の挙動がバージョンによってかなり違うということ。
次のコードを実行してみる。
from collections import Counter V = list( map( int, input().split())) CV = Counter(V) for x in CV: print(x)
入力はこれ。
2 1 1 3 5 4 4 4
AtCoderで使われているpython3.4.3だと
1 2 3 4 5
ってなる。
python3.6.0以降だと、
2 1 3 5 4
ってなる。
つまり、pytho3.6.0より前だと、数字の小さい順に出てきて、python3.6.0以降だと、listに出ていた順ででてくる。
次のWandboxに同じコードで実験できるようにしている。
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ。
AtCoderで通らなかったコードは次。正しいはず。
from math import factorial from collections import Counter def combination(a,b): if a < b: a, b = b, a comb = 1 for i in range(b): comb *= a-i comb //= factorial(b) return comb N, A, B = map( int, input().split()) V = list( map( int, input().split())) V.sort( reverse = True) print( sum(V[:A])/A) CV = Counter(V) ans = 0 K = CV[ max(V)] if A <= K: for i in range(A, min(K, B)+1): ans += combination(K, i) else: cnt = A for x in CV: if cnt <= CV[x]: ans += combination(CV[x],cnt) break else: cnt -= CV[x] print(ans)
AtCoderで通るようにしたもの。Counterを使いたかった。
from math import factorial from collections import Counter def combination(a,b): if a < b: a, b = b, a comb = 1 for i in range(b): comb *= a-i comb //= factorial(b) return comb N, A, B = map( int, input().split()) V = list( map( int, input().split())) V.sort(reverse = True) print( sum(V[:A])/A) S = list( set(V)) S.sort(reverse = True) CV = Counter(V) ans = 0 K = CV[S[0]] if A <= K: for i in range(A, min(K, B)+1): ans += combination(K, i) else: cnt = A for x in S: if cnt <= CV[x]: ans += combination(CV[x],cnt) break else: cnt -= CV[x] print(ans)
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も然り。
コマンドを作る
自作のコマンドを作成した - 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))
ってやっててエラーが出続けていた。
