YNU.cpc

横浜国立大学競技プログラミング部 ( YNU.cpc )

活動日記 day 31

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest

A - 加算王
文字列として入力を受け取り、1桁目と2桁目の和を出力します。
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int main() {
  string s;
  cin >> s;
  cout << ( s[0] - '0' + s[1]- '0' ) << endl;
  return 0;
}

B - 手芸王
あらかじめ100以下のアクセサリーを作成し、連想配列等にそのアクセサリーの情報を保持しておきます。
入力で与えられた文字列が連想配列内に存在すれば、その値を出力します。
無ければ-1です。
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int main() {
  string s = "b";
  map<string,int> mp;
  mp[s] = 0;
  REP(n,1,110) {
    if( n % 3 == 0 ) {
      s = "b" + s + "b";
      mp[s] = n;
    } else if( n % 3 == 1 ) {
      s = "a" + s + "c";
      mp[s] = n;
    } else {
      s = "c" + s + "a";
      mp[s] = n;
    }
  }
  int n;
  cin >> n;
  cin >> s;
  if( mp.count(s) ) {
    cout << mp[s] << endl;
  } else {
    cout << -1 << endl;
  }
  return 0;
}

C - 収集王
まず各行と各列ごとに、飴の出現回数を数えます。
次に行iについて、K - (行iの飴の出現回数) 個 だけ飴が出現している列の数を数えます。
その際に、行iに含まれる飴の出現回数は各列の飴の出現回数から引いておく必要があります。
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
#define MAX 100100
 
int R,C,K,N,r[100100],c[100100];
ll cR[MAX],cC[MAX];
deque<int> deq[MAX];
map<int,ll> mR,mC;
 
void compute() {
  rep(i,R) ++mR[cR[i]];
  rep(i,C) ++mC[cC[i]];
  long long ans = 0;
  rep(i,C) {
    int v1 = cC[i];
    int v2 = K - v1;
    if( v2 < 0 ) continue;
    rep(j,(int)deq[i].size()) {
      int dex = deq[i][j];
      int v = cR[r[dex]];
      --mR[v];
      ++mR[v-1];
    }
    ans += (ll)mR[v2];
    rep(j,(int)deq[i].size()) {
      int dex = deq[i][j];
      int v = cR[r[dex]];
      ++mR[v];
      --mR[v-1];
    }
  }
  cout << ans << endl;
}
 
int main() {
  cin >> R >> C >> K;
  cin >> N;
  rep(i,N) {
    cin >> r[i] >> c[i];
    --r[i], --c[i];
    deq[c[i]].push_back(i);
    ++cR[r[i]];
    ++cC[c[i]];
  }
  compute();
  return 0;
}

D - 射撃王
答えとなる値を二分探索で決め打ちします。
つまり、全ての風船を破壊した際に発生するペナルティの最大値 x を二分探索で決めます。
x が決まれば、各風船をペナルティがx以下になるような時間で破壊できるかどうか判定ができます。
(各風船iについて H[i] + ti * S[i] <= x となるような ti の最大値を求め、それらの風船をti以下の時間帯で割ることができるかどうか判定すれば良いです )
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
#define MAX 100100
 
 
int N;
long long H[MAX], S[MAX];
 
bool check(ll maxi) {
  map<ll,int> cnt;
  rep(i,N) {
    if( H[i] > maxi ) return false;
    ll t = ( maxi - H[i] ) / S[i];
    ++cnt[t];
  }
  ll sum = 0;
  for(auto v : cnt) {
    sum += (ll)v.second;
    if( sum > v.first + 1 ) return false;
  }
  return true;
}
 
int main() {
  cin >> N;
  rep(i,N) cin >> H[i] >> S[i];
  // 最小をもとめる
  ll L = 0, R = LLONG_MAX-10LL;
  while( L + 1 < R ){
    ll M = ( L + R ) / 2;
    assert( M >= 0LL );
    if( check(M) ) R = M;
    else           L = M;
  }
  if( check(L) ) cout << L << endl;
  else if( check((L+R)/2) ) cout << (ll)((L+R)/2) << endl;
  else cout << R << endl;
  return 0;
}

E - タコヤ木

  • 1が連続していくる区間ごとに、それを満たすような割り当てが何通りあるのかを考えます。

