2012-07-24

AtCoder006

A - 宝くじ

■問題
購入した宝くじと当選結果の一致している数字の数を数えてそれに対応した順位を出力する。
５つだった場合はボーナス数字があるかどうかで決める。

■解法
一致しているものを数えるだけ
やるだけ

■ソース

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<string>

#include<vector>

using namespace std;

int e[10],l[10],b,ee,ll;

int main(void){

  int a=0,c=0;

  int ans[]={0,0,0,5,4,3,1,2};

  for(int i=0;i<6;i++){

    cin >> ee;

    e[ee]++;

  }

  cin >> b;

  for(int i=0;i<6;i++){

    cin >> ll;

    l[ll]++;

  }



  for(int i=0;i<10;i++){

    if(e[i] && l[i]){

      a++;

    }

  }

  if(a == 5 && l[b]){

    a+=2;

  }

  cout << ans[a] << endl;



}

B - あみだくじ

■問題
あみだくじの線とあたりが与えられたときあたりにたどり着ける線がどれか求める。

■解法
下からルール通りたどるだけ
やるだけ

■ソース

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<string>

#include<vector>

using namespace std;

int main(void){

  int n,l,m;

  char s[21][101];

  cin >> n >> l;

  int sl=n*2-1;

  cin.get();

  for(int i=0;i<l+1;i++){

    fgets(s[i],sizeof(s[i]),stdin);

  } 

  for(int i=0;i<sl;i++){

    if(s[l][i]=='o'){

      m=i;

      break;

    }

  }

  for(int i=l-1;i>=0;i--){

    if(m < sl-1 && s[i][m+1]=='-'){

      m+=2;

    }else if(0 < m && s[i][m-1]=='-'){

      m-=2;

    }

  }

  cout << m/2+1 << endl;

}

C - 積み重ね

■問題
箱が下のものより上のものが軽いか同じ重さになるように積んだとき、山の数が最小の値を求めなさい。

■解法
積む時は、積める山の中で一番軽いところに積むのが最適である。
積めるところがない場合は新しい山を作る。
全探索でやるとＴＬＥするのでこのように貪欲法でやる。

■ソース

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<string>

#include<vector>

using namespace std;

int n,w[51];

int t[51];

int ans =100;

void solve(int i,int ti){

  if(i==n){

    ans = min(ans,ti);

    return;

  }

  int best=ti;

  for(int j=0;j<ti;j++){

    if(t[j] >= w[i]){

      if(best == ti || t[best]>t[j]){

	best=j;

      }

    }

  }

  int temp=t[best];

  t[best] = w[i];

  solve(i+1,ti+((best==ti)?1:0) );

  t[best]= temp;

}

int main(void){

  cin >> n;

  for(int i=0;i<n;i++){

    cin >> w[i] ;

  }

  solve(0,0);

  cout << ans << endl;

}

D - アルファベット探し

■問題
入力データの中に'A、'B'、'C'と同じ形の図形が何個あるか求めろ。
整数倍に拡大したものや回転させたものも同じ図形である。

■解法
Aのつながっている数は12、Bのつながっている数は16、Cのつながっている数は11である。
回転してもその数は変わらず、整数倍してもその数は倍率^2の値になる。
後は数えるのを深さ優先ではなく幅優先でやって良い感じにする。

■ソース

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<string>

#include<vector>

#include<queue>

using namespace std;

string s[1001];

int h,w;

int a,b,c;

int dx[]={0,0,1,1,1,-1,-1,-1};

int dy[]={1,-1,0,1,-1,0,1,-1};



struct P{

  int x,y;

  P(){}

  P(int x,int y):x(x),y(y){}

};

int solve(int x,int y){

  queue<P> que;

  que.push(P(x,y));

  s[x][y]='.';

  int ret=1;

  while(!que.empty()){

    P p = que.front();

    que.pop();

    for(int i=0;i<8;i++){

      int nx=p.x+dx[i];

      int ny=p.y+dy[i];

      if(0 <= nx && nx < h && 0<=ny && ny < w && s[nx][ny]=='o'){

	s[nx][ny]='.';

	ret++;

	que.push(P(nx,ny));

      }

    }

  }

  return ret;

}





int main(void){

  cin >> h >> w;

  for(int i=0;i<h;i++){

    cin >> s[i];

  }

  for(int i=0;i<h;i++){

    for(int j=0;j<w;j++){

      if(s[i][j]=='o'){

	int temp = solve(i,j);

	for(int l=1;;l++){

	  int ll=l*l;

	  if(temp==12*ll){

	    a++;

	    break;

	  } else if(temp==16*ll){

	    b++;

	    break;

	  } else if(temp==11*ll){

	    c++;

	    break;

	  }

	}


      }

    }

  }

  cout << a << ' ' << b << ' ' << c << endl;

}

