kurarrr's memooo

主に競プロ備忘録

ARC 086 D - Non-decreasing (600)

AtCoder 競プロ 数列操作

問題概要

N個の整数からなる数列が与えられる.
x,yについて,a[y]にa[x]を足す,という操作を繰り返して,
a[0] <= a[1] <= ... <= a[N] を満たすようにしたい.
条件を満たす2N回以内の操作を出力せよ.
そのような操作が存在することは保証されている.
2 <= N <=50 , abs(a[N]) <= 106

解法

a[i]が全て正の時, a[1] += a[0], a[2] += a[1],..., a[N-1] += a[N-2]
とすれば, 新しいa'[i]はa[i]の累積和となり条件を満たす.
全て負の時は a[N-2] += a[N-1], ... a[0] += a[1]とすれば良い.

正負が混じっている時,min(a[i]) < 0 , max(a[i]) >= 0 であり,
abs(min(a[i])) > abs(max(a[i])) の時は全てのa[i]にminを,
そうでない時は全てのa[i]にmaxを足せば上に帰着できる.

メモ

最小手数のものを求めよかと思っていた.日本語力.

コード

#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 = 51;
int a[MAX_N];

vector<P> ans;

int main(){
  int N; cin >> N ;
  int _min = INF, _max = -INF;
  int argmin,argmax;
  rep(i,N){
    scanf("%d",a+i);
    if(a[i]<_min){
      _min = a[i];
      argmin = i;
    }
    if(a[i]>_max){
      _max = a[i];
      argmax = i;
    }
  }
  if(_min<0 && _max>0){
    if(abs(_min)>abs(_max)){
      // 全部負にする
      rep(i,N){
        if(a[i]<0) continue;
        ans.pb(P(argmin+1,i+1));
      }
    }else{
      // 全部正にする
      _min = 1;
      rep(i,N){
        if(a[i]>0) continue;
        ans.pb(P(argmax+1,i+1));
      }
    }
  }
  if(_min>=0){
    rep(i,N-1) ans.pb(P(i+1,i+2));
  }else{
    for(int i=N;i>1;i--) ans.pb(P(i,i-1));
  }
  cout << ans.size() << endl;
  rep(i,ans.size()) cout << ans[i].first << " " << ans[i].second << endl;
  return 0;
}

ARC 064 D - An Ordinary Game

AtCoder 競プロ

問題概要

英小文字から成る文字列sが与えられる.
両端以外から,その両隣が同じ文字でないならば文字を1つ取り除け,文字が取り除けなくなったら負けというゲームをする.
先手と後手どちらが勝つか.

解法

ゲーム終了時の文字列は"abab..ab" または "abab..aba"となる.
両端の文字は変わらないから,s[0]==s[N-1]なら前者,そうでないなら後者になる.
上の終了時の文字列以外では必ず手があることに注意すると,
(ゲームの手数) = N-(最終文字列)の偶奇がわかる.
ゲームの手数の偶奇によって勝敗が決まるから, if (先頭==終端) xor (Nが偶数) -> 後手勝ち
else -> 先手勝ち となる.

メモ

最終的な文字列->考察できた
手数の偶奇に注目する->できなかった
最終的な文字列を具体的に求めようとしていたのが敗因っぽい.
こういうタイプの問題よく出る気がするので,手数の偶奇に注目するの覚えておこう.

コード

#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
#define DEBUG false

using namespace std;

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

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

int main(){
  string s; cin >> s; int N = s.size();
  cout << ((N%2==0 ^ s[0]==s[N-1]) ? "Second" : "First") << endl;
  return 0;
}

AGC 020 C - Median Sum (700)

AtCoder 競プロ

問題概要