(各区間について組み合わせの数を求めれば、それらを掛け合わせたものが最終的な組み合わせの数になります)
つまり、a -1 -1 ... -1 bのような区間について、何通りの割りあてがあるのかを考えます。
さて、問題の見方を少し変えてみると次のような問題になります。
0以上の整数であるc個の変数の総和がb - a以下になる組み合わせは何通りか?
これは重複組み合わせで求めることができるので、求めましょう。
(例) 2 -1 -1 9 について考える。
これは2個の変数の総和が7以下になるような組み合わせを求める問題として考えることができる。
そのような組み合わせの数は
7+2C2 = 36
O O O O O O O の間に | | を入れるアレ
その際には逆元を求める必要があります。
ちなみに80点まではよくある式を少しいじるタイプのDPでとけます。

コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
#define MAX 2010
 
ll mod = 1000000007;
 
long long extgcd(long long a,long long b,long long& x,long long& y) {
  long long d = a;
  if(b != 0) {
    d = extgcd(b,a%b,y,x);
    y -= (a/b)*x;
  }
  else x = 1,y = 0;
  return d;
}
 
long long mod_inv(long long a,long long m) {
  long long x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
 
int N,A[MAX];
 
void compute() {
  vector<int> vec,num;
  rep(i,N) if( A[i] != -1 ) {
    vec.push_back(A[i]);
    int cur = i + 1;
    while( cur < N && A[cur] == -1 ) ++cur;
    num.push_back(cur-i-1);
  }
  long long ans = 1;
  rep(i,(int)vec.size()-1) {
    int a = vec[i+1] - vec[i];
    int b = num[i];
    long long denom = 1, numer = 1;
    REP(j,1,b+1) {
      ( denom *= ( (ll)( a + b - ( j - 1 ) ) % mod ) ) %= mod;
      ( numer *= (ll)j ) %= mod;
    }
    ( ans *= ( ( denom * mod_inv(numer,mod) ) % mod ) ) %= mod;
  }
  cout << ans << endl;
}
 
int main() {
  cin >> N;
  rep(i,N) cin >> A[i];
  compute();
  return 0;
}

おまけ (80点をとるためのDPコード)

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
#define MAX 2010
 
ll mod = 1000000007;
 
int N,A[MAX], pre[MAX],nex[MAX];
long long dp[MAX][2100];
 
void compute() {
  nex[0] = A[0], nex[N-1] = A[N-1];
  pre[0] = A[0], pre[N-1] = A[N-1];
  for(int i=N-2;i>=1;--i) {
    if( A[i] == -1 ) nex[i] = nex[i+1];
    else             nex[i] = A[i];
  }
  REP(i,1,N-1) {
    if( A[i] != -1 ) pre[i] = A[i];
    else             pre[i] = pre[i-1];
  }
 
  dp[0][A[0]] = 1;
  REP(i,1,N) {
    REP(j,1,nex[i]+1) {
      dp[i][j] = ( dp[i][j-1] + dp[i-1][j] ) % mod;
    }
    rep(j,pre[i]) dp[i][j] = 0;
  }
  cout << dp[N-1][A[N-1]] << endl;
}
 
int main() {
  cin >> N;
  rep(i,N) cin >> A[i];
  compute();
  return 0;
}

一言コメント:
来週は立命館大学競技プログラミング合宿(RUPC2017)ですね。

活動日記 day 30

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest

A - Best Body
実際にN日間の第10の変化を計算してベストボディーである日を数えます。
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int n,s,t;
int w;
 
int main() {
  int cnt = 0;
  cin >> n >> s >> t;
  cin >> w;
  int cur = w;
  if( s <= cur && cur <= t ) ++cnt;
  rep(i,n-1) {
    int a;
    cin >> a;
    cur = cur + a;
    if( s <= cur && cur <= t ) ++cnt;
  }
  cout << cnt << endl;
  return 0;
}

B - Bumble Bee
i番目より前に訪れた花の種類を配列等で保持し、i番目の花の種類がすでに存在するかどうかを判定します。
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int n, A[100010];
bool found[100010];
 
int main() {
  cin >> n;
  int cnt = 0;
  rep(i,n) {
    cin >> A[i];
    if( found[A[i]] ) ++cnt;
    found[A[i]] = true;
  }
  cout << cnt << endl;
  return 0;
}

C - Blue Bird
答えとなる閉路は家1を端点に持つ辺をちょうど2本含みます。
そのため、家1から出ている辺を全て取り除いた状態のグラフの全点間の最短経路をワーシャルフロイドやdijkstraで求めた後に
どの2つの辺を答えとなる閉路に含めるか全パターン試します。
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
struct Edge {
  int t,v;
};
 
struct Data {
  int cur, c;
  bool operator < ( const Data & data ) const {
    if( c != data.c ) return c > data.c;
    return cur < data.cur;
  }
};
 
int V,E;
vector<Edge> G[400];
vector<int> ID[400];
int mini[400];
 
int dijkstra(int e) {
  rep(i,V) mini[i] = INT_MAX;
  int dst = G[0][e].t;
  if( dst == 0 ) return INT_MAX;
  mini[0] = 0;
  priority_queue<Data> Q;
  Q.push((Data){0,0});
  while(!Q.empty()) {
    Data d = Q.top(); Q.pop();
    if( d.cur == dst ) return d.c + G[0][e].v;
    rep(i,(int)G[d.cur].size()) {
      int nex = G[d.cur][i].t;
      if( ID[d.cur][i] == ID[0][e] )  continue;
      if( mini[nex] > d.c + G[d.cur][i].v ) {
	mini[nex] = d.c + G[d.cur][i].v;
	Q.push((Data){nex,mini[nex]});
      }
    }
  }
  return INT_MAX;
}
 
void compute() {
  int ans = INT_MAX;
  rep(i,(int)G[0].size()) {
    ans = min(ans,dijkstra(i));
  }
  if( ans == INT_MAX ) puts("-1");
  else cout << ans << endl;
}
 
int main() {
  cin >> V >> E;
  rep(i,E) {
    int s,t,v;
    cin >> s >> t >> v;
    --s, --t;
    G[s].push_back((Edge){t,v});
    G[t].push_back((Edge){s,v});
    ID[s].push_back(i);
    ID[t].push_back(i);
  }
  compute();
  return 0;
}


D - Big Bang
問題文中の処理を行ったとしても、その点集合において変化しない情報について考えます。
例えば、最も近い2点は処理後も変化しません。
そのため、処理前と処理後の最も近い2点間の距離を求め、処理後の距離で処理前の距離を割ればPが求まります。
その他にも、点集合の凸包をとってできた凸多角形の重心と各点との距離からもPを求めることができます。
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)
 