2012-07-01

Atcoder#005

競技プログラミング Atcoder

A - 大好き高橋君 ( Love me do )

■問題
n個の単語でできた文が与えられて、指定された文字列が入力の中に何個あるか数える。

■解法
単語が指定の文字列と同じか比較するだけ
やるだけ
'.'が最後についても良いことに注意する

■ソース

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(void){
  string s;
  int n,ans=0;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> s;
    if(s == "TAKAHASHIKUN" ){
      ans++;
      continue;
    }
    if(s == "Takahashikun" ){
      ans++;
      continue;
    }
    if(s == "takahashikun" ){
      ans++;
      continue;
    }    
    if(s == "TAKAHASHIKUN." ){
      ans++;
      continue;
    }
    if(s == "Takahashikun." ){
      ans++;
      continue;
    }
    if(s == "takahashikun." ){
      ans++;
      continue;
    }
  }
  cout << ans << endl;
}

B - P-CASカードと高橋君 ( This story is a fiction )

■問題
9*9の数字が並べられてます。
ある場所からある方向に４つの値を取ってそれを出力します。
範囲外に行こうとしたら跳ね返ります。

■解法
４回入力の方に進ませて、範囲外になったら対処するだけ。
やるだけ
バグで死んで汚いので参考にしてはいけない。

■ソース
※閲覧注意

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int dx[]={0,1,1,1,0,-1,-1,-1};
int dy[]={-1,-1,0,1,1,1,0,-1};
int main(void){
  int x,y,ang;
  string w,s[10];
  cin >> x >> y >> w;
  x--;
  y--;
  for(int i=0;i<9;i++){
    cin >>  s[i];
  }

  if(w == "U"){
    ang = 0;
  }
  else if(w == "RU"){
    ang = 1;
  }
  else if(w == "R"){
    ang = 2;
  }
  else if(w == "RD"){
    ang = 3;
  }
  else if(w == "D"){
    ang = 4;
  }
  else if(w == "LD"){
    ang = 5;
  }
  else if(w == "L"){
    ang = 6;
  }
  else if(w == "LU"){
    ang = 7;
  }
  string ans;
  for(int i=0;i<4;i++){
    ans += s[y][x];
    cout << ang << endl;

    int nx=dx[ang]+x;
    int ny=dy[ang]+y;
    if(!(0 <= nx && nx < 9 && 0 <= ny && ny < 9)){
      if(x == 0 && y == 0 && ang == 7) ang=3;
      else if(x == 8 && y == 0 && ang == 1) ang=5;
      else if(x == 0 && y == 8 && ang == 5) ang=1;
      else if(x == 8 && y == 8 && ang == 3) ang=7;

      else if(x==0 && ang == 7) ang=1;
      else if(x==0 && ang == 5) ang=3;
      else if(x==0 && ang == 6) ang=2;
      else if(x==8 && ang == 1) ang=7;
      else if(x==8 && ang == 3) ang=5;
      else if(x==8 && ang == 2) ang=6;      

      else if(y==0 && ang == 1) ang=3;
      else if(y==0 && ang == 7) ang=5;
      else if(y==0 && ang == 0) ang=4;
      else if(y==8 && ang == 3) ang=1;
      else if(y==8 && ang == 5) ang=7;
      else if(y==8 && ang == 4) ang=0;
    } 

    x+=dx[ang];
    y+=dy[ang];
  }
  cout << ans << endl;
}

2012-05-27

AOJ0023

競技プログラミング AOJ

Circles Intersection

■問題
2つの円の中点の座標と半径が与えられる。
1つの円がもう一つの円の中にあるか、円周が交わっているかいないかという2つの円の関係を求める。

■解法
2つの中点との距離hを求めて、
Br+h>Ar だったら円Aの中にBがある。
Ar+h>Br だったら円Bの中にAがある。
h>=Ar+Br だったら円周が交わっている。
と言うことになる。
何言ってるんだと思ったら絵を書いてみるとすぐわかる。

■ソース

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    double x[2],y[2],r[2],h;
    for(int j=0;j<2;j++) scanf("%lf %lf %lf",&x[j],&y[j],&r[j]);
    h=hypot(abs(x[0]-x[1]),abs(y[0]-y[1]));
    if(h+r[1]<r[0]) puts("2");
    else if(h+r[0]<r[1]) puts("-2");
    else if(h<=r[0]+r[1]) puts("1");
    else puts("0");
  }
}

2012-05-27

AOJ0022

競技プログラミング AOJ

Maximum Sum Sequence

■問題
整数nとn個の整数が与えられます。
その中の連続する値の合計の最大値を求めなさい。

