ありよりのあり

\主に競プロ備忘録/

AGC 002 C - Knot Puzzle

問題概要

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

解法

解くことができる <-> 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

解法

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

この問題は,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;
}

AGC 001 B - Mysterious Light

問題概要

長さNの正三角形ABCがある.
AB上にあり,AP=Xであるような点からBCと平行に光を放つ.
この光は,辺とそれまで通った点に反射する.
光はどれだけの長さを通るか.
2 <= N <= 1012

解法

ab の平行四辺形に光を放った時の光の長さをf(a,b)とすると,
答えは N + f(X,N-X) であり,
a<b の時, f(a,b) = 2a + f(b-a,a).
ユークリッドの互除法と同じ原理で,
bがaの倍数でない時,
f(a,b) = 2a
floor(b/a)a + f(b%a,a)
bがaの倍数の時,
f(a,b) = (2a
floor(b/a) -1)*a
となる.

メモ

それっぽいのはできたけどイージーミスでWAが取れなかった.
定式化のスキルが足りない.

コード

#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 = 100005;

int main(){
  ll N,X,ans;
  cin >> N >> X;
  ans = N;
  ll a = max(X,N-X);
  ll b = min(X,N-X);
  while(b!=0){
    if(a%b!=0LL) ans += 2*(a/b)*b;
    else ans += (2*(a/b)-1)*b;
    ll a1 = max(a%b,b);
    ll b1 = min(a%b,b);
    a = a1; b = b1;
  }
  cout << ans << endl;
  return 0;
}

AGC 013 B - Hamiltonish Path

問題概要

N頂点M辺の連結な無向グラフが与えられる.
2個以上の頂点を通り,1頂点を1回以内しか通らず,
両端の少なくとも一つと繋がっている頂点を全て通るようなパスを求めよ.

解法

適当なパスを決めて,両端を条件を満たすか確認し,greedyに伸ばしていけば良い.
dequeなどを使うか,始点から伸ばしたパスと終点から伸ばしたパスを格納するvectorを使う.

メモ

次数最小の頂点を始点として,終点だけを伸ばしていく方針でやったらWAした.
条件を満たすか確認するところでO(N)かかるかと思ったが,結局1辺につき1回しか確認しないのでO(M)で済む.
greedyに両端を伸ばしていくというのが思いつかなかったのはそういう問題をやったことがないというのと,
それで必ず満たすパスが存在するというのが実感として得られなかったからであるように思う.

コード

#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 = 100005;
vector<int> graph[MAX_N];
bool passed[MAX_N];

int main(){
  int N,M;
  cin >> N >> M;
  rep(i,M){
    int a,b;
    scanf("%d%d",&a,&b);
    graph[a-1].pb(b-1);
    graph[b-1].pb(a-1);
  }
  deque<int> deq;
  deq.push_back(0);
  deq.push_back(graph[0][0]);
  while(true){
    bool ok = true;
    int s = deq.front();
    int e = deq.back();
    passed[s] = passed[e] = true;
    bool update = false;
    for(auto u:graph[s]){
      if(!passed[u]){
        deq.push_front(u);
        update = true;
        break;
      }
    }
    if(update) continue;
    for(auto u:graph[e]){
      if(!passed[u]){
        deq.push_back(u);
        update = true;
        break;
      }
    }
    if(update) continue;
    break;
  }
  cout << deq.size() << endl;
  for(auto u:deq) cout << u+1 << " ";
  cout << "" << endl;
  return 0;
}

AGC 015 C - Nuske vs Phantom Thnook

問題概要

N x Mのグリッドが与えられ,各々に0,1のいずれかが書いてある.
1のマスで閉路はできないようになっている.
Q個のクエリx1_i, y1_i, x2_i, y2_i (1<=i<=Q)が与えられる.
x1_i <= x <= x2_i, y1_i <= y <= y2_i に含まれる,1の連結成分はいくつか,それぞれ求めよ.
1 <= Q <= 2105, 1 <= N,M <= 2103

解法

1のマスをノード,隣接しているマスを辺と考えると,
問題文よりグリッド全体の1の集合は森である.(各々の連結成分が木になっている)
木の性質として (辺の数) - (ノードの数) = 1 なので,
グリッド内の (辺の数) - (ノードの数)がグリッド内の木の数になる.
これを累積和で求めると, O(Q+NM)で解ける.
辺については,x方向,y方向でそれぞれ累積和を取らないと求められない.

メモ

ハマった. 木の性質すぐ出るようにしよう.

コード

#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 = 2003;

int a[MAX_N][MAX_N],node[MAX_N][MAX_N],edgex[MAX_N][MAX_N],edgey[MAX_N][MAX_N];
string S[MAX_N];

