SRM618 div1 easy Family

考えたこと

サンプルのグラフを書いてみると、parent1[i]とparent2[i]が2つの異なる値で分類できれば可能であると判定できそうなことに気づく。これはparent1[i]とparent2[i]をつないだグラフが2部グラフであるかどうか判定すればできる。提出したら通った。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;

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

VI g[105];
int color[105];

bool dfs(int v, int c) {
  color[v] = c;
  for(int i: g[v]) {
    if(color[i] == c) return false;
    if(color[i] == 0 && !dfs(i, -c)) return false;
  }
  return true;
}

class Family {
   public:
   string isFamily(vector <int> p1, vector <int> p2)
  {
    int n = p1.size();
    REP(i, n) {
      if(p1[i] == -1) continue;
      g[p1[i]].PB(p2[i]);
      g[p2[i]].PB(p1[i]);
    }

    REP(i, n) {
      if(!color[i]) {
        if(!dfs(i, 1)) {
          return "Impossible";
        }
      }
    }
    return "Possible";
  }
};

SRM617 div1 easy MyLongCake

概要

長さnのケーキがあり友人に配るためケーキを切っておきたい。友人には同じ長さの連続したピースのケーキを渡せるようにしたい。来る友人の人数はn以外のnの約数の人数ということしかわかっていない。この条件を満たすような最小のピースの数を出力しろ。

解法

a人来るときは{n/a, 2n/a, 3n/a, …, (a-1)*n/a}の位置を切るしかない。 約数の列挙はO(sqrt(n))でできるので解ける。

#include <bits/stdc++.h>
using namespace std;

class MyLongCake {
   public:
   int cut(int n)
  {
    set<int> st;
    for(int i=2; i*i<=n; ++i) {
      if(n%i==0) {
        for(int j=n/i; j<n; j+=n/i) st.insert(j);
        for(int j=i; j<n; j+=i) st.insert(j);
      }
    }
    return st.size()+1;
  }
};

Tenka1 Programmer Contest C - 4/N

問題ページ C - 4/N

考えたこと

何かうまい構成方法でO(1)？と思ったがよくよく考えると全探索できる。誤差死とオーバーフローに気をつけつつ算数をすると通った。
時間かけすぎで反省。

解法

hとnを決めるとwは一意に決まるのでO(3500²)の探索をする

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

signed main(void)
{
  int n;
  cin >> n;
  FOR(i, 1, 3501) FOR(j, 1, 3501) {
    if(4*i*j-n*i-n*j == 0) continue;
    int k = n*i*j/(4*i*j-n*i-n*j);
    if(1 <= k && 4LL*i*j*k == n*(i*j+j*k+k*i)) {
      cout << i << " " << j << " " << k << endl;
      return 0;
    }
  }
  assert(false);

  return 0;
}

Tenka1 Programmer Contest D - IntegerotS

問題ページ
D - IntegerotS

考えたこと

ナップザック問題っぽさを感じる。Kをそのまま配列に持つのは無理なのでbitが立ってる本数を配列に持つのかなあと考えるがうまくいきそうにない。
いろいろ実験してるとKのある桁を1から0にしたとき、それ以下の桁は全て1にするべきなことに気づく。取る数字のorを全て取ったものをXとすると、Xは高々30通りしか存在せず、O(n)で各Xについて最善な取り方が求まるので計算量的に問題ない。

#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 a[100010], b[100010];
signed main(void)
{
  int n, k;
  cin >> n >> k;
  REP(i, n) cin >> a[i] >> b[i];

  int ret = 0;
  REP(j, n) {
    bool flag = true;
    REP(l, 30) {
      if((a[j]>>l)&1 && !((k>>l)&1)) {flag = false; break;}
    }
    if(flag) ret += b[j];
  }

  int ans = ret;
  REP(i, 30) {
    // kの上位ibit目が1 → そこを0にしてそこより下位のbitを1に
    if(k>>i&1) {
      int c = k&~(1LL<<i);
      c |= (1LL<<i)-1;
      // a[j]でbitが立っていてcでbitが立っていない → だめ
      int ret = 0;
      REP(j, n) {
        bool flag = true;
        REP(l, 30) {
          if((a[j]>>l)&1 && !((c>>l)&1)) {flag = false; break;}
        }
        if(flag) ret += b[j];
      }
      chmax(ans, ret);
    }
  }
  cout << ans << endl;

  return 0;
}

Tenka1 Programmer Contest E - CARtesian Coodinate

問題ページ
E - CARtesian Coodinate

解法

解説を見た。
https://img.atcoder.jp/tenka1-2017/editorial.pdf
www.youtube.com

