kurarrr's memooo

主に競プロ備忘録

D - Restoring Road Network

AtCoder 競プロ

問題概要

N個のノードのグラフの全点間最短距離A_ijが与えられる.
これを満たすような辺の張り方は存在するか.あるなら辺のコストの総和を求めよ.
1 <= N <= 300, 1 <= A_ij <= 109

解法

各頂点間について,A_ijの辺があるか,辺が存在しないかのいずれかである.
A_ijを元にWarshall Floydで全点間最短距離B_ijを求める.
A_ij != B_ijなら条件を満たすグラフは存在しない.
次に条件を満たすグラフが存在するとして,その間に辺があるか存在しないかを判定する.
辺が存在しない <-> 迂回路が存在する
ということであるから,迂回する頂点kとして
a[i][j] = a[i][k] + a[k][j] であれば,辺が存在しない.
そうでないような辺を全て足して出力する.

メモ

各辺について毎回Dijkstraをする解法が思いついたがこれだと間に合わず.
union-findを使って連結でなければ無条件で辺を足し,連結でないならばDijkstraで辺が必要か判定,とやるとギリギリ間に合った.

想定解法のような柔軟な解法が出したい.
辺の存在が迂回路で確かめられることは覚えておこう.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 302;

using PP = pair<ll,P>;

ll a[MAX_N][MAX_N],b[MAX_N][MAX_N];

int main(){
  int N;
  cin >> N;
  rep(i,N) rep(j,N) scanf("%lld",&a[i][j]);
  bool conf = true;
  rep(i,N) conf &= (a[i][i]==0LL);
  rep(i,N-1) REP(j,i+1,N) conf &= (a[i][j]==a[j][i]);
  if(!conf){
    cout << "-1" << endl;
    return 0;
  }
  rep(i,N) rep(j,N) b[i][j] = a[i][j];
  rep(i,N) rep(j,N) rep(k,N) b[i][j] = b[j][i] = min(b[i][j],b[i][k]+b[j][k]);
  ll ans = 0LL;
  rep(i,N-1) REP(j,i+1,N){
    if(b[i][j]!=a[i][j]){
      cout << "-1" << endl;
      return 0;
    }else{
      bool pls = true;
      rep(k,N){
        if(k==j||k==i) continue;
        // 迂回路が存在するか?
        pls &= (b[i][k]+b[k][j]!=b[i][j]);
      }
      if(pls) ans += b[i][j];
    }
  }
  cout << ans << endl;
  return 0;
}

ARC 072 D - Alice&Brown

AtCoder 競プロ ゲーム

問題概要

2つの山にX,Y個の石が置かれている.
プレイヤーは一つの山から2i個(2<=2i<=XorY)とってもう片方の山にi個置くことができる.
石が取れなくなったら負け.
どちらのプレイヤーが勝つか.
1 <= X,Y <= 1018

解法

とりあえず実験してみる.
X<=1 & Y <= 1 の時は必敗で,B勝ち.
solve(i, j,'A') := X=i, Y=jはAであるか？とすると,
solve(i, j,'A') = (i, jから移動できるパターンのいずれかがBである ->必敗形で相手に手番を渡せる )
solve(i, j,'B') = (i, jから移動できるパターンの全てがAである -> どう動いても相手に必勝形で渡してしまう)
として遷移を書き, 10x10ぐらいで試すと,

B B A A A A A A A A
B B B A A A A A A A
A B B B A A A A A A
A A B B B A A A A A
A A A B B B A A A A
A A A A B B B A A A
A A A A A B B B A A
A A A A A A B B B A
A A A A A A A B B B
A A A A A A A A B B

となり, abs(X-Y) <= 1で勝敗が判定できることが分かる.

メモ

傾き-2,-1/2で移動できることが分かると簡単にプロットできるみたいだった.
実験すればできる問題だったが,証明力も磨きたい.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;

char res[101][101];

bool solve(int i,int j,char t){
  if(res[i][j]!='X'){
    return res[i][j] == t;
  }
  bool ret;
  if(t=='A'){
    ret = false;
    REP(k,1,i/2+1) ret |= solve(i-2*k,j+k,'B');
    REP(k,1,j/2+1) ret |= solve(i+k,j-2*k,'B');
    if(ret) res[i][j] = 'A';
    else res[i][j] = 'B';
  }else{
    ret = true;
    REP(k,1,i/2+1) ret &= solve(i-2*k,j+k,'A');
    REP(k,1,j/2+1) ret &= solve(i+k,j-2*k,'A');
    if(ret) res[i][j] = 'B';
    else res[i][j] = 'A';
  }
  return ret;
}

