2018-04-15

ARC094 D - Worst Case

考えたこと

よくわからないのでとりあえず実験する
A<=Bとか仮定しておくと便利そう
一回目、二回目に小さい順位を取った人が条件を満たすようにしたい
A=8,B=9 みたいなのが来たら下のように構成できて14個

1,71 71,1
2,35 35,2
3,23 23,2
4,17 17,4
5,14 14,5
6,11 11,6
7,10 10,7

x*(x+1) < ABとなるような最大のxを見つけると下のような構成ができる気持ちになる yは単調減少な列

1,y_1
2,y_2
 …
x,y_x

なので大体2x-2人になりそう
問題として A[i] <= x のときや y_j = B[i] のときをどう判定するか
B[i] = y_x みたいなときは B[i] = y_x - 1 とすれば条件を満たせそうな気がしたがy_(x-1) = y_x - 1みたいなときとかいろいろまずいケースがありそう
場合分けを頑張ったりするのかなあと思いいろいろ実験するがよくわからない -----(解説)http://kmjp.hatenablog.jp/entry/2018/04/07/0900を見た-----
2A-2人分は必ず達成できる
以下のように構成すればよい

1,A+B-1
2,A+B-2
  …
A-1,B+1

B+1,A-1
  …
A+B-2,2
A+B-1,1

A<=Bなので (A-x)(B+x) = AB + (A-B)x + x^2 < AB を満たす
上の構成の間である一回目で[A+1,B]位を取り二回目で[A,B-1]位を取る人の組で条件を満たす人が何人いるか
一回目で小さい順位を取った人にできるだけ大きな順位を当てた方がよさそう
したがって(A+1,A+x-1)(A+2,A+x-2)(A+3,A+x-3)…(A+x,A)みたいな組み合わせをしたい
x人全員のスコアがAB未満の条件を満たすような最大のxを求めたい
単調性がありそうなので二分探索をする
xの範囲は[0,B-A]
x人全員について判定をすると二分探索の判定部分の計算量がやばそう
冷静になって考えると (A+1)(A+x-1) が (A+x/2)^2 より大きくなることはなさそう
真ん中の部分だけ考えればいいので判定がO(1)でできる
まとめると 2A-2 + (二分探索で求めた人数) となる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

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

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

  int q;
  cin >> q;
  VI a(q), b(q);
  REP(i, q) {
    cin >> a[i] >> b[i];
    if(a[i] > b[i]) swap(a[i], b[i]);
  }

  REP(i, q) {
    // [lb, ub)
    int lb = 0, ub = b[i]-a[i]+1;
    auto check = [&](int mid) -> bool {
      for(int j=mid/2-2; j<=mid/2+2; ++j) {
        if(j<0 || b[i]-a[i]<j) continue;
        if((a[i]+j)*(a[i]+mid-j) >= a[i]*b[i]) return false;
      }
      return true;
    };
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(check(mid)) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    cout << a[i]*2-2 + lb << endl;
  }

  return 0;
}

2018-04-15

ARC095 E - Symmetric Grid

競技プログラミング AtCoder

問題ページ
E - Symmetric Grid

考えたこと

行、列全体をswapするような操作をしてもその行、列に含まれる文字の集合は変わらない
行と列独立に考えたくなる
行を交換する操作について考える
ある行を二つ取り出してきたときにその二つの行の組み合わせで点対称になるように出来るか
s[i],s[j]に対して(s[i][k],s[j][k]) (0<=k<w) のような組の個数を数える
文字c,dに対して (c,d)の個数 = (d,c)の個数ならok
例としてs[i]="abcb"、s[j]="cdad"みたいな文字列の組に対して判定をしてみる
(a,c)(d,b)(c,a)(b,d)みたいな組ができる
(a,c)の個数=(c,a)の個数=1、(b,d)の個数=(d,b)の個数=1 なのでこれはok
注意としてWが奇数だと一つ真ん中に何でもおける場所が存在する
対応を取るのが不可能な行があったら"NO"
これで対応させるべき行がわかったので点対称になるような位置に置く

