ykmakuのブログ

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

AtCoder Grand Contest 023 B - Find Symmetries

競プロ よく観察する
  • 問題

B - Find Symmetries

  • 解法

2つ目の盤面が良い盤面であるかどうかチェックするには愚直にやるとO(N^2)の計算量時間がかかる。考えられる(A,B)の個数はO(N^2)個なので全ての(A,B)に対して2つ目の盤面をチェックする方法ではO(N^4)の計算量時間がかかってTLEになる。
なので盤面チェックの時間を減らすか、考える(A,B)の個数を減らすかのどちらかができないか考える。
ここで、ある(A,B)に対してこのときの2つめの盤面が良い盤面なら、(A+1,B+1), \ (A+2,B+2), \ \dots \ (A+n-1,B+n-1)に対する2つ目の盤面も良い盤面であることに気がつく。
すると、考える(A,B)は(0,0), \ (1,0). \ \dots \ (n-1,0)だけでよいことになる。
この方法ならO(N^3)の計算量時間で問題が解けて制限時間に間に合う。

#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<string> s(n);
  for(int i = 0; i < n; i++){
    s[i].resize(n);
    for(int j = 0; j < n; j++){
      cin >> s[i][j];
    }
  }

  int ans = 0;

  vector<string> t(n);
  for(int a = 0; a < n; a++){
    bool flag = true;
    for(int i = 0; i < n; i++){
      t[i].resize(n);
    }
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        t[i][j] = s[(i+a)%n][j];
      }
    }
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        if(t[i][j] != t[j][i]) flag = false;
      }
    }

    if(flag) ans += n;
  }

  cout << ans << endl;

  return 0;
}

AtCoder Beginner Contest 099　D - Good Grid

競プロ 全探索 事前に計算する
  • 問題

D - Good Grid

  • 解法

色の塗替えの候補は30×29×28通り。
すべての色の塗り替え方について各マス目を見て違和感を計算する方法ではO(N^2 C^3)の時間計算量がかかりTLEになってしまう。
そこでk=0,1,2に対して(i+j)\ \% \ 3 = kとなるマス目にどの色が何個あるかを事前に計算しておけば、色の塗り替え方に対しすべてのマス目を見る必要がなくなる。
結局O(C^4)の時間計算量でこの問題は解ける。

こういう問題に遭遇するとREPマクロ使いたくなる。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#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 int INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int N,C;
	cin >> N >> C;

	int d[31][31] = {0}, c[501][501]= {0};
	for(int i = 1; i <= C; i++){
		for(int j = 1; j <= C; j++){
			cin >> d[i][j];
		}
	}
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			cin >> c[i][j];
		}
	}

	map<int,int> color[3];
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			color[(i+j)%3][c[i][j]]++;
		}
	}

	int ans = INF;
	for(int i = 1; i <= C; i++){
		for(int j = 1; j <= C; j++){
			for(int k = 1; k <= C; k++){
				if(i != j && j != k && k != i){
					int res = 0;
					for(int l = 0; l < 3; l++){
						int m = i;
						if(l == 1) m = j;
						else if(l == 2) m = k;
						for(auto itr = color[l].begin(); itr != color[l].end(); ++itr){
							res += d[itr->first][m] * itr->second;
						}
					}
					ans = min(res,ans);
				}
			}
		}
	}

	cout << ans << endl;

	return 0;
}

AtCoder Regular Contest 093 D - Grid Components

競プロ
  • 問題

D - Grid Components

  • 解法

まず100×100のグリッドを用意します。
上半分を白、下半分を黒で塗ります。
上半分のうち奇数行目を見ていき各行について1個おきにマス目を黒くします。A-1個のマスを黒く塗ったら終了。
こうすることで白の連結成分の数を変えずに黒の連結成分を1個ずつ増やせます。
下半分は偶数行目を見て同じようにB-1個のマスを白く塗ればよいです。

白の連結成分の数を変えずに黒の連結成分を1個ずつ増やすにはどうしたらよいかを考えると解法が浮かぶと思いました。

#include <iostream>
#include <string>

using namespace std;

int main()
{
  int a,b;
  cin >> a >> b;
  string s[100];
  for(int i = 0; i < 100; i++){
    for(int j = 0; j < 100; j++){
      if(i<50) s[i].push_back('.');
      else s[i].push_back('#');
    }
  }
  int cnt = 0;
  for(int i = 0; i < 50; i += 2){
    if(cnt == b-1) break;
    for(int j = 0; j < 100; j += 2){
      if(cnt == b-1) break;
      s[i][j] = '#';
      cnt++;
    }
  }
  cnt = 0;
  for(int i = 51; i < 100; i += 2){
    if(cnt == a-1) break;
    for(int j = 0; j < 100; j += 2){
      if(cnt == a-1) break;
      s[i][j] = '.';
      cnt++;
    }
  }
  cout << 100 << " " <<  100 << endl;
  for(int i = 0; i < 100; i++){
    cout << s[i] << endl;
  }

  return 0;
}

