utsubo’s blog

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

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

SRM654 Div2 Med / OneEntrance

topcoder
問題

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

topcoder
問題

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

topcoder
問題

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 魔法少女

yukicoder
問題

No.60 魔法少女 - yukicoder

感想

二次元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
問題

D: 金塊ゲーム - AtCoder Beginner Contest #008 | AtCoder

感想

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

当時は解説スライド見ても解けなかったし成長を僅かながら感じられた。

yukicoder No.164 ちっちゃくないよ！！

yukicoder
問題

No.164 ちっちゃくないよ！！ - yukicoder

感想

それぞれ、(含まれている数字の最大値+1)進数で最小。
str.to_i(n)で文字列をn進数にできてruby凄い。

n = gets.to_i
a = []
for i in 1..n
	a.push(gets.to_s)
end

t = 0
dic = {}
for s in "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".chars
	dic[s] = t
	t += 1
end

ar = []
for i in 0..n-1
	ar.push(a[i].to_i(dic[a[i].chars.max]+1))
end
puts ar.min

C++で書くのは辛そうだったので、久々にRubyで書いたけど全く覚えてなくて結局辛かった。