0 aabbzz
1 bbaazz
2 cdefgg
3 efcdgg

みたいなのがきたら(0,1)、(2,3)が対応するので

0 aabbzz
2 cdefgg
3 efcdgg
1 bbaazz

にする。Hが奇数のときに注意

列を交換する操作について考える
点対称にするときに対応させられる2列の組について考える
もう行の入れ替えは適切なものになってるので気にしない
するとi列目とj列目が対応する条件は i列目 = j列目の反転になる
行の交換操作と同様に対応させる列がわかる
対応を取るのが不可能な列があったら"NO"
Hが奇数の場合1行対応が取れていなくてもいい行があることに注意
行に関しても列に関しても対応が取れたら"YES"

H,Wが奇数のときに注意

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
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()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
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); }
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<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

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

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

  VI can(h, -1);
  REP(i, h) {
    if(can[i] != -1) continue;
    FOR(j, i+1, h) {
      if(can[j] != -1) continue;
      // s[i]とs[j]を組み合わせて点対称を作れるか
      vector<pair<char, char>> v(w);
      map<pair<char, char>, int> mp;
      REP(k, w) {
        v[k] = {s[i][k], s[j][k]};
        mp[{s[i][k], s[j][k]}]++;
      }
      bool flag = true, able = w%2==1;
      for(auto k: mp) {
        cout << k << endl;
        pair<char, char> p = k.first;
        if(mp.find({p.second, p.first}) == mp.end()) {
          flag = false;
          break;
        }
        // ok
        if(mp[{p.second, p.first}] == k.second) continue;
        // ng
        if(abs(mp[{p.second, p.first}] - k.second) == 1) {
          if(able) able = false;
          else {
            flag = false;
            break;
          }
        }
        if(abs(mp[{p.second, p.first}] - k.second) > 1) {
          flag = false;
          break;
        }
      }
      if(flag) {
        // s[i]とs[j]がok
        can[i] = j;
        can[j] = i;
        break;
      }
    }
  }
  // cout << can << endl;

  vector<string> t1, t2;
  string center;
  vector<bool> used(h, false);
  bool able = h%2==1;
  REP(i, h) {
    if(used[i]) continue;
    if(can[i] == -1) {
      if(able) {
        able = false;
        continue;
      } else {
        cout << "NO" << endl;
        return 0;
      }
    }
    t1.PB(s[i]);
    used[i] = true;
    t2.PB(s[can[i]]);
    used[can[i]] = true;
  }
  reverse(ALL(t2));
  if(h%2) {
    REP(i, h) if(!used[i]) center = s[i];
  }

  vector<string> t(t1);
  if(h%2) t.PB(center);
  REP(i, t2.size()) t.PB(t2[i]);

  // REP(i, t.size()) cout << t[i] << endl;

  able = w%2 == 1;
  used.assign(w, false);
  REP(i, w) {
    if(used[i]) continue;
    // i列目と対応する列を見つける
    int idx = -1;
    REP(j, w) {
      if(i==j || used[i] || used[j]) continue;
      string tmp1 = "", tmp2 = "";
      REP(k, h) tmp1 += t[k][i], tmp2 += t[k][j];
      reverse(ALL(tmp1));
      if(tmp1 == tmp2) {
        idx = j;
        used[i] = used[j] = true;
        break;
      }
    }
    if(idx == -1) {
      if(able) {
        able = false;
      } else {
        cout << "NO" << endl;
        return 0;
      }
    }
  }

  cout << "YES" << endl;

  return 0;
}

2018-04-14

ARC095 D - Binomial Coefficients

競技プログラミング AtCoder

問題ページ D - Binomial Coefficients

考えたこと

C(x,y)はxが大きければ大きいほどよさそう
x = max(a) で固定
O(n)でC(a[n-1],a[i])を全部求めればいい気持ちになるがa<=10^9で無理
よくよく考えるとC(x,y)のyはx/2に近い方がいい
パスカルの三角形を考えると真ん中の方がいいのは証明できそう
C(x,y) = C(x,x-y) なので max(min(a[i],a[n-1]-a[i])) を求める

