2018-11-07

ABC 113 D - Number of Amidakuji

問題

beta.atcoder.jp

解放

DPを使いましょう。
dp[i][j] を上からicm目まで横棒を引いたとき左からj本目の縦棒に行くあみだくじの数とします。
こうするとdp[H][K]が答えになります。
最初は1本目の縦棒にいるのでdp[0][1] = 1です。
正しいあみだくじの条件から、上からi-1cm目のどこかから上からicm目、左からj本目の位置に行けるのは、上からi-1cm目でいた縦棒の位置が左からj-1, j, j+1本目だったときだけです。
f:id:ykmaku:20181107191149j:plain
つまりdp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]が分かればdp[i][j]を求めることができます。
(i-1,j-1)から(i,j)へ行くときのことを考えてみます。
このときi行目の横線の引き方をMとすると(i-1,j-1)から(i,j)への行き方はdp[i-1][j-1]×Mとなります。
横線の引き方ですが、まず次の3つの条件が成り立たないといけません。

j-1とjの間に横線がある。
j-1とj-2の間に横線はない。
jとj+1の間に横線はない。

この条件からあとは1〜j-2本目までの横線の引き方とj+1〜W本目の横線の引き方を求めればそれらをかけあわせたものがMになります。
そこで縦線がN本のときの横線の引き方の数f(N)を考えます。f(0)=f(1)=1なのは明らかです。f(N)は1本目と2本目の間に線を引いたときの残りの決め方と1本目と2本目の間に線を引かないときの残りの決め方の和になります。前者の場合、2本目と3本目の間に横線があってはいけないので、残りの決め方はf(N-2)通りです。後者の場合はf(N-1)通りです。つまりf(N)=f(N-1)+f(N-2)となりf(N)はフィボナッチ数列のN番目の項に等しくなることがわかります。
f:id:ykmaku:20181107194024j:plain
ということでM = f(j-2)*f(W-j-1)になります。

他の2つの場合も同様にして求めることでdp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]からdp[i][j]を求めることができます。

#include <iostream>

using namespace std;

typedef long long int ll;

const ll mod = 1e9+7;

int main()
{
	ll h,w,k;
	cin >> h >> w >> k;

	ll fib[10] = {0};
	fib[0] = 1;
	fib[1] = 1;
	for(int i = 2; i < 10; i++){
		fib[i] = fib[i-1]+fib[i-2];
	}

	ll dp[120][10] = {0};

	dp[0][1] = 1;
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(j>1){
				dp[i][j] += dp[i-1][j-1]*fib[j-2]*fib[w-j];
				dp[i][j] %= mod;
			}
			if(j<w){
				dp[i][j] += dp[i-1][j+1]*fib[j-1]*fib[w-j-1];
				dp[i][j] %= mod;
			}

			dp[i][j] += dp[i-1][j]*fib[j-1]*fib[w-j];
			dp[i][j] %= mod;
		}
	}

	cout << dp[h][k] << endl;

	return 0;
}

2018-10-21

ARC 088 D - Wide Flip

前から順に見る文字列

問題

beta.atcoder.jp

解法

前から順に見ていって...01...(または...10...)というように異なる文字に出会ったら"...0"か"1..."の長い方を反転すれば良い。反転したものの中で一番短いものが答えになる。

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

using namespace std;


int main()
{
	string s;
	cin >> s;
	int n = s.size();
	s = '.' + s;
	int ans = n;
	for(int i = 2; i <= n; i++){
		if(s[i] != s[i-1]){
			int x = max(i-1,n-i+1);
			ans = min(ans,x);
		}
	}
	cout << ans << endl;

	return 0;
}

2018-10-21

ARC 088 E - Papple Sort

文字列前から順に見る BIT

問題

beta.atcoder.jp

解法

回文は各アルファベットに対して左半分と右半分でそのアルファベットが出てくる回数が同じである。
以下の場合は回文にすることはできない。

Sにおいて奇数回現れる文字が2種類以上
Sにおいて奇数回現れる文字が1種類かつ|S|が偶数
Sにおいて奇数回現れる文字が0種類かつ|S|が奇数

