ferinの競プロ帳

競プロについてのメモ

AOJ2613 Unordered Operators

AOJ 競技プログラミング

問題ページ

解法

まず演算子の優先順序が*>+>-となっている場合のBNFを書いてみる。左再帰と演算子の優先順序に気をつけつつ書くと以下のようになる。

<expr1> = <expr2> ['-' <expr2>]*
<expr2> = <expr3> ['+' <expr3>]*
<expr3> = <factor> ['*' <factor>]*
<factor> = '(' <expr1> ')' | <number>

他の優先順序の場合についても同様にBNFを書ける。BNFにしたがって再帰型構文解析を書けばよい。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

char op[3] = {'+', '-', '*'};

int pos;
string s;

ll exprA1();
ll exprA2();
ll exprA3();
ll factorA();
ll exprB1();
ll exprB2();
ll factorB();
ll exprC1();
ll exprC2();
ll factorC();
ll exprD1();
ll factorD();
ll number();

ll exprA1() {
  ll ret = exprA2();

  while(pos < s.size()) {
    if(s[pos] == op[0]) {
      if(op[0] == '+') pos++, ret += exprA2();
      else if(op[0] == '*') pos++, ret *= exprA2();
      else if(op[0] == '-') pos++, ret -= exprA2();
    } else {
      break;
    }
  }
  return ret;
}

ll exprA2() {
  ll ret = exprA3();

  while(pos < s.size()) {
    if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += exprA3();
      else if(op[1] == '*') pos++, ret *= exprA3();
      else if(op[1] == '-') pos++, ret -= exprA3();
    } else {
      break;
    }
  }
  return ret;
}

ll exprA3() {
  ll ret = factorA();

  while(pos < s.size()) {
    if(s[pos] == op[2]) {
      if(op[2] == '+') pos++, ret += factorA();
      else if(op[2] == '*') pos++, ret *= factorA();
      else if(op[2] == '-') pos++, ret -= factorA();
    } else {
      break;
    }
  }
  return ret;
}

ll factorA() {
  ll ret;
  if(s[pos] == '(') {
    pos++;
    ret = exprA1();
    pos++;
  } else {
    ret = number();
  }
  return ret;
}

ll exprB1() {
  ll ret = exprB2();

  while(pos < s.size()) {
    if(s[pos] == op[0]) {
      if(op[0] == '+') pos++, ret += exprB2();
      else if(op[0] == '*') pos++, ret *= exprB2();
      else if(op[0] == '-') pos++, ret -= exprB2();
    } else if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += exprB2();
      else if(op[1] == '*') pos++, ret *= exprB2();
      else if(op[1] == '-') pos++, ret -= exprB2();
    } else {
      break;
    }
  }
  return ret;
}

ll exprB2() {
  ll ret = factorB();

  while(pos < s.size()) {
    if(s[pos] == op[2]) {
      if(op[2] == '+') pos++, ret += factorB();
      else if(op[2] == '*') pos++, ret *= factorB();
      else if(op[2] == '-') pos++, ret -= factorB();
    } else {
      break;
    }
  }
  return ret;
}

ll factorB() {
  ll ret;
  if(s[pos] == '(') {
    pos++;
    ret = exprB1();
    pos++;
  } else {
    ret = number();
  }
  return ret;
}

ll exprC1() {
  ll ret = exprC2();

  while(pos < s.size()) {
    if(s[pos] == op[0]) {
      if(op[0] == '+') pos++, ret += exprC2();
      else if(op[0] == '*') pos++, ret *= exprC2();
      else if(op[0] == '-') pos++, ret -= exprC2();
    } else if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += exprC2();
      else if(op[1] == '*') pos++, ret *= exprC2();
      else if(op[1] == '-') pos++, ret -= exprC2();
    } else {
      break;
    }
  }
  return ret;
}

