はやし屋

競技プログラミングのメモ きたない

AOJ 0094 0095 0096 0097 0098 0099

AOJ 0094 坪面積の計算
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0094

1坪のをコピペする

#include<cstdio>
int main(){
  double a,b;
  scanf("%lf%lf",&a,&b);
  printf("%.6lf\n",a*b/3.305785);
  return 0;
}

AOJ 0095 ワカサギ釣り大会
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0095

pairな問題

#include<iostream>
using namespace std;
int main(){
  int n ;cin >> n;
  pair < int , int > ret(-1<<28,1<<28);
  while(n--){
    int a , b ;cin >> a >> b;
    ret = max(ret,make_pair(b,-a));
  }
  cout << -ret.second << " " << ret.first << endl;
}

AOJ 0096 Sum of 4 Integers II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096

かける

#include<iostream>
using namespace std;
int c[4096];
int main(){

  for(int i = 0 ; i <= 1000 ; ++i){
    for(int j = 0 ; j <= 1000 ; ++j){
      c[i+j]++;
    }
  }

  int n ;
  while(cin >> n){
    long long cnt = 0 ;
    for(int i = 0 ; i <= 2000 ; ++i){
      for(int j = 0 ; j <= 2000 ; ++j){
	if(i+j == n)cnt+=c[i]*c[j];
      }
    }
    cout << cnt << endl;
  }
  return 0;
}

AOJ 0097 Sum of Integers II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0097

状態をどう持ってどう数え上げるか考えさせるdp問題だった

#define int long long
ってできるんだ怖

メモ化

#include<iostream>
#include<cstring>
using namespace std;
#define int long long
 
int n , s;
// num , sum , idx
int dp[10][1024][101];
 
int solve(int depth , int sum , int idx){
  if(!depth)return dp[depth][sum][idx] = !sum?1:0;
  if(~dp[depth][sum][idx])return dp[depth][sum][idx];
  int ret = 0;
  for(int i = idx+1 ; i <= 100 && i <= sum; ++i){
    ret += solve(depth-1,sum-i,i);
  }
  return dp[depth][sum][idx] = ret;
}
 
main(){
  while(cin >> n >> s && (n|s)){
    memset(dp,-1,sizeof(dp));
    cout << solve(n,s,-1) << endl;
  }
}


for
きたない

#include<iostream>
using namespace std;
#define int long long

int n , s;
// kosuu , sum , num
int dp[10][1024][101];

main(){

  for(int i = 0 ; i < 101 ; ++i)dp[0][i][i] = 1;

  for(int i = 1 ; i < 9 ; ++i){
    for(int j = 0 ; j < 1024; ++j){
      for(int k = 0 ; k < 101; ++k){
	for(int l = k+1 ; l < 101 ; ++l){
	  if(j-l>=0)dp[i][j][l] += dp[i-1][j-l][k];
	}
      }
    }
  }

  int res[11][1024]={};
  for(int i = 0 ; i < 9 ; ++i){
    for(int j = 0 ; j < 1024 ; ++j){
      for(int k = 0 ; k < 101 ; ++k){
	res[i][j] += dp[i][j][k];
      }
    }
  }

  while(cin >> n >> s && (n|s)){
    cout << res[n-1][s] << endl;
  }
}

AOJ 0098 Maximum Sum Sequence II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098

四角形をゴニョゴニョするかんじ

#include<iostream>
#include<vector>
#define max(a,b) (a>b?a:b)
using namespace std;
#define int long long

int n , s;
int dp[111][111];

main(){
  int n ;cin >> n;
  int ret = -1<<28 ;

  for(int Q = 0 ; Q < n ; ++Q){
    vector < int > v(n);
    for(int i = 0 ; i < n ; ++i)cin >> v[i];

    for(int row = 0 ; row < n ; ++row){
      int sum = 0;
      for(int col = row ; col < n ; ++col){
	sum += v[col]; 
	dp[row][col] = max(0,dp[row][col])+sum;
	ret = max(ret,dp[row][col]);
      }
    }
  }

  cout << ret << endl;

  return 0;
}

AOJ 0099 ワカサギ釣り大会 2
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0099

簡単じゃんって思ったらところどころつまずいた
速く解きたい。

いろんな解法ある

priority_queue解

#include<iostream>
#include<vector>
#include<map>
#include<queue>

using namespace std;

main(){
  // num , -id
  priority_queue < pair < int , int > > que;
  int n , Q;cin >> n >> Q;

  map < int , int > mp; 

  while(Q--){
    int a , b;cin >> a >> b;
    mp[a] += b;que.push(make_pair(mp[a],-a));
    for(;;que.pop()){
      pair < int , int > pi = que.top();
      if(mp[-pi.second] == pi.first){
	cout << -pi.second << " " << pi.first << endl;
	break;
      }
    }

  }
  return 0;
}

set解

#include<iostream>
#include<vector>
#include<set>
#include<map>

using namespace std;

main(){
  // num , -id
  set < pair < int , int > > st;
  int n , Q;cin >> n >> Q;

  map < int , int > mp; 

  while(Q--){
    int a , b;cin >> a >> b;
    st.erase(make_pair(-mp[a],a));
    mp[a] += b;st.insert(make_pair(-mp[a],a));
    cout << st.begin()->second << " " << -st.begin()->first << endl;
  }
  return 0;
}

SegmentTree解
lg(10^6) = 19.9315685693
です。

#include<iostream>
#include<vector>
#include<set>
#include<map>

using namespace std;

pair < int , int > seg[1 << 22];

void add(int id , int a){
  int k = id + (1 << 20);
  seg[k].first += a;
  while(k){
    k = (k-1)/2;
    seg[k] = max(seg[2*k+1],seg[2*k+2]);
  }
}

main(){

  int n , Q;cin >> n >> Q;

  for(int i = 0 ; i < (1<<20) ; ++i){
    seg[(1<<20)+i].second = -i;
  }
  while(Q--){
    int a , b;cin >> a >> b;a--;
    add(a,b);
    cout << -seg[0].second+1 << " " << seg[0].first << endl;
  }
  return 0;
}

僕はSegmentTree解が綺麗で好きです