活動日記 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;
}