YNU.cpc

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

活動日記 day 34

活動日記

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

A - 25個の文字列
N-1を5で割った商と余りを１文字目と２文字目のインデックスに指定すれば解くことができます。
（全列挙したものをソートしても解くことは可能です。）

#include <iostream>
using namespace std;
 
int main() {	
	string S;
	int N;	
	cin >> S >> N;
	
	cout << S[(N - 1) / 5] << S[(N - 1) % 5] << endl;
	
	return 0;
}

B - 双子とスイカ割り
1行ずつシミュレートしましょう。

#include <iostream>
using namespace std;
 
int main() {	
	int N, A, B;
	cin >> N >> A >> B;
	
	int sum = 0;
	
	for(int i = 0; i < N; i++){
		string s;
		int d;		
		cin >> s >> d;
		
		if(d < A) d = A;
		else if(d > B) d = B;
		
		if(s == "West") sum += d;
		else sum -= d;
 
	}
	
	if(sum == 0) cout << 0 << endl;
	else if(sum > 0) cout << "West " << sum << endl;
	else cout << "East " << -sum << endl;
 
	return 0;
}

C - 双子と○×ゲーム
未定

D - 25個の整数
未定

E - ウサギとカメ
未定

活動日記 day 33

活動日記

活動内容 :
コンテスト (チーム戦)
コンテスト : Virtual Arena: Room 3394

A - Selection of Participants of an Experiment

全探索で解けます。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>
 
#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 a[1001]={0};
 
int main() {
  int n;
  while(scanf("%d",&n),n!=0){
    for(int i=0;i<n;++i){
      scanf("%d ",&a[i]);
    }
    int minimum = INT_MAX;
    for(int i=0;i<n;++i){
      for(int j=i+1;j<n;++j){
        if(abs(a[i] - a[j]) < minimum)minimum = abs(a[i] - a[j]);
      }
    }
    printf("%d\n",minimum);
  }
 
  return 0;
}

B - Look for the Winner!
入力を捨てるのを忘れないようにしましょう。

#include <iostream>
#include <stdio.h>
using namespace std;
 
int main()
{
    while (true)
    {
    LABEL:
        int array[30] = {0};
        int n;
        int top = 0;
        int topalpha = 0;
        int next = 0;
        int nextalpha = 0;
        int amari = 0;
        cin >> n;
        if (n == 0)
        {
            return 0;
        }
        char temp;
        for (int i = 0; i < n; i++)
        {
            cin >> temp;
            temp = temp - 65;
            array[temp]++;
 
            //top sagashi
            for (int j = 0; j < 30; j++)
            {
                if (top < array[j])
                {
                    top = array[j];
                    topalpha = j;
                }
            }
 
            //2nd sagashi
            for (int j = 0; j < 30; j++)
            {
                if (next < array[j] && j != topalpha)
                {
                    next = array[j];
                    nextalpha = j;
                }
            }
            amari = n - i - 1;
            char hoge;

            if (top <= next + amari)
            {
                //mada wakaran
                continue;
            }
            else
            {
                //win top or tie
                if (top == next)
                {
                    cout << "TIE" << endl;

                    for (int j = 0; j < amari; j++)
                    {
                        cin >> hoge;
                    }
                    goto LABEL;
                }
                else
                {
                    printf("%c ", 65 + topalpha);
                    printf("%d\n", i + 1);
                    for (int j = 0; j < amari; j++)
                    {
                        cin >> hoge;
                    }
                    goto LABEL;
                }
            }
        }
        printf("TIE\n");
    }
    return 0;
}

E - Arithmetical CAPTCHA
全探索です。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>
 
#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[5];
char op[] = {'+','-','='};
 
bool check(deque<char> &ops) {
  bool found = false;
  rep(i,3) if( ops[i] == '=' ) { found = true; break; }
  if( !found ) return false;
  set<int> S;
  int v = n[0];
  rep(i,3) {
    if( ops[i] == '+' ) {
      v += n[i+1];
    } else if( ops[i] == '-' ) {
      v -= n[i+1];
    } else {
      S.insert(v);
      v = n[i+1];
    }
  }
  S.insert(v);
  return S.size() == 1;
}
 
bool dfs(int cur,deque<char> &deq) {
  if( cur >= 3 ) {
    return check(deq);
  }
  rep(i,3) {
    deq.push_back(op[i]);
    if( dfs(cur+1,deq) ) return true;
    deq.pop_back();
  }
  return false;
}
 
void compute() {
  deque<char> deq;
  assert( dfs(0,deq) );
  cout << n[0] << " ";
  rep(i,3) {
    cout << deq[i] << " " << n[i+1];
    if( i != 2 ) cout << " ";
  } puts("");
}
 
int main() {
  int T,CNT=1;
  cin >> T;
  while( T-- ) {
    cout << "Case #" << CNT++ << ": ";
    rep(i,4) cin >> n[i];
    compute();
  }
  return 0;
}

コメント：
蟻本を読んでSG定理を復習しようと思います。

活動日記 day 32

活動日記

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

A - 動物園
問題文中にある通りに実装します

def main():
    A,B,C,K = map(int,input().split())
    S,T = map(int,input().split())
    ans = S * A + T * B
    if S + T >= K:
        ans -= (S+T) * C
    print(ans)

if __name__ == "__main__":
    main()

B - 自動ドア
１秒ごとにシミュレーションすると間に合わないので、
イベント点のみのシミュレートし答えを計算します

import sys

def main():
    N,T = map(int,input().split())
    A = [int(input()) for _ in range(N)]
    ans,pre = 0, 0
    for v in A:
        if pre < v:
            ans += T
            pre = v + T
        else: 
            ans += ( v + T - pre )
            pre = v + T
    print(ans)

if __name__ == "__main__":
    main()

C - 民族大移動
未来

D - 動的計画法
未来

C - だれじゃ
未来

活動日記 day 31

活動日記

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

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;
 
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
答えとなる閉路は家１を端点に持つ辺をちょうど２本含みます。
そのため、家１から出ている辺を全て取り除いた状態のグラフの全点間の最短経路をワーシャルフロイドや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;
 
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
問題文中の処理を行ったとしても、その点集合において変化しない情報について考えます。
例えば、最も近い２点は処理後も変化しません。
そのため、処理前と処理後の最も近い２点間の距離を求め、処理後の距離で処理前の距離を割れば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個１を出力すれば良いです。
コード:

#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 - 嘘つきの高橋くん
同じ町を２回以上訪れている場合は明らかに最短ではないです。
a,b,P[i]の中に現れる整数で、その出現回数が２回以上のものが存在すれば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 - 正直者の高橋くん
辺の重みが１なので、幅優先で最短経路を計算しつつ
実際にそのような経路が何通りあるのか計算しましょう。

コード:

#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 - 増築王高橋君
５５点しかとれませんでした。
貪欲に選んでゆけば良いのですが、

５５点解法は、
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
全探索で１５点しかとれず...

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