int main(){
  ll X,Y; cin >> X >> Y;
  // rep(i,100) rep(j,100) res[i][j] = 'X';
  // res[0][0] = res[0][1] = res[1][0] = res[1][1] = 'B';
  // rep(i,10){
  //   rep(j,10){
  //     cout << (solve(i,j,'A') ? 'A' : 'B') << " ";
  //   }
  //   cout << "" << endl;
  // }
  if(abs(X-Y)>1) cout << "Alice" << endl;
  else cout << "Brown" << endl;
  return 0;
}

CODE FESTIVAL 2016 Grand Final(Parallel) B - Inscribed Bicycle

AtCoder 競プロ

問題概要

A(x1,y1), B(x2,y2), C(x3,y3)が与えられる.
ABC内部に半径の同じ円を2つ描く時,最大の半径を求めよ.

解法

BC,CA,ABをそれぞれa,b,cとする.
またcが最大の辺とする.
内接円の中心O,半径r, 内部に描く二つの円の半径をxとすると,以下のようになる.
f:id:kurarrr:20180124192735p:plain
(図が汚いが各円と辺は接している.)
ODEとOABは相似なため,DE = c * (r-x) / x,
DE = 2x なので c(r-x)/x = 2xを解けば良い.

メモ

中学受験っぽい.内心に注目するのが出てこなかった.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;

int main(){
  double x1,y1,x2,y2,x3,y3;
  cin >> x1 >> y1;
  cin >> x2 >> y2;
  cin >> x3 >> y3;
  double a,b,c,r,d,x;
  a = hypot(x1-x2,y1-y2);
  b = hypot(x2-x3,y2-y3);
  c = hypot(x3-x1,y3-y1);
  r = abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))/(a+b+c);
  d = max(a,max(b,c));
  x = d/(2+d/r);
  printf("%.12lf",x);
  return 0;
}

AGC 010 B - Boxes

AtCoder 競プロ

問題概要

N個の数列{a_i} (1<=i<=N)に対して,
数字iを選び,全ての1<=j<=Nに対し, a_(i+j)%N を -jする
という操作を行う.

全てのaiを0にすることができるか.
1 <= N <= 105, 1 <= a_i <= 109

解法

1回の操作を行うと,合計は+N(N+1)/2されるので,合計をこれで割ると何回操作が行われるかがわかる.これをk回とする.
(N(N+1)/2で割って余りが出る場合はNOである)
ここで b_i = a_(i+1) - a_i に注目すると,1回の操作で1つが+(N-1)され,他が-1される(*)ことがわかる.
つまり,{b_i}に対してこの操作をk回繰り返して,全て0にできるか.という問題になる.

ここで,(*)の操作を以下のように分解すると,
1. 全て-1する
2. 一つ選び+Nする
操作はどの順番で行っても良い為,最初に全て-kしておき+Nをk回繰り返して0にできるか.という問題になる.
{b_i}の合計が0であることは b_i = a_(i+1) - a_iより明らかなので,
{b_i - k}が全てNの倍数で負であることが必要十分条件となる.

メモ

諸々エッセンスが詰まってそうな問題だった.
数列の操作が苦手なので押さえておきたい.
最初に考えること -> 操作は何回あるか?
連続して足していく -> 階差数列
数列の操作 -> 操作の分解,逆操作
この問題を思い出した.
こういう操作典型っぽい.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;
int a[MAX_N];