（二項係数慣れてれば）Cよりこっちのほうが簡単そう

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
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()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
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); }
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<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

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

  int n;
  cin >> n;
  VI a(n);
  REP(i, n) cin >> a[i];

  sort(ALL(a));
  int ma = -1;
  REP(i, n-1) {
    if(min(a[i], a[n-1]-a[i]) > ma) {
      ma = a[i];
    }
  }
  cout << a[n-1] << " " << ma << endl;

  return 0;
}

2018-04-14

ARC095 C - Many Medians

競技プログラミング AtCoder

問題ページ
C - Many Medians

考えたこと

中央値を取りうるのはa[n/2-1]かa[n/2]の二択
n/2番目以降ならa[n/2-1]、それ以外ならa[n/2]
ソートすればいいのになぜか座圧を書く
座圧を書いたあとsampleを見て気づいてソートに書き直す
出すと通る

無駄に時間かけすぎ

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
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()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
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); }
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<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

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

  int n;
  cin >> n;
  VI a(n);
  vector<PII> v(n);
  REP(i, n) cin >> a[i], v[i] = {a[i], i};

  sort(ALL(v));
  int x = v[n/2-1].first, y = v[n/2].first;
  VI ans(n);
  REP(i, n) {
    if(i < n/2) {
      ans[v[i].second] = y;
    } else {
      ans[v[i].second] = x;
    }
  }

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

  return 0;
}

2018-04-13

AOJ2304 Reverse Roads

競技プログラミング AOJ

問題ページ
Reverse Roads | Aizu Online Judge

考えたこと

有向グラフの辺を反転することでs-tフローを最大化する
与えられた辺を無向辺のように扱って両方の向きに辺を張ってフローを流す
最大フローの値はこれで求まる
反転すべき辺を求めるのには残余グラフを使うとよさそう
辺の容量が0で逆辺が1の辺があればその向きにその辺を使っている
使ってる方向が本来与えられた向きと逆であればその辺を反転したとして出力

残余グラフはじめて使った

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
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()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
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); }
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<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

const int MAX_N = 300;
struct edge {int to, cap, rev;};
vector<edge> G[MAX_N+1];
bool used[MAX_N+1];

void add_edge(int from, int to, int cap) {
  G[from].push_back((edge){to, cap, (int)G[to].size()});
  G[to].push_back((edge){from, 0, (int)G[from].size()-1});
}

int dfs(int v, int t, int f) {
  if(v == t) return f;
  used[v] = true;
  REP(i, G[v].size()) {
    edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0) {
      int d = dfs(e.to, t, min(f, e.cap));
      if(d > 0) {
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s, int t) {
  int flow = 0;
  while(true) {
    memset(used, 0, sizeof(used));
    int f = dfs(s, t, INF);
    if(f == 0) return flow;
    flow += f;
  }
}

int g[305][305];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m, s, t;
  cin >> n >> m;
  REP(i, m) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    g[y][x] = i+1;
    add_edge(x, y, 1);
    add_edge(y, x, 1);
  }
  cin >> s >> t;
  s--, t--;

  cout << max_flow(s, t) << endl;
  VI ans;
  REP(i, n) {
    for(edge e: G[i]) {
      // i->e.toの辺について
      if(e.cap == 0 && G[e.to][e.rev].cap == 1) {
        if(g[i][e.to]) {
          ans.PB(g[i][e.to]);
        }
      }
    }
  }
  sort(ALL(ans));
  ans.erase(unique(ALL(ans)), ans.end());
  cout << ans.size() << endl;
  for(int i: ans) cout << i << endl;

  return 0;
}

2018-04-13

AOJ2382 KingSlime

競技プログラミング AOJ

問題ページ
King Slime | Aizu Online Judge

考えたこと