using namespace std;
 
struct Point { 
  int x,y; 
  bool operator < ( const Point &p ) const {
    if( x != p.x ) return x < p.x;
    return y < p.y;
  }
};
 
#define MAX 100010
 
bool cmp_y(const Point &a,const Point &b) {
  return a.y < b.y;
}
 
//#define pow2(x) ((x)*(x))
//double mydist(Point a,Point b) { return sqrt(pow2(a.x-b.x)+pow2(a.y-b.y)); }
 
double mydist(Point a,Point b) { 
  //double dx = ((a.x - b.x)*(a.x-b.x));
  //double dy = ((a.y - b.y)*(a.y-b.y));
  double dx = (a.x - b.x);
  double dy = (a.y - b.y);
  dx = dx * dx;
  dy = dy * dy;
  return sqrt(dx+dy);
  //return sqrt(dx+dy); 
}
 
double closest_pair(Point *ps,int n) {
  if( n <= 1 ) return INT_MAX;
  int m = n / 2;
  double x = ps[m].x;
  double d = min(closest_pair(ps,m),closest_pair(ps+m,n-m));
  inplace_merge(ps,ps+m,ps+n,cmp_y);
  vector<Point> vec;
  rep(i,n) {
    if( fabs(x-ps[i].x) >= d ) continue;
    for(int j=(int)vec.size()-1;j>=0;--j) {
      double dy = fabs(ps[i].y-vec[j].y);
      if( dy >= d ) break;
      d = min(d,mydist(ps[i],vec[j]));
    }
    vec.push_back(ps[i]);
  }
  return d;
}
 
int n;
Point A[MAX], B[MAX];
 
void compute() {
  sort(A,A+n);
  double mini1 = closest_pair(&A[0],n);
  sort(B,B+n);
  double mini2 = closest_pair(&B[0],n);
  printf("%.10f\n",mini2/mini1);
}
 
