読者です 読者をやめる 読者になる 読者になる

utsubo’s blog

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

100問マラソン 2問目 SRM 665 Div2 Hard: LuckySum

100問マラソン topcoder
問題

LuckyNumberは全桁4,7で構成された数字のことを言う.LuckySumとはLuckyNumber2つの和である.
'?'または0-9で構成された文字列(note)が渡されるので,それに一致するような最小のLuckySumを求める.

制約

noteの文字数 <= 14

解法

下の桁から埋めるように全探索.写経.

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

class LuckySum {

public:
	string note;
	long long INF;
	long long solve(int n,int up,bool secondEnd) {
		if(n == -1){
			if(up == 0)return 0;
			return INF;
		}

		long long ret = INF;
		vector<int> sum;
		if(secondEnd){sum.push_back(4);sum.push_back(7);}
		else{sum.push_back(11);sum.push_back(14);sum.push_back(8);}

		for(int i=0;i<sum.size();i++){
			sum[i] += up;
			if( note[n] == '?' || (sum[i]%10+'0') == note[n]){
				ret = min(ret, solve(n-1,sum[i]/10,secondEnd) * 10 + (sum[i]-up));
				if(!secondEnd)
					ret = min(ret, solve(n-1,sum[i]/10,true) * 10 + (sum[i]-up));
			}
		}
		if(n == 0 and up > 0 and (note[0] == '1' or note[0] == '?'))
						ret = min(ret,solve(n-1,0,secondEnd) * 10 );

		return ret;
	}

	long long construct(string note) {
		this->note = note;
		INF = 1e17;
		long long res = solve(note.size()-1, 0,false);
		if(res == INF)return -1;
		return res;
	}

};

本番中は分岐を全部書こうとして無限に時間を使っていた.こういう書き方できるようになりたい.
これで間に合うのか微妙な気がしたけど間に合うらしい.

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

topcoder 100問マラソン

問題

木の頂点に得点が設定されており,木の上をL回移動できる時の最高得点を求める.
一度取った頂点の得点を,もう一度取ることはできない.

制約

頂点数 <= 50
L <= 100

解法

解けなかったので,Editorialの解法で書いた.
http://apps.topcoder.com/wiki/display/tc/SRM+666

宝探しページを作った

雑記

宝探しページを作りました。
宝探し!
ページのどこかに隠されている合言葉を探し出すというものです。CTFっぽいの。
(まだ、5つしか合言葉はないです。)


ほとんどPHP+MySQLで、
ユーザー管理部分は↓が大変参考になりました。
ユーザー管理をするWebサービスを作ろう (全19回) - プログラミングならドットインストール

Bootstrapでそれっぽいものを作りたいという気持ちの元やってたんですが
PHPとかセッション周りの方がメインになってしまった。

合言葉の隠し方はCTF for ビギナーズの時やったのを幾つか入れています。
たぶん、合言葉はこれから増えていくはずです。


"thank_you_for_reading"

ICPC国内予選 2015

雑記
参加まで

サークルのような活動をしていたのでそこにいた先輩2人とチームを組んで、コーチ・監督は研究室の先輩と先生にそれぞれお願いしました。
週1で練習会を開き、本番まで時間があまりなかったので、過去問を2014年〜順々にやっていってました。

感想

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

反省

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

Square Route

AOJ
感想

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;
}

Problem F Gather the Maps!

感想

誰が誰の地図を持っているか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登録フェイズがきちんと完了できるかがとてつもなく不安です。

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

標準入力用ファイル
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でグラフ系のものを書くのは初めてだったので、勉強になりました。言語的に間違っているのか、書いたアルゴリズムが間違ってるのか特定できず、割りと時間がかかってしまった。