JOI予選 2012-2013

全完してる気がする。

1、
やるだけだけど、ちょっとひねりが利いている。

#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
  int a, b, c, d, l;
  
  scanf("%d%d%d%d%d",&l,&a,&b,&c,&d);
  
  printf("%d\n",l-max((a+c-1)/c,(b+d-1)/d));
  
  return 0;
}

2、
こういうレベルの問題は入力の順番を変えるだけで難易度あがったりするんだなぁとか。

#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int c[3][101], x[3][205], sc[205];

int main(){
  int n;
  scanf("%d",&n);
  
  rep(i,n)rep(j,3){
    scanf("%d",&x[j][i]);
    c[j][x[j][i]]++;
  }
  
  rep(i,n){
    rep(j,3) if(c[j][x[j][i]] == 1) sc[i] += x[j][i];
    printf("%d\n",sc[i]);
  }
  
  return 0;
}

3、
「等間隔」という条件がストーリーの設定とかみ合っていてnice

#include<cstdio>
#include<algorithm>
#include<string>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

char in[105];
string s, t;

int main(){
  int n, ans = 0, tl, l, c;
  bool bl;
  scanf("%d%s",&n,in);
  t = in; tl = t.size();
  
  rep(i,n){
    scanf("%s",in);
    s = in; l = s.size();
    bl = false;
    rep(j,l)rep(k,l){
      c = 0;
      for(int h = k; h < l && c < tl; h += j){
        if(s[h] != t[c]) break;
        c++;
      }
      if(c == tl) bl = true;
    }
    if(bl) ans++;
  }
  
  printf("%d\n",ans);
  
  return 0;
}

4、
直前に着た服だけを覚えておけば良い。
なるほど。こういうDPきたか。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

const int INF = 100000000;

int t[205], a[205], b[205], c[205], dp[205][205];

int main(){
  int d, n, ans = 0;
  scanf("%d%d",&d,&n);
  
  rep(i,d) scanf("%d",&t[i]);
  rep(i,n) scanf("%d%d%d",&a[i],&b[i],&c[i]);
  
  rep(i,d)rep(j,n) dp[i][j] = -INF;
  
  rep(j,n) if(a[j] <= t[0] && t[0] <= b[j]) dp[0][j] = 0;
  
  for(int i = 1; i < d; i++){
    rep(j,n){
      if(a[j] <= t[i] && t[i] <= b[j]){
        rep(k,n) dp[i][j] = max(dp[i][j], dp[i-1][k]+abs(c[j]-c[k]));
      }
    }
  }
  
  rep(i,n) ans = max(ans,dp[d-1][i]);
  printf("%d\n",ans);
  
  return 0;
}

5、
座標圧縮+imos法でやりました。
なんか座標圧縮の境界とか自信無い・・・
これ普通にムズイと思う。

#include<cstdio>
#include<algorithm>
#define fi first
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;

P p[3][205]; int q[105][3];
int d[205][205][205];

int main(){
  int n, n2, k, x, y, z, hu;
  scanf("%d%d",&n,&k); n2 = n*4;
  
  rep(i,n*2)rep(j,3){
    scanf("%d",&x); if(i&1) x--;
    p[j][i*2] = P(x,(i&1)==0?i:n*2);
    p[j][i*2+1] = P(x+1,(i&1)==1?i:n*2);
  }
  
  rep(j,3) sort(p[j],p[j]+n2);
  rep(j,3){
    x = 0;
    rep(i,n2){
      if(p[j][i].fi != p[j][x].fi) x = i;
      q[p[j][i].second][j] = x;
    }
  }
  
  rep(i,n){
    rep(j,8){
      hu = 1;
      if(j&1){ x = q[i*2+1][0]; hu *= -1;} else x = q[i*2][0];
      if(j&2){ y = q[i*2+1][1]; hu *= -1;} else y = q[i*2][1];
      if(j&4){ z = q[i*2+1][2]; hu *= -1;} else z = q[i*2][2];
      d[x][y][z] += hu;
    }
  }
  
  rep(i,n2)rep(j,n2)rep(h,n2) d[i+1][j][h] += d[i][j][h];
  rep(i,n2)rep(j,n2)rep(h,n2) d[i][j+1][h] += d[i][j][h];
  rep(i,n2)rep(j,n2)rep(h,n2) d[i][j][h+1] += d[i][j][h];
  
  ll ans = 0;
  rep(i,n2)rep(j,n2)rep(h,n2){
    if(d[i][j][h] >= k){
      ans += ll(p[0][i+1].fi-p[0][i].fi)*ll(p[1][j+1].fi-p[1][j].fi)*ll(p[2][h+1].fi-p[2][h].fi);
    }
  }
  
  printf("%lld\n",ans);
  
  return 0;
}

6、
同じところを通っても1回しかお土産を買えないというのがネック。
最初気づかなくてdp[回数][x][y]みたいなことして、簡単やなぁとか思ってた・・・
左or上に移動する回数が3回までならば、7ターン以上前に通った地点を通ることがないことに気づけば良い。
mem[6個前までの移動法][タイムロスな動き方をした回数][x][y] でメモ化再帰した。
メモ化の方がDPより実装分かりやすいし、探索量も不可能なパターンを探索せずにすむので減る。

#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

const int INF = 100000000, n12 = 1<<12;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int h, w, k;
char m[55][55];
int mem[1<<12][4][51][51];

int dfs(int s, int c, int x, int y){
  if(mem[s][c][x][y]) return mem[s][c][x][y];
  int nx, ny, t = (s<<2)&(n12-1), u, r = -INF;
  rep(v,2){
    nx = x+dx[v]; ny = y+dy[v];
    if(nx<h&&ny<w&&m[nx][ny]!=-1){
      r = max(r,dfs(t+v,c,nx,ny));
    }
  }
  
  if(c < k){
    for(int v = 2; v < 4; v++){
      nx = x+dx[v]; ny = y+dy[v];
      if(nx>=0&&ny>=0&&m[nx][ny]!=-1){
        r = max(r,dfs(t+v,c+1,nx,ny));
      }
    }
  }
  
  bool bl = false;
  u = s; nx = x; ny = y;
  rep(i,6){
    nx -= dx[u&3]; ny -= dy[u&3];
    if(!(nx>=0&&ny>=0&&nx<h&&ny<w)) break;
    if(nx == x && ny == y) bl = true;
    u >>= 2;
  }
  
  if(!bl) r += m[x][y];
  
  if(r < 0 && x == h-1 && y == w-1) r = 1;
  
  //printf("%d %d %d %d : %d\n",s,c,x,y,r);
  return mem[s][c][x][y] = r;
}

int main(){
  scanf("%d%d%d",&h,&w,&k);
  
  rep(i,h){
    scanf("%s",m[i]);
    rep(j,w){
      if(m[i][j] == '.') m[i][j] = '0';
      if(m[i][j] == '#') m[i][j] = -1; else m[i][j] -= '0';
    }
  }
  
  printf("%d\n",dfs(0,0,0,0)-1);
  
  return 0;
}

メモかテーブルの初期化を省くために全ての値を+1で計算していますが、普通に-1とかに初期化しとく方が分かりやすくて良いと思った。