■解法
累積和を求めて連続の前と後ろをループで全通り試す。

■ソース

#include<cstdio>
#include<algorithm>
using namespace std;
int d[5005];
int main(void){
  while(1){
    int n;
    scanf("%d",&n);
    if(!n) break;
    for(int i=0;i<n;i++){
      scanf("%d",&d[i]);
      if(i) d[i]+=d[i-1];
    }
    int sum=d[0];
    for(int i=0;i<n;i++){
      sum=max(d[i],sum);
      for(int j=0;j<i;j++){
	sum=max(d[i]-d[j],sum);
      }
    }
    printf("%d\n",sum);
  }
}

2012-05-27

AOJ0016

競技プログラミング AOJ

Treasure Hunt

■問題
幾つかの移動歩数と回転角度が与えられます。
座標(0,0)地点で北向きに立っている状態から移動歩数分前に進み、回転角度分右に（負の値なら左）向きます。
それを入力が"0,0"になるまで続けた時の座標の整数部分を答えなさい。

■解法
移動歩数と角度がわかるため三角関数を使うことでxとyの移動距離がわかる。
あとはやるだけ

■ソース

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int main(void){
  int w,a,ang=90;
  double x=0,y=0,r;
  while(1){
    scanf("%d,%d",&w,&a);
    if(w==0 && a==0)break;
    r=(double)ang/180.0*M_PI;
    x+=cos(r)*w;
    y+=sin(r)*w;
    ang-=a;
  }
  printf("%d\n%d\n",(int)x,(int)y);
}

2012-04-30

AOJ0223

競技プログラミング AOJ

Stray Twins

■問題
もう一方と上下左右反対に移動する双子がいます。
二人の座標とデパートの情報が与えられた時二人が巡り合えるまでの最短距離を求めなさい。
最短距離が100以上になるときは"NA"と出力しなさい。

■解法
現在の距離、2人のx,y座標を持たせて幅優先探索するだけ。
二人の移動方向が逆なのと、やり方によってはMemory Limit Exceededになるのでフラグたてたり無駄な動きをなくしたり頑張る。
queueのpopの直後にフラグ立ててたのでMemory Limit Exceededだった。死にたい。

■ソース
デバック苦戦したため要らないとことかあって汚い。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef struct P{
  int tx,ty,kx,ky,c;
};
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int d[55][55];
bool used[55][55][55][55];
int X,Y;
P fa;
int main(void){
  int ans;
  while(1){

    scanf("%d %d",&X,&Y);
    if(!X && !Y) break;
    scanf("%d %d %d %d",&fa.tx,&fa.ty,&fa.kx,&fa.ky);
    fa.c=0;
    for(int i=1;i<=Y;i++){
      for(int j=1;j<=X;j++){
	scanf("%d",&d[j][i]);
      }
    }


    ans=-1;
    memset(used,0,sizeof(used));
    queue<P> que;
    que.push(fa);

    while(!que.empty()){
      P p=que.front();
      que.pop();
      used[p.tx][p.ty][p.kx][p.ky]=true;
      if(p.c>100)break;
      if(p.tx==p.kx && p.ty==p.ky){
	ans=p.c;
	break;
      }
      if((abs(p.tx-p.kx)+abs(p.ty-p.ky)+1)/2>100-p.c)break;
      for(int i=0;i<4;i++){
	int f=0;
	int x[2]={p.tx,p.kx};
	int y[2]={p.ty,p.ky};
	for(int j=0;j<2;j++){
	  int t=1;
	  if(j)t=-1;
	  if(0<x[j]+dx[i]*t && x[j]+dx[i]*t<=X &&
              0<y[j]+dy[i]*t && y[j]+dy[i]*t<=Y){
	    if(!d[x[j]+dx[i]*t][y[j]+dy[i]*t]){
	      x[j]+=dx[i]*t;
	      y[j]+=dy[i]*t;
	      f++;
	    }
	  }
	}
	if(!f){
	  continue;
	}
	if(used[x[0]][y[0]][x[1]][y[1]]){
	  continue;
	}
	P pu={x[0],y[0],x[1],y[1],p.c+1};
	used[x[0]][y[0]][x[1]][y[1]]=true;
	que.push(pu);
      }
    }

    if(ans==-1)puts("NA");
    else printf("%d\n",ans);

  }
}

2012-04-27

2011年JOI本選

競技プログラミング 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ムズすぎ
説明ムズすぎ
日本語ムズすぎ

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

ド素人のメモ帳

解いた問題のプログラムとか載せてくと思います。

AtCoder006

Atcoder#005

AOJ0023

AOJ0022

AOJ0016

AOJ0223

2011年JOI本選