2015-09-06

100問マラソン 3問目 SRM 664 Div2 Hard: BearSortsDiv2

問題

配列に対しマージソートを適用する．
しかし，そのマージソートは大小比較部分が間違いがあり，数字の大小関係なしに，確率で大小を判定する．
seqという配列が入力として渡されるので，先のマージソートを適用した時，その配列が1,2,...,Nとなるような確率を求め，対数を取って答えよ

制約

1 <= N <= 40

解法

大小比較するごとに50%を選ばないといけないので，大小比較関数が呼び出されるごとに0.5ずつ掛けてlogを取った．

class BearSortsDiv2 {

	public:

	vector<vector<int> > ls;
	double ret;
	bool LESS(int a,int b){
		ret *= 0.5;
		if(ls[a][b] == 1){
			return true;
		}
		else return false;
	}
	double mergeSort(int left,int right,vector<int>& T){
		if(left+1 >= right)return 0;
		int mid = (left+right) / 2;
		mergeSort(left,mid,T);
		mergeSort(mid,right,T);

		int p1 = left,p2 = mid;
		vector<int> merged;
		while(p1 < mid or p2 < right){
			if(p1 == mid){
				merged.push_back(T[p2]);
				p2 += 1;
			}else if(p2 == right){
				merged.push_back(T[p1]);
				p1 += 1;
			}else{
				if(LESS(T[p1],T[p2])){
					merged.push_back(T[p1]);
					p1 += 1;
				}else{
					merged.push_back(T[p2]);
					p2 += 1;
				}
			}
		}
		for(int i=left;i<right;i++){
			T[i] = merged[i-left];
		}
	}

	double getProbability(vector<int> seq) {
		ls.resize(seq.size()+1);
		for(int i=0;i<=seq.size();i++)ls[i].resize(seq.size()+1);

		for(int i=0;i<seq.size();i++){
			for(int j=i+1;j<seq.size();j++){
				ls[seq[i]][seq[j]] = 1;
			}
		}

		ret = 1;
		vector<int> T(seq.size());
		for(int i=0;i<seq.size();i++)
			T[i] = i + 1;

		mergeSort(0,seq.size(),T);

		return log(ret);
	}
};

system test通しておらず．

2015-09-04

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

};

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

2015-09-04

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

topcoder 100問マラソン

問題

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

制約

頂点数 <= 50
L <= 100

解法

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

2015-08-06

宝探しページを作った

雑記

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

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

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

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

"thank_you_for_reading"

2015-06-30

ICPC国内予選 2015

雑記

参加まで

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

感想

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

utsubo’s blog

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