ferinの競プロ帳

競プロについてのメモ

AGC005 C - Tree Restoring

問題ページ
C: Tree Restoring - AtCoder Grand Contest 005 | AtCoder

解法

まず、max(a[i]) = Xの距離のグラフをつくることを考える。このグラフをつくるのに
* Xが偶数のとき
距離がX/2の頂点が1個、X/2+1~Xまでの頂点が2個ずつ必要
* Xが奇数のとき
距離がceil(X/2)+1~Xの頂点が2個ずつ必要
となる。このグラフに頂点を付け加えていくことを考えると
* Xが偶数のとき
距離がX/2+1~Xまでの頂点は付け加えられる
* Xが奇数のとき
距離がceil(X/2)+1~Xの頂点は付け加えられる となる。 f:id:ferin_tech:20171016225346p:plain

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const int INF = (1LL<<30);
#else
const ll INF = (1LL<<60);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[105], cnt[105];
signed main(void)
{
  int n;
  cin >> n;
  int ma = 0;
  REP(i, n) {
    int a;
    cin >> a;
    cnt[a]++;
    chmax(ma, a);
  }

  if(ma%2==0) {
    for(int i=ma; i>=0; --i) {
      if(i > ma/2) {
        if(cnt[i] < 2) {
          cout << "Impossible" << endl;
          return 0;
        }
      } else if(i == ma/2) {
        if(cnt[i] != 1) {
          cout << "Impossible" << endl;
          return 0;
        }
      } else {
        if(cnt[i]) {
          cout << "Impossible" << endl;
          return 0;
        }
      }
    }
  } else {
    for(int i=ma; i>=0; --i) {
      if(i > ma/2+1) {
        if(cnt[i] < 2) {
          cout << "Impossible" << endl;
          return 0;
        }
      } else if(i == ma/2+1) {
        if(cnt[i] != 2) {
          cout << "Impossible" << endl;
          return 0;
        }
      } else {
        if(cnt[i]) {
          cout << "Impossible" << endl;
          return 0;
        }
      }
    }
  }
  cout << "Possible" << endl;

  return 0;
}

ARC069 E - Frequency

問題ページ
E: Frequency - AtCoder Regular Contest 069 | AtCoder

解法

辞書順最小なのでその時点で追加できる最小のものを追加していくようにする。

0 1 2 3 4 5 6 7 8 9
1 2 1 3 2 4 2 5 8 1 -> 8が3(=(8-5)*(8以上の数の個数))回追加 (最大の石の数は8)
1 2 1 3 2 4 2 5 5 1 -> 7が2(=(5-4)*(5以上の数の個数))回追加 (最大の石の数は5)
1 2 1 3 2 4 2 4 4 1 -> 5が3回追加 (最大の石の数は4)
1 2 1 3 2 3 2 3 3 1 -> 3が4回追加 (最大の石の数は3)
1 2 1 2 2 2 2 2 2 1 -> 1が7回追加 (最大の石の数は2)
1 1 1 1 1 1 1 1 1 1 -> 0が10回追加(最大の石の数は1)
0 0 0 0 0 0 0 0 0 0

a[i]が取りうる値を昇順に並べたものをX_iとする。X_i以上で最も左に存在するindexが(X_i以上のa[i]の個数)*(X_i-X_{i-1})回追加される。したがってX_i以上の個数とX_i以上で最も左にあるindexを保持しておけば計算できる。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const int INF = (1LL<<30);
#else
const ll INF = (1LL<<60);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[100010], cnt[100010], l[100010], ans[100010];

// xx, yy, zzにそれぞれ座圧する元の配列を突っ込むとx, y, zが座圧された配列で返ってくる
// zip[座圧前] = 座圧後、unzip[座圧後] = 座圧前
VL xx, x, unzip(100010);
unordered_map<int, int> zip;
void compress() {
  x = xx;
  sort(ALL(xx));
  xx.erase(unique(ALL(xx)), xx.end());
  REP(i, xx.size()) {zip[xx[i]] = i; unzip[i] = xx[i];}
  REP(i, x.size()) x[i] = zip[x[i]];
}

signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) {
    cin >> a[i];
    xx.PB(a[i]);
  }
  compress();

  memset(l, -1, sizeof(l));
  int ma = 0;
  REP(i, n) {
    chmax(ma, (int)x[i]);
    cnt[x[i]]++;
    if(l[x[i]] == -1) l[x[i]] = i;
  }
  for(int i=ma; i>=1; --i) cnt[i-1] += cnt[i];
  int mi = INF;
  for(int i=ma; i>=0; --i) {
    chmin(mi, l[i]);
    l[i] = mi;
  }
  REP(i, ma+1) {
    int tmp = i==0 ? xx[i] : xx[i] - xx[i-1];
    ans[l[i]] += cnt[i] * tmp;
  }

  REP(i, n) cout << ans[i] << endl;

  return 0;
}

