2019-09-09

Atcoder Beginner Contest ABC 140 E - Second Sum

問題

解法

これと同じ感じでやる。
atcoder.jp
ある数 $X$ が2番目に大きい区間 $I$ はどういう特徴があるか考える。
よく考えると $I$ は $X$ より大きい数をちょうど1つ含んでいる区間である事がわかる。
$X$ より大きく、かつ $X$ より右側にあるもののうち一番左側にあるものを $X_R$ 、その一つ右側の数を $X_{RR}$ とする。
同様に $X$ より大きく、かつ $X$ より左側にあるもののうち一番右側にあるものを $X_L$ 、その一つ左側の数を $X_{LL}$ とする。

$X$ が2番目に大きい区間は $X,X_L$ を両方含み $X_{LL},X_R$ を含まない区間、または $X,X_R$ を両方含み $X_{L},X_{RR}$ を含まない区間のどちらかとなる。

$X,X_L$ を両方含み $X_{LL},X_R$ を含まない区間は区間の左端が $(X_{LL},X_L$ ]、右端が $[X,X_R)$ であるような区間であることがわかる。
f:id:ykmaku:20190909205502p:plain
このような区間の数は $X_{LL},X_L,X,X_R$ の数列中での位置をそれぞれ $pos_{LL},pos_L,pos,pos_R$ とすれば $(pos_L-pos_LL)\times(pos_R-pos)$ 個ある。
$X,X_R$ を両方含み $X_{L},X_{RR}$ を含まない区間の数も同様に求められる。

あとは $X$ に対して $X_{LL},X_L,X_R,X_{RR}$ の位置を求められれば良い。
これは $X$ を $N\to1$ の順で見ていき、 $X_{LL},X_L,X_R,X_{RR}$ をの位置を求めたのち(これらはlower_boundで求めることができる)、multisetに $X$ の位置posを挿入すれば良い。

感想

multisetのイテレータを前から見るとmultiset内の要素を昇順に見れることを忘れていました...

#include <iostream>
#include <vector>
#include <set>


using namespace std;

typedef long long int ll;

#define rep(i,n) for(int i=0;i<(n);++i)


int main()
{
	int n;
	cin>>n;
	vector<ll> p(n),pos(n+1,0);
	rep(i,n){
		cin>>p[i];
		pos[p[i]] = i+1;
	}
	ll ans = 0;

	multiset<ll> s;
	s.insert(0);
	s.insert(0);
	s.insert(n+1);
	s.insert(n+1);
	for (ll now = n; now >= 1; now--){
		auto it = s.lower_bound(pos[now]);
		ll pos_r = *it;

		it++;
		ll pos_rr = *it;

		it--;
		it--;
		ll pos_l = *it;

		it--;
		ll pos_ll = *it;

		ans += now*(pos_r-pos[now])*(pos_l-pos_ll);
		ans += now*(pos_rr-pos_r)*(pos[now]-pos_l);

		s.insert(pos[now]);
	}
	cout<<ans<<endl;
	
	return 0;
}

2019-03-17

AGC 031 B - Reversi

このAGCは引越の疲れで参加できてなかった...

問題

atcoder.jp

解法

手で実験してみるとDPぽいな〜と思ったのでDPを考えます.
$dp[i] = a[0],\dots,a[i-1]$ に対する塗り方の個数
とします.
色が切り替わるときに注目します.
f:id:ykmaku:20190317021023p:plain
いま，j+1番目の石を見ているとしましょう.
さらにj+1番目の石の色と同じ色の石で，(j以下で)j+1に最も近いものの位置をiとします.
このとき，iとj+1番目の石を選んで操作を行ったときの色の塗り方は $a[0],\dots,a[i-1]$ の塗り方の個数なので $dp[i]$ です.
iとj+1番目の石に対して操作を行わなかったときの色の塗り方は $dp[j]$ です.
したがって $dp[j+1] = dp[i] + dp[j]$ であることが分かります.

