2011年JOI本選 - ド素人のメモ帳

2011年のJOI本選問題を解いてみました。
１～３までは苦戦しながらも自力で行けましたが４，５はヒントを貰ったり色々して解きました。
実力がほしいのと解法の証明とかできるようになりたい。
□１問目
 □２問目
 □３問目
 □４問目
 □５問目

1.Planetary Exploration
■ 問題

横n、縦mの'J','O','I'だけでできた文字列が与えられる。
k個の左上と右下の座標が与えられて、その範囲の中にある'J','O','I'の数を出力する。

■ 解法

一見与えられた範囲の中を２重ループで調べれば良いと思うが、オーダーがO(NMK)となり、kの範囲が大きいためとてもじゃないが間に合わない。
なので、二次元累積和を用い、いらないところを引いていくということをすると、
累積和を求めるのにO(NM)、範囲を調べるのに(K)となり、間に合う用になる。

■ ソース

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<utility>
#include<string>

using namespace std;

char str[1005];
int js[1005][1005];
int os[1005][1005];
int is[1005][1005];

main(){
  int J,O,I;
  int m,n,k;
  int i,j,l;
  int a,b,c,d;
  int maxx,maxy,minx,miny;

  memset(str,0,sizeof(str));
  scanf("%d %d",&m,&n);
  scanf("%d",&k);
  for(i=1;i<=m;i++){
    scanf("%s",str);
    for(j=0;j<n;j++){
      if(str[j]=='J') js[i][j+1]++;
      if(str[j]=='O') os[i][j+1]++;
      if(str[j]=='I') is[i][j+1]++;
    }
  }
  for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
      js[i][j] += js[i][j-1];
      os[i][j] += os[i][j-1];
      is[i][j] += is[i][j-1];
    }
  }
  for(j=1;j<=n;j++){
    for(i=1;i<=m;i++){
      js[i][j] += js[i-1][j];
      os[i][j] += os[i-1][j];
      is[i][j] += is[i-1][j];
    }
  }
 
  for(l=0;l<k;l++){
    scanf("%d %d %d %d",&a,&b,&c,&d);
    minx=min(a,c);
    miny=min(b,d);
    maxx=max(a,c);
    maxy=max(b,d);
    minx--;
    miny--;
    J=js[maxx][maxy]-js[maxx][miny]-js[minx][maxy]+js[minx][miny];
    O=os[maxx][maxy]-os[maxx][miny]-os[minx][maxy]+os[minx][miny];
    I=is[maxx][maxy]-is[maxx][miny]-is[minx][maxy]+is[minx][miny];
    printf("%d %d %d\n",J,O,I);
  }

}

2.Books
■ 問題
n冊の本の値段とジャンルが与えられる。
同じジャンルをたくさん売るとちょっと高く売れる。
k冊の本を売るときの最大金額を求める。
■ 解法
ジャンルごと大きい順にソートして、各ジャンルごと高いものから何冊ずつ取るかでDPする。
ジャンルごとソートするだけじゃなくて、上から何冊かとった時の値段を入れとくと計算が楽そう。
ループで解いたがメモ化再起の方が分かりやすそう。
■ ソース

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cctype>
#include<vector>

using namespace std;
vector<int> book[10];
vector<int> yen[10];
int dp[11][2001];

main(){
  int n,k;
  int c,g;
  int sum;
  int a=0;

  scanf("%d %d",&n,&k);
  for(int i=0;i<n;i++){
    scanf("%d %d",&c,&g);
    book[g-1].push_back(c);
  }


  for(int i=0;i<10;i++){
    sort(book[i].begin(),book[i].end(),greater<int>());
    sum=0;
    for(int j=0;j<book[i].size();j++){
      sum+=book[i][j];
      yen[i].push_back(sum+j*(j+1));
    }
  }

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

  for(int i=0;i<10;i++){
    for(int j=0;j<yen[i].size();j++){
      a=i;
      for(int l=j;l<k;l++){
	dp[i+1][l+1]=max(max(dp[i+1][l+1],dp[i][l+1]),dp[i][l-j]+yen[i][j]);
      }
    }
  }
  printf("%d\n",dp[a+1][k]);
}