SRM625 div1 easy PalindromePermutations

解法

まず、回文が存在する条件として
* それぞれの文字種の個数が全て偶数
* 一つの文字種だけ奇数でそれ以外は偶数
のいずれかの条件を満たす必要がある。文字種ごとに文字列内の個数を数え、奇数のものが2個以上あれば存在しないので0を出力する。
cnt[i] = 文字種iの個数とすると、文字列を並べ替えるパターン数は (|S|!)/(cnt[0]!cnt[1]!cnt[25]!) となる。回文の数は (|S|/2)! / ((cnt[0]/2)!(cnt[0]/2)!(cnt[0]/2)!) なので計算すればできる。オーバーフローに注意。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

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); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int cnt[30];

class PalindromePermutations {
   public:
   double palindromeProbability(string word)
  {
    memset(cnt, 0, sizeof(cnt));
    for(char c: word) cnt[c-'a']++;
    bool ng = false;
    int sum = 0;
    REP(i, 26) {
      if(!ng && cnt[i]%2) ng = true;
      else if(ng && cnt[i]%2) return 0;
      sum += cnt[i];
    }
    double ret = 1;
    FOR(i, (sum/2)+1, sum+1) {
      ret /= i;
    }
    REP(i, 26) {
      FOR(j, cnt[i]/2+1, cnt[i]+1) {
        ret *= j;
      }
    }
    return ret;
  }
};

SRM624 div1easy BuildingHeights

考えたこ

題意がよくわからなかったのでサンプルを試してみると、同じ高さのビルをi個(1<=i<=N)つくるために必要なコストをA[i]としたとき、A[1]^A[2]^…A[N]を出力すればよさそう。離れた階層のビルの高さを同じにする利点はないのでソートして考える。
dp[i][j] = (i+2個同じ高さのビルをつくる際にheights[j]の高さに合わせるときのコスト)をO(N^2)で計算できれば解けそう。i=0のときは階差数列を求めれば良い。DPテーブルを書いていると累積和っぽくやればできそうなことに気づく。i=0以外のときはdp[i][j] = dp[i-1][j] + (heights[j+i+1] - heights[j])でdpの更新を行えるのでO(N^2)でできる。
あとは各iについて最も小さいdp[i][j]の値を求めそのxorを出力すれば良い。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

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); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[4010][4010];
class BuildingHeights {
  public:
  int minimum(vector <int> heights)
  {
    int n = heights.size();
    sort(ALL(heights));

    int ret = 0;
    REP(i, n-1) {
      int mi = INF;
      REP(j, n-i-1) {
        dp[i][j] = heights[j+i+1] - heights[j];
        if(i > 0) dp[i][j] += dp[i-1][j+1];
        chmin(mi, dp[i][j]);
      }
      ret ^= mi;
    }

    return ret;
  }
};

SRM623 div1easy UniformBoard

考えたこ

PをAに置き換えるためにはPをどこか別の空マスに移し、Aをどこかから持ってくるため2手かかる。.をAに置き換えるためには1手かかる。
ある長方形の範囲を条件を満たす範囲とできるかを考える。Aが2個、Pが1個、.が1個ある範囲を全てAに置き換えるためには、
* Aが他の部分に2個以上存在する
* Pが1個→2手 .が1個→1手 より 3手 <= K
の条件を満たす必要がある。したがって、長方形の範囲内のP、A、.の数を高速に求める必要がありこれは累積和で前計算しておくことでO(1)でできる。長方形はO(N^4)個存在するため合計O(N^4)で解くことが出来る。