ll exprC2() {
  ll ret = factorC();

  while(pos < s.size()) {
    if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += factorC();
      else if(op[1] == '*') pos++, ret *= factorC();
      else if(op[1] == '-') pos++, ret -= factorC();
    } else if(s[pos] == op[2]) {
      if(op[2] == '+') pos++, ret += factorC();
      else if(op[2] == '*') pos++, ret *= factorC();
      else if(op[2] == '-') pos++, ret -= factorC();
    } else {
      break;
    }
  }
  return ret;
}

ll factorC() {
  ll ret;
  if(s[pos] == '(') {
    pos++;
    ret = exprC1();
    pos++;
  } else {
    ret = number();
  }
  return ret;
}

ll exprD1() {
  ll ret = factorD();

  while(pos < s.size()) {
    if(s[pos] == op[0]) {
      if(op[0] == '+') pos++, ret += factorD();
      else if(op[0] == '*') pos++, ret *= factorD();
      else if(op[0] == '-') pos++, ret -= factorD();
    } else if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += factorD();
      else if(op[1] == '*') pos++, ret *= factorD();
      else if(op[1] == '-') pos++, ret -= factorD();
    } else if(s[pos] == op[2]) {
      if(op[2] == '+') pos++, ret += factorD();
      else if(op[2] == '*') pos++, ret *= factorD();
      else if(op[2] == '-') pos++, ret -= factorD();
    } else {
      break;
    }
  }
  return ret;
}

ll factorD() {
  ll ret;
  if(s[pos] == '(') {
    pos++;
    ret = exprD1();
    pos++;
  } else {
    ret = number();
  }
  return ret;
}

ll number() {
  ll ret = 0;
  while(pos < s.size() && isdigit(s[pos])) {
    ret *= 10;
    ret += s[pos]-'0';
    pos++;
  }
  return ret;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> s;

  ll ans = LLONG_MIN;
  sort(op, op+3);
  do {
    pos = 0;
    ll ret = exprA1();
    chmax(ans, ret);
  } while(next_permutation(op, op+3));

  sort(op, op+3);
  do {
    pos = 0;
    ll ret = exprB1();
    chmax(ans, ret);
  } while(next_permutation(op, op+3));

  sort(op, op+3);
  do {
    pos = 0;
    ll ret = exprC1();
    chmax(ans, ret);
  } while(next_permutation(op, op+3));

  sort(op, op+3);
  do {
    pos = 0;
    ll ret = exprD1();
    chmax(ans, ret);
  } while(next_permutation(op, op+3));

  cout << ans << endl;

  return 0;
}

久々に構文解析かいたらfactor置く位置とか意味不明なバグらせ方をした。

Tenka1 Programmer Contest E - Equilateral

AtCoder 競技プログラミング

問題ページ

考えたこと

  • 45度回転
  • これ以降チェビジェフ距離で考える
  • 距離が等しい点はある正方形上の点になる
  • 2点を固定してその2点のどちらとも距離が等しい点を探す
  • 各点を中心として2点間の距離*2を1辺の長さとする正方形を書く
  • 2点どちらとも距離が等しい点は正方形の交点になる
  • 2点を固定して正方形の交点にコインが置いてあるかを判定すると4乗は書けるがこれはTLE
  • 高速化をする
  • 正方形の交点はどちらかの点と同じ行・列に存在することがわかる
  • 同じ行にコインが2枚存在したときにどこにあれば条件を満たす3点になるか
  • #にコインがあったとするとxにコインがあると条件を満たす