まず、N点からのマンハッタン距離の和が最小になる点について考える。マンハッタン距離はx座標、y座標それぞれ独立に足すことができるのx方向とy方向でそれぞれ独立に考えることができる。また、距離の和が最小になる点は中央値になる。中央値から右にΔt動かしたとすると(右の頂点の数)Δtの分距離の総和が減るが、(左の頂点の数)Δtの分距離の総和が増えるため総和が減ることはありえない。左に動かすのも同様。よって中央値から動かして得になるケースは絶対に存在しない。

(Δt*2減るがΔt*3増えるので得しない)

よって、交点の座標の中央値を求めることができれば解ける。交点はO(N^2)個存在するので愚直に全列挙するのは間に合わない(はず)。二分探索することを考えると座標sより左側にある交点を高速に列挙できれば二分探索が可能。
座標sの地点で直線が並ぶ順番と左側に交点が存在しない十分左の座標で直線が並ぶ順番はそれぞれO(N)で求めることができる。このとき、交点は順番が入れ替わっている直線の数となり、これは転倒数となる。

転倒数はBITを用いてO(NlogN)で求めることができるので二分探索の判定部分はO(NlogN)で可能。したがって求めることができる。

学び

マンハッタン距離の総和は次元ごとに独立に考えられる。総和が最小になる地点は中央値。
直線の交点の数は転倒数に帰着できる。

#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 n;
int a[40010], b[40010], c[40010];
pair<double, int> p[40010], p2[40010], p3[40010];

ll con;

int bit[40010], m = 40010;

//0からi-1番目までの和
int sum(int i) {
  i++;
  int s = 0;
  while(i > 0) {
    s += bit[i];
    i -= i&-i;
  }
  return s;
}

//i番目(0-index)にxを加える
void add(int i, int x) {
  i++;
  while(i <= m) {
    bit[i] += x;
    i += i&-i;
  }
}

bool check(double mid) {
  // 数列を求める
  // 画像と数列の並べ方が反対になってる
  REP(i, n) {
    int idx = p[i].second;
    p2[i] = {-(double)a[idx]/b[idx]*mid+(double)c[idx]/b[idx], i};
  }
  sort(p2, p2+n);
  // p2.secondの転倒数を求める
  memset(bit, 0, sizeof(bit));
  ll ans = 0;
  REP(i, n) {
    ans += i - sum(p2[i].second);
    add(p2[i].second, 1);
  }
  return ans >= con;
}

bool check2(double mid) {
  // 数列を求める
  REP(i, n) {
    int idx = p3[i].second;
    p2[i] = {-(double)b[idx]/a[idx]*mid+(double)c[idx]/a[idx], i};
  }
  sort(p2, p2+n);
  // p2.secondの転倒数を求める
  memset(bit, 0, sizeof(bit));
  ll ans = 0;
  REP(i, n) {
    ans += i - sum(p2[i].second);
    add(p2[i].second, 1);
  }
  return ans >= con;
}

signed main(void)
{
  cin >> n;
  REP(i, n) {
    cin >> a[i] >> b[i] >> c[i];
    p[i] = {-(double)a[i]/b[i], i};
    p3[i] = {(double)b[i]/a[i]*INF+(double)c[i]/a[i], i};
  }
  sort(p, p+n); sort(p3, p3+n);
  reverse(p, p+n);

  // 中央値はcon番目
  con = n*(n-1)/4 + !!(n*(n-1)%4);

  // x座標
  // 小数の二分探索は定数回で固定して回す
  double low = -1e10, high = 1e10;
  REP(_, 300) {
    double mid = (low+high)/2;
    if(check(mid)) {
      high = mid;
    } else {
      low = mid;
    }
  }
  cout << fixed << setprecision(15) << low << " ";

  // y座標
  low = -1e10, high = 1e10;
  REP(_, 300) {
    double mid = (low+high)/2;
    if(check2(mid)) {
      high = mid;
    } else {
      low = mid;
    }
  }
  cout << low << endl;

  return 0;
}

ARC039 C - 幼稚園児高橋君

問題ページ
C: 幼稚園児高橋君 - AtCoder Regular Contest 039 | AtCoder

考えたこと

解説を見た。
4方向の近傍だけ持ってればよくて通ったところとその近傍しか情報いらないからmapでうまく持てばO(KlogK)で解ける。linked listを思い出しつつバグらせないように気をつけながら実装をすると通った。

//#define __USE_MINGW_ANSI_STDIO 0
#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[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};

// x, y, dir の 最近傍の未訪問座標
// dir 0,右 1,下 2,左 3,上
map<VI, PII> mp;