考察はすぐにできたが実装でバグらせて時間を掛けて反省。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int cnt[25][25][3];
class UniformBoard {
  public:
  int getBoard(vector <string> board, int K)
  {
    int n = board.size();
    memset(cnt, 0, sizeof(cnt));
    FOR(i, 1, n+1) FOR(j, 1, n+1) {
      cnt[i][j][0] = cnt[i-1][j][0] + cnt[i][j-1][0] - cnt[i-1][j-1][0];
      if(board[i-1][j-1] == 'A') cnt[i][j][0]++;
    }
    FOR(i, 1, n+1) FOR(j, 1, n+1) {
      cnt[i][j][1] = cnt[i-1][j][1] + cnt[i][j-1][1] - cnt[i-1][j-1][1];
      if(board[i-1][j-1] == 'P') cnt[i][j][1]++;
    }
    FOR(i, 1, n+1) FOR(j, 1, n+1) {
      cnt[i][j][2] = cnt[i-1][j][2] + cnt[i][j-1][2] - cnt[i-1][j-1][2];
      if(board[i-1][j-1] == '.') cnt[i][j][2]++;
    }

    int all = cnt[n][n][0];
    if(cnt[n][n][0] == 0) return 0;

    int ret = 0;
    FOR(sx, 1, n+1) FOR(sy, 1, n+1) FOR(gx, sx, n+1) FOR(gy, sy, n+1) {
      int apple = cnt[gy][gx][0] - cnt[sy-1][gx][0] - cnt[gy][sx-1][0] + cnt[sy-1][sx-1][0];
      int pear = cnt[gy][gx][1] - cnt[sy-1][gx][1] - cnt[gy][sx-1][1] + cnt[sy-1][sx-1][1];
      int emp = cnt[gy][gx][2] - cnt[sy-1][gx][2] - cnt[gy][sx-1][2] + cnt[sy-1][sx-1][2];
      int menseki = (gy-sy+1)*(gx-sx+1);
      // 交換不可能
      if(cnt[n][n][2] == 0) {
        if(menseki == apple) chmax(ret, apple);
        continue;
      }
      if(all - apple < menseki - apple) continue;
      if(pear*2 + emp <= K) chmax(ret, menseki);
    }
    return ret;
  }
};

SRM621 div1 easy RadioRange

考えたこ

中心が(0, 0)で半径がrの円と中心が(X, Y)で半径がRの円が共有する部分を持つ条件について考える。半径rが (2円が外接する半径r_1)<= r < (2円が内接する半径r_2)の条件を満たすときと言い換えられる。
r_1 = max(0, sqrt(XX+YY)) (円の中に(0, 0)が存在する場合0)
r_2 = min(Z, sqrt(XX+YY))
とできるのでそれぞれの円について[r_1, r_2]を求めこの範囲の和集合を取ることで共有部分を持つ区間を求めることができる。

和集合を取る部分をバグらせまくったりオーバーフローさせたりいろいろ反省。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

pair<double, double> p[105];
class RadioRange {
  public:
  double RadiusProbability(vector <int> X, vector <int> Y, vector <int> R, int Z)
  {
    int n = X.size();
    REP(i, n) {
      double l = sqrt((double)X[i]*X[i]+(double)Y[i]*Y[i]);
      p[i] = {max(l-R[i], 0.0), min(l+R[i], (double)Z)};
    }
    sort(p, p+n);
    double sum = 0;
    double l = 0, r = 0;
    REP(i, n) {
      if(p[i].first >= Z) break;
      if(p[i].first>=r) {
        l = p[i].first, r = p[i].second;
        sum += r-l;
      } else if(p[i].second>=r) {
        sum += p[i].second - r;
        r = p[i].second;
      }
    }

    return 1-sum/Z;
  }
};

SRM619 div1easy SplitStoneGame

考えたこ

ゲームで石の山だしgrundy数かなあと思いつつ問題文を読む。敗北条件を考えると石の数が1個以下の山しか存在しない場合か山が2個以下しかない場合になる。サンプルを読んでいると山の石の数は2個以上か1個の2パターンしか考慮しなくていいことに気づく。1個の山の数をA、2個以上の山の数をBと置く。
それぞれの手番でのA, Bの遷移がどうなってるか考えると
* Bがマイナス1 (B>=3)
* Aがマイナス1 (A>=1, B>=2)
* Bがプラス1、Aがマイナス2 (A>=2, B>=1)
の3通りになる。
AとBからwinとloseの状態を一意に決めることができ、メモ化再帰で求めることでできる。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

int dp[55][55];

int dfs(int A, int B) {
  if(dp[A][B] != -1) return dp[A][B];
  if(A+B <= 2 || B == 0)  return dp[A][B] = 0;

  bool res = true;
  if(B >= 3) res &= dfs(A, B-1);
  if(A >= 1 && B >= 2) res &= dfs(A-1, B);
  if(A >= 2 && B >= 1) res &= dfs(A-2, B+1);
  return dp[A][B] = !res;
}

class SplitStoneGame {
   public:
   string winOrLose(vector <int> number)
  {
    int a = 0, b = 0;
    REP(i, number.size()) {
      if(number[i] == 1) a++;
      else b++;
    }
    memset(dp, -1, sizeof(dp));
    if(dfs(a, b) == 0) return "LOSE";
    return "WIN";
  }
};