各色に対して，１番右側にあるものの位置(またはそのdpの値)を記憶しておけば，j+1番目の石の色と同じ色の石で，(j以下で)j+1に最も近いものの位置(またはそのdpの値)は $O(1)$ で求められます.
結局，この問題は $O(N)$ で解けることになります.

#include <iostream>
#include <vector>

using namespace std;

typedef long long int ll;

const ll mod = 1e9+7;
const ll MAXN = 2*1e5+1;

int main()
{
	ll n;
	cin>>n;
	vector<ll> c(n);
	for(int i = 0; i < n; i++){
		cin>>c[i];
	}
	vector<ll> dp(MAXN,0);
	dp[c[0]]=1;
	for(int i = 1; i < n; i++){
		if(c[i]!=c[i-1]){
			dp[c[i]] = (dp[c[i]]+dp[c[i-1]]) % mod;
		}
	}

	cout << dp[c[n-1]] << endl;

	return 0;
}

2019-03-04

ABC 120 D - Decayed Bridges

Union-Find 順番を工夫する

問題

atcoder.jp

解法

連結無向グラフから枝を取り除いていったときに非連結な頂点のペアの個数を答える問題.

一般に，グラフから枝や頂点を取り除くという操作は難しいです.
逆に枝や頂点を追加するという操作は比較的かんたんです.

今回の場合，枝を後ろから順に見ていくことを考えます.
後ろから見るということは枝を追加していくということに対応します.
枝 $(x,y)$ が追加されるとき， $x$ と $y$ が同じ連結成分に含まれていないならば， $x$ $\left(y\right)$ を含む連結成分の頂点の個数を $size(x)$ ( $size(y)$ )とすれば，枝 $(x,y)$ 追加されたとき不便さは $size(x)\times size(y)$ だけ解消されます.

無向グラフの連結成分を扱うにはUnion-Findが便利です.

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;


struct union_find{
  vector<int> par,r,size;

  union_find(int n) : par(n),r(n),size(n){init(n);}

  void init(int n){
    for(int i = 0; i < n; i++) par[i] = i;
    for(int i = 0; i < n; i++) r[i] = 0;
    for(int i = 0; i < n; i++) size[i] = 1;
  }

  int find(int x){
    if(par[x] == x) return x;
    else return find(par[x]);
  }

  void unite(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(r[x] < r[y]){
      par[x] = y;
      size[y] += size[x];
    }else{
      par[y] = x;
      size[x] += size[y];
      if(r[x] == r[y]) r[x]++;
    }
  }

  bool same(int x,int y){
    return find(x) == find(y);
  }
};

int main()
{
	ll n,m;
	cin>>n>>m;
	vector<pair<int,int> > edge(m);
	for(int i = 0; i < m; i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		edge[i] = pair<int,int>(a,b);
	}

	reverse(all(edge));
	vector<ll> ans(m+1);
	ans[0] = (n-1)*n/2;
	union_find uf(n);
	ll cnt = 0;
	for(int i = 0; i < m; i++){
		int a = edge[i].first,b=edge[i].second;
		if(uf.same(a,b)) ans[i+1] = ans[i];
		else{
			cnt += uf.size[uf.find(a)]*uf.size[uf.find(b)];
			uf.unite(a,b);
			ans[i+1] = (n-1)*n/2-cnt;
		}
	}
	reverse(all(ans));
	for(int i = 1; i < ans.size(); i++){
		cout << ans[i] << endl;
	}

	return 0;
}

2019-02-19

AGC 008 C - Tetromino Tiling

よく観察する同一視場合分けをする個数を数える

問題

atcoder.jp

解法

まずT,S,Z型は使えません.
また，O型はそれ単体で横の長さが2の長方形になので必ず求めたい長方形に含めることができます.
結局I,J,L型の組み合わせを考えればいいです.