void update(int x, int y) {
  // (x, y)から右下左上への接続をする
  REP(i, 4) {
    // 存在しないなら生成
    if(mp.find({x, y, (int)i}) == mp.end()) {
      mp[{x, y, (int)i}] = {x+dx[i], y+dy[i]};
    }
  }
  // (x, y)の近傍から(x, y)への接続
  // 右の左 = 左
  PII p = mp[{x, y, 0}];
  mp[{p.first, p.second, 2}] = mp[{x, y, 2}];
  // 左の右 = 右
  p = mp[{x, y, 2}];
  mp[{p.first, p.second, 0}] = mp[{x, y, 0}];
  // 上の下 = 下
  p = mp[{x, y, 3}];
  mp[{p.first, p.second, 1}] = mp[{x, y, 1}];
  // 下の上 = 上
  p = mp[{x, y, 1}];
  mp[{p.first, p.second, 3}] = mp[{x, y, 3}];
}

signed main(void)
{
  int n;
  string s;
  cin >> n >> s;

  update(0, 0);
  int x = 0, y = 0;
  REP(i, n) {
    if(s[i] == 'R') {
      PII p = mp[{x, y, 0}];
      x = p.first, y = p.second;
      update(p.first, p.second);
    } else if(s[i] == 'D') {
      PII p = mp[{x, y, 1}];
      x = p.first, y = p.second;
      update(p.first, p.second);
    } else if(s[i] == 'L') {
      PII p = mp[{x, y, 2}];
      x = p.first, y = p.second;
      update(p.first, p.second);
    } else if(s[i] == 'U') {
      PII p = mp[{x, y, 3}];
      x = p.first, y = p.second;
      update(p.first, p.second);
    }
  }
  cout << x << " " << y << endl;

  return 0;
}

AOJ 2429 marukaite

問題ページ
marukaite | Aizu Online Judge

考えたこと

解説を見た。

最小費用流を流すところは書けたが操作の復元に手間取った…最小費用流を行ったあと、容量が0の辺が存在すればその辺には流れたといえる。つまりR_iからC_jへの辺の容量が0であれば(i, j)は最終的に'o'であるといえる。よって最初の盤面と最終的な盤面を比較して異なる座標に操作を行ったといえる。

//#define __USE_MINGW_ANSI_STDIO 0
#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};

#define MAX_V 10000
struct edge { int to, cap, cost, rev; };

int V;
vector<edge> G[MAX_V];
int dist[MAX_V], prevv[MAX_V], preve[MAX_V];

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

int min_cost_flow(int s, int t, int f) {
  int res = 0;
  while(f > 0) {
    fill(dist, dist+V, INF);
    dist[s] = 0;
    bool update = true;
    while(update) {
      update = false;
      REP(v, V) {
        if(dist[v] == INF) continue;
        REP(i, G[v].size()) {
          edge &e = G[v][i];
          if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
            dist[e.to] = dist[v] + e.cost;
            prevv[e.to] = v;
            preve[e.to] = i;
            update = true;
          }
        }
      }
    }
    if(dist[t] == INF) return -1;

    int d = f;
    for(int v = t; v != s; v = prevv[v]) {
      chmin(d, G[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res += d * dist[t];
    for(int v = t; v != s; v = prevv[v]) {
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}

int w[105][105], e[105][105];
string s[105], t[105];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) REP(j, n) cin >> w[i][j];
  REP(i, n) REP(j, n) cin >> e[i][j];
  REP(i, n) cin >> s[i];
  REP(i, n) t[i] = string(n, '.');

  // 'o'の位置のeraseコストの和を求める
  int sum = 0;
  REP(i, n) REP(j, n) if(s[i][j] == 'o') sum += e[i][j];

  // supersource:0, supersink:1, 行:2からn+1, 列:n+2から2*n+1
  V = 2*n+2;
  REP(i, n) add_edge(0, i+2, 1, 0);
  REP(i, n) add_edge(n+2+i, 1, 1, 0);
  REP(i, n) REP(j, n) {
    if(s[i][j] == 'o') {
      add_edge(i+2, j+n+2, 1, -e[i][j]);
    } else {
      add_edge(i+2, j+n+2, 1, w[i][j]);
    }
  }

  cout << sum + min_cost_flow(0, 1, n) << endl;

  // capが0の辺は使用している→最終盤面で'o'
  FOR(i, 2, n+2) for(edge e: G[i]) {
    if(e.cap == 0 && n+2 <= e.to && e.to < 2*n+2) {
      t[i-2][e.to-n-2] = 'o';
    }
  }

  // 最初の盤面から変化していればその座標は操作している
  vector<PII> ans;
  REP(i, n) REP(j, n) {
    if(s[i][j] == t[i][j]) continue;
    ans.PB({i, j});
  }

  cout << ans.size() << endl;
  for(auto i: ans) {
    cout << i.first+1 << " " << i.second+1;
    if(s[i.first][i.second] == '.') {
      cout << " write" << endl;
    } else {
      cout << " erase" << endl;
    }
  }

  return 0;
}