.xxx.
.....
.#.#.
.....
.xxx.
  • 以上のように連続する区間にコインが何枚あるかわかればよい
  • これは行ごとに累積和を数えておけばO(1)でわかる
  • 列に関しても同様、ただし行とだぶって数えないように注意
  • 行・列ごとにまとめられたので3乗に落ちたのでこれは通る
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll h, w;
  cin >> h >> w;
  vector<string> s(h);
  REP(i, h) cin >> s[i];

  vector<string> t(h+w, string(h+w, '.'));
  REP(i, h) REP(j, w) {
    t[j+i][j-i+h-1] = s[i][j];
  }

  ll n = h+w;
  auto cnt1 = make_v<ll>(n, n);
  REP(i, n) {
    if(t[i][0] == '#') cnt1[i][0] = 1;
    FOR(j, 1, n) {
      cnt1[i][j] += cnt1[i][j-1] + (t[i][j]=='#'?1:0);
    }
  }
  auto cnt2 = make_v<ll>(n, n);
  REP(i, n) {
    if(t[0][i] == '#') cnt2[0][i] = 1;
    FOR(j, 1, n) {
      cnt2[j][i] += cnt2[j-1][i] + (t[j][i]=='#'?1:0);
    }
  }

  ll ret = 0;
  REP(i, n) {
    REP(l, n) {
      if(t[i][l] == '.') continue;
      FOR(r, l+1, n) {
        if(t[i][r] == '.') continue;
        if(i-(r-l) >= 0) {
          ret += cnt1[i-(r-l)][r] - (l==0?0:cnt1[i-(r-l)][l-1]);
        }
        if(i+(r-l) < n) {
          ret += cnt1[i+r-l][r] - (l==0?0:cnt1[i+r-l][l-1]);
        }
      }
    }
  }
  REP(i, n) {
    REP(l, n) {
      if(t[l][i] == '.') continue;
      FOR(r, l+1, n) {
        if(t[r][i] == '.') continue;
        if(i-(r-l) >= 0) {
          ret += cnt2[r-1][i-(r-l)] - (l==0?0:cnt2[l][i-(r-l)]);
        }
        if(i+(r-l) < n) {
          ret += cnt2[r-1][i+r-l] - (l==0?0:cnt2[l][i+r-l]);
        }
      }
    }
  }

  cout << ret << endl;

  return 0;
}

Tenka1 Programmer Contest D - Crossing

競技プログラミング AtCoder

問題ページ

考えたこと

  • とりあえず実験
  • 部分集合の大きさを4に固定してみる
  • 1つ目の集合に異なる要素が3個は入っていないと、積集合の大きさが1となる条件を満たせない
  • 1つ目と2つ目、1つ目と3つ目、1つ目と4つ目については以下のように取れば条件を満たす
1 2 3
1
2
3
  • 同様に2つ目の集合に異なる要素が2個は入っていないと条件を満たさない
  • 1つの数は2つの部分集合までしか入れないので1,2,3は使えない
  • 以下のように数を入れる
1 2 3
1 4 5
2 4
3 5
  • 同様に3つ目と4つ目の部分集合で条件を満たすように入れると以下のようになる
1 2 3
1 4 5
2 4 6
3 5 6
  • 以上のように部分集合の数を固定すると構成は一つに定まりそう
  • 部分集合の要素数をmとするとn=m*(m+1)/2については構成できる
  • これ以外のnで構成できることはなさそう
  • 実装すると通る
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;

  ll m = -1;
  for(ll i=1; i<=n; ++i) {
    if(i*(i+1)/2 == n) {
      m = i;
    }
  }
  
  // cout << m << endl;

  if(m == -1) {
    cout << "No" << endl;
    return 0;
  }

  vector<vector<ll>> ans(m+1);
  ll idx1 = 0, idx2 = 1, j = 1;
  for(ll i=m; i>=1; --i) {
    // cout << "i=" << i << endl;
    for(ll k=0; k<i; j++,k++) {
      // cout << idx1 << " " << idx2 << " " << j << endl;
      ans[idx1].push_back(j);
      ans[idx2].push_back(j);
      idx2++;
    }
    idx1++;
    idx2 = idx1+1;
  }

  cout << "Yes" << endl;
  cout << m+1 << endl;
  REP(i, m+1) {
    cout << ans[i].size();
    for(auto j: ans[i]) cout << " " << j;
    cout << endl;
  }

  return 0;
}

Tenka1 Programmer Contest C - Align

AtCoder 競技プログラミング

問題ページ