int main(){
  ll N; cin >> N;
  ll ss = 0LL;
  rep(i,N){
    scanf("%d",a+i);
    ss += a[i];
  }
  bool ans = (ss%(N*(N+1)/2) == 0LL);
  ss /= (N*(N+1)/2);
  rep(i,N){
    ll b = (a[(i+1)%N] - a[i]);
    b -= ss;
    ans &= (b<=0LL && b%N==0LL);
  }
  if(ans) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

ARC 089 D - Checker (500)

AtCoder 競プロ 累積和

問題概要

N個の点(xi,yi)と色(B|W),自然数Kが与えられる.
幅Kの市松模様で,(xi,yi)を与えらえれた色にするという希望を最大何個満たすことができるか.
1 <= N <= 105, 1 <= K <= 103, 0 <= xi,yi <= 109

解法

全てのマスに対して,(x,y)の色C(x,y)は,C(x,y) = C(x+2K,y) = C(x,y+2K)なので,
x,y %= 2Kとして 0 <= x,y < 2Kで考えて良い.
また,C(x,y) != C(x+K,y)であるから,C(x,y)=W <-> C(x+K,y)=B より,
全てC(x,y)をBにできるか,と言い換えることができる.

市松模様の黒正方形の左下を決めてやると模様を確定させることができるので,
黒正方形の左下(xs,ys) (0<=x<=2K-1,0<=y<=K-1)を全て試せば全パターンが試せる.
矩形領域内の総和は二次元累積和を使うと前処理O(K2),クエリO(1)で出せるのでO(N+K2)で十分間に合う.

解説と解説放送では別の方法を提示していた.
解説はimos法で,左下(xs,ys)としてK*Kの領域を取った時(xi,yi)が入るような正方形区間,
すなわち xi-K+1<=xs<=xi, yi-K+1<=ys<=yi と xi+1<=xs<=xi+2K,yi+1<=ys<=yi+2K に全て+1する.(後半の領域はmod2Kをとるとxi,yiと重なる)
全てのマスに+1していたのでは間に合わないのでimos法を使わないとだめ.
なお,0<=x,y<=2K-1でははみ出してしまうので,0<=x,y<=4K-1でやっといて,
0<=x,y<=2K-1からはみ出しているx,yにはS[x%2K][y%2K] += S[x][y] とする.

解説放送の方法ではシンプルに
S[x][y] = sum(0<=i<=x, 0<=j<=y) (a[i][j])とすると
sum(x1<=x<=x2, y1<=y<=y2)(a[x][y]) = S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1]
で求められることを用いてxs,ysを左下にした時の5つの黒正方形領域の和を求めている.
なお前処理としてS[x][y]を求めるのは
S[x][y] = a[x][y] + S[x-1][y] + S[x][y-1] - S[x-1][y-1] で求められる.
(横に足していって縦に足していってもOK)

コードでは条件分岐させたくないのでx,yを+1して,a[0][y] = a[x][0] = 0としている.
本来は0<=x<=2K-1,0<=y<=K-1だが,(x,y)を黒にした時k個条件を満たすならば, (x,y)を白左下にすればN-k個条件を満たすことを用いて,0<=x,y<=K-1で済んでいる.

メモ

実装で色々ミスして間に合わなかった.
二次元累積和 -> 区間内の和を求める
imos法 -> 区間に値を足す
というのが実は区別がついていなかったので色々為になった.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 2003;

int N,K,c[MAX_N][MAX_N],s[MAX_N][MAX_N];

void prepare(){
  REP(x,1,2*K+2)
    REP(y,1,2*K+2) s[x][y] = c[x][y] + s[x-1][y] + s[x][y-1] - s[x-1][y-1];
}

int query(int x1,int y1,int x2,int y2){
  // return sum(x1<=x<=x2,y1<=y<=y2)
  if(x1>x2||y1>y2) return 0;
  else return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N >> K;
  fill(c[0],c[MAX_N-1],0);
  rep(i,N){
    int x,y; char cc;
    cin >> x >> y >> cc;
    if(cc=='B') x += K;
    x %= (2*K); y %= (2*K);
    c[x+1][y+1]++;
  }
  prepare();
  int ans = -INF;
  REP(x,1,K+1) REP(y,1,K+1){
    int temp = query(x,y,x+K-1,y+K-1) + query(x+K,y+K,2*K,2*K) + query(1,1,x-1,y-1)
               + query(x+K,1,2*K,y-1) + query(1,y+K,x-1,2*K);
    ans = max(ans,max(temp,N-temp));
  }
  cout << ans << endl;
  return 0;
}

AGC 002 C - Knot Puzzle (500)

AtCoder 競プロ 必要条件の列挙

問題概要

a[i] (1<=i<=N) の長さのロープN本がある.これらは順に繋がっている.
長さがLより小さくならないように一つずつ結び目を解くことができるか,できる時解き方を出力せよ.
2 <= N <= 105, 1 <= a_i,L <= 109

解法

解くことができる <-> a[i] + a[i+1] >= Lなるiが存在する
と言い換えることができる.
このようなiを発見したら,1,2,..,i-1, N,N-1,..,i
とすれば必ず解くことができる.

メモ

