YNU.cpc

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

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

活動日記 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: 高橋くんと魔法の箱
入力で与えられた各値について、２で割る限り割り続けます。
その後に残った値の種類の数が答えです。

#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. どこでも良いので１つノードを選んでそこから最も遠いノード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


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

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

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なので愚直にシミュレーションしてよさそうです。
( 文字列の長さ * 操作の回数 * １回の操作にかかる処理の回数 = 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;
}