同じ型を２つ組み合わせることで横の長さが4の長方形ができます.(それぞれII型，JJ型，LL型と呼ぶことにします.)
これとは別にI,J,L型を１個ずつ使うと横の長さが6の長方形ができます.
この長方形をIJL型と呼ぶことにするとIJL型は高々1個だけ使うことにして良いです.
なぜならIJL型が2つあると横の長さの合計は12ですが，これはI,J,Lを2個ずつ使った場合の横の長さの合計に等しいので， IJL型2個はII型JJ型LL型の組1つ分と同一視できるからです.

以上から，IJL型を使うか使わないかで場合分けをして横の長さが大きい方を出力すれば良いです.

感想

そんなに難しくないはずなんだけど，J型とL型を組み合わせて長方形を作れると勘違いしたせいでWAを量産してしまった.
こういうアホなミスをなくしていきたい.

#include <iostream>


using namespace std;

typedef long long int ll;


int main()
{
	ll i,o,t,j,l,s,z;
	cin>>i>>o>>t>>j>>l>>s>>z;

	ll ans = 0;
	ans += 2*o;

	ll ijl = min(min(i,j),l);
	ll res = 0;
	if(ijl>0){ // ijlを１個使う
		res += 6 + ((i-1)/2)*4 + ((j-1)/2)*4 + ((l-1)/2)*4;
	}

	ans += max(res,(i/2)*4 + (j/2)*4 + (l/2)*4);
	cout << ans/2 << endl;

	return 0;
}

2019-02-14

ARC 089 D - Checker

累積和個数を数える

問題

atcoder.jp

解法

まず $(x,y)$ と $(x+2K,y),\ (x,y+2K)$ の色は一致するので入力の $x,y$ を $x \% 2K,y\%2k$ としていいです.

黒色の正方形の左下をどこにするかで平面の色の塗り方は決まります.
塗り方の周期性から黒色の正方形の左下の座標の候補は $[0,2K)\times[0,2K)$ としていいです.

したがって $4K^2$ 個の塗り方全てに対して叶えられる希望の個数を数えてそれのmaxを取れば良いです.
累積和を使うと1つの塗り方に対して叶えられる希望の個数を $O(1)$ の計算量時間で求めることができます.

感想

解説には全ての色をBにできると書いてあったが気が付かなかった...
累積和もパッと書けるようになりたい

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n,k;
	cin>>n>>k;
	int grid[2][4000][4000]={0};
	for(int i = 0; i < n; i++){
		int x,y;
		char c;
		cin>>x>>y>>c;
		x%=2*k;
		y%=2*k;
		if(c=='B'){
			grid[0][x][y]++;
			grid[0][x+2*k][y]++;
			grid[0][x][y+2*k]++;
			grid[0][x+2*k][y+2*k]++;
		}else{
			grid[1][x][y]++;
			grid[1][x+2*k][y]++;
			grid[1][x][y+2*k]++;
			grid[1][x+2*k][y+2*k]++;
		}
	}
	int sum[2][4000][4000]={0};
	for(int color = 0; color < 2; color++){
		for(int i = 0; i < 4*k; i++){
			for(int j = 0; j < 4*k; j++){
				sum[color][i][j] = (j==0?0:sum[color][i][j-1]) + grid[color][i][j];
			}
		}
		for(int i = 1; i < 4*k; i++){
			for(int j = 0; j < 4*k; j++){
				sum[color][i][j] += sum[color][i-1][j];
			}
		}
	}

	int ans = 0;
	for(int i = 0; i < 2*k; i++){
		for(int j = 0; j < 2*k; j++){
			int res = sum[0][i+k][j+k] - sum[0][i][j+k] - sum[0][i+k][j] + sum[0][i][j];
			res += sum[1][i+k][j+2*k] - sum[1][i][j+2*k] - sum[1][i+k][j+k] + sum[1][i][j+k];
			res += sum[1][i+2*k][j+k] - sum[1][i+2*k][j] - sum[1][i+k][j+k] + sum[1][i+k][j];
			res += sum[0][i+2*k][j+2*k] - sum[0][i+2*k][j+k] - sum[0][i+k][j+2*k] + sum[0][i+k][j+k];
			ans = max(ans,res);
		}
	}

	cout << ans << endl;

	return 0;
}