縦横で同じ軸にいるスライムは移動1回でくっつけられそう
sample1を見ると縦横で同じ軸にいるスライムをつないでいってその連結成分にいるスライムは移動1回でまとめられそう
つまり(連結成分の大きさ-1)回移動することになりそう
異なる連結成分に属するスライム同士をくっつけるには全て端に寄せてつなげていくことになりそう
端に寄せるのに(連結成分数)回、寄せたあとくっつけるのに(連結成分数-1)回かかる
ここで端に寄せるときにそもそも端にいるスライムの分は移動させなくて良い
同じ辺に複数スライムがいる場合でもそのスライムは同じ連結成分としてまとまるので引くのは1匹分でよい
連結成分をまとめるところでO(n^2)でちょっと怖いが8secで定数倍軽いしAOJを信じる
連結成分の管理をunionfindでやることにして実装すると通った

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
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()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
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); }
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<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

class UnionFind {
public:
  VI par, s;
  UnionFind(int n=1e5) { init(n); }
  void init(int n=1e5) { par.resize(n); s.assign(n, 1); REP(i, n) par[i] = i; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y];
    else par[y] = x, s[x] = s[x] + s[y];
  }
  bool same(int x, int y) { return find(x) == find(y);}
};

int x[40010], y[40010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, h, w;
  cin >> n >> w >> h;
  bool flag=false;
  REP(i, n) {
    cin >> x[i] >> y[i];
    x[i]--, y[i]--;
    if(x[i]==0 || x[i]==w-1 || y[i]==0 || y[i]==h-1) flag = true;
  }

  UnionFind uf(n);
  REP(i, n) FOR(j, i+1, n) {
    if(x[i] == x[j] || y[i] == y[j]) {
      uf.unite(i, j);
    }
  }

  int ret = 0, cnt = 0;
  REP(i, n) {
    if(i == uf.find(i)) {
      ret += uf.s[uf.find(i)] - 1;
      cnt++;
    }
  }
  if(cnt >= 2) ret += cnt + cnt - 1 - (flag?1:0);

  cout << ret << endl;

  return 0;
}

2018-04-13

AOJ2297 Rectangular Stamps

競技プログラミング AOJ

問題ページ
Rectangular Stamps | Aizu Online Judge

考えたこと

各マスについてempty,R,G,Bの4種類の状態を持ちたい
これが持てると集合を持ちつつ探索していけそう
4^16は無理
考察するとそのマスで必要な情報は最終的な色に達しているかどうかの2種類しかない
集合の状態が2^16に落ちてこれなら持てる
BFSで探索

実装がたいへん

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

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

const int INF = (1LL<<30);

char col[] = {'R', 'G', 'B'};
string board[4];
int n, d[1<<16], h[20], w[20];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;
  REP(i, n) cin >> h[i] >> w[i];
  REP(i, 4) cin >> board[i];

  REP(i, 1<<16) d[i] = INF;
  d[0] = 0;
  queue<int> que;
  que.push(0);

  while(que.size()) {
    int bit = que.front(); que.pop();
    if(bit == (1LL<<16)-1) break;
    // i番目のはんこで左上を(y,x)で色をcとして押す
    REP(i, n) FOR(y, -h[i]+1, 4) FOR(x, -w[i]+1, 4) REP(c, 3) {
      int n_bit = bit;
      FOR(ny, max(0LL, y), min(y+h[i],4LL)) FOR(nx, max(0LL, x), min(x+w[i],4LL)) {
        // 押した結果同じ色なら1に、違う色なら0に
        if(board[ny][nx] == col[c]) n_bit |= 1<<(ny*4+nx);
        else n_bit &= ~(1<<(ny*4+nx));
      }
      if(d[n_bit] == INF) {
        d[n_bit] = d[bit] + 1;
        que.push(n_bit);
      }
    }
  }

  cout << d[(1LL<<16)-1] << endl;

  return 0;
}

ferinの競プロ帳

競プロについてのメモ

ARC094 D - Worst Case

考えたこと

ソースコード

ARC095 E - Symmetric Grid

考えたこと

ソースコード

ARC095 D - Binomial Coefficients

考えたこと

ソースコード

ARC095 C - Many Medians

考えたこと

ソースコード

AOJ2304 Reverse Roads

考えたこと

ソースコード

AOJ2382 KingSlime

考えたこと

ソースコード

AOJ2297 Rectangular Stamps

考えたこと

ソースコード