「AOJ561～570」の編集履歴（バックアップ）一覧に戻る
AOJ561～570 - (2013/09/19 (木) 07:54:05) のソース
堀江伸一
ハンドルネーム sinapusu2002
*0564 Bug Party
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0564
微生物を題材にしたプログラムの練習問題。
昔一位を取ったのですが結構抜かれました。
コードを一か所書き換えただけで3位に返り咲き。
しかし一位は凄いな。
どんなコードを使ってるのか想像もつかない。
とりあえず私が独自に達した答えの考え方は簡単。
一番ｂの許容量が低い微生物を選んだ場合,他の微生物をどう選ぼうがｂはこれ以上悪化しない。
よってaを低い順からシャーレに入れていけばよい、一番ｂが低いやつが耐えきれなくなるまでaを低い順に足す。
耐えきれなくなったら次にｂの２番目に許容量が低い微生物を選び、一番ｂの低いのをシャーレに入ってる入ってない関係なく廃棄します。
2番目に低い連中が耐えれなくなったらそれを廃棄しｂが3番目に低いのを選んで以下同様。
これを一番ｂが高い微生物まで繰り返したとき最大種類数が答えとなります。
種が分かれば簡単な問題でした。
コードはメモリ使用量に無頓着なのでこちらのほうは改善できるはず。
3位は嫌だったので1位タイのコードも別にもうひとつ書いたけど、メモリ使用量で1位に負けており実質2位。
#include<stdio.h>
#include <algorithm>
#include<string.h>
struct foo{
long long int a,b;
int no;
};
class fooSorterA {
public:
bool operator()(const foo& l, const foo& r) const {
return l.a<r.a;//aの小さい順
}
};
class fooSorterB {
public:
bool operator()(const foo& l, const foo& r) const {
return l.b<r.b;//aの小さい順
}
};
foo memoA[300002];
foo memoB[300002];
bool spents[300002];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld %lld",&memoA[i].a,&memoA[i].b);
memoA[i].no=memoB[i].no=i;
memoB[i].a=memoA[i].a;
memoB[i].b=memoA[i].b;
}
std::sort(memoA,memoA+n,fooSorterA());//aの小さい順
std::sort(memoB,memoB+n,fooSorterB());//ｂの小さい順に並べる
memset(spents,false,sizeof(spents));
foo f;
int p=0,count=0,ans=0;
long long int sum=0;
//まずBが一番小さい微生物を考えると、それより小さいBは存在しない。
//するとAを小さい方から足していけば貪欲に問題が解ける
//B が溢れたらBを一つ進めてｆを足しこんでいたら削除する
for(int i=0;i<n;i++){
f=memoB[i];
while(p<n&&memoA[p].a+sum<=f.b*(count+1)){
if(spents[memoA[p].no]==true){
p++;
continue;
}
sum+=memoA[p].a;
spents[memoA[p].no]=true;//使用済み
count++;
p++;
ans=std::max(ans,count);
}
if(spents[f.no]==true){
if(count>0)count--;//念のため
sum-=f.a;//使用済みのｆを削除する
}
spents[f.no]=true;
}
printf("%d\n",ans);
}
0564の1位タイバージョンを書いてみた。
といっても上記のコードでソート処理の計算量を省いただけである。
メモリ使用量は下がったし速度も少し上がったがコードからエレガントさが消えたので個人的に余り好きなコードではない。
1位がとれてないのも悔しいところです。
タイムは一位と同じでもう少しで抜けそうに見えるがこれ以上の高速化は多分無理。
多分処理の9割位がデータの読み込み時間になっているのでこれ以上計算部分を高速化しても意味はありません。
私のサイトはキチガイの書いた意味不明な英文もどきがたくさん掲載されていると噂を流されたこともあります。
競技プログラマのかたにはお分かり頂けると思いますが、キチガイどころかAOJというローカルな場所ながらコード実行速度上位を狙って実際に上位に入ることが可能なコードを掲載しているだけです。
誹謗中傷って怖いですね。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
const int up=100001;
int main()
{
long long int AsCount[up]={0},SumA=0,CountFoo=0,pointB=0,pointA=1,tempA,ans=0;
std::vector<long long int> BtoAs[up];
std::vector<long long int>::iterator it;
int n,a,b,j=0,k=0,p=0;
std::cin>>n;
for(int i=0;i<n;i++){
scanf("%d %d",&a,&b);
BtoAs[b].push_back(a);
AsCount[a]++;
}
while(pointB<up&&BtoAs[(int)pointB].empty())pointB++;
while(pointA<up&&pointB<up)
{
while(pointA<up&&SumA<=pointB*CountFoo)
{
ans=std::max(ans,CountFoo);
if(j<AsCount[(int)pointA])
{
SumA+=pointA;
CountFoo++;
j++;
}else
{
j=0;
p=0;
pointA++;
}
}
for(it=BtoAs[(int)pointB].begin();it!=BtoAs[(int)pointB].end();it++)
{
tempA=(*it);
if(tempA<pointA)
{
SumA-=tempA;
CountFoo--;
}else if(tempA>pointA)
{
AsCount[(int)tempA]--;
}else
{
if(p<j)
{
SumA-=tempA;
CountFoo--;
p++;
}else{
AsCount[(int)tempA]--;
}
}
}
do{
pointB++;
}while(pointB<up&&BtoAs[(int)pointB].empty());
}
std::cout<<ans<<"\n";
return 0;
}
*561 Books
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0561
古本屋に本を売りに行く問題。
この問題は動的計画法で片が付きます。
まず同一ジャンルの本を売るとき、同じ冊数なら値段の高い方から売ったほうがお得です。
同一ジャンルのなかでは貪欲法だと判明します。
次にジャンル別に本を売っていき、ｎ冊売った時の値段をメモして、ｎ冊打った時最も販売額が高くなる組み合わせのみ残して後は動的計画法で終わりです。
簡単な問題なので肩慣らしにちょうどよいようです。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <functional>
int memo[2001];//n冊目の本を売った時の価格
std::vector<int> books[11];
int main(){
memset(memo,0,sizeof(memo));
int n,k,c,g;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d %d",&c,&g);
books[g].push_back(c);
}
int ans=0;
for(int i=1;i<11;i++){
//本の種類
std::sort(books[i].begin(),books[i].end(),std::greater<int>());
for(int j=k-1;j>=0;j--){
//起点とする本の冊数
int sum=0;
for(int L=0;L<books[i].size();L++){
//このジャンルの本を売る数
int count=j+L+1;
if(count>k) break;
sum+=books[i][L]+2*L;
memo[count]=std::max(memo[count],memo[j]+sum);
ans=std::max(ans,memo[count]);
}
}
}
printf("%d\n",ans);
}
*562 Shopping in JOI Kingdom
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0562
グラフ上に散らばった街とショッピングモールまでの距離を数える問題。
どの道路上の家の住人も一番近くのショッピングモールに向かうとき、最も長い距離を移動しなくてはいけない住人の移動距離を求めよ。
解法
どのショッピングモールもゴールという点では見分けがつきません。
よって全てのショッピングモールが実は距離0でつながっている同じものなのだと考えます。
点番号0から全てのショッピングモールへ距離０の線を伸ばし一方通行とします。
後は点0～の各点への距離をダイクストラ法で求め、最後に線分上の家の計算を行えば簡単にアセプトとなります。
見分けがつかないものをまとめて問題を一段簡単なものに翻訳するのは競技プログラムにおける基本テクニックです。
#include<stdio.h>
#include<vector>
#include<queue>
struct E{
int no,cost;//辺とダイクストラ両方で使う
bool operator<(const E& e)const{
return cost>e.cost;
}
};
std::vector<E> cons[3002];
void calc(){
E e;
int n,m,k,a,b;
scanf("%d %d %d",&n,&m,&k);
for(int i=0;i<m;i++){
scanf("%d %d %d",&a,&b,&e.cost);
e.no=b;
cons[a].push_back(e);
e.no=a;
cons[b].push_back(e);
}
e.cost=0;//ショッピングモールは距離0一方通行で点0から全てつながっているとする
for(int i=0;i<k;i++){
scanf("%d",&e.no);
cons[0].push_back(e);
}
E p,nextP;
p.no=p.cost=0;
std::priority_queue<E> pQ;
pQ.push(p);
int ans[3002];//ダイクストラ法の答え
for(int i=1;i<=n;i++)ans[i]=1000000000;
ans[0]=0;//点0からスタートする
while(pQ.empty()==false){
p=pQ.top();
pQ.pop();
if(ans[p.no]<p.cost)continue;
int no=p.no;
for(int i=0;i<cons[no].size();i++){
e=cons[no][i];
nextP.no=e.no;
nextP.cost=e.cost+p.cost;
if(ans[nextP.no]>nextP.cost){
ans[nextP.no]=nextP.cost;
pQ.push(nextP);
}
}
}
int c1,c2,c3,c4,lastAns=0;
for(int i=1;i<=n;i++){
//printf("%d\n",ans[i]);
c1=ans[i];
for(int j=0;j<cons[i].size();j++){
e=cons[i][j];
c2=ans[e.no];
c3=c1>c2?c1:c2;
c4=(c1+c2+e.cost);
//printf("(i=%d no2=%d c1=%d c2=%d cost=%d)",i,e.no,c1,c2,e.cost);
c4=c4/2+(c4%2);//四捨五入
if(c4>=c3) c3=c4;
lastAns=lastAns>c3?lastAns:c3;
}
}
printf("%d\n",lastAns);
}
int main(){
calc();
}
*565 Lunch
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0565
簡単な問題なので工夫する気すら起きませんでした。
もし工夫するならショートコーディングくらいかな。
#include<stdio.h>
int main(){
int min1=10000,min2=10000,v;
for(int i=0;i<3;i++){
scanf("%d",&v);
min1=min1>v?v:min1;
}
for(int i=0;i<2;i++){
scanf("%d",&v);
min2=min2>v?v:min2;
}
printf("%d\n",min1+min2-50);
}
*566 Soccer
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0566
最初ソートすればいいかと思ったがソート関数の定義がめんどくさくなったので手抜き実装。
意外とコードが短くなった。
#include<stdio.h>
#include <string.h>
int main(){
int n,scores[102],a,b,c,d,ranks[400],max=-1;
scanf("%d",&n);
memset(scores,0,sizeof(scores));
memset(ranks,0,sizeof(ranks));
for(int i=0;i<(n*(n-1))/2;i++){
scanf("%d %d %d %d",&a,&b,&c,&d);
a--;
b--;
if(c>d){
scores[a]+=3;
}else if(c<d){
scores[b]+=3;
}else{
scores[a]+=1;
scores[b]+=1;
}
}
for(int i=0;i<n;i++){
ranks[scores[i]]++;
max=max>scores[i]?max:scores[i];
}
for(int i=max;i>0;i--){
ranks[i-1]+=ranks[i];
}
for(int i=0;i<n;i++){
printf("%d\n",ranks[scores[i]+1]+1);
}
}
*0567 Best Pizza
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0567
一回目油断しまくりで、＄頭カロリー計算を整数扱いで挑戦して転ぶ。
double型を使う実装に変えてアセプト。
こんな簡単な問題で油断しすぎた。
#include<stdio.h>
#include <algorithm>
#include <functional>
int main(){
int n;
double a,b,c,costLine,ansV,ansC,cs[101];
scanf("%d %lf %lf %lf",&n,&a,&b,&c);
costLine=c/a;
ansV=a;
ansC=c;
for(int i=0;i<n;i++){
scanf("%lf",&cs[i]);
}
sort(cs, cs + n, std::greater<int>());
for(int i=0;i<n;i++){
ansV+=b;
ansC+=cs[i];
if(ansC/ansV>costLine){
costLine=ansC/ansV;
}else{
break;
}
}
printf("%d\n",(int)(costLine));
}
*0568 Pasta
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568
普通にメモ化計算で一応正答。
賢い方法を思いつかなかったのでハードコーディングしまくり、このコードを参考にしてはいけない。
例えばｎ日連続で続いてはいけない等問題が一般に変更されたら対応できないし他にも色々問題のあるコード。
初日２日間の特殊処理だの、その後のメモ化のハードコーディングだの完璧に反面教師。
#include<stdio.h>
#include<string.h>
int mode=10000;
int n;
int datas[101];
int firstMemo[3];
void firstSet(int deep,int memo[3][3]){
if(deep==2){
memo[firstMemo[0]][firstMemo[1]]=1;//こんなハードコーディング駄目だよなと思いつつ楽な方に流れてしまった、、
return;
}else{
if(datas[deep]==-1){
for(int i=0;i<3;i++){
firstMemo[deep]=i;
firstSet(deep+1,memo);
}
}else{
firstMemo[deep]=datas[deep];
firstSet(deep+1,memo);
}
}
}
int main(){
int k,a,b;
int memo[3][3];
int next[3][3];
scanf("%d %d",&n,&k);
memset(datas,-1,sizeof(datas));
memset(memo,0,sizeof(memo));
for(int i=0;i<k;i++){
scanf("%d %d",&a,&b);
a--;//扱いやすい0日目を初日にとる
b--;//同じく扱いやすい0から始める
datas[a]=b;
}
//最初の二日間を綺麗に扱う方法を思いつかないので特別に計算する。
firstSet(0,memo);
//ここも綺麗な解法を思いつかないのでループする、ｎ日とかになったらどうすると言われたら困る
//-30点くらいのコードですね
for(int d=2;d<n;d++){
memset(next,0,sizeof(next));
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
int k=datas[d];
if(k!=-1){
if(!(i==j && k==j)){
next[j][k]=(next[j][k]+memo[i][j])%mode;
}
}else{
for(int k=0;k<3;k++){
if(!(i==j && k==j)){
next[j][k]=(next[j][k]+memo[i][j])%mode;
}
}
}
}
}
memcpy(memo,next,sizeof(next));
}
int ans=0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
ans=(ans+next[i][j])%mode;
}
}
printf("%d\n",ans);
}
*0569 Illumination
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569
幼稚園児と同じレベルで素直に解く。
外側から到達できる部分に２という色を塗っていき、全部の色が塗れたら後は１に隣接している２の数を数え上げていく。
コードサイズを見ると私は最下位クラスなのでもっと賢い方法があるらしい。
#include<stdio.h>
#include<string.h>
int dxsKi[]={ 1, 1, 0,-1, 0, 1};
int dysKi[]={ 0,-1,-1, 0, 1, 1};
int dxsGu[]={ 1, 0,-1,-1,-1, 0};
int dysGu[]={ 0,-1,-1, 0, 1, 1};
int map[104][104];
int w,h;
bool inArea(int x,int y){
if(x<0||x>w+1||y<0||y>h+1)return 0;
return 1;
}
void saiki(int x,int y){
if(inArea(x,y)==0||(map[y][x]&2)==2||(map[y][x]&1)==1) return;
map[y][x]=2;
int nx,ny;
for(int i=0;i<6;i++){
if(y%2==0){
nx=x+dxsGu[i];
ny=y+dysGu[i];
}else{
nx=x+dxsKi[i];
ny=y+dysKi[i];
}
saiki(nx,ny);
}
}
int main(){
//1bit目を建物に、2bit目を外から到達可能な地点のフラグ
//まず最初に外側から到達できるヘクスの情報を取る
memset(map,0,sizeof(map));//外側を番兵にする
scanf("%d %d",&w,&h);
for(int y=1;y<=h;y++){
for(int x=1;x<=w;x++){
scanf("%d",&map[y][x]);
}
}
//まずは外側から到達できる地点のフラグを建てる。
for(int x=1;x<=h+1;x++){
saiki(x,0);
saiki(x,h+1);
}
for(int y=1;y<=w+1;y++){
saiki(0,y);
saiki(w+1,y);
}
int ans=0;
int check[104][104];
memset(check,0,sizeof(check));
int nx,ny;
for(int y=1;y<=h;y++){
for(int x=1;x<=w;x++){
for(int i=0;i<6;i++){
if(y%2==0){
nx=x+dxsGu[i];
ny=y+dysGu[i];
}else{
nx=x+dxsKi[i];
ny=y+dysKi[i];
}
if(map[y][x]==1 && map[ny][nx]==2){
ans++;
check[y][x]++;
}
}
}
}
//for(int y=1;y<=h;y++){
// printf("\n%s",y%2==0?" ":" ");
// for(int x=1;x<=w;x++){
// printf("%d ",check[y][x]);
// }
//}
printf("%d\n",ans);
}
*570 Zig-Zag Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0570
ジグザグ数と呼ばれる数かつある倍数の数が指定された範囲内にいくつあるかを答える問題。
数字の範囲が10＾500と広いので普通に計算してたら間に合わない問題です。
基本は桁位置、ジグザグ数のタイプ、今計算したところまでの先頭桁の数字、余りの４次元空間で足しては余りを計算するメモ化を一段ずつ積み重ねるイメージで解きます。
for(int iから始まる４重ループがメモ化計算の基本土台となります。
上限値と下限値だけ特別に扱うためにループの後ろの方で色々小細工しています。
この問題速度を重視して解いてみたらコードが膨らみました、おかげでコード実行速度２位です。
最初自信満々でコードを書きあげて投稿するも２連続ＷＡ。
一発で通るつもり自信満々で投稿したのに理由がわからず公開されているジャッジデータで試してみたところ。
printf("%d\n",(ans2-ans1+inf)%inf);
と書くべきところを
printf("%d\n",(ans2-ans1));
と書いていたポカミスだったと判明、１回目の投稿コードのこの一行だけを修正してアセプト。
ジャッジデータによるチェックはカンニングと同義、ジャッジデータを使う前の時点で99％実力で解けていたのになんか残念。
惜しいことをしたなと思う問題。
他の人はコードサイズが半分程度なのでもっと賢い方法がある様子。
ここまでコードが膨らむなら速度よりコードサイズのほうが大事と思うし。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int memo[502][2][10][502];//桁位置、ジグザグ数のタイプ、先頭一ケタの数、余りの４次元空間でメモ化する。
int amaris[502][11];
int ups[502][2][502];//桁位置、ジグザグ数のタイプ,余り
int m;
int inf=10000;//テスト中
void calcAmari(int mode){
int ans;
memset(amaris,0,sizeof(amaris));
for(int i=0;i<10;i++){
ans=i;
for(int j=0;j<502;j++){
ans=ans%mode;
amaris[j][i]=ans;
ans*=10;
}
}
}
void dell1(char num[502]){
int last=(int)strlen(num);
if(last==1){
num[0]--;
return ;
}
int d=1;
for(int i=last-1;i>=0;i--){
int t=num[i]-'0'-d;
if(t<0){
d=1;
num[i]=(t+10)%10+'0';
}else{
d=0;
num[i]=(t+'0');
}
}
int p=0;
for(int i=0;i<last;i++){
if(num[i]!='0')break;
p++;
}
for(int i=0;i<last-p;i++){
num[i]=num[i+p];
}
num[last-p]='\0';
if(num[0]=='\0'){
num[0]=0;
}
}
int calcZiguzagu(char num[502]){
int last,ans=0;
last=(int)strlen(num);
if(last==1){
return (num[0]-'0')/m;
}
memset(memo,0,sizeof(memo));
memset(ups,0,sizeof(ups));
for(int i=0;i<last/2;i++){
//計算しやすいよう数字を逆転する
int p=last-1-i;
char t=num[i];
num[i]=num[p];
num[p]=t;
}
for(int i=0;i<last;i++)num[i]-='0';//計算を簡単にするために先に数字にしておく
for(int i=0;i<10;i++){
//初期設定
memo[0][0][i][i%m]++;
memo[0][1][i][i%m]++;
if(i==num[0]){
ups[0][0][i%m]++;
ups[0][1][i%m]++;
}
}
for(int i=1;i<10;i++){
ans+=memo[0][0][i][0];
}
int nAmari,sum1=0,sum2=0;
for(int i=0;i<last-1;i++){
//桁位置
for(int k=0;k<10;k++){
//次の桁の数字
for(int a=0;a<m;a++){
//余り
nAmari=(a+amaris[i+1][k])%m;
//右がより大きなジグザグ数
for(int l=k+1;l<10;l++){
memo[i+1][0][k][nAmari]=(memo[i+1][0][k][nAmari]+memo[i][1][l][a])%inf;
}
for(int l=0;l<k;l++){
memo[i+1][1][k][nAmari]=(memo[i+1][1][k][nAmari]+memo[i][0][l][a])%inf;
}
}
if(i==last-2){
if(k<num[last-1]&&k!=0){
sum1=(sum1+memo[i+1][0][k][0])%inf;
sum2=(sum2+memo[i+1][1][k][0])%inf;
}
}else{
if(k!=0)sum1=(sum1+memo[i+1][0][k][0])%inf;
sum2=(sum2+memo[i+1][1][k][0])%inf;
}
//printf("(%d %d)",memo[i+1][0][k][0],memo[i+1][1][k][0]);
}
ans=(ans+sum1+sum2)%inf;
//printf("\n(%d %d %d)\n",sum1,sum2,ans);
sum1=sum2=0;
//上限値だけ特別計算。
//普通に数字を書いたとき右の数字がより大きい
for(int k=num[i+1]+1;k<num[i];k++){
for(int a=0;a<m;a++){
nAmari=(amaris[i+1][num[i+1]]+a)%m;
ups[i+1][0][nAmari]=(ups[i+1][0][nAmari]+memo[i][1][k][a])%inf;
}
}
//右の数字のほうが大きいなら足す
if(num[i]>num[i+1]){
for(int a=0;a<m;a++){
nAmari=(amaris[i+1][num[i+1]]+a)%m;
ups[i+1][0][nAmari]=(ups[i+1][0][nAmari]+ups[i][1][a])%inf;
}
}
//右の数字がより小さいジグザグ数
for(int k=0;k<num[i+1]&&k<num[i];k++){
for(int a=0;a<m;a++){
nAmari=(amaris[i+1][num[i+1]]+a)%m;
ups[i+1][1][nAmari]=(ups[i+1][1][nAmari]+memo[i][0][k][a])%inf;
}
}
//右の下限の数字のほうが小さいなら
if(num[i]<num[i+1]){
for(int a=0;a<m;a++){
nAmari=(amaris[i+1][num[i+1]]+a)%m;
ups[i+1][1][nAmari]=(ups[i+1][1][nAmari]+ups[i][0][a])%inf;
}
}
}
ans=(ans+ups[last-1][0][0]+ups[last-1][1][0])%inf;
//printf("<%d %d>\n",ups[last-1][0][0],ups[last-1][1][0]);
//printf("%d\n",ans);
return ans;
}
int main(){
char a[502],b[502];
scanf("%s %s %d",a,b,&m);
dell1(a);
calcAmari(m);
int ans1=calcZiguzagu(a);
int ans2=calcZiguzagu(b);
printf("%d\n",(ans2-ans1+inf)%inf);
}
