NetworkXでグラフを描いた(最短経路他)
研究室の方でNetworkXを教えて頂いたので、試しに色々弄ってみました。
最短経路(ダイクストラ)・経路復元と最長経路(トポロジカルソート+DP)で書いてます。
最短経路・経路復元
# -*- coding: utf-8 -*- # Verify(Time Limit Exceeded) # http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp import networkx as nx import matplotlib.pyplot as plt INF = 1000000 g = nx.Graph() # グラフオブジェクトの生成 # 標準入力から以下の形式で読み込む # |V| |E| # ai bi wi (辺ai->biのweightがwi) V,E = map(int,raw_input().split()) edges = [[] for i in range(V)] # 隣接リスト edge_labels = {} # 辺の描画用のラベル for i in xrange(E): (a,b,w) = map(int,raw_input().split()) g.add_edge(a,b,weight=w) edges[a].append({'to':b,'weight':w}) edges[b].append({'to':a,'weight':w}) edge_labels[(a,b)] = w # Dijkstra from A(0) distance = [INF] * V # Aからの距離 visited = [False] * V # 頂点が訪問済みかどうか distance[0] = 0 for i in range(V): min_v = -1 for v in range(V): # A(0)からの最短頂点を見つける (ヒープを使えば計算量を落とせる) if not visited[v] and (min_v == -1 or distance[v] < distance[min_v]): min_v = v # 訪問済みに visited[min_v] = True # 隣接してる頂点を更新 for e in edges[min_v]: distance[e['to']] = min(distance[min_v] + e['weight'],distance[e['to']]) # 表示 print 'distance from A(0)' for i in range(V): print '%2d: %d' % (i,distance[i]) # trace back from L(11) to A(0) now = 11 path = [11] while now != 0: for e in edges[now]: # labelを利用して経路復元 (頂点更新時に前の頂点を保存しておけば) if distance[now]-e['weight'] == distance[e['to']]: now = e['to'] path.append(now) break print 'trace back from L(11)' print path labels = {} # ノードの描画用のラベル s = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ") for i in range(V): labels[i] = s[i] # distance[i]に変更すれば,ラベルがAからの最短経路長になる # 適当に表示 pos = nx.spring_layout(g) nx.draw_networkx_nodes(g,pos,nodelist=g.nodes(),node_size=600) nx.draw_networkx_edges(g,pos,edgelist=g.edges()) nx.draw_networkx_labels(g,pos,labels,font_size=20) nx.draw_networkx_edge_labels(g, pos, edge_labels=edge_labels,font_size=12) nx.draw_networkx_edges(g,pos,edgelist=[(path[i],path[i+1]) for i in range(len(path)-1)],width=5,edge_color='b') nx.draw_networkx_nodes(g,pos,nodelist=path,node_size=600,node_color='b',alpha=0.8) plt.axis('off') plt.show()
最長経路
# -*- coding: utf-8 -*- import networkx as nx import matplotlib.pyplot as plt import Queue INF = 10000000 class Critical: def __init__(self,v,V,edges): self.v = v self.edges = edges self.tplist = [] # トポロジカルソート def topological_sort(self): visited = [False] * V tplist = [] for i in range(V): if not visited[i]: self.trace(i,visited) self.tplist.reverse() print self.tplist def trace(self,v,visited): visited[v] = True for e in edges[v]: if visited[ e['to'] ]: continue self.trace(e['to'],visited) self.tplist.append(v) # トポロジカル順序で動的計画法 def run(self,s): dp = [0] * V self.topological_sort() for v in self.tplist: for e in edges[v]: dp[e['to']] = max(dp[v]+e['weight'], dp[e['to']]) print dp return dp # Dijkstraっぽく最長ノードを使っていくのは駄目 def run2(self,s): dp = [INF] * V visited = [False] * V q = Queue.PriorityQueue() q.put((0,s)) dp[s] = 0 while not q.empty(): d,v = q.get() visited[v] = True for e in edges[v]: if visited[e['to']] or dp[v]+e['weight'] > dp[e['to']]: continue dp[e['to']] = dp[v] + e['weight'] q.put((d-e['weight'],e['to'])) print dp return dp V,E = map(int,raw_input().split()) edges = [[] for i in range(V)] #隣接リスト edge_labels = {} # 辺の描画用のラベル g = nx.DiGraph() #有向グラフの生成 for i in xrange(E): (a,b,w) = map(int,raw_input().split()) g.add_edge(a,b,weight=w) edges[a].append({'to':b,'weight':w}) edge_labels[(a,b)] = w # critical path cr = Critical(0,V,edges) cr.run2(0) distance = cr.run(0) labels = {} # ノードの描画用のラベル s = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ") for i in range(V): labels[i] = s[i] #s[i] を distance[i]に変えれば,最長距離がノードのラベル # 適当に表示 pos = nx.spring_layout(g) nx.draw_networkx_nodes(g,pos,nodelist=g.nodes(),node_size=600) nx.draw_networkx_edges(g,pos,edgelist=g.edges()) nx.draw_networkx_edge_labels(g, pos, edge_labels=edge_labels,font_size=12) nx.draw_networkx_labels(g,pos,labels,font_size=20) plt.axis('off') plt.show()
上2つのコードでは、特に下のグラフ中でのAからLについて考えていて、A~Lに0~11を対応させています。
標準入力用ファイル
12 19 0 1 3 0 2 2 0 4 9 1 3 2 1 4 4 2 4 6 2 5 9 3 6 3 4 6 1 4 7 2 5 7 1 5 8 2 6 9 5 7 9 5 7 11 9 7 10 6 8 10 2 9 11 5 10 11 3
グラフを描画する時、適当な位置に頂点を配置してくれるのは嬉しいけど、やや面倒くさい(もっと良いやり方があるのかも)
頂点の配置のアルゴリズムもそのうち確認しておきたい。
Pythonでグラフ系のものを書くのは初めてだったので、勉強になりました。言語的に間違っているのか、書いたアルゴリズムが間違ってるのか特定できず、割りと時間がかかってしまった。
Indeedなう(オープンコンテストB)A~E
A - Counting on a Triangle
それぞれの段の重みの合計を計算しておく。OEISで検索すると、a(n) = n^2*(n+1)/2と出てきた。
A002411 - OEIS
http://indeednow-finalb-open.contest.atcoder.jp/submissions/376663
int main(void) { int A,B; cin >> A >> B; vector<ll> a(1000001); for(ll i=0;i<1000001;i++){ a[i] = i*i*(i+1)/2; } ll ans = 0; for(int i=A;i<=B;i++){ ans += a[i]; ans %= (ll)1e9+7; } cout << ans << endl; return 0; }
B - How are you?
全社員の出社時刻をソートしておく。ソート列の中から、退社時刻までにある要素数から出社時刻までにある要素数を引けば(二分探索で要素数を数える)自分がオフィスにいる時に何人入ってきたか分かる。
http://indeednow-finalb-open.contest.atcoder.jp/submissions/376891
int main(void) { int N; cin >> N; vector<int> s(N),t(N); vector<int> qs(N),qt(N); for(int i=0;i<N;i++){ int ss,tt; cin >> ss >> tt; s[i] = qs[i] = ss; t[i] = qt[i] = tt; } s.push_back(0); sort(s.begin(),s.end()); for(int i=0;i<N;i++){ cout << (lower_bound(s.begin(),s.end(),qt[i]) - s.begin()) - (lower_bound(s.begin(),s.end(),qs[i]) - s.begin()) - 1 << endl; } return 0; }
C - Palindrome Concatenation
解説スライドと一緒で、部分文字列の回文の前処理はそれぞれの文字の中心から左右に広げる+DP。
https://indeednow-finalb-open.contest.atcoder.jp/submissions/378026
int main(void) { int n;string s; cin >> n >> s; vector<ll> c(n); for(int i=0;i<n;i++){ cin >> c[i]; } vector<vector<bool>> palin(5001,vector<bool>(5001)); for(int i=0;i<n;i++){ int d = 0; //部分文字列の長さが奇数 while(i-d>=0 && i+d<n && s[i-d] == s[i+d]){ palin[i-d][i+d] = true; d++; } //部分文字列の長さが偶数 int l = i-1,r = i; while(l >= 0 && r < n && s[l] == s[r]){ palin[l][r] = true; l--;r++; } } vector<ll> dp(s.size()+1,INF); dp[0] = c[0]; for(int i=1;i<s.size();i++){ dp[i] = min(dp[i] , dp[i-1] + c[0]); for(int j=0;j<i;j++){ if(palin[j][i]){ if(j==0)dp[i] = min(dp[i] , c[i-j]); else dp[i] = min(dp[i] , dp[j-1] + c[i-j]); } } } cout << dp[s.size()-1] << endl; return 0; }
D - Game on a Grid
最大全域木らしい。Kruskalの重みの大小関係を反転させた。
http://indeednow-finalb-open.contest.atcoder.jp/submissions/377939
int dx[] = {0,-1,0,1}; int dy[] = {-1,0,1,0}; struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool unite(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool same(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; struct edge{ int u,v; int cost; bool operator<(const edge& e)const{ return cost > e.cost; } }; class Kruskal{ public: UnionFind uf; vector<edge> es; int V; Kruskal(int V,vector<edge> es):uf(V),es(es){} int exec(){ sort(es.begin(),es.end()); ll res = 0; for(int i=0;i<es.size();i++){ edge e = es[i]; if(!uf.same(e.u,e.v)){ uf.unite(e.u,e.v); res += e.cost; } } return res; } }; int transgraph(int x,int y,int w){ return (y*w)+x; } int main(void) { int h,w; int sx,sy,gx,gy; cin >> h >> w; cin >> sx >> sy >> gx >> gy; vector<vector<int>> p(h,vector<int>(w)); ll sum = 0; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ cin >> p[i][j]; sum += p[i][j]; } } vector<edge> es(w*h+1); for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ for(int k=0;k<4;k++){ int nx = j + dx[k],ny = i + dy[k]; if(nx < 0 || ny < 0 || nx >= w || ny >= h)continue; int v = transgraph(j,i,w),nv = transgraph(nx,ny,w); int c = p[i][j]*p[ny][nx]; es.push_back(edge{v,nv,c}); } } } Kruskal kruskal(w*h+1,es); cout << kruskal.exec()+sum << endl; return 0; }
E - Line up!
座標圧縮し、身長を0~N-1に圧縮。圧縮後の配列サイズと元の配列サイズが同じではないと身長がユニークではないので-1を出力。
あとは、ARC31 C問題の解説のように各身長要素の移動回数を数えて(ARCのは左側と右側の小さい方だけど、これは左側だけ)、その身長との積を取った。
AtCoder Regular Contest 031 解説
http://indeednow-finalb-open.contest.atcoder.jp/submissions/377346
template <class T> struct BIT{ int N;vector<T>bit; BIT(int n):N(n),bit(n+1){} void add(T k,int i){i++;for(int x=i;x<=N;x+=x&-x)bit[x]+=k;} T sum(int i){i++;T r=0;for(int x=i;x>0;x-=x&-x)r+=bit[x];return r;} T sum(int l,int r){return l<=r ? sum(r)-sum(l-1):sum(r)+sum(l,N-1);} T get(int i){return sum(i) - sum(i-1);} void set(T k,int i){add(k-get(i),i);} }; int compress(vector<int>& X){ vector<int> x = X; sort(x.begin(),x.end()); x.erase(unique(x.begin(),x.end()),x.end()); for(int i=0;i<X.size();i++){ X[i] = lower_bound(x.begin(),x.end(),X[i]) - x.begin(); } return x.size(); } int main(void) { int n; cin >> n; vector<int> h(n),H; vector<int> id(n); for(int i=0;i<n;i++){ cin >> h[i]; } H = h; if(n != compress(h)){ cout << -1 << endl; return 0; } BIT<int> bit(n+1); for(int i=0;i<n;i++){ bit.set(1,i); id[h[i]] = i; } ll ans = 0; for(int i=0;i<n;i++){ ans += (ll)(bit.sum(0,id[i])-1) * H[id[i]]; bit.add(-1,id[i]); } cout << ans << endl; return 0; }
ABEで3完でした。楽しかった。
SRM654 Div2 Med / OneEntrance
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13698
真姫の新しい家に家具をN個設置したい。部屋の隣接関係と入り口の部屋の番号が与えられ、部屋の隣接関係は木構造をしている。N個の家具を順番に部屋に設置していくが、家具を設置した部屋はその後通行不可になる。全ての家具を設置できる方法が何通りあるか計算する。
解法
制約が小さいので全探索
class OneEntrance { public: vector<vector<int> > es; bool ok(vector<int>& ord,int s){ vector<bool>used(ord.size()); for(int i=0;i<ord.size();i++){ if(!dfs(s,-1,ord[i],used))return false; } return true; } bool dfs(int v,int p,int g,vector<bool>& used){ if(used[v])return false; if(v == g){ used[v] = true; return true; } bool ret = false; for(int i=0;i<es[v].size();i++){ if(es[v][i] == p)continue; ret |= dfs(es[v][i],v,g,used); } return ret; } int count(vector<int> a, vector<int> b, int s) { es.resize(a.size()+1); for(int i=0;i<a.size();i++){ es[a[i]].push_back(b[i]); es[b[i]].push_back(a[i]); } vector<int>ord(a.size()+1); for(int i=0;i<a.size()+1;i++){ ord[i] = i; } int cnt = 0; do{ if(ok(ord,s))cnt++; }while(next_permutation(ord.begin(),ord.end())); return cnt; } };
にこまき!
SRM654 Div2 Easy / SquareScoresDiv2
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13700
ある文字列の部分文字列の中で同じ文字が連続しているものをカウントする。
解法
全探索
class SquareScoresDiv2 { public: int getscore(string s) { int ret = 0; for(int i=0;i<s.size();i++){ for(int j=i;j<s.size();j++){ if(s[i] == s[j])ret++; else break; } } return ret; } };
SRM654 Div2 Hard / SuccessiveSubtraction2
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13699
配列aが与えられ、それはa[0]-a[1]-...-a[n]という式を表す。この式の中に括弧を2組まで入れた時式の結果の最大値答える。
解法
Editorial一部改変。 http://apps.topcoder.com/wiki/display/tc/SRM+654
const int INF = 1e9; int dp[2001][3][3]; class SuccessiveSubtraction2 { public: int n; vector<int> a; //何個目、括弧が開いているか、残りの括弧 int func(int p, int open, int remaining) { int& res = dp[p][open][remaining]; if (res == -INF) { if (p == n) { //終わり res = 0; } else { //open==0 括弧がない そのまま減算 int x = ((open % 2 == 0) ? -a[p] : a[p]); if (remaining > 0 && open == 0) { //括弧の残りが1個以上 && 開いた括弧がない → 開けられる res = max(res, x + func(p + 1, open + 1, remaining - 1)); } if (open > 0) { //括弧開いているので閉じられる res = max(res, func(p, open - 1, remaining)); } //何もしない res = max(res, x + func(p + 1, open, remaining)); } } return res; } vector<int> calc(vector<int> b, vector<int> p, vector<int> v) { n = b.size(); a = b; vector<int> ans(p.size()); for (int i = 0; i < p.size(); i++) { //初期化 for (int i = 0; i < 2001; i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { dp[i][j][k] = -INF; } } } //更新 a[p[i]] = v[i]; //1つ目(0-indexed)、閉じている、残り2回 //最初のはどうやっても加算固定 ans[i] = a[0] + func(1, 0, 2); } return ans; } }; <||
yukicoder No.60 魔法少女
感想
二次元imos法で各座標に加わるダメージを計算する。
いもす法 - いもす研 (imos laboratory)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9; const int MOD = 1e9+7; int main(void) { int N,K; cin >> N >> K; vector<vector<ll>> enemys(1510,vector<ll>(1510)); vector<vector<ll>> area(1510,vector<ll>(1510)); const int GETA = 500; for(int i=0;i<N;i++){ int x,y,hp;cin >> x >> y >> hp; enemys[y+GETA][x+GETA] += hp; } for(int i=0;i<K;i++){ int x,y,w,h,d;cin >> x >> y >> w >> h >> d; y += GETA; x += GETA; area[y][x] += d; area[y+h+1][x+w+1] += d; area[y+h+1][x] -= d; area[y][x+w+1] -= d; } for(int i=0;i<1510;i++){ for(int j=0;j<1510-1;j++){ area[i][j+1] += area[i][j]; } } for(int i=0;i<1510;i++){ for(int j=0;j<1510-1;j++){ area[j+1][i] += area[j][i]; } } ll ret = 0; for(int i=0;i<1510;i++){ for(int j=0;j<1510;j++){ ret += max(0LL,enemys[i][j] - area[i][j]); } } cout << ret << endl; return 0; }
imos法好き。
AtCoder Beginner Contest #008 D- 金塊ゲーム
感想
AtCoder Beginner Contest 008 解説
解説スライドを見ながら解きました。
#include <bits/stdc++.h> using namespace std; int w,h; vector<int> x,y; map<tuple<int,int,int,int>,int> memo; int dfs(int l,int r,int u,int d){ int res = 0; //枠内に回収機があるか bool f = false; tuple<int,int,int,int> tp = make_tuple(l,r,u,d); if(memo.count(tp) != 0)return memo[tp]; for(int i=0;i<x.size();i++){ int ret = 0; //枠内に回収機がある if(l <= x[i] && x[i] <= r && u <= y[i] && y[i] <= d){ //回収機が枠の端以外にある時は、次の範囲を探索 if(x[i] != l){ if(y[i] != u) ret += dfs(l,x[i]-1,u,y[i]-1); if(y[i] != d) ret += dfs(l,x[i]-1,y[i]+1,d); } if(x[i] != r){ if(y[i] != u) ret += dfs(x[i]+1,r,u,y[i]-1); if(y[i] != d) ret += dfs(x[i]+1,r,y[i]+1,d); } f = true; } res = max(res,ret); } //枠内に1個も回収機がない if(!f)return 0; //回収機があれば、(幅+高さ-1)個の金塊が回収できる return memo[tp] = res + (r-l+1)+(d-u+1)-1; } int main(void) { cin >> w >> h; int n; cin >> n; x.resize(n);y.resize(n); for(int i=0;i<n;i++){ cin >> x[i] >> y[i]; } cout << dfs(1,w,1,h) << endl; return 0; }
当時は解説スライド見ても解けなかったし成長を僅かながら感じられた。