int main(){
  int N,M,Q; cin >> N >> M >> Q ;
  fill(node[0],node[MAX_N-1],0);
  fill(edgex[0],edgex[MAX_N-1],0);
  fill(edgey[0],edgey[MAX_N-1],0);
  rep(i,N) cin >> S[i];
  rep(i,N) rep(j,M) a[i+1][j+1] = int(S[i][j]=='1');
  REP(i,1,N+1) REP(j,1,M+1) node[i][j] = a[i][j] + node[i-1][j] + node[i][j-1] - node[i-1][j-1];
  REP(i,1,N+1) REP(j,1,M+1){
    edgex[i][j] = (a[i][j]&a[i-1][j]) + edgex[i-1][j] + edgex[i][j-1] - edgex[i-1][j-1];
    edgey[i][j] = (a[i][j]&a[i][j-1]) + edgey[i-1][j] + edgey[i][j-1] - edgey[i-1][j-1];
  }
  rep(i,Q){
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    int n = node[x2][y2] - node[x1-1][y2] - node[x2][y1-1] + node[x1-1][y1-1];
    int ex = edgex[x2][y2] - edgex[x1][y2] - edgex[x2][y1-1] + edgex[x1][y1-1];
    int ey = edgey[x2][y2] - edgey[x1-1][y2] - edgey[x2][y1] + edgey[x1-1][y1];
    cout << n - (ex + ey) << endl;
  }
  return 0;
}

AGC 016 B - Colorful Hats

問題概要

N匹の猫がいて,それぞれが色のついた帽子をかぶっている.
N匹の猫に,自分以外の猫の帽子の色は何種類あるかという質問をした時の答えa[i] (1<=i<=N) が与えられる.
条件を満たすような帽子のかぶり方は存在するか.
1 <= a[i] <= N-1, 1 <= N <= 105

解法

全ての猫がA種類の帽子をかぶっているとする.
自分以外で自分と同じ色の帽子をかぶっている猫がいるとき,その猫をaloneであるとする.
猫iがaloneである時, a[i] = A-1
猫iがaloneでない時, a[i] = A となる.

よってmin = min(a[i]) , max = max(a[i])とすると, max - min >= 2ならば満たすかぶり方は存在しない.
(1) min = max
(2) max = min+1 = A
それぞれの場合について考える.

(1) 全ての猫がalone, または全ての猫がnot aloneである.
前者の時は, A = a[i]+1 = N でなければならない.
後者の時の, Aの範囲について考える.
最小は全て同じ色にすれば良いから,1色である.
最大は,猫は少なくとも2匹で組を作らなければならない(同じ色の猫がいなければならない)と考えると,
floor(N/2)となる.
よって後者の時は A <= floor(N/2) を満たしていれば良い.

(2) min = A-1, max = Aと考えて良い.
ということはminを答えた猫はaloneであり, maxと答えた猫はnot aloneである.
minと答えた猫の数をx, maxと答えた猫の数をyとすると,
aloneである猫の色の数はx.
not aloneな猫の色の数は,(1)と同様に考察すると1〜floor(y/2)のいずれかである.
よって, x+1 <= A <= x+floor(y/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 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(){
  int N; cin >> N;
  int _max = -INF, _min = INF;
  rep(i,N){
    scanf("%d",a+i);
    _max = max(_max,a[i]);
    _min = min(_min,a[i]);
  }
  bool ans = false;
  if(_min==_max){
    if(_min==N-1 || _min<=N/2) ans = true;
  }else if(_max==_min+1){
    int cnt_min = 0;
    rep(i,N) if(a[i]==_min) cnt_min++;
    if(_max >= cnt_min+1 && _max <=(cnt_min)+(N-cnt_min)/2) ans = true;
  }
  cout << (ans ? "Yes" : "No") << endl;
  return 0;
}

AGC019 B - Reverse and Compare

問題概要

文字列Sが与えられる.
1回だけ,Sの i〜j文字目(1<=i<j<=N)だけを反転させることを考える.
文字列は何種類できるか.

解法

重複を含めると,2文字選ぶ組み合わせの数だから,N*(N-1)/2である.
S[i] = S[j]の時,作業(i,j)は(i+1,j-1)と同じであるから,
S[i] = S[j]となる2文字の組み合わせを除けば良い.
j = i+1,i+2の時は(i+1,j-1)の組み合わせは存在しなくなるが,
aa,abaを反転しても元と変わらないので,数えなくて良い.

S[i] = S[j] なる(i,j)の組み合わせの数は,a〜zについて, その出現回数をz(char)とすると,z(char) * (z(char) - 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 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 = 202;

int main(){
  string s; cin >> s;
  map<char,ll> mp;
  ll N = s.size();
  rep(i,N){
    if(EXIST(mp,s[i])) mp[s[i]]++;
    else mp[s[i]] = 1;
  }
  ll ans = N * (N-1) / 2 + 1;
  for(char c = 'a'; c <= 'z'; c++) ans -= mp[c]*(mp[c]-1)/2;
  cout << ans << endl;
  return 0;
}