土下座しながら探索中

主に競技プログラミング

TCO17 Algorithm Round 2A DistanceZeroAndOne

以下備忘録
解法:
d0,d1からグラフを構築し、それらのグラフを1つにまとめる
ある辺を答えとなるグラフに追加するかどうかは次のように決定する
1. d0,d1から構築したグラフの両方がその辺を持つなら答えのグラフにもその辺を追加
2. 片方しか持たないなら、その辺を追加した場合もう片方の最短距離に影響しないかどうかをチェックし、影響しないなら追加
最後にこうしてできたグラフの0,1からの最短距離がd0,d1と一致するか調べる

コード:

#include<bits/stdc++.h>

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

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;

class DistanceZeroAndOne {
public:
  
  vector<int> bfs(vector<string> &G,int sp) {
    int n = G.size();
    vector<int> mini(n,IINF);
    mini[sp] = 0;
    deque<int> deq;
    deq.push_back(sp);
    while( !deq.empty() ) {
      int c = deq.front(); deq.pop_front();
      rep(i,n) {
        if( G[c][i] == 'Y' )  {
          if( mini[c] + 1 < mini[i] ) {
            mini[i] = mini[c] + 1;
            deq.push_back(i);
          }
        }
      }
    }
    return mini;
  }

  bool check(vector<string> &G,vector<int> &d0,vector<int> &d1) {
    vector<int> m0 = bfs(G,0);
    vector<int> m1 = bfs(G,1);
    if( m0 == d0 && m1 == d1 ) return true;
    return false;
  }

  void makeG(vector<string> &G,vector<int> &d,int sp) {
    int n = G.size();
    vector<int> pre;
    pre.push_back(sp);
    REP(i,1,n) {
      vector<int> nex;
      rep(j,n) if( d[j] == i ) {
        nex.push_back(j);
        rep(k,(int)pre.size()) {
          G[j][pre[k]] = 'Y';
          G[pre[k]][j] = 'Y';
        }
      }
      pre = nex;
    }
  }

  vector <string> construct( vector <int> d0, vector <int> d1 ) {
    int n = d0.size();
    vector<string> ans(n);
    vector<string> G0(n),G1(n);
    rep(i,n) ans[i] = G0[i] = G1[i] = string(n,'N');
    makeG(G0,d0,0);
    makeG(G1,d1,1);
    rep(i,n) {
      rep(j,n) {
        if( G0[i][j] != G1[i][j] ) {
          char tmp = 'N';
          if( G0[i][j] == 'Y' ) {
            int vi = d1[i], vj = d1[j];
            if( vi + 1 < vj || vj + 1 < vi )  tmp = 'N';
            else tmp = 'Y';
          } else {
            int vi = d0[i], vj = d0[j];
            if( vi + 1 < vj || vj + 1 < vi )  tmp = 'N';
            else tmp = 'Y';
          }
          ans[i][j] = tmp;
        } else {
          ans[i][j] = G0[i][j];
        }
      }
    }
    if( check(ans,d0,d1) ) return ans;
    return vector<string>();
  }
};

TCO17 Algorithm Round 2A Easy FoxAndCake2

以下備忘録

