僕はA,Bの問題に目を通した後、Cを紙コーディングしてました。
先輩がAをコーディングしているところを横目で見ていたんですが、バグりそうな実装だなぁと思いながらも黙々やってたら、結局バグってしまっていて一旦Aのソースを印刷して、Bをやっていた先輩とバトンタッチ。
Bは比較的すんなりACしてくれて、Aのバグの原因がまだ分かってないようだったので、先にPC借りて紙に書いておいたCを写してAC。
その後、Aも方針を変えて無事AC。
残りの時間はどれも難しいう～んってやってたら時間が終わりました。
Ω＼ζ°)ﾁｰﾝ

反省

行き当たりばったりで参加を決めた割には(先輩方のおかげで)チームとしてまとまったのではないかと思います。一応目標としていた3完ができたので初参加にしてはなかなか良かったです。
やっぱ先輩主導になっちゃったなぁって感じなので自分のその辺の能力の無さを感じました。
あと、ずっと熱っぽかったし体調管理をしっかりしようと思いました（やっと治りそう）。

2015-06-06

Square Route

AOJ

問題

Square Route | Aizu Online Judge

感想

ACM/ICPC国内予選突破の手引き
で幾何と分類されているけど、幾何ではない気がする。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

bool solve(){
	int n,m;
	cin >> n >> m;
	if(n == 0 && m == 0)return false;
	vector<int> h(n+1),w(m+1);
	for(int i=1;i<=n;i++){
		cin >> h[i];
		h[i] += h[i-1];
	}
	for(int i=1;i<=m;i++){
		cin >> w[i];
		w[i] += w[i-1];
	}

	vector<int> hei(1500001);
	for(int i=0;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			hei[h[j]-h[i]]++;
		}
	}

	int cnt = 0;
	for(int i=0;i<=m;i++){
		for(int j=i+1;j<=m;j++){
			cnt += hei[w[j]-w[i]];
		}
	}
	cout << cnt << endl;
	return true;
}

int main(void){
	while(solve()){}
	return 0;
}

2015-06-06

Problem F Gather the Maps!

問題

Gather the Maps! | Aizu Online Judge

感想

誰が誰の地図を持っているかsetで持たせました。
とても遅いし、怪しいところあるけど通ればいいよね。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main(void){

	int n;
	while(cin >> n, n !=0){
		vector<vector<int>> ok(n,vector<int>(31));
		bool f = true;
		for(int i=0;i<n;i++){
			int m;cin >> m;
			for(int j=0;j<m;j++){
				int a;cin >> a;
				ok[i][a] = 1;
			}
		}


		vector<set<int>> st(n);
		for(int i=0;i<n;i++)
			st[i].insert(i);

		for(int i=0;i<31;i++){
			vector<int> vec;
			for(int j=0;j<n;j++){
				if(ok[j][i] == 1)vec.push_back(j);
			}

			for(int k=0;k<vec.size();k++){
				for(int j=k+1;j<vec.size();j++){
					st[vec[k]].insert(st[vec[j]].begin(),st[vec[j]].end());
					st[vec[j]].insert(st[vec[k]].begin(),st[vec[k]].end());
				}
			}

			for(int j=0;j<n;j++){
				if(st[j].size() == n){
					cout << i << endl;
					f = false;
					goto END;
				}
			}
		}
		END:
		if(f)cout << -1 << endl;
	}
	return 0;
}

ICPC登録フェイズがきちんと完了できるかがとてつもなく不安です。

2015-04-18

NetworkXでグラフを描いた（最短経路他）

雑記

研究室の方でNetworkXを教えて頂いたので、試しに色々弄ってみました。
最短経路(ダイクストラ)・経路復元と最長経路(トポロジカルソート+DP)で書いてます。
f:id:utsubo_21:20150418190100p:plain

最短経路・経路復元

# -*- 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を対応させています。
f:id:utsubo_21:20150418185331p:plain

標準入力用ファイル

グラフを描画する時、適当な位置に頂点を配置してくれるのは嬉しいけど、やや面倒くさい（もっと良いやり方があるのかも）
頂点の配置のアルゴリズムもそのうち確認しておきたい。

Pythonでグラフ系のものを書くのは初めてだったので、勉強になりました。言語的に間違っているのか、書いたアルゴリズムが間違ってるのか特定できず、割りと時間がかかってしまった。

2015-04-01

Indeedなう（オープンコンテストB）A~E

AtCoder

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完でした。楽しかった。

utsubo’s blog

競技プログラミングとか．

100問マラソン 1問目 SRM 666 Div2 Hard: CollectingTokens

問題

制約

解法

宝探しページを作った

ICPC国内予選 2015

参加まで

感想

反省