以上のいずれの条件も満たさないときは以下のようにしてSから回文を作ることができる。
まずSの各文字が左半分か中央(|S|が奇数のときのみ)、右半分のどこに属するのかを決める。これは例えばSにaが5回出てくるなら1個めと2個めは左半分、3個めは中央、残りは右半分とすれば良い。(sample2なら"ataatmma"→"atamatma")
この操作を行ったあと、右半分を左半分の文字列を反転させたものと同じになるようにswapしていく。("atam atma"→"atam mata")

出来上がった回文の各文字がSのどこにあったのかを記憶しておけばバブルソートの交換回数を求める要領で必要な操作回数が求められる。
(sample2なら"ataatmma(12345678)" → "atammata(12367458)"なので12367458に対するバブルソートの交換回数を求めれば良い。)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef long long int ll;

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

struct BIT{
    ll N;
    vector<ll> bit;
    BIT(ll N) : bit(N+1),N(N){};

    ll sum(ll i){
        ll s = 0;
        while(i>0){
           s += bit[i];
           i -= i& -i;
        }
        return s;
    }

    void add(ll i,ll x){
        while(i <= N){
            bit[i] += x;
            i += i & -i;
        }
    }
};

//反転数を求める
ll inverse_number(vector<ll> z){
    ll n = z.size();
    ll inv_num = 0;

    BIT b(n);
    for(ll i = 0; i <= n; i++){
        b.bit[i] = 0;
    }

    for(ll i = 0; i < n; i++){
        inv_num += i - b.sum(z[i]);
        b.add(z[i],1);
    }

    return inv_num;
}

int main()
{
	string s;
	cin >> s;

	ll n = s.length();
	vector<vector<ll> > al_pos(26);  //initial position

	for(ll i = 0; i < n; i++){
		al_pos[s[i]-'a'].push_back(i);
	}

	ll odd_al = -1;
	for(ll i = 0; i < 26; i++){
		if(al_pos[i].size() % 2 != 0){
			if(odd_al >= 0){
				cout << -1 << endl;
				return 0;
			}else{
				odd_al = i;
			}
		}
	}

	if((odd_al>=0 && n%2==0) || (odd_al<0 && n%2!=0)){
		cout << -1 << endl;
		return 0;
	}

	ll al_now[26] = {0};

	string front,back,center;
	for(ll i = 0; i < n; i++){
		if(n%2!=0 && al_now[s[i]-'a'] == al_pos[odd_al].size()/2 && s[i]-'a' == odd_al){
			center.push_back(s[i]);
			al_now[s[i]-'a']++;
		}else if(al_now[s[i]-'a']+1<= al_pos[s[i]-'a'].size() / 2){
			front.push_back(s[i]);
			al_now[s[i]-'a']++;
		}else{
			back.push_back(s[i]);
			al_now[s[i]-'a']++;
		}
	}

	for(ll i = 0; i < 26; i++) al_now[i]=0;

	vector<ll> kaibun_index; //回文にしたあとのindex
	for(ll i = 0; i < front.length(); i++){
		kaibun_index.push_back(al_pos[front[i]-'a'][al_now[front[i]-'a']]);
		al_now[front[i]-'a']++;
	}
	for(ll i = 0; i < center.length(); i++){
		kaibun_index.push_back(al_pos[center[i]-'a'][al_now[center[i]-'a']]);
		al_now[center[i]-'a']++;
	}
	for(ll i = front.length()-1; i >= 0; i--){
		kaibun_index.push_back(al_pos[front[i]-'a'][al_now[front[i]-'a']]);
		al_now[front[i]-'a']++;
	}

	for(ll i = 0; i < n; i++) kaibun_index[i]++;

	cout << inverse_number(kaibun_index) << endl;

	return 0;
}

2018-10-18

AtCoder Grand Contest 003 C - BBuBBBlesort!

ソート競プロ

問題

beta.atcoder.jp

解法

