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