AtCoder Regular Contest 087 D - FT Robot

DP
  • 問題

D - FT Robot

  • 解法

s中でTが出て来るたびにロボットが動く方向がx軸方向→y軸方向→x軸方向\dotsとなる。ここでx軸方向とy軸方向の動きは独立に考えても良い。
x軸方向について動いているときを考える。このときロボットが移動できる点は(1回前にx軸方向について動いたときに到達した点)±(今回動ける距離)となる。
したがって、(x軸方向について動いた回数i ,\ i回目にロボットが到達できるx座標)のペアを保持すればi+1回目にロボットが到達できるx座標がわかる。
y軸方向について動いているときも同様に求められる。

文字列の最初がFのときはx軸の正の方向にしか動けないことに注意する。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long int ll;

const ll MAXN = 8020;

int main()
{
  string s;
  cin >> s;
  int x,y;
  cin >> x >> y;

  vector<int> t;
  int cnt = 0;
//文字列を変形する
  for(int i = 0; i < s.size(); i++){
    if(s[i] == 'T'){
      if(cnt != 0) t.push_back(cnt);
      t.push_back(0);
      cnt = 0;
    }else{
      cnt++;
      if(i == s.size()-1) t.push_back(cnt);
    }
  }

  bool dp_x[MAXN][MAXN*2] = {false}, dp_y[MAXN][MAXN*2] = {false};
  dp_x[0][8000] = true;
  dp_y[0][8000] = true;

  bool flag = false;
  bool xy = true; // trueならx軸について見ている
  int cnt_x = 0,cnt_y = 0;

  for(int i = 0; i < t.size(); i++){
    if(t[i] == 0){
      xy  = !xy;
    }else if(xy){
      cnt_x++;
      for(int j = 0; j < MAXN*2; j++){
        if(dp_x[cnt_x-1][j]){
          if(j+t[i] < MAXN*2) dp_x[cnt_x][j+t[i]] = true;
          if(j-t[i] >= 0 && flag) dp_x[cnt_x][j-t[i]] = true;
        }
      }
    }else if(!xy){
      cnt_y++;
      for(int j = 0; j < MAXN*2; j++){
        if(dp_y[cnt_y-1][j]){
          if(j+t[i] < MAXN*2) dp_y[cnt_y][j+t[i]] = true;
          if(j-t[i] >= 0) dp_y[cnt_y][j-t[i]] = true;
        }
      }
    }

    if(!flag) flag = true;
  }

  cout << ((dp_x[cnt_x][x+8000] && dp_y[cnt_y][y+8000]) ? "Yes" : "No") << endl;

  return 0;
}

AtCoder Regular Contest 101 D - Median of Medians

二分探索 数式変形をする 個数を数える
  • 問題

D - Median of Medians

  • 解法

N\leq 10^5であり、数列mの長さは\frac{N(N+1)}{2}なので数列mを実際につくるとTLEになるので別の方法を考えないといけない。
editorialがめちゃめちゃ分かりやすいので特に書くことなし。
BITでの反転数の求め方はここ
www.geeksforgeeks.org
が分かりやすいと思いました。

#include <iostream>
#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;
        }
    }
};

//数列の値の範囲を[1,n]に変える
vector<ll> convert_array(vector<ll> z){
    ll n = z.size();
    vector<ll> temp = z;
    sort(all(temp));
    for(int i = 0; i < n; i++){
        z[i] = lower_bound(all(temp), z[i]) - temp.begin() + 1;
    }
    return z;
}

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

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

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

    return inv_num;
}

//数列の変形をしてxが中央値の候補かどうか調べる
bool check(ll x,vector<ll> z){
    ll n = z.size();
    vector<ll> b(n);
    for(int i = 0; i < n; i++){
        if(z[i] >= x) b[i] = 1;
        else b[i] = -1;
    }
    vector<ll> s(n+1,0);  //ここ長さn+1になることに注意
    for(int i = 1; i <= n; i++){
        s[i] = s[i-1] + b[i-1];
    }

    return (n*(n+1)/2 - inverse_number(s)) >= (n*(n+1)/2+1)/2;
}

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

    ll low = *min_element(all(a))-1, high = *max_element(all(a))+1;

    while(high - low > 1){
        ll mid = (low+high)/2;
        if(check(mid,a)) low = mid;
        else high = mid;
    }

    cout << low << endl;

    return 0;
}