3.Shopping in JOI Kingdom
■ 問題
N個の街とそれらをつなぐM個の道路があります。
K個の街にショッピングモールがある時、ショッピングモールまでの距離が最長となる地点の距離を、四捨五入して求めなさい。（最長の地点は道路の場合もある。）
■ 解法
ショッピングモールのある街をすべて始点としてダイクストラして、それぞれの街までの最短距離を求める。
街a,b、道路の距離cとして
a+x==a+(c-x)
となるような道路をｘで分けたところをが道路間の最長になるので全部の辺に試す。
ショッピングモールからの距離が最長の街の街から続く道路だけでもよさそう。
■ ソース

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define INF 1<<30

struct edge{
  int to,cost;
};
struct road{
  int now,to,cost;
};
typedef pair<int , int> P;
int id[3333];
vector<road> ro;
vector<edge> cost[3333];
priority_queue<P, vector<P> , greater<P> >que;

int n,m,k;
int res=-1;

int main(void){
  int h,t,c,s;
  fill(id,id+3333,INF);
  scanf("%d %d %d",&n,&m,&k);
  for(int i=0;i<m;i++){
    scanf("%d %d %d",&h,&t,&c);
    edge temp={t,c};
    road tamp={h,t,c};
    ro.push_back(tamp);
    cost[h].push_back(temp);
    temp.to=h;
    cost[t].push_back(temp);
  }
  for(int i=0;i<k;i++){
    scanf("%d",&s);
    id[s]=0;
    que.push(P(0,s));
  }

  while(!que.empty()){
    P p=que.top();
    que.pop();
    int v=p.second;
    if(id[v]<p.first)continue;
    for(int i=0;i<cost[v].size();i++){
      edge e=cost[v][i];
      if(id[e.to]>id[v]+e.cost){
	id[e.to]=id[v]+e.cost;
	que.push(P(id[e.to],e.to));
      }
    }
  }
  for(int i=0;i<ro.size();i++){
    road r=ro[i];
    int z=id[r.now]-id[r.to];
    z*=(z<0)?-1:1;
    z+=r.cost;
    z=(int)(((double)z/2)+0.5);
    res=max(res,min(id[r.now]+z,id[r.to]+z));
  }
  printf("%d\n",res);
}

4.Walking Santa
■ 問題
N個の家がある村のある点からサンタがチョコレートケーキを配る。
一度に複数のケーキは配れないので一軒一軒、家と任意の点を往復する。
ただし、最後だけは片道で良い。
その時、総移動距離が最短となる点の座標とすべてを配るときの総距離を求める。
■ 解法
家の座標をx,yごと別々にソートして、家の総数の半分番目のデータ（総数が奇数なら1つ、偶数なら2つ）に求めるべき任意の点が含まれているらしい。
なので、ソートした真ん中のｘとｙの座標に関してだけ調べれば良い。（たぶん最大４通り）
これでほんとうにいいかはわからない。
■ ソース

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

typedef struct{
  long long int x,y;
}ho;
ho house[100000];
vector<long long int> hx;
vector<long long int> hy;
long long int x[2]={0};
long long int y[2]={0};
long long int ans=1LL<<62,ax=0,ay=0;

int w,h,n;