解法 :
与えられる整数c,sの偶奇で場合分けする。
1. cとsがともに偶数ならば Possible ( 分割しなくても gcd(c,s) != 1 なので
2. cとsがともに奇数ならば
- c と s がともに 3 以上なら Possible ( (3,3) (c-3,s-3)とすればよい
- そうでないなら、 c か s の一方は1なので Impossible
3. cとsのうち片方だけが偶数ならば
- これを (偶、偶)(偶、奇)に分割する
  奇はできるだけ小さくしたほうがよいので 3
偶も(3とのgcdが1でないようなもののなかで)できるだけ小さくしたほうがよいので 6
  cとsから(3,6)のペアを作ったあとにc,sがそれぞれ2以上なら Possible
それ以外は Impossible

コード :

const string YES = "Possible";
const string NO  = "Impossible";

class FoxAndCake2 {
public:
  string isPossible( int _c, int _s ) {
    ll c = _c, s = _s;
    if( __gcd(c,s) != 1LL ) return YES;
    if( c % 2 == 1 && s % 2 == 1 && min(c,s) >= 3 )  return YES;
    ll even = c ,odd = s;
    if( !( even % 2LL == 0 ) ) swap(even,odd);
    odd -= 3LL;
    even -= 6LL;
    if( odd >= 2LL && even >= 2LL ) return YES;
    return NO;
  }
};

SRM 714 div 1 easy : ParenthesisRemoval

問題概要 :
正しい対応関係を持つ括弧の文字列が与えられる
その文字列の先頭の開き括弧 ( とそれより後ろにあるいずれかの閉じ括弧 ) を削除する
削除後の文字列の括弧の対応関係も正しくなければならない
このとき、括弧の消し方は何通りあるか?

解法:
後ろから数え上げる
文字列を後ろから見ていき、 開き括弧がきたら
それより後ろの閉じ括弧の数 - それより後ろの開き括弧の数 # コメント : これはいま見ている開き括弧と一緒に消すことができる括弧の数
を答えにどんどんかけていく

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

typedef long long ll;

const int IINF = INT_MAX;

const ll mod = 1000000007;

class ParenthesisRemoval {
public:
  int countWays(string s) {
    ll ans = 1;
    int L = 0, R = 0;
    for(int i=(int)s.size()-1;i>=0;--i) {
      if( s[i] == ')' ) ++R;
      else {
	ans = ( ans * ( R - L ) ) % mod;
	++L;
      }
    }
    return ans;
  }
};

SRM 712 DIV 1 easy : LR

問題概要:
サイズがnであるような2つの数列s,tが与えられる。
数列s,tの各要素には0からn-1まで番号がふられている。
数列sに対して以下の2つの操作を任意の回数だけ適用してtにできるか。
できるならその適用した順序を1つ出力せよ。
操作1. s[i] = s[i] + s[i-1] ( ただし i-1 < 0 なら s[i-1] は s[n-1] )

操作2. s[i] = s[i] + s[i+1] ( ただし i+1 >= n なら s[i+1] は s[0] )

解法:
操作1と操作2の使用回数が同じ場合、その順番によって結果は変わらない。
つまり、(操作1)→(操作2)→(操作1)→(操作2)の結果得られる数列と
(操作1)→(操作1)→(操作2)→(操作2)の結果得られる数列は同じである。
そのため、操作1と操作2を同じ回数で何回適用するか決め打ちする。
その後操作1だけを適用してtを作れるか、また操作2だけを適用してtを作れるかを試す。

注意点::オーバーフロー

s = { 1, 1 }
t = { 0, 0 }

のようなケースでオーバーフローしないか?
私は「そんなうまいケースないでしょ」と手を抜いてしまいeasy落としました。
悔い改めます。

コード:

#include<bits/stdc++.h>

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

typedef long long ll;

const string NO = "No solution";

class LR {
public:
  vector<ll> tmp;
  void simulateL(vector<long long> &vec) {
    int n = (int)vec.size();
    vector<long long> next(n);
    rep(i,n) next[i] = vec[i] + vec[((i-1)+n)%n];
    vec = next;
  }

  void simulateR(vector<long long> &vec) {
    int n = (int)vec.size();
    vector<long long> next(n);
    rep(i,n) next[i] = vec[i] + vec[(i+1)%n];
    vec = next;
  }

  bool check(vector<ll> &s,vector<ll> &t) {
    rep(i,(int)s.size()) {
      if( s[i] < tmp[i] ) return false;
      if( s[i] != t[i] ) return false;
    }
    return true;
  }

  int checkL(vector<ll> s,vector<ll> t,int rem) {
    if( check(s,t) ) return 0;
    REP(i,1,rem+1) {
      simulateL(s);
      rep(j,(int)s.size()) if( s[j] < tmp[j] ) return -1;
      if( check(s,t) ) return i;
    }
    return -1;
  }

  int checkR(vector<ll> s,vector<ll> t,int rem) {
    if( check(s,t) ) return 0;
    REP(i,1,rem+1) {
      simulateR(s);
      rep(j,(int)s.size()) if( s[j] < tmp[j] ) return -1;
      if( check(s,t) ) return i;
    }
    return -1;
  }

  string construct(vector<long long> s, vector<long long> t) {
    string ans = "";
    tmp = s;
    rep(i,101) {
      if( 100 - 2 * i < 0 ) break;
      if( check(s,t) ) {
	return ans;
      }
      int use;
      if( ( use = checkL(s,t,100-2*i) ) != -1 ) {
	rep(_,use) ans += "L";
	return ans;
      }
      if( ( use = checkR(s,t,100-2*i) ) != -1 ) {
	rep(_,use) ans += "R";
	return ans;
      }
      simulateL(s);
      rep(j,(int)s.size()) if( s[j] < tmp[j] ) break;
      simulateR(s);
      rep(j,(int)s.size()) if( s[j] < tmp[j] ) break;
      ans += "LR";
    }
    return NO;
  }
};

SRM 711 : ConsecutiveOnes

問題概要:
整数nとkが与えられる
次の条件を満たすような最小の整数mを求めよ:
1. m は n 以上である
2. m を2進数表記にしたとき、1が少なくともk個連続する箇所が存在する

制約 :
1 <= n <= 2^50 - 1
1 <= k <= 50

解法:
mの中で1がk個連続する箇所をループで決める
このとき、mがn以上ならそれを答えの候補にする
そうでないとき、mがn以上でなおかつそのような値の中で最小になるように調整し答えの候補に追加する
答えの候補の中の最小値を答えとして返す

mがn未満の場合にn以上でなおかつ最小になるように調整する 手順は次の通り
m = 0..01..10..0
1. n - mを求める
これをxとする
2. xとmの論理積 x & m が 0 なら、

m = x | m 

として調整終了
そうでないなら、

m = ( m | x ) & ~((1LL<<sp)-1LL)
m += (1LL<<(sp+k))

とする
このとき、
m = 0..01..10..0
の赤くなっている1の位置がsp


注意点:
オーバーフローしないように、ビットをシフトする際には

1<<k 

ではなく

1LL<<k

とすること

コード:

typedef long long ll;
class ConsecutiveOnes {
public:
  ll compute(int sp,ll n,int k) {
    ll v = 0LL;
    rep(i,k) v |= (1LL<<(sp+i));
    if( v >= n ) return v;
    ll need = n - v;
    if( ( v & need ) == 0LL ) {
      return v | need;
    }
    v = ( v | need ) & ~((1LL<<sp)-1LL);
    v += (1LL<<(sp+k));
    return v;
  }
  
  long long get(long long n, int k) {
    ll mini = LLONG_MAX;
    rep(i,100) {
      if( i + k >= 62 ) break;
      mini = min(mini,compute(i,n,k));
    }
    return mini;
  }
};

SRM 709 Div1 easy : Xscoregame

問題概要 :

長さ n (1 <= n <= 15) の数列 A が与えられる
Aの各要素A[i]は 0 以上 50 以下である
この数列に対して以下の処理を行う

1. 変数 X を用意し、 X に 0 を代入する
2. 数列 A のなかから、まだ使っていない要素 A[i] を選び X の値を次の式で更新する :
X = X + ( X xor A[i] )
  これを選べる要素がなくなるまで続ける
3. X の値を出力する

最終的に X のとりうる最大の値を答えよ

解法 :
ビットDP
dp[Aのどの要素を使ったかをbitで保持, 1<<15][下位6bit x, 1<<6] = 下位6bit が x であるような値の最大値

愚直にやると、bool dp[state1][state2]
bool dp[Aのどの要素を使ったかをbitで保持, 1<<15][ Aの要素を使用した状態が state1 であるときの最大値 ] = state2を作れるか
とやれば良い
ただ、サンプルの最後を見るとわかる通りstate2がかなり大きくなる

Xの値を計算する際に xor をとるため、単純に大きい値だけを保持していてもそれが最終的に最大値になるかどうかはわからない
そのためbitの情報をすべて state2 としてとっていたのだが、A[i] <= 50 であることに注目すればわざわざ全てのbitの情報を保持しておく必要がないことが分かる
なぜなら、( X xor A[i] ) において X の 6bit目以降は xor の計算で影響を受けない
なので6bit目以下だけをdpの状態として保持すれば良い

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

const int IINF = INT_MAX;

#define MAX 64

int dp[1<<15][MAX];

class Xscoregame {
public:
  int getscore(vector <int> A) {
    int n = A.size();
    sort(A.begin(),A.end());    
    memset(dp,-1,sizeof dp);
    dp[0][0] = 0;
    rep(bit,(1<<n)) {
      rep(bet,MAX) {
	if( dp[bit][bet] == -1 ) continue;
	rep(i,n) {
	  if( (bit>>i) & 1 ) continue;
	  int nbit = bit | (1<<i);
	  int value = dp[bit][bet] + ( dp[bit][bet] ^ A[i] );
	  int beet = value % MAX;
	  dp[nbit][beet] = max(dp[nbit][beet],value);
	}
      }
    }
    int maxi = 0;
    rep(i,MAX) maxi = max(maxi,dp[(1<<n)-1][i]);
    return maxi;
  }
};

SRM 708 : Div1 easy BalancedStrings

問題概要:
1以上100以下の整数Nが与えられる。
以下の条件を満たすサイズNの文字列の集合Sを1つ見つけよ。
条件を満たすようなものは必ず存在する。

条件 1. 集合Sの要素である文字列の長さは1以上100以下である。
条件 2. 集合Sの要素である文字列は英小文字aからzから構成される。
条件 3. 集合Sの安定度と不安定度は等しい。

集合Sの安定度と不安定度は以下のように定義される。

安定度. Sに属する全ての文字列 s の連続する同じ英小文字を1つにまとめた文字列s'の長さ-1の総和
例 : S = { "aabcccdd", "a", "abccdde" } の安定度は 3 + 0 + 4 = 7

不安定度. Sに属する異なる二つの要素 s, t について、共通に現れる英小文字のペアの数の総和
 例 : S = { "aabcccdd", "a", "abccdde" } の不安定度は 16
"aabcccdd" と "a" から 2
"aabcccdd" と "abccdde" から 2 + 1 + 6 + 4 = 13
"a" と "abccdde" から 1
よって 16

解法:

不安定度を決定した後に安定度をそれに合わせる方針をとる。
以下、うまく説明をまとめることができなかったのでコンテスト中の自分がどのように考えていったのかについて書きます。
~~~ コンテスト中
どうしようか。
まず次のようなサイズNの文字列の集合 { "a", "a", ..., "a" }を用意して、この安定度を増加させていく方針で考えてみようかな。
この段階で不安定度は N * ( N - 1 ) / 2 だから、N が最大のとき、つまり100 なら不安定度は 4950。
さて、後は要素の文字列を変更して安定度を調整しよう。
aを使うと不安定度が変わるから、まだ集合の中にない文字列を二つ選んで追加しよう。
{ "abcbc", "adedede", ..., "ayzyzyz" } みたいな感じでね。
文字列の長さは最大100だから、この方法を使えば一つの文字列で安定度を最大99まで上げることができるな。
一度使った英小文字は別の文字列では使えない (使うと不安定度が上がる) から、最大 25 / 2 = 12 の文字のペアを使えて、 12 * 99 = 1188までは自由に安定度を増加させれるな。
あれ、不安定度は4950だよな。
(安定度が足り)ないじゃん。
不安定度を減らさなきゃ。
じゃあ { "a", ..., "a", "b", ..., "b" } としようかな。
するとN = 100のときの不安定度は ( 50 * 49 / 2 ) * 2 = 2450。
残りの英小文字で作れる安定度の最大は 24 / 2 = 12 ペア * 99 = 1188。
まだ足りない。
...
{ "a", ..., "a", "b", ..., "b", "c", ..., "c", "d", ..., "d", "e", ..., "e" }はどうだろう。
N = 100 のとき不安定度は ( 20 * 19 / 2 ) * 5 = 950。
残りの英小文字で作れる安定度の最大は 21 / 2 = 10 ペア * 99 = 990。
これなら不安定度と安定度を同じにできる!

コード:

#include<bits/stdc++.h>

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

using namespace std;

class BalancedStrings {
public:

  int calcS(vector<string> vec) {
    int S = 0;
    rep(i,(int)vec.size()) {
      map<char,int> cnt;
      rep(j,(int)vec[i].size()) ++cnt[vec[i][j]];
      REP(j,i+1,(int)vec.size()) {
	rep(k,(int)vec[j].size()) {
	  S += cnt[vec[j][k]];
	}
      }
    }
    return S;
  }

  vector <string> findAny(int N) {
    vector<string> ret;
    rep(i,N) ret.push_back(string(1,(char)(('a'+i%5))));
    int sim = calcS(ret);
    rep(i,N) if( sim ) {
      char p = (char)('f'+i*2), q = (char)('g'+i*2);
      while( (int)ret[i].size() < 100 && sim ) {
	int len = ret[i].size();
	if( len & 1 ) {
	  ret[i] += string(1,p);
	  --sim;
	} else {
	  ret[i] += string(1,q);
	  --sim;
	}
      }
    }
    return ret;
  }
};