int main() {
  cin >> n;
  rep(i,n) cin >> A[i].x >> A[i].y;
  rep(i,n) cin >> B[i].x >> B[i].y;
  compute();
  return 0;
}

E - ロミオとジュリエット
木の直径を求めれば良いです。
木の直径の求め方はday 27のセットにも出ましたね。
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
#define MAX_V 100010
 
int V;
vector<int> G[MAX_V];
 
typedef pair<int,int> ii;
 
ii visit(int p,int v) {
  ii r(0,v);
  rep(i,(int)G[v].size()) {
    int e = G[v][i];
    if(e != p) {
      ii t = visit(v,e);
      t.first += 1;
      if(r.first < t.first) r = t;
    }
  }
  return r;
}
 
int diameter() {
  ii r = visit(-1,0);
  ii t = visit(-1,r.second);
  cout << r.second + 1 << " " << t.second + 1 << endl;
  return t.first;
}
 
int main() {
  cin >> V;
  rep(i,V-1) {
    int s,t;
    cin >> s >> t;
    --s, --t;
    G[s].push_back(t);
    G[t].push_back(s);
  }
  diameter();
  return 0;
}

活動日記 day 29

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest

A - 足し算
n個1を出力すれば良いです。
コード:

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;

int main() {
  int n;
  cin >> n;
  cout << n << endl;
  rep(i,n) cout << 1 << endl;
  return 0;

B - 嘘つきの高橋くん
同じ町を2回以上訪れている場合は明らかに最短ではないです。
a,b,P[i]の中に現れる整数で、その出現回数が2回以上のものが存在すればNO, そうでなければ YESです。
コード:

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int main() {
  int n,a,b,k;
  cin >> n >> a >> b >> k;
  set<int> S;
  S.insert(a);
  S.insert(b);
  bool mini = true;
  rep(i,k) {
    int p;
    cin >> p;
    if( S.count(p) ) mini = false;
    S.insert(p);
  }
  cout << ( mini ? "YES" : "NO" ) << endl;
  return 0;
}

C - 正直者の高橋くん
辺の重みが1なので、幅優先で最短経路を計算しつつ
実際にそのような経路が何通りあるのか計算しましょう。

コード:

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
#define MAX_V 110
 
const ll mod = 1000000007;
 
int V,s,t,E;
vector<int> G[MAX_V];
int mini[MAX_V]; // 最短ステップ
ll ans[MAX_V];  // 最短経路の総数
 
void compute() {
  rep(i,V) mini[i] = INT_MAX;
  mini[s] = 0;
  ans[s] = 1;
  deque<int> deq;
  deq.push_back(s);
  while( !deq.empty() ) {
    int cur = deq.front(); deq.pop_front();
    rep(i,(int)G[cur].size()) {
      int pv = G[cur][i];
      if( mini[cur] == mini[pv] + 1 ) {
	( ans[cur] += ans[pv] ) %= mod;
      }
    }
    if( cur == t ) break;
    rep(i,(int)G[cur].size()) {
      int nx = G[cur][i];
      if( mini[nx] > mini[cur] + 1 ) {
	mini[nx] = mini[cur] + 1;
	deq.push_back(nx);
      }
    }
  }
  cout << ans[t] << endl;
}
 
int main() {
  cin >> V;
  cin >> s >> t;
  --s, --t;
  cin >> E;
  rep(i,E) {
    int x,y;
    cin >> x >> y;
    --x, --y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  compute();
  return 0;
}

D - 多重ループ
n * (n+1) * ... * ( n+k-1 ) / ( 1 * 2 * ... * k ) が答えです。
modの割り算が必要になるので逆元を求めなければなりません。

コード (100点):

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
#define MAX 300000
 
long long mod = 1000000007;
 
 
long long extgcd(long long a,long long b,long long& x,long long& y)
{
  long long d = a;
  if(b != 0){
    d = extgcd(b,a%b,y,x);
    y -= (a/b)*x;
  }
  else
    x = 1,y = 0;
  return d;
}
 
long long mod_inv(long long a,long long m)
{
  long long x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
 
int n,k;
long long frac[MAX], denom[MAX];
 
long long f(ll x) {
  if( x == 1 ) return 1;
  return ( ( frac[x+k-1] * mod_inv(frac[x-1],mod) ) % mod * mod_inv(frac[k],mod) ) % mod;
}
 
int main() {
  frac[0] = frac[1] = 1;
  REP(i,2,MAX) frac[i] = ( frac[i-1] * (ll)i ) % mod;
  cin >> n >> k;
  cout << f(n) << endl;
  return 0;
}

99点までは動的計画法でとれます。
O(n^2)です。
dp[i][j] = i番目の要素までで選んだ値の最大値がjであるときの総数

dp[i][j] = dp[i-1][1] + dp[i-1][2] + ... + dp[i-1][j]
で求めることができます。
dp[i][j-1] = dp[i-1][1] + dp[i-1][2] + ... + dp[i-1][j-1]
であることに注目すると
dp[i][j] = dp[i][j-1] + dp[i-1][j]
と書き直すことができます。
この式でループを回せばO(n^2)でとけます。

コード (99点):

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
#define MAX_N 1010
#define MAX_K 1010
 
long long mod = 1000000007;
 
int n,k;
ll dp[MAX_N][MAX_K];
 
int main() {
  dp[0][1] = 1;
  cin >> n >> k;
if( !( n <= 1000 && k <= 1000 ) ) assert(false);
  REP(i,1,k+1) {
    REP(j,1,n+1) {
      dp[i][j] = ( dp[i][j-1] + dp[i-1][j] ) % mod;
    }
  }
  long long sum = 0;
  REP(j,1,n+1) {
    ( sum += dp[k][j] ) %= mod;
  }
 
  cout << sum  << endl;
  return 0;
}

C - 増築王高橋君
55点しかとれませんでした。
貪欲に選んでゆけば良いのですが、

55点解法は、
AOJにあるワカサギ釣りと同じ感じです。
priority_queueに値を入れて、今の値とpriority_queueの値が一致していればその値は正しいので選択します。
一致していないのであれば古い値なのでpopします。
コード(55点):

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
#define MAX 100010
 
struct Data {
  int id,v;
  bool operator < ( const Data &data ) const {
    if( v != data.v ) return v > data.v;
    return id < data.id;
  }
};
 
int K,N;
ll A[MAX],D[MAX];
 
int get(priority_queue<Data> &Q) {
  while( !Q.empty() && A[Q.top().id] != Q.top().v ) {
    Q.pop();
  }
  assert( !Q.empty() );
  return Q.top().id;
}
 
void compute() {
  priority_queue<Data> Q;
  rep(i,N) Q.push((Data){i,A[i]});
  long long ans = 0;
  rep(i,K) {
    int ID = get(Q);
    ans += A[ID];
    A[ID] += D[ID];
    Q.push((Data){ID,A[ID]});
  }
  cout << ans << endl;
}
 
int main() {
  cin >> K;
  cin >> N;
  rep(i,N) cin >> A[i] >> D[i];
  compute();
  return 0;
}

活動日記 day 28

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest

コンテスト:

A - クイズ
入力が1ならABC,2ならchokudaiと出力します。
コード:

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
  int v;
  cin >> v;
  if( v == 1 ) puts("ABC");
  else puts("chokudai");
  return 0;
}

B - 足し算
整数値を一旦文字列に変換して連接したあと、整数値にもどします。
整数値から文字列への変換は
C++ならstringstream
C++11が使える環境なら to_string
などがあります。
文字列から整数値への変換は
Cなら atoi (intへ変換) や atoll (long longへ変換)
があります。

コード:

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int main() {
  int a,b;
  cin >> a >> b;
  string s = to_string(a) + to_string(b);
  long long v = atoll(s.c_str());
  cout << v * 2LL << endl;
  return 0;
}

C - 壁抜け
xの値を二分探索で決めてdijkstraをします。
コード:

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int H,W,T;
string s[20];
int sx,sy,gx,gy;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
 
bool isValid(int x,int y) { return 0 <= x && x < W  && 0 <= y && y < H; }
 
ll mini[20][20];
 
struct Data {
  int x,y;
  ll v;
  bool operator < ( const Data &data ) const  {
    if( v != data.v ) return v > data.v;
    if( x != data.x ) return x > data.x;
    return y < data.y;
  }
};
 
bool check(ll x) {
  rep(i,H) rep(j,W) mini[i][j] = LLONG_MAX;
  mini[sy][sx] = 0;
  priority_queue<Data> Q;
  Q.push((Data){sx,sy,0});
  while( !Q.empty() ) {
    Data d = Q.top(); Q.pop();
    if( d.x == gx && d.y == gy ) {
      return d.v <= T;
    }
    rep(i,4) {
      int nx = d.x + dx[i];
      int ny = d.y + dy[i];
      if( !isValid(nx,ny) ) continue;
      ll nv = d.v;
      if( s[ny][nx] == '.' ) ++nv;
      else nv += x;
      nv = min(nv,T+10LL);
      if( mini[ny][nx] > nv ) {
	mini[ny][nx] = nv;
	Q.push((Data){nx,ny,nv});
      }
    }
  }
  return false;
}
 
void compute() {
  rep(i,H) rep(j,W) {
    if( s[i][j] == 'S' ) {
      sx = j, sy = i;
      s[i][j] = '.';
    }
    if( s[i][j] == 'G' ) {
      gx = j, gy = i;
      s[i][j] = '.';
    }
  }
  // 最大をもとめる
  ll L = 0, R = T + 10LL;
  while( R - L ){
    ll M = ( L + R ) / 2LL;
    if( check(M) ) L = M + 1LL;
    else           R = M;  
  }
  cout << L - 1LL << endl; 
  
}
 
int main() {
  cin >> H >> W >> T;
  rep(i,H) cin >> s[i];
  compute();
  return 0;
}

D - LCM Rush
全探索で15点しかとれず...

C - A mod B Problem
Bが素数の場合しか解けず...
コード:

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
ll my_pow(ll a,ll e)
{
  return !e?1:
    (e%2?a*my_pow(a,e-1):my_pow(a*a,e/2));
}
 
ll a[10010], L[10010];
 
ll modpow(ll x, ll y, ll mod) {
    ll ret = 1;// ret = x^y%mod;
    while(y) {
        if(y&1)
            ret = (ret*x)%mod;
	//ret = modmultiply(ret, x, mod);
        x = (x*x)%mod;
        //x = modmultiply(x, x, mod);
        y >>= 1;
    }
    return ret;
}
 
long long extgcd(long long a,long long b,long long& x,long long& y)
{
  long long d = a;
  if(b != 0){
    d = extgcd(b,a%b,y,x);
    y -= (a/b)*x;
  }
  else
    x = 1,y = 0;
  return d;
}
 
long long mod_inv(long long a,long long m)
{
  long long x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
 
ll getLength(ll v) {
  stringstream ss;
  ss << v;
  return (ll)ss.str().size();
}
 
ll calcSum(ll init,ll r,ll n,ll B) {  
  ll s = ( ( modpow(r,n,B) - 1 + B ) % B * init ) % B;
  ll t = ( ( r - 1  + B) ) % B;
  return ( s * mod_inv(t,B) ) % B;
}
 
int main() {
  int N;
  cin >> N;
  rep(i,N) cin >> a[i] >> L[i];
  ll B;
  cin >> B;
  ll ans = 0;
  ll total = 0;
  for(int i=N-1;i>=0;--i) {
    ll len = getLength(a[i]);
    ll v = ( (a[i]%B) * calcSum(modpow(10,total,B),modpow(10,len,B),L[i],B) ) % B;
    ans += v;
    ans %= B;
    total += (len * L[i]);
  }
  cout << ans << endl;
  return 0;
}

活動日記 day 27

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest



コメント :
木の直径の求め方を覚えましょう。

A : 高橋くんと年齢
解法 1
実際にソートして真ん中を出力

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
int main() {
  int arr[3];
  rep(i,3) cin >> arr[i];
  sort(arr,arr+3);
  cout << arr[1] << endl;
  return 0;
}

解法 2
総和 - 最大値 - 最小値

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
  int a,b,c;
  cin >> a >> b >> c;
  cout << ( a + b + c ) - max(a,max(b,c)) - min(a,min(b,c)) << endl;
  return 0;
}

B: 高橋くんと文字列圧縮
その通りにシミュレーションしましょう。

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
int main() {
  string s;
  cin >> s;
  rep(i,(int)s.size()) {
    cout << s[i];
    int cnt = 1;
    int sp = i;
    while( i+1 < (int)s.size() && s[sp] == s[i+1] ) {
      ++cnt, ++i;
    }
    cout << cnt;
  } puts("");
  return 0;
}

C: 高橋くんと魔法の箱
入力で与えられた各値について、2で割る限り割り続けます。
その後に残った値の種類の数が答えです。

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int n,a[100010];
 
int main() {
  cin >> n;
  rep(i,n) {
    cin >> a[i];
    while( a[i] % 2 == 0 ) a[i] /= 2;
  }
  set<int> S;
  rep(i,n) S.insert(a[i]);
  cout << (int)S.size() << endl;
  return 0;
}

D: 高橋くんと木の直径
木の直径の求め方をそのまま実行します。
木の直径の求め方は以下の通りです。
1. どこでも良いので1つノードを選んでそこから最も遠いノードxを求めます。
2. 先ほど求めたノードxから最も遠いノードyを求めます。
xとyの距離が木の直径です。

詳細はあり本に蟻ます。

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int main() {
  int n,v;
  cin >> n;
  vector<int> dist1;
  dist1.push_back(0);
  REP(i,1,n) {
    cout << "? 1 " << i+1 << endl;
    cin >> v;
    dist1.push_back(v);
  }
  int next_sp = 0;
  REP(i,1,n) {
    if( dist1[next_sp] < dist1[i] ) next_sp = i;
  }
  int maxi = 0;
  rep(i,n) {
    if( i != next_sp ) {
      cout << "? " << next_sp+1 << " " << i+1 << endl;
      cin >> v;
      maxi = max(maxi,v);
    }
  }
  cout << "! " << maxi << endl;
  return 0;
}

活動日記 day 26

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest


コメント :
動的計画法が2問でましたね。

今回から簡単な解説を残しておこうかと思います。

A - 豆まき

ソートしてその値が何番目かを出力しました。

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
int main() {
  vector<int> vec(3), tmp;
  rep(i,3) cin >> vec[i];
  tmp = vec;
  sort(tmp.begin(),tmp.end());
  rep(i,3) cout << 3 - ( lower_bound(tmp.begin(),tmp.end(),vec[i]) - tmp.begin() ) << endl;
  return 0;
}

vector, sortやlower_boundは良く使うのでここで覚えておきましょう。

vectorは可変長の配列です。
配列と同じように使うことができます。
使用例を以下に示します。

#include<vector>
#include<iostream>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main() {
  vector<int> vec(10); // int vec[10]; みたいなものです。
  rep(i,10) vec[i] = i; // 配列と同様にアクセスすることができます。
  rep(i,10) cout << vec[i] << " "; puts(""); // 0 1 2 3 4 5 6 7 8 9 と出力されます。
  vec.push_back(10); // 後から要素を追加することができます。
  cout << vec.size() << endl; // vecのサイズを出力します。 ここでは 11 と出力されます。
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 0 1 2 3 4 5 6 7 8 9 10 と出力されます。
  vec.clear(); // vectorの中身をすべて消します。 
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 空の行が出力されます。

  vec.push_back(1); // vec[0] = 1 です。
  cout << -vec.size() << endl; // どうなるんでしょうね?
  return 0;
}

sortはその名の通りです。
使用例を以下に示します。

#include<vector>
#include<iostream>
#include<algorithm>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main() {
  vector<int> vec = {5,1,4,2,3}; // C++11から int vec[] = {5,1,4,2,3}; みたいですね。
  sort(vec.begin(),vec.end());
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 1 2 3 4 5 と出力されます。
  sort(vec.begin(),vec.end(),greater<int>()); 
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 5 4 3 2 1 と出力されます。
  return 0;
}