$B = \{a_0,a_2,a_4,\dots\} ,\ C = \{a_1,a_3,a_5,\dots\}$ とすると操作2のみでソートしようとする場合、 $B,C$ それぞれの中でバブルソートをしていることになる。つまり操作1を行う必要があるのは $B$ の要素と $C$ の要素を入れ替えたいときだけである。
操作1を行う回数を求めるには $A$ をソートしたものを $A^{\prime}$ とすれば $A$ でのindexが奇数であって $A^{\prime}$ でのindexが偶数であるものの個数を求めれば良い。

#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()

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  vector<int> sorted = a;
  sort(all(sorted));

  set<int> even,odd;
  for(int i = 0; i < n; i++){
    if(i%2 == 0) even.insert(sorted[i]);
    else odd.insert(sorted[i]);
  }

  int ans = 0;
  for(int i = 0; i < n; i++){
    if(i % 2 != 0){
      if(even.count(a[i]) > 0) ans++;
    }
  }

  cout << ans << endl;

  return 0;
}

2018-10-01

ARC 103 E - Tr/ee

よく観察する例をつくってよく観察する前から順番に決める、決まる

問題

E - Tr/ee

解法

木という条件から、 $s_1 = 1, \ s_n = 0, \ s_i = s_{n-i}$ でないといけない事がわかります。
逆にこの条件が成り立っているとき条件を満たす木を構成できます。
まず $(1,2)$ という枝を用意します。 $now=2$ とします。 $s$ の2文字目から見ていき、 $i$ 番目の文字を見ているとき枝 $(now,i+1)$ を追加します。 $s_i=1$ なら $now=i+1$ とします。
イメージとしては作りたい木をイモムシだと思ったときに $s_i=1$ ならイモムシの体をのばして、そうでないなら体の先端に足をはやす、という感じでしょうか。（英語版解説にあるcaterpillarは毛虫という意味だそうです。）

感想

コンテスト中にこの問題を通せたので嬉しかった。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef pair<int,int> P;

int main()
{
  string s;
  cin >> s;
  int n = s.size();

  if(s[0] == '0' || s[n-1] == '1'){
    cout << -1 << endl;
    return 0;
  }

  s = s[n-1] + s;

  for(int i = 0; i <= n; i++){
    if(s[i] != s[n-i]){
      cout << -1 << endl;
      return 0;
    }
  }

  int now = 2;
  vector<P> ans;
  ans.push_back(P(1,2));
  for(int i = 2; i < n; i++){
    if(s[i] == '0'){
      ans.push_back(P(now,i+1));
    }else{
      ans.push_back(P(now,i+1));
      now = i+1;
    }
  }

  for(int i = 0; i < ans.size(); i++){
    cout << ans[i].first << " " << ans[i].second << endl;
  }

  return 0;
}

2018-09-30

ARC 103/ABC 111 C - /\/\/\/

個数を数える場合分けをする競プロ

問題

C - /\/\/\/

解法

偶数番目の要素からなる数列をeven、奇数番目の要素からなる数列をoddとすればそれぞれの数列での最頻値even_1、odd_1に書き換えれば良さそうなことに気がつく。しかし問題の制約からeven_1 ≠ odd_1でないといけない。そこで、それぞれの数列での2番目によく出現する値even_2、odd_2を取得する。
even中のeven_1,even_2の個数をe1,e2として、odd中のodd_1,odd_2の個数をo1,o2とすれば、even_1 ≠ odd_1のときはn/2-e1+n/2-o2とn/2-e2+n/2-o1のうち小さい方が最適値となる。

感想

もっと簡潔なコードを書きたい。