2019-02-06

ABC 002 D - 派閥

bit全探索グラフで考える

問題

atcoder.jp

解法

最大クリークを求める問題 (無向グラフGのクリークとはGの完全部分グラフ(の頂点集合)のこと).
頂点数が少ないので全ての部分グラフを見てあげることができる.
全列挙にはbitを使うのが便利.

#include <iostream>
#include <vector>
#include <set>


using namespace std;

typedef pair<int,int> P;


int main()
{
	int n,m;
	cin >> n >> m;
	vector<P> rel(m);
	for(int i = 0; i < m; i++){
		cin >> rel[i].first >> rel[i].second;
		rel[i].first--;
		rel[i].second--;
	}

	int ans = 1;
	for(int bit = 0; bit < (1<<n); bit++){
		set<int> S;
		for(int i = 0; i < n; i++){
			if(bit & (1<<i)) S.insert(i);
		}

		int edge = 0;
		for(int i = 0; i < m; i++){
			if(S.count(rel[i].first) && S.count(rel[i].second)) edge++;
		}
		if(edge == S.size()*(S.size()-1)/2) ans = max(ans,(int)S.size());
	}
	cout << ans << endl;

	return 0;
}

2018-12-26

ARC 087 E - Prefix-free Game

文字列 Grundy数 Trie木

問題

atcoder.jp

解法

根が空の文字列に対応していて、左の子には０を右の子には1を文字列に足したものを対応させる完全二分木を考えます。
そうすると良い文字列 $s\in S$ があったとき、この二分木上で $s$ の先祖子孫に対応する文字列は $S$ に追加することはできません。
つまり $S$ が与えられたとき、 $S$ に追加できるのは $S$ に含まれる各文字列の先祖子孫をすべて集めたもの以外となります。
このとき追加できる文字列たちは、二分木上ではいくつかの完全二分木に分かれています。
この小さな完全二分木の高さを $i$ としたとき、二分木のgrundy数は実験してみると $i$ を割り切る最大の2のべきとなることがわかります。
各grundy数の総xorが0ならAlice,そうでないならBobの勝ちです。
小さな完全二分木を見つけるには入力文字列から作られるTrie木を根から全探索すればいいです。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

struct trie{
	bool leaf;
	trie* node[2];
	trie(){
		leaf = false;
		for(int i = 0; i < 2; i++){
			node[i] = (trie*)0;
		}
	}

	void insert(const string &s){
		trie* r = this;
		for(int i = 0; i < s.length(); i++){
			int c = s[i]-'0';
			if(!r->node[c]) r->node[c] = new trie;
			r = r->node[c];
		}
		r->leaf = true;
	}
};

ll ans = 0;

ll grundy(ll x){
	if(x== 0) return 0;
	ll res = 1;
	while(x%(res*2)==0) res*=2;
	return res;
}

void solve(trie *t,ll d,ll l){
	if(t->leaf || d>=l) return;
	if((!t->node[0]&&t->node[1]) || (!t->node[1]&&t->node[0])){
		ans ^= grundy(l-d);
	}
	for(int i = 0; i < 2; i++){
		if(t->node[i]) solve(t->node[i],d+1,l);
	}
	return;
}

int main()
{
	ll n,l;
	cin >> n >> l;
	trie t;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		t.insert(s);
	}
	solve(&t,(ll)0,l);
	cout << (ans!=(ll)0?"Alice":"Bob") <<endl;

	return 0;
}

ykmakuのブログ

競技プログラミングをがんばるブログ

Atcoder Beginner Contest ABC 140 E - Second Sum

AGC 031 B - Reversi

ABC 120 D - Decayed Bridges

AGC 008 C - Tetromino Tiling

ARC 089 D - Checker

ABC 002 D - 派閥

ARC 087 E - Prefix-free Game