最後にlower_boundの使用例を示します。
lower_boundは引数の配列の指定した範囲の中にある要素の中で、ある値以上のもののうちもっとも左にある要素の位置を返す関数です。

#include<vector>
#include<iostream>
#include<algorithm>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main() {
  vector<int> vec = {10,1,5,2,3}; // C++11から
  sort(vec.begin(),vec.end()); // lower_bound は使う前にsortしておく必要があります。
  cout << *lower_bound(vec.begin(),vec.end(),1) << endl; // vecの中で、1以上であるような要素のうち最も左にある要素を出力します。 ここでは 1 が出力されます。
  cout << *lower_bound(vec.begin(),vec.end(),4) << endl; // 5 が出力されます。
  return 0;
}

B - 文字列の反転

文字列の長さ、操作の回数が高々100なので愚直にシミュレーションしてよさそうです。
( 文字列の長さ * 操作の回数 * 1回の操作にかかる処理の回数 = 100 * 100 * 100 = 10^6 <= 10^8 なので 2sec あれば十分間に合います )
C++を使っているのであれば、string型を利用しましょう。

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
int main() {
  string s;
  cin >> s;
  int n;
  cin >> n;
  rep(i,n) {
    int a,b;
    cin >> a >> b;
    --a, --b;
    reverse(s.begin()+a,s.begin()+b+1); 
  }
  cout << s << endl;
  return 0;
}