#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;
	cin >> n;
	vector<int> v(n);
	for(int i = 0; i < n; i++){
		cin >> v[i];
	}
	map<int,int> even,odd; //mapで各数列での要素の出現数を記録する
	for(int i = 0; i < n; i++){
		if(i%2==0) odd[v[i]]++;
		else even[v[i]]++;
	}

	int even_1=0,even_2=0,odd_1=0,odd_2=0;
	int e1=0,e2=0,o1=0,o2=0;
	int cnt = 0;
	for(auto itr = even.begin();  itr != even.end() ; ++itr){
		if(itr->second > cnt){
			cnt = itr->second;
			even_1 = itr->first;
		}
	}
	e1 = cnt;
	cnt = 0;
	for(auto itr = even.begin();  itr != even.end() ; ++itr){
		if(itr->second > cnt && itr->first != even_1){
			cnt = itr->second;
			even_2 = itr->first;
		}
	}
	e2 = cnt;

	cnt = 0;
	for(auto itr = odd.begin();  itr != odd.end() ; ++itr){
		if(itr->second > cnt){
			cnt = itr->second;
			odd_1 = itr->first;
		}
	}
	o1= cnt;
	cnt = 0;
	for(auto itr = odd.begin();  itr != odd.end() ; ++itr){
		if(itr->second > cnt && itr->first != odd_1){
			cnt = itr->second;
			odd_2 = itr->first;
		}
	}
	o2=cnt;

	if(even_1 == odd_1){
		cout << min(n-e1-o2, n-e2-o1) << endl;
	}else{
		cout << n-e1-o1 << endl;
	}

	return 0;
}

2018-09-15

AtCoder Grand Contest 025 B - RGB Coloring

よく観察する事前に計算する個数を数える全探索数式変形をする競プロ組合せ

問題

B - RGB Coloring

解法

緑色で塗られたマスは $A+B$ 点もらえることから、緑色のマス目は赤色と青色の両方が塗られたマス目だと思うことができる。赤色、青色、緑色に塗られたマス目の個数をそれぞれ $r,b,g$ とすると、このときの得点は $rA+bB+g(A+B) \ = \ (r+g)A + (b+g)B \ = xA + yB \ (ただし\ x = r+g,\ y = b+g)$ 点である。ここで $0 \le x,y \le N$ であることに注意する。得点が $K$ 点の塗り方の個数を数えればよいので、結局この問題は $\begin{align}\sum_{\substack{0\le x,y\le N\\Ax+By=K}}　{}_N C _x \times {}_N C _y \end{align}$ を求めれば良いことになる。 $x$ に対し $y$ は一意に決まるので $x$ に関して全探索すればこの問題は $O(N)$ の計算量時間で解ける。 ${}_N C _m\ (0\le m \le N)$ は事前に計算しておきます。

大きい $N$ に対して ${}_N C _x$ を求める方法は蟻本を見るかググってみてください。

#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 = 998244353;
const ll INF = 1e9;
const ll MAXN = 1e9;

vector<ll> fact,inv;

ll f(ll a,ll b, ll p)  // a^b mod pを求める
{
  if (b == 0)
  {
    return 1;
  }else if (b % 2 == 0)
  {
    ll d = f(a,(ll)b/2,p);  //a^b = a^(2k) = (a^k)^2  k = b / 2
    return d * d % mod;
  }else
  {
    return a * f(a,b-1,p) % mod;
  }
}

void init(ll n)
{
  fact.resize(n+1,(ll)1);
  inv.resize(n+1,(ll)1);

  for(int i = 2; i <= n; i++)  //　nまでの階乗を求める
  {
    fact[i] = fact[i-1] * i % mod;
  }
  for(int i = 2; i <= n; i++)  //a^(-1) mod p = a^(p-2) mod p
  {
    inv[i] = f(fact[i],mod-2,mod) % mod;
  }
}

ll comb(ll n,ll k)  //n_C_kを返す
{
  if (n < k)
  {
    return 0;
  }
  return (fact[n] * inv[k] % mod) * inv[n-k] % mod;
}

int main()
{
  ll n,a,b,k;
  cin >> n >> a >> b >> k;

  init(n);
  ll ans = 0;
  for(ll x = 0; x <= n; x++){
    if((k-x*a) % b != 0) continue; //Ax+By=Kを満たす整数yがない
    ll y = (k-x*a)/b;
    if(y < 0 || n < y) continue; //0 <= y <= n
    ans += (comb(n,x) % mod) * comb(n,y) % mod;
    ans %= mod;
  }

  cout << ans << endl;

  return 0;

ykmakuのブログ

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

ABC 113 D - Number of Amidakuji

ARC 088 D - Wide Flip

ARC 088 E - Papple Sort

AtCoder Grand Contest 003 C - BBuBBBlesort!

ARC 103 E - Tr/ee

ARC 103/ABC 111 C - /\/\/\/

AtCoder Grand Contest 025 B - RGB Coloring