N個の自然数から成る数列a[i] (1<=i<=N) が与えられる.
a[i] の部分列の和 S_1, S_2, ... , S((2N)-1) の中央値(すなわち{S}を昇順に並べた時のS(2N-1)を求めよ.
1 <= N, a_i <= 2*103

解法

S_0 = 0 として考える.
ある S_j がいくつかの a_i を含んでいるとする.
このS_j に関して,上記の a_i 以外の全ての {a} を含んでいる和を考えると, {S}を2N-1組として考えることができる.
また, S_all = S_((2N)-1) , ペアのうち小さい方をS_small, 大きい方をS_largeとして,
S_small + S_large = S_all , S_small <= S_largeから, S_small <= floor(S_all / 2), S_large >= ceil(S_all / 2) ... (*)となる.
全てのペアについてS_small, S_largeの数は2N-1であり,S_smallにS_0が含まれることを考えれば,
求めるべきはS_largeのうち最小のものであることがわかる.

また,和をある値にするような部分列は存在するか？というのは典型的なDPの問題であり,
dp[i][j] := (a_k(1 <= k <= i)までを用いて和をjにできるか) とおけば組める.
が,N3では間に合わないので,bitsetを用いて高速化すればO(N3/64)で間に合う.

メモ

Sを二組に分ける考察ができなかった.

追記
べき集合 ( 2N ) について,
A or B = 2N (全体) , A and B = φ(空集合) であるようなものを考えると良い感じの不変条件が出ることがあるみたいだ.
今回は和が一定だった.

コード

#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
#define DEBUG false

using namespace std;

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

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

bitset<MAX_N * MAX_N> dp;
int a[MAX_N];

int main(){
  int N; cin >> N ;
  rep(i,N) scanf("%d",a+i);
  int _sum = 0;
  rep(i,N) _sum += a[i];
  dp[0] = 1; 
  rep(i,N) dp |= (dp << a[i]);
  REP(i,(_sum+1)/2,_sum+1){
    if(dp[i]){
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}

ドワンゴ 予選 D - ディスクの節約

AtCoder 競プロ

問題概要

N個のtask,そのメモリ使用x[i] (1<=i<=N), タスク依存関係a[i] (2<=i<=N) が与えられる.
iのタスクはa[i]のタスク実行後にしか実行できず,その中でもタスク1は他の全てのタスク実行後にしか実行できない.
メモリx[i]はタスクi実行後に消すことができる.タスク実行に必要なメモリ最大値を求めよ.
1<=N<=20, 1<=xi<=106

解法

制約からbitDPっぽい.
タスクiのメモリが残っているか(1<=i<=N)をiビット目で表して,その時のメモリを表す.
状態->メモリ使用量は2N * N2で求めておくことができる.(状態遷移を用いると2Nでできそう)
状態1(タスク1のメモリだけ残っている状態)に達するまでに使用したメモリ使用量の最大値,の最小値をmemo[state]で表す.
後はstateの内で立っているbit(実行済みのタスク・親)を一つ選んでそのタスクを実行するために必要な依存先のタスク(子)を実行した時の状態に戻す.
その状態時のコストと,その状態から親を消した(親を実行する前の)状態に達するまでの最大コストを,各親タスクについて求める.
その中で最小のものが求めるmemo[state]となる.
後はメモ化探索する.
コストはO(2N * N2)で結構不安だったが,まあ間に合った.

メモ

DFSでやってWAした.
時間後に自力ACできたのでかなり後悔...

コード

#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
#define DEBUG false

using namespace std;

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

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

ll x[MAX_N],sumx[1<<21],memo[1<<21];
vector<int> graph[MAX_N];
int N;

ll solve(int state){
  if(memo[state]>=0LL) return memo[state];
  ll res = LINF;
  rep(i,N){
    // 立っているbitを選んで子を立たせる
    if(((1<<i)&state)==0) continue;
    int next = state;
    for(auto u:graph[i]) next |= (1<<u);
    // cout << "next = " << next << endl;
    res = min(res,max(sumx[next],solve(next^(1<<i))));
  }
  // cout << "res = " << res << endl;
  return memo[state] = res;
}

int main(){
  cin >> N ;
  rep(i,N) cin >> x[i] ;
  rep(i,N-1){
    int a; cin >> a ;
    graph[a-1].pb(i+1);
  }
  fill(memo,memo+(1<<N),-1LL);
  memo[0] = 0LL;
  rep(i,1<<N){
    rep(j,N) if((i&(1<<j))!=0) sumx[i] += x[j];
  }
  cout << solve(1) << endl;
  return 0;
}

ARC069 D - Menagerie

AtCoder

問題概要

羊(S)と狼(W)が円状に並んでいる.
Sは両隣が同じ動物の時o,そうでない時xと答える.
Wは両隣が同じ動物の時x,そうでない時oと答える.
動物の数Nと,各動物の答えS(|S|=N)が与えられる.
答えを満たす動物の並びが存在すればその内1つを,存在しなければ-1を出力せよ.

解法

反転の問題. 最初を決めてやればパタパタと決まっていく.
この問題の場合,最初の2つの動物を決めると次の動物が次々決まって行く.
よって4通り全て試せば良いのでO(N)で十分間に合う.

メモ

union find treeで同じのをまとめていくやつか…？と思ったがしばらくしたら思いついた.手を動かすの大事.

コード

#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
#define DEBUG false

using namespace std;

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

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

int next(int pre,int now,const char &c){
  int res;
  if(!now){
    // now -> 'S'
    if(c=='o') res = pre;
    else res = pre^1;
  }else{
    // now -> 'W'
    if(c=='o') res = pre^1;
    else res = pre;
  }
  return res;
}

int main(){
  int N; string S;
  cin >> N >> S;
  map<int,string> mp;
  mp[0] = "S"; mp[1] = "W";
  rep(i,2) rep(j,2){
    int pre,now;
    pre = i; now = j;
    string ans = mp[i] + mp[j];
    rep(k,N-1){
      pre = next(pre,now,S[k+1]);
      if(k!=N-2) ans += mp[pre];
      swap(now,pre);
    }
    if(now==i&&next(j,i,S[0])==pre){
      cout << ans << endl;
      return 0;
    }
  }
  cout << "-1" << endl;
  return 0;
}

ARC 071 E - TrBBnsformBBtion

AtCoder 競プロ

問題概要

ABから成る文字列S,Tが与えられる。
次の操作をいくらでも行うことができる。
1. 'AA' -> 'B', 'BB' -> 'A' の変換
2. 'AAA' または 'BBB' の消去

以下のQ個のクエリを処理せよ。
ai,bi,ci,di(1<=i<=Q)が与えられる。
Sの部分文字列S[ai:bi+1]をTの部分文字列[ci:di+1]に一致させることができるか判定せよ。
1<=|S|,|T|<=105,1<=Q<=105,ai<=bi,ci<=di

解法

''(空文字列)<->'AAA'<->'BBB'<->'AB'<->'BA'
'A'<->'BB' 'AA'<->'B'
と相互変換できることに注目する。(ただし''->'AAA'の変換は隣の1文字を用いる)
条件より部分文字列が空文字列であることはないので、部分文字列を何個の'A'に変換できるか、と考えてグループ分けして問題ない。
'A','B'に関してそういう演算子を定義しても問題ないが、
'A'=1,'B'=2として、(文字の和)%3を考えればうまく行くことがわかる。
累積和を計算しておけば各クエリをO(1)で判定できるので十分間に合う。

メモ

変換ができることは考察できたが、''->'AAA'に気づかなくて詰まった。
この難易度ならクエリ系の問題は大体累積和かSeg木を最初に考えて問題なさそう。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#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
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

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

int p[MAX_N],q[MAX_N];

int main(){
  string S,T;
  cin >> S >> T ;
  int temp = 0;
  rep(i,S.size()) p[i+1] = (temp = (temp + int(S[i]-'A') + 1) % 3 );
  temp = 0;
  rep(i,T.size()) q[i+1] = (temp = (temp + int(T[i]-'A') + 1) % 3 );
  int Q,a,b,c,d;
  cin >> Q ;
  rep(i,Q){
    scanf("%d%d%d%d",&a,&b,&c,&d);
    if((p[b]-p[a-1]-q[d]+q[c-1])%3==0) printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}

ARC 070 D - No Need

AtCoder 競プロ

問題概要

N個の自然数a[i] (1<=i<=N)と自然数Kが与えられる。
その組み合わせからなる2Nの集合を考え、そのうち部分和がKを超えるものを良い集合とする。
a[i]を含む任意の良い集合Aに対し、A\ {a[i]}(Aからa[i]を除いた集合)も良い集合であるならばa[i]は不必要であるとする。
a[i] (1<=i<=N)のうち、不必要な自然数の個数を求めよ。
1<=N,K<=5*103,1<=a[i]<=109(部分点解法は1<=N,K<=400)

解法

まず、a[i]>=Kならばa[i]は必要であるため、1<=a[i]<Kなるa[i]についてのみ考えれば良い。
よって1<=a[i]<=5*103となる。
不必要の定義は次のように言い換えられる。 「a[i]を除いた部分和でK-a[i]<=sum<Kなるものが存在するならa[i]は不必要でない」

部分点解法から。
dp[i][sum] := (iを除いて部分和sumを作れるか)として、iを除いた時の部分和を列挙していく。 for(k:K+1->0) for(j!=i) dp[i][k]] |= dp[i][k-a[j]] という漸化式に従う。
各iについて計算するとO(N3)となる。

a[i] >= a[j] でa[i]が不必要ならばa[j]も不必要であるという関係が成り立つことに注意すると、二分探索できることがわかる。
O(N2*logN)になり、間に合う。

また、 dp1[i][sum] := (a[j] (1<=j<=i)までの部分和でsumが作れるか)
dp2[i][sum] := (a[j] (i<=j<=N) ..)
として各DPを計算しておく。
a[j] (1<=j<i)の部分和x、a[j] (i<j<=N)の部分和yとして、 各iについてxが作れるならば、K-a[i] <= x+y < Kなるyが取れれば条件を満たすため、 K-a[i]-y <= y < K-xを満たすyが存在するかを判定すれば良い。yに関する累積和を作っておけばこれはO(K)で判定できる。 よって全体でO(NK)=O(N2)で解けることになる。

メモ

k:0->K+1とすると0->a[j]->2*a[j]とtrueになっていってしまう。(よくやるミス) そうならないためにはもう一次元増やすか、bitsetでやると良い。
最速解法見てるとO(NlogN)で解けてるっぽいんだけど全然わからん。

コード

部分点

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#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
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

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

int N,K,a[MAX_N];
bool dp[MAX_N][MAX_N*2];

int main(){
  scanf("%d%d",&N,&K);
  int temp = 0;
  rep(i,N){
    int b;
    scanf("%d",&b);
    if(b<K) a[temp++] = b;
  }
  N = temp;
  fill(dp[0],dp[MAX_N-1],false);
  rep(i,N) dp[i][0] = true;
  int ans = 0;
  rep(i,N){
    rep(j,N){
      if(j==i) continue;
      for(int k=K+1; k>=a[j]; k--){
        dp[i][k] |= dp[i][k-a[j]];
      }
    }
    bool need = false;
    REP(j,K-a[i],K) need |= (dp[i][j]);
    if(!need) ans++;
  }
  cout << ans << endl;
  return 0;
}

満点

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#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
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

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

int N,K,a[MAX_N];
bool dp[MAX_N*2];

int main(){
  scanf("%d%d",&N,&K);
  int temp = 0;
  a[temp++] = 0; //dummy
  rep(i,N){
    int b;
    scanf("%d",&b);
    if(b<K) a[temp++] = b;
  }
  N = temp;
  sort(a,a+N);
  a[N] = K; //dummy
  int l = 0,r = N+1,mid;
  while(abs(r-l)>1){
    mid = (l+r)/2;
    fill(dp,dp+K,false);
    dp[0] = true;
    rep(j,N){
      if(j==mid) continue;
      for(int k=K; k>=a[j]; k--){
        dp[k] |= dp[k-a[j]];
      }
    }
    bool need = false;
    REP(j,K-a[mid],K) need |= (dp[j]);
    if(!need) l = mid;
    else r = mid;
  }
  cout << l << endl;
  return 0;
}