reverseは指定した範囲をreverseする関数です。

#include<vector>
#include<iostream>
#include<algorithm>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main() {
  string s = "0123456789";
  reverse(s.begin()+1,s.begin()+6); // [1,6)の範囲をreverseします。
  cout << s << endl; // 0543216789 と出力されます。

  vector<int> vec = {1,2,3,4,5};
  reverse(vec.begin()+1,vec.begin()+4); // [1,4)の範囲をreverseします。
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 1 4 3 2 5 と出力されます。
  return 0;
}

C - 菱型カウント

問題概要 :
R行C列の長方形領域があり、各マスには'o'か'x'が書いてあります。
一辺の長さがKであるような菱形を置けるマスは何箇所ありますか?
ただし、菱形の中に'x'があってはいけません。

一辺の長さが2の菱形
o*o
***
o*o
一辺の長さが3の菱形
oo*oo
o***o
*****
o***o
oo*oo

解法:
動的計画法で解きました。

愚直に計算していくことを考えます。
各マス(x,y)について、そこに長さKの菱形が置けるかどうかを判定するば良いです。
このとき計算量はO(R*C*K*K)なので、最悪の場合 500 * 500 * 500 * 500 = 62,500,000,000となり、2secでは終わりません。
ただ、この問題には部分点がついていて、それであれば R <= 50 かつ C <= 50 であるため最悪でも 50 * 50 * 50 * 50 = 6,250,000 <= 10^8 となり間に合います。
満点を取りたい場合はどうすれば良いのでしょうか。
各マスについて見ていくのはそのままで、そこのマスに菱形を置けるかどうかの判定をO(1)で行うことができれま解けそうです。
可能でしょうか?
動的計画法を使えば可能です。
動的計画法を用いて、そこのマスに菱形の一番下の部分がくるように菱形を置いたときの長さの最長を求めます。