int main(void){
  scanf("%d %d %d",&w,&h,&n);
  for(int i=0;i<n;i++){
    scanf("%d %d",&house[i].x,&house[i].y);
    hx.push_back(house[i].x);
    hy.push_back(house[i].y);
  }
  sort(hx.begin(),hx.end());
  sort(hy.begin(),hy.end());

  int xs,xp=(hx.size()+1)%2+1;
  int ys,yp=(hy.size()+1)%2+1;
  xs=hx.size();
  ys=hy.size();
  for(int i=0;i<xp;i++) x[i]=hx[xs/2+i-xp/2];
  for(int i=0;i<yp;i++) y[i]=hy[ys/2+i-yp/2];

  long long int nx,ny;
  long long int lx,ly;
  long long int nmax=0;
  long long int temp=0;
  for(int i=0;i<xp;i++){
    nx=x[i];
    for(int j=0;j<yp;j++){
      ny=y[j];
      nmax=0;
      temp=0;
      for(long long int l=0;l<n;l++){
	lx=nx-house[l].x;
	ly=ny-house[l].y;
	lx*=(lx>=0)?1:-1;
	ly*=(ly>=0)?1:-1;
	long long int tamp=lx+ly;
	if(nmax<tamp) nmax=tamp;
	tamp*=2;
	temp+=tamp;
      }
      temp-=nmax;
      if(temp<ans){
	ans=temp;
	ax=nx;
	ay=ny;
      }
    }
  }
  printf("%lld\n%lld %lld\n",ans,ax,ay);
}

5.Bug Party
■ 問題
調査対象の微生物N匹分の毒素の放出量と許容量が与えられる。
シャーレの中にいる微生物の放出量の平均が微生物の許容量より大きいとその微生物は死んでしまう。
シャーレの中の微生物が全て生きられるときのシャーレに入れられる微生物の数の最大値を求める。
■ 解法
n匹取った時出来るかどうかで二分探索して最大値を求める。
n匹の時全て生き残らせられるか放出量を小さいものからｎ匹取り出して試し、出来なかったら１匹捨てて次に放出量が小さいものを取る。
捨てるものはｎ匹の中から最も許容量が低いものを選ぶ。
なお、最も～な時を選ぶというので同じ値だった場合はもう一方のデータで決める。（pair使うと便利）
大きいものの取り出し等はsortやpriority_queueを使うといい感じにできる。
放出量の平均を求めると誤差が出てしまうので割り算を使わないように式変形する。
■ ソース

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include <utility>
#include<vector>
using namespace std;

typedef pair<long long int, long long int> ui;
ui uil[333333];
long long int n;
long long int res=0;
long long int s,h,e;


bool cha(long long int nn){
  long long int i;
  long long int tamp;
  ui temp,tempp;
  long long int ho=0;
  long long int kmin=100009;
  priority_queue<ui,vector<ui>,greater<ui> >tq;

  for(i=0;i<nn;i++){
    temp=uil[i];
    temp.second*=-1;
    ho+=temp.first;
    if(temp.second<kmin)kmin=temp.second;

    tamp=temp.first;
    temp.first=temp.second;
    temp.second=tamp;

    temp.second*=-1;
    tq.push(temp);
  }

  for(;i<n;i++){
    if(!(ho>kmin*nn))return true;

    temp=tq.top();
    tq.pop();
    ho-=temp.second*-1;

    temp=uil[i];
    temp.second*=-1;
    ho+=temp.first;

    tamp=temp.first;
    temp.first=temp.second;
    temp.second=tamp;

    temp.second*=-1;
    tq.push(temp);

    temp=tq.top();
    kmin=temp.first;
  }
  if(!(ho>kmin*nn))return true;
  return false;
}


int main(void){
  scanf("%d",&n);
  for(long long int i=0;i<n;i++){
    scanf("%d %d",&uil[i].first,&uil[i].second);
    uil[i].second*=-1;
  }
  sort(uil,uil+n); 
  s=1;
  e=n;
  while(s<=e){
    h=(s+e)/2;
    if(cha(h)){
      res=(res<h)?h:res;
      s=h+1;
    }
    else{
      e=h-1;
    }
  }
  printf("%d\n",res);
}

■感想

HTMLムズすぎ
説明ムズすぎ
日本語ムズすぎ

初めてのブログだったのでかなり手こずった。
次回からは短く見やすくわかりやすい「日本語」を書きたい。