思考過程

  • ジグザグにするのがよさそう
  • 一番小さい、大きいのを端に置くと損してる
  • ジグザグな山みたいなのをつくるのがよさそう
  • 一番小さいのを中央に置くか、一番大きいのを中央に置くかで2種類あるのに気をつけながら書くと通った
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
ll MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  ll mid = n/2;
  if(n%2==0) mid--;
  sort(ALL(a));
  vector<ll> v(n);
  v[mid] = a[0];
  for(int i=mid+2, j=1; i<n; i+=2, j+=2) {
    v[i] = a[j];
  }
  for(int i=mid+1, j=n-1; i<n; i+=2, j-=2) {
    v[i] = a[j];
  }
  for(int i=mid-2, j=2; i>=0; i-=2, j+=2) {
    v[i] = a[j];
  }
  for(int i=mid-1, j=n-2; i>=0; i-=2, j-=2) {
    v[i] = a[j];
  }
  ll ret = 0;
  FOR(i, 1, n) ret += abs(v[i]-v[i-1]);
  ll ans = ret;

  reverse(ALL(a));
  v[mid] = a[0];
  for(int i=mid+2; i<n; i+=2) {
    v[i] = a[i-mid-1];
  }
  for(int i=mid+1, j=n-1; i<n; i+=2, j-=2) {
    v[i] = a[j];
  }
  for(int i=mid-2, j=2; i>=0; i-=2, j+=2) {
    v[i] = a[j];
  }
  for(int i=mid-1, j=n-2; i>=0; i-=2, j-=2) {
    v[i] = a[j];
  }
  ret = 0;
  FOR(i, 1, n) ret += abs(v[i]-v[i-1]);
  chmax(ans, ret);

  cout << ans << endl;

  return 0;
}

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

AtCoder 競技プログラミング 要復習

問題ページ

解法

回文が成り立つ⇔奇数個の文字が1種類以下 である。回文が成り立つかの判定を高速にするため hash = (文字種iが奇数個だったらiビット目を1とする) となるハッシュを考える。このハッシュを使うと 回文が成り立つ⇔1のビットの数が1個以下 となる。h[i]=(区間[0,i)のハッシュ)とする。
dpの定義を dp[i]=(i番目までで条件を満たすような最小の分割数) とすると遷移はdp[i] = min_j (dp[j]) + 1 (区間[j,i)が回文になる=h[j] xor h[i]が2べきか0)となる。このdpを普通に書くとO(N^2)なので高速化する。
h[j] xor h[i] = 2べきか0 となるようなjを見つけなければならない。h[j] = h[i] xor (2べきか0) となるようなjであればよい。h[j]が取りうる値はたかだか27個なのでdpの遷移をこれで抑えることを考える。これはdp2[i] = (ハッシュがiとなるような分け方のうち最小の分割数) があればできる。dpの遷移は dp[i] = min(dp2[h[i] xor (2べきか0)]) + 1 となる。これでdpの更新がO(文字種)で抑えられた。dp2の更新はdp2[h[i]] = min(dp2[h[i]], dp[i]) とすればよくO(1)でできる。これでO(N*(文字種))で解けた。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;
  ll n = s.size();

  // dp[i] = (i番目までで条件を満たす最も少ない分割数)
  // dp[i] = dp[j] + 1 (a[i]^a[j]が0もしくは2べき)
  // dp2[i] = (ハッシュ値がiのもののうち分割数のmin)
  // dp[i] = min(dp[a[i]^x]) + 1

  ll a = 0;
  vector<int> dp(n), dp2(1LL<<26, INF);
  dp[0] = 0, dp2[0] = 0;
  REP(i, n) {
    a ^= 1LL<<(s[i]-'a');
    int mi = dp2[a];
    REP(j, 26) chmin(mi, dp2[a^(1LL<<j)]);
    dp[i] = mi + 1;
    chmin(dp2[a], dp[i]);
  }
  cout << dp[n-1] << endl;

  return 0;
}

Mujin Programming Challenge 2017 A - Robot Racing

競技プログラミング AtCoder

問題ページ

