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