詳しくは以下の記事を参考にしてください。(時間ができたらあとで解説を書き直します)

UVa 10593 : Kites - 土下座しながら探索中

D - バレンタインデー

解けた人は今年バレンタインデーのチョコがもらえるかもしれませんね。
私は解けたのでもらえるかもしれません。

以下解法の概略です。
女子の選び方を全て試します。
女子の選び方が決まったときの男子の選び方を動的計画法で求めます。 ( dp[i] := i人の男子を選んだときの幸福度の最大値 )
その中の最大値が答えです。

#include<iostream>
#include<cstdio>
#include<cassert>
#include<climits>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<vector>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<map>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
#define MAX 300
int N,M,P,Q,R,x[MAX*MAX],y[MAX*MAX],z[MAX*MAX];
int mat[MAX][MAX];
int popcount[1<<20];
 
int dp[20];
 
int score(int girls,int boy) {
  int ret = 0;
  rep(i,N) {
    if( (girls>>i) & 1 ) {
      ret += mat[i][boy];
    }
  }
  return ret;
}
 
void compute() {
  int maxi = 0;
  rep(i,(1<<N)) {
    if( popcount[i] != P ) continue;
    memset(dp,-1,sizeof dp);
    dp[0] = 0;
    rep(j,M) {
      for(int k=Q-1;k>=0;--k) {
	if( dp[k] == -1 ) continue;
	dp[k+1] = max(dp[k+1],
		      dp[k]+score(i,j));
      }
    }
    if( dp[Q] == -1 ) continue;
    maxi = max(maxi,dp[Q]);
  }
  cout << maxi << endl;
}
 
int main() {
  rep(i,(1<<20)) popcount[i] = __builtin_popcount(i);
  memset(mat,0,sizeof mat);
  cin >> N >> M >> P >> Q >> R;
  rep(i,R) {
    cin >> x[i] >> y[i] >> z[i];
    --x[i], --y[i];
    mat[x[i]][y[i]] = z[i];
  }
  compute();
 return 0;
}