考えたこと

  • ロボットiの前にたくさんロボットがいるとロボットiがゴールするのは不可能
  • ロボットiがゴールする前にある程度捌けてもらわないといけない
  • ロボットiがゴールするのに必要な条件を考える
  • 1 or 2マスジャンプなので2台連続でロボットがいると不可能
  • 2マスにつき1台ロボットがいる状況なら問題ない
  • x=2までに1台、x=4までに2台、x=6までに3台、x=8までに4台…ならok
  • i番目のロボットまでの並びからi+1番目以降のロボットが通るのが不可能か？
  • これはx/2+1台以上ロボットがいるか？で判定できる
  • 不可能ならばi番目のロボットの中から1台をi+1番目以降のロボットより先にゴールさせないといけない
  • 答えにi番目のロボットまででまだゴールしていないロボットの台数を掛ける
  • 順序の制限がつくロボットについてゴールさせたら残りのロボットは自由な順序でゴールさせられる
  • (順序制限つきのロボットのゴールさせかたの組み合わせ数) * (残りのロボットの台数)! が答え
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
ll MOD = 1000000007;

struct mint {
  ll x;
  mint(): x(0) { }
  mint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}
  ll get() const { return x; }
  // e乗
  mint pow(ll e) {
    ll a = 1, p = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    return mint(a);
  }
  // Comparators
  bool operator <(mint b) { return x < b.x; }
  bool operator >(mint b) { return x > b.x; }
  bool operator<=(mint b) { return x <= b.x; }
  bool operator>=(mint b) { return x >= b.x; }
  bool operator!=(mint b) { return x != b.x; }
  bool operator==(mint b) { return x == b.x; }
  // increment, decrement
  mint operator++() { x++; return *this; }
  mint operator++(signed) { mint t = *this; x++; return t; }
  mint operator--() { x--; return *this; }
  mint operator--(signed) { mint t = *this; x--; return t; }
  // Basic Operations
  mint &operator+=(mint that) {
    x += that.x;
    if(x >= MOD) x -= MOD;
    return *this;
  }
  mint &operator-=(mint that) {
    x -= that.x;
    if(x < 0) x += MOD;
    return *this;
  }
  mint &operator*=(mint that) {
    x = (ll)x * that.x % MOD;
    return *this;
  }
  mint &operator/=(mint that) {
    x = (ll)x * that.pow(MOD-2).x % MOD;
    return *this;
  }
  mint &operator%=(mint that) {
    x = (ll)x % that.x;
    return *this;
  }
  mint operator+(mint that) const { return mint(*this) += that; }
  mint operator-(mint that) const { return mint(*this) -= that; }
  mint operator*(mint that) const { return mint(*this) *= that; }
  mint operator/(mint that) const { return mint(*this) /= that; }
  mint operator%(mint that) const { return mint(*this) %= that; }
};
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;
  vector<ll> x(n);
  cin >> x;

  mint ret = 1;
  ll used = 0;
  REP(i, n) {
    if(x[i]%2 && x[i]+1==x[i+1]) continue;
    ll tmp = ((x[i]-1)/2 + 1) * 2;
    if(tmp/2 < i+1-used) {
      ret *= i+1-used;
      used++;
    }
  }
  REP(i, n-used) ret *= i+1;

  cout << ret << endl;
  return 0;
}

ARC014 C - 魂の還る場所

AtCoder 競技プログラミング

問題ページ

考えたこと

  • sample1のうちGBGGBGみたいな部分列は一方向から入れ続けても全部消せる
  • 上のような部分列は当然消せる
  • これを消した後はRGBGBRみたいに同じ色が絶対に隣り合わない列となる
  • 筒に入っているボールをできるだけ消すとして考えてみると同じ色のボールが2個以上入ることはなさそう
  • 筒の中に1,2個しか入っていないときに同じ色のボールが来たら当然消せる
  • 3個入っているときには次の色と同じ色のボールを端にしておけば必ず消せる
  • 3色しかないので3個入っているときは必ず消せる
  • 4個以上になることはありえない
  • ということは偶数個の色のボールは全て消せる
  • 奇数個の色の数を答えればよい

かなりきれいで好き

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  string s;
  cin >> n >> s;

  ll r = 0, g = 0, b = 0;
  REP(i, n) {
    if(s[i] == 'R') r++;
    else if(s[i] == 'G') g++;
    else b++;
  }

  cout << r%2 + g%2 + b%2 << endl;

  return 0;
}