AtCoder Regular Contest 069 D - Menagerie

競プロ 前から順に見る 前から順番に決める、決まる
  • 問題

D - Menagerie

  • 解法

最初の2人の動物の種類が決まれば、3番目以降の動物の種類は順番に決まっていく、ということに気がつけば後は実装するだけ。
最初の2人の動物の種類の組合せは4通りなので、全部試してそれぞれ条件に矛盾しないかどうかを調べる。
ここでいう条件とは、動物の種類を決めていったときに1番目の動物とn+1番目の動物が同じであることと、1番目の動物の両隣が文字列と矛盾しないかどうかである。

  • 感想

最初は

ans[0] = true,ans[1] = true;
 
	for(int i = 1; i < n; i++){
		if(s[i] == 'o'){
			if(ans[i]) ans[i+1] = ans[i-1];
			else ans[i+1] = !ans[i-1];
		}else{
			if(ans[i]) ans[i+1] = !ans[i-1];
			else ans[i+1] = ans[i-1];
		}
	}
if(check()){
		for(int i = 0; i < n; i++){
			if(ans[i]) cout << 'S';
			else cout << "W";
		}printf("\n");
		return 0;
	}

を4回コピペしていました。
こういうときにスッとbitの形のループ?(下のコード)で書けるようになりたい。
あんまりbitの操作を使わないので積極的に使って慣れていきたい。

  • コード
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#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 n;
string s;
vector<bool> ans; // true = S, false = W

bool check(){
	bool zero = (ans[0] == ans[n]);
	bool ss = true;
	if(s[0] == 'o'){
		if(ans[0]){
			if(ans[n-1] != ans[1]) ss = false;
		}else{
			if(ans[n-1] == ans[1]) ss = false;
		}
	}else{
		if(ans[0]){
			if(ans[n-1] == ans[1]) ss = false;
		}else{
			if(ans[n-1] != ans[1]) ss = false;
		}
	}

	return (zero&&ss);
}

void circle(bool x,bool y){
	ans[0] = x,ans[1] = y;

	for(int i = 1; i < n; i++){
		if(s[i] == 'o'){
			if(ans[i]) ans[i+1] = ans[i-1];
			else ans[i+1] = !ans[i-1];
		}else{
			if(ans[i]) ans[i+1] = !ans[i-1];
			else ans[i+1] = ans[i-1];
		}
	}
}

int main()
{
	cin >> n >> s;
	ans.resize(n+1);

	for(int i = 0; i < (1<<2); i++){
		circle(1&(i>>0),1&(i>>1));
		if(check()){
			for(int i = 0; i < n; i++){
				if(ans[i]) cout << 'S';
				else cout << "W";
			}cout << endl;
		return 0;
		}
	}
	cout << -1 << endl;

	return 0;
}

AtCoder Grand Contest 006 B - Median Pyramid Easy

競プロ 例をつくってよく観察する
  • 問題

B - Median Pyramid Easy

  • 解法

実際にピラミッドを作るには\mathcal{O}(N^{2})の時間計算量がかかるため無理。なので入力から直接数列を作ることを考えないといけない。
x = 1 ,\ x = 2n-1のときは無理である(中央値になりえないため)。x = nのときは1,2,\dots,2n-1を出力すれば良い。他の場合は解説pdfにある通りで2段目の真ん中の2マスがxになればよい。このようにするには、x{<}nのときは数列の真ん中に1を、その隣にxを配置すれば良い。x{>}nのときは数列の真ん中に2n-1、その隣にxを配置すれば良い。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#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,x;
  cin >> n >> x;
  if(x == 1 || x == 2*n-1) cout << "No" << endl;
  else{
    cout << "Yes" << endl;
    vector<int> ans(2*n);
    for(int i = 0; i < ans.size(); i++){
      ans[i] = i;
    }
    if(x != n){
      if(x < n){
        ans[n-1] = x;
        ans[x] = n-1;
        ans[n] = 1;
        ans[1] = n;
      }else{
        ans[n+1] = x;
        ans[x] = n+1;
        ans[2*n-1] = n;
        ans[n] = 2*n-1;
      }
      
    }

    for(int i = 1; i <= 2*n-1; i++){
      cout << ans[i] << endl;
    }
  }

  return 0;
}