両端から短い方を解く,としたらWAした.
反例は
4 5
2 3 1 3 とか.
必要条件から考えていくべきだった.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;

ll a[MAX_N];

int main(){
  ll N,L; cin >> N >> L;
  ll re = 0LL; int r = 0;
  rep(i,N) scanf("%lld",a+i);
  rep(i,N-1){
    ll t = a[i] + a[i+1];
    if(t>re){
      re = t;
      r = i;
    }
  }
  if(re<L) cout << "Impossible" << endl;
  else{
    cout << "Possible" << endl;
    REP(i,1,r+1) cout << i << endl;
    RREP(i,N-1,r+1) cout << i << endl;
  }
  return 0;
}

第4回ドワンゴ 予選 C - Kill/Death (500)

AtCoder 競プロ DP 分布 分割数

解法

前提知識 分割数
蟻本にも載ってる.

この問題は,X=sum(death)=sum(相手チームのkill)とすると,
kill数が全員同じ -> sum(death_i) = X, death_i は昇順の通り数 -> すなわち分割数,DPで出せる
kill数が全員違う -> sum(death_i) = X, death_i の順番なしの通り数 -> コンビネーション,DPで出せる

なので,kill数が同じ人を同じグループとして,分割数をあらかじめ計算しておき,
dp[j][i] := (jグループまでで和iを分割する通り数) とおくと,(j,iが逆なのは分割数の計算をdp[和 i][人数 j]としたから)
dp[j][i] = sum_(0<=k<=i) (dp[j-1][i-k] * (和kをグループjで分割する分割数))
という漸化式が生える.
O(N*(sum(kill))2) = O(108)ぐらいでちょっと危うそうだが間に合った.

なお,より良い解法があって,
こちらはkill数が同じプレイヤーが複数いた時,昇順になるので後ろのプレイヤーにもdeathを配るというもの.
すなわち,dp[i][j] := (i人までにjを分割する通り数) と置いて,

後ろにkill数が同じ人がいない時,
dp[i][j] = dp[i-1][j] + dp[i][j-1]から,

後ろにkill数が同じ人が自分含めk人いる時,
dp[i][j] = dp[i-1][j] + dp[i][j-k]
(上とまとめられる)
また, j < k の時(和よりも後ろにいる人数の方が多い時), 自分は0しか取れないので
dp[i][j] = dp[i-1][j]
となる.天才か.

メモ

区別あり/なしの和の分割の話は覚えておきたい.
分割数を覚えてなかったので,その前提がないと難しそう.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 102, MAX_SUM = 1003;

ll part_dp[MAX_SUM][MAX_N],dp[MAX_N][MAX_SUM];

void prepare(){
  REP(i,1,MAX_SUM) part_dp[i][1] = 1LL;
  rep(i,MAX_N) part_dp[0][i] = 1LL;
  REP(i,1,MAX_SUM) REP(j,2,MAX_N){
    if(j>i) part_dp[i][j] = part_dp[i][i];
    else part_dp[i][j] = (part_dp[i-j][j] + part_dp[i][j-1]) % lmod;
  }
}

ll solve(vector<int> &kill,int death){
  int depth[MAX_N];
  fill(depth,depth+MAX_N,0);
  int prev = kill[0], N = kill.size(), cnt = 0;
  depth[cnt]++;
  if(N>1){
    REP(i,1,N){
      if(kill[i]==prev) depth[cnt]++;
      else{
        prev = kill[i];
        cnt++;
        depth[cnt]++;
      }
    }
  }
  cnt++;
  fill(dp[0],dp[MAX_N-1],0LL);
  dp[0][0] = 1LL;
  REP(j,1,cnt+1) REP(i,0,death+1){
    rep(k,i+1) (dp[j][i] += dp[j-1][i-k] * part_dp[k][depth[j-1]]) %= lmod;
    // cout << j << "," << i << " " << dp[j][i] << endl;
  }
  // cout << dp[cnt][death] << endl;
  return dp[cnt][death];
}

int main(){
  vector<int> a,b;
  int N,M; cin >> N >> M;
  int a_sum = 0,b_sum = 0;
  rep(i,N){
    int k; scanf("%d",&k);
    a.pb(k);
    a_sum += k;
  }
  rep(i,M){
    int k; scanf("%d",&k);
    b.pb(k);
    b_sum += k;
  }
  prepare();
  cout << solve(a,b_sum) * solve(b,a_sum) % lmod << endl;
  return 0;
}