はやし屋

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

JOI予選2013の復習

ぼちぼち色々埋めていきます

1.宿題 (Homework) AOJ0576
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0576
切り上げる。

#include<iostream>
using namespace std;
int main(){
  int l , a , b , c , d;
  cin >> l >> a >> b >> c >> d;
  cout << (l-max((a+c-1)/c,(b+d-1)/d)) << endl;
}

2. 数当てゲーム (Unique number) AOJ0577
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0577
行と列がごっちゃにならんようにする

#include<iostream>
using namespace std;
int main(){
  int n;cin >> n;
  int x[1111][3];
  int res[3][111111] = {};
  for(int i = 0 ; i < n ; ++i){
    for(int j = 0 ; j < 3 ; ++j){
    cin >> x[i][j];
    res[j][x[i][j]]++;
    }
  }
  for(int i = 0 ; i < n ; ++i){
    int ret = 0;
    for(int j = 0; j < 3 ; ++j){
      if(res[j][x[i][j]] == 1){
       ret += x[i][j];
      }
    }
    cout << ret << endl;
  }
}

3. 看板 (Signboard) AOJ0578
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0578
等間隔に切り落としてゆく。
判定を関数化するとgotoとかいらなくて綺麗だと思う。

#include<iostream>
#include<string>
using namespace std;
string target;
int chk(string s){
  // 何個飛ばしか
  for(int t = 1 ; t < s.size() ; ++t){
    // どこから始まる
    for(int idx = 0; idx < s.size() ; ++idx){
      // じゃっじ
      string ret;
      for(int j = idx ; j < s.size() ; j += t){
        ret += s[j];
      }
      if(~ret.find(target)){
       return 1;
      }
    }
  }
  return 0;
}
 
int main(){
  int ret = 0;
  int n ; cin >> n;
  cin >> target;
  for(int i = 0 ; i < n ; ++i){
    string s ; cin >> s;
    ret += chk(s);
  }
  cout << ret << endl;
}

4. 暑い日々 (Hot days) AOJ0579
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0579
普通のdp。
確実にやるにはやっぱメモ化がよい。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
 
int t[1111];
 
int a[1111],b[1111],c[1111];
 
int dp[222][222];
 
int n ,d;
 
int solve(int idx ,int huku){
 
  if(idx == d) return 0;
  if(~dp[idx][huku])return dp[idx][huku];
  int ret = 0;
 
  for(int i = 0 ; i < n ; ++i){
    if(a[i] <= t[idx] && t[idx] <= b[i]){
      ret = max(ret,solve(idx+1,i)+abs(c[i]-c[huku]));
    }
  }
 
  return dp[idx][huku] = ret;
}
 
int main(){

  cin >> d >> n;
  for(int i = 0 ; i < d ; ++i){
    cin >> t[i];
  }
 
  for(int i = 0 ; i < n ; ++i){
    cin >> a[i] >> b[i] >> c[i];
  }
 
 
  int ret = 0;
  memset(dp,-1,sizeof(dp));
  for(int i = 0 ; i < n ; ++i){
    if(a[i] <= t[0] && t[0] <= b[i]){
      ret = max(ret,solve(1,i));
    }
  }
 
  cout << ret << endl;
}

5.魚の生息範囲 (Fish) AOJ0580
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0580
解説見ながら書いた
思いつくわけ無い

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 56
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define rep(i,n) for(ll i = 0; i < (ll)n ; ++i)
 
 
ll n ,k;
ll x1[N],x2[N],y1[N],y2[N],z1[N],z2[N];
vector < ll > xs,ys,zs;
ll calc(){
  ll ans = 0;
  rep(x,xs.size()-1)
    rep(y,ys.size()-1)
    rep(z,zs.size()-1)
    {
    ll cnt = 0;
    rep(i,n){
      if(x1[i] <= xs[x] && xs[x+1] <= x2[i] && 
     y1[i] <= ys[y] && ys[y+1] <= y2[i] && 
     z1[i] <= zs[z] && zs[z+1] <= z2[i] )++cnt;
    }
    if(cnt >= k)
      ans += (xs[x+1]-xs[x]) * (ys[y+1] - ys[y]) * (zs[z+1] - zs[z]);
    }
  return ans;
}
int main(){
  scanf("%lld%lld",&n,&k);
  rep(i,n)
    scanf("%lld%lld%lld %lld%lld%lld",x1+i,y1+i,z1+i ,x2+i,y2+i,z2+i);
  rep(i,n){
    xs.pb(x1[i]);ys.pb(y1[i]);zs.pb(z1[i]);
    xs.pb(x2[i]);ys.pb(y2[i]);zs.pb(z2[i]);
  }
  sort(ALL(xs));sort(ALL(ys));sort(ALL(zs));
  printf("%lld\n",calc());
  return 0;
}

6.お土産購入計画 (Gifts) AOJ0581
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581
またとく
2ビットでほげんのかな

追記:解いた
http://hayashiya.hatenablog.com/entry/2013/11/11/220117


感想
・5問目おもいつかん
・ざあつこわい
・3問目は良問
・問題飲み込むの遅いなあ...
・JOIなんか難化してる