「AOJ551～560」の編集履歴（バックアップ）一覧に戻る
AOJ551～560 - (2012/03/08 (木) 10:48:20) のソース
----
*0551 Icicles
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0551
軒下に連なったつららがいつ全て折れるかを計算する問題です。
つららは隣のつららより長いつららのみ成長し、一定の長さになると折れます。
解法
この問題は あるつららが伸び始めるタイムが隣の先に延び始めたつららが折れるまで伸びないという点に注目点があります。
つまりあるつららが折れる時間は 隣のつららが折れた時間+L-初めの長さ。
という親子関係が全てのつららで成り立ちます。
これが判明すれば後はつららの折れるタイムを優先順位付きキューに入れれば実装は簡単です。
この発想法は実装の簡単さを優先しましたが、メモリを多めに使ってしまいます。
工夫すればメモリを節約できるようなので他の方のコードを参考にすることをお勧めします。
#include<stdio.h>
#include<queue>
struct turara{
int len,point,time;
bool spent,grown;
bool operator<(const turara t)const{
return t.time<time;
}
};
const int mymax=100001;
turara map[mymax];
bool addOK(int p,int n,turara map[mymax]){
if(p<0 || n<=p) return false;//ｐ番目のつららが伸びることが出来るかのチェック
if(map[p].spent==true || map[p].grown==true)return false;//伸びてる途中でないか折れ済ではないかチェック
if(p>0){
if(map[p-1].spent==false && map[p-1].len>=map[p].len){
return false;//隣より短いならノー
}
}
if(p<n-1){
if(map[p+1].spent==false && map[p+1].len>=map[p].len){
return false;
}
}
return true;//隣より長いことが判明伸ばすことを決定
}
void setData(int n,int L){
std::priority_queue<turara> turaras;
turara t,nt;
t.spent=false;
t.grown=false;
t.time=0;
for(int i=0;i<n;i++){
scanf("%d",&t.len);
t.point=i;
map[i]=t;
}
for(int i=0;i<n;i++){
if(addOK(i,n,map)){
map[i].grown=true;
t=map[i];
t.time=L-t.len;//次に折れるタイミング
turaras.push(t);
}
}
int p;
while(!turaras.empty()){
t=turaras.top();//ｔのつららが折れた
turaras.pop();
p=t.point;
map[p].spent=true;//ｔを親に左右のつららが伸びることが出来るかチェック
if(addOK(p-1,n,map)){
map[p-1].grown=true;
nt=map[p-1];
nt.time=L-nt.len+t.time;
turaras.push(nt);
}
if(addOK(p+1,n,map)){
map[p+1].grown=true;
nt=map[p+1];
nt.time=L-nt.len+t.time;
turaras.push(nt);
}
}
printf("%d\n",t.time);
}
int main(){
int n,L;
while(scanf("%d %d",&n,&L)!=EOF){
setData(n,L);
}
}
----
*0553 Dungeon
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0553
RPGダンジョンを題材に取った問題。
地下１０万階までHPの最大値が1000万以下でダンジョンにもぐり、ダンジョンを一階降りるたびに指定量ダメージをうける。
ダンジョンのその階にある回復の泉でHPを指定量回復できる。
という構造になっています。
最下層の階とHPと各階から下るときに受けるダメージと泉のHP回復量が与えられたとき最下層まで降りるのに必要な回復の泉の最小使用回数を求めよという問題。
解法
この問題は貪欲法で片がつきます。
まずHPが0以下になるまでひたすらもぐり続けます。
HPが０以下になったら、ここまでの階に存在した最もHP回復できる階を選択し実はその階で回復していたのだ(子供の発想ですね)ということにします。
while(floors[nowFloor+1].nowHP<=0)内の処理。
まず最初にメモした最大回復量階でのHPの最大値を超えないように回復し、その階より深い階でのHPを更新します。
それでもまだ回復量が足らない場合 nextHealSearch関数で更新したHPで回復量の最大値となる階を探します。
後は同じノリで更新した階で回復してHPが0以上になったらWhileをぬけてまた地下への探索を進めます。
この発想の場合、地下1階でHP１０００万、1Fから2Fへ行く過程で９９９万9999のダメージ受け、地下２階のHP回復量が2でそれ以外のHP回復量が1でダメージが非常に小さい場合など計算量が膨れ上がるという欠点があります。
ランダムなデータに対して強いが特殊なデータに対してい計算量が不安定になるという欠点があります。
#include<stdio.h>
struct Floor{
int nowFloor,damage,heal,nowHP;//今いる階、この階でのダメージと回復量,この階でのHPのメモ
};
//グローバル変数開始
Floor floors[100001];
int h;//HPの最大値、変数名が問題で指定されているので仕方なく使ってるが分かりづらい
int n;//最下層
//グローバル変数終わり
int healNum(const Floor& f){
int t=h-f.nowHP;//HPが上限を超えるかのチェック
if(f.nowHP<=0 || t<=0) return 0;//HP0以下ならこの階の泉は使えない
else return f.heal>t?t:f.heal;//回復の結果HP最大値を超えてしまうならtを返す
}
Floor nextHealSearch(int ep,const Floor& memoHealFloor,int healCount){
//今いる階での回復量がHP最大値を超えるのでより深い階での回復に更新する場合この関数を呼び出す
//Floor変数はサイズが小さいので値渡しでも多分問題なし
int sp =memoHealFloor.nowFloor;//探索のスタート地点となる階
int Heal =memoHealFloor.heal*healCount;//この階で回復した分を次の階に反映するためのHP回復量
int maxHeal =healNum(memoHealFloor);//回復量の値を求める
if(healCount==0)Heal=maxHeal;//0を渡されたら。
int tempHeal;
int nextHealFloor=sp;//答えとなる階層
maxHeal=-1;//最大回復量を更新するため-1を渡す
for(int i=sp;i<=ep;i++){
floors[i].nowHP+=Heal;//手前の階より必ずHPが低い状態なのでこの計算はHP最大値を超えない
tempHeal=healNum(floors[i]);
if(tempHeal>=maxHeal&& floors[i].nowHP>0){
maxHeal=tempHeal;//この階での回復のほうが多いか同じでより深い階なので更新する
nextHealFloor=i;
}
}
return floors[nextHealFloor];//更新されない場合もある
}
void setData(){
int nowFloor=0;//到達できた階層
for(int i=0;i<n-1;i++){
floors[i].nowFloor=i;
scanf("%d %d",&floors[i].damage,&floors[i].heal);
}
Floor memoHealFloor=floors[0];//nowFloorまでの階層のうち
floors[0].nowHP=h;
int tempHeal,maxHeal=0;//一層目は0回復しかできないので
int calcHP1,calcHP2,calcHP3,tempFloor,tempCount,ansCount=0;
while(nowFloor<n-1){
floors[nowFloor+1].nowHP=floors[nowFloor].nowHP-floors[nowFloor].damage;
if(floors[nowFloor+1].nowHP>0){
tempHeal=healNum(floors[nowFloor+1]);
if(tempHeal>=maxHeal){
maxHeal=tempHeal;//最大回復できる階が見つかった
memoHealFloor=floors[nowFloor+1];
}
nowFloor++;//次の階へ
continue;
}
//HPが0以下になった
tempFloor=-1;//
while(floors[nowFloor+1].nowHP<=0){
calcHP1=-floors[nowFloor+1].nowHP;
calcHP2=((h-memoHealFloor.nowHP)/memoHealFloor.heal)*memoHealFloor.heal;//最大値を超えない回復量を求める
if(tempFloor!=memoHealFloor.nowFloor){
//前に回復したのと同じ階ではない場合
tempFloor=memoHealFloor.nowFloor;
if(calcHP1<=calcHP2){
tempCount=(calcHP1)/memoHealFloor.heal+(calcHP1==calcHP2?0:1);//memoFloorの階で最大値まで回復できる量のほうが多いので
}else{
tempCount=(calcHP2)/memoHealFloor.heal;//回復に使用した階では回復しきれない場合
}
memoHealFloor=nextHealSearch(nowFloor+1,memoHealFloor,tempCount);//HP回復した分を更新して次の回復階を探す
ansCount+=tempCount==0?1:tempCount;//答えのカウント
}else{
tempFloor=memoHealFloor.nowFloor;
//最大値止まりで回復するので
ansCount++;
memoHealFloor=nextHealSearch(nowFloor+1,memoHealFloor,0);//0を渡すと最大値切り上げまで回復
}
maxHeal=healNum(memoHealFloor); //最大回復できる階の更新
}
}
printf("%d\n",ansCount);
}
int main(){
while(scanf("%d %d",&n,&h)!=EOF){
setData();
}
}
----
*0554 Total Time
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0554
移動時間の合計を算出せよという問題。
解法
計算するだけです。
#include<stdio.h>
int main(){
int a,b,c,d,t;
scanf("%d %d %d %d",&a,&b,&c,&d);
t=a+b+c+d;
printf("%d\n%d\n",t/60,t%60);
}
----
*0555 Ring
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0555
リングに刻まれた文字列のなかから特定の文字列を探すという問題。
解法
std::stringの基本機能を使いこなせるかだけの問題で計算量も小さいので気楽に解きます。
#include<iostream>
#include<string>
int main(){
std::string text,ring;
int n,count=0;
std::cin>>text>>n;
for(int i=0;i<n;i++){
std::cin>>ring;
ring+=ring;
if(std::string::npos!=ring.find(text,0))count++;
}
std::cout<<count<<"\n";
}
----
*0556 Tile
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0556
規則的なタイル模様のうち欠けた部分の座標から補修に必要なタイルの色を求める問題。
解法
盤面の対称性を利用して１～2回折りたたんで計算します。
折りたたむと、盤面が非常に簡単になります。
#include<stdio.h>
int main(){
int n,m,herf,x,y;
scanf("%d %d",&n,&m);
herf=(n+1)/2;
for(int i=0;i<m;i++){
scanf("%d %d",&x,&y);
if(x>herf)x=n-x+1;
if(y>herf)y=n-y+1;//盤面を1/4か1/2に折りたたむ
if(x>=y){
printf("%d\n",(y-1)%3+1);
}else{
printf("%d\n",(x-1)%3+1);
}
}
}
----
*0557 A First Grader
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557
算数を題材にしたメモ化計算の問題。
解法
典型的なメモ化計算の問題ですので簡単にサクッと実装します。
#include<stdio.h>
#include<string.h>
int main(){
int nums[101],n,t;
unsigned long long int memo[21];
unsigned long long int next[21];
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&nums[i]);
memset(memo,0,sizeof(memo));
memo[nums[0]]=1;
for(int i=1;i<n-1;i++){
memset(next,0,sizeof(next));
for(int j=0;j<21;j++){
t=j+nums[i];
if(t<21){
next[t]+=memo[j];
}
t=j-nums[i];
if(-1<t){
next[t]+=memo[j];
}
}
memcpy(memo,next,sizeof(next));
}
printf("%llu\n",memo[nums[n-1]]);
}
----
*0558
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558
升目になっているマップの上でネズミがチーズを求めて移動する。
チーズは硬さが決まっており、やわらかいチーズを先に食べて体力をつけないと硬いチーズは食べられない。
全てのチーズを食べることのできる最短ルートの距離を求めよという問題です。
解法
この問題は気持高速に動作するコードときれいなコードどちらを掲載するか迷いました。
ほとんど速度差がないので綺麗なほうを掲載することにしました。
問題の本質はスタートからチーズ、チーズからチーズへのルートの探索だけです。
幅優先探索でチーズからチーズへの移動距離を求めます。
#include<stdio.h>
#include<queue>
#include<string.h>
struct point{
int x,y,len;
bool operator<(const point p)const{
return p.len<len;
}
};
//グローバル変数はすべてここに
int turn[1001][1002];
char map[1001][1002];
int dxs[4]={1,0,-1,0};
int dys[4]={0,1,0,-1};
//グローバル変数終わり
int search(point p1,point p2,int h,int w){
int gx=p2.x;
int gy=p2.y;
std::priority_queue<point> points;
points.push(p1);
int nx,ny,nt;
turn[p1.y][p1.x]=1;//スタート地点だけダミーデータ
while(!points.empty()){
p1=points.top();//幅優先探索、経路は水量の上がる水溜りのように外郭だけとなるのでqueueに入るデータ量は少なめ
points.pop();
for(int i=0;i<4;i++){
nx=p1.x+dxs[i];
ny=p1.y+dys[i];
nt=p1.len+1;//縦横チェック
if(nx<0 || w<=nx || ny<0 || h<=ny) continue;
if(map[ny][nx]=='X' || (turn[ny][nx]!=0 && nt>=turn[ny][nx])) continue;
if(nx==gx && ny==gy)return nt;
turn[ny][nx]=nt;
p2.x=nx;
p2.y=ny;
p2.len=nt;
points.push(p2);
}
}
return 0;
}
int main(){
int h,w,n;
int sx,sy;
char t;
point points[10];
scanf("%d %d %d",&h,&w,&n);
for(int y=0;y<h;y++){
scanf("%s",map[y]);
for(int x=0;x<w;x++){
t=map[y][x];
if(t=='S'){
points[0].x=x;//スタート座標
points[0].y=y;
points[0].len=0;
}else if('1'<=t && t<='9'){
points[t-'0'].x=x;//チーズ座標
points[t-'0'].y=y;
points[t-'0'].len=0;
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
memset(turn,0,sizeof(turn));
ans+=search(points[i-1],points[i],h,w);//スタートからチーズへチーズからチーズへの経路を検索
}
printf("%d\n",ans);
}
----
*0559 JOI Flag
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0559
升目で区切られた旗にJOIという文字を入れていく。
条件を満たす旗を良い旗とするがこのよい旗の組み合わせうがいくつかあるか求める問題。
解法仮説
この問題は直接解くのは大変なので別の形に翻訳して解くことにします。
左上から右下まで旗の各升目にP1～Pmnまでの番号を付けていきます。
Pi番目で初めてJOIという(PiはIという文字が入ります)並びが出てくる場合を考えます。
Pi番目で初めてJOIが出てくる並びの集合をSiとしその要素数をf(Si)とします。
するとi>jのときSiとSjは共通集合を持ちません。
この問題は
答え=Σf(Si)(1<=i<=nm)
という形に分解できます。
今取り組んでいるのは
*Pi番目までJOIという並びがでない場合の組み合わせをどう求めるか。
*旗に最初からJOIという並びがある場合どう対処するか
という点です。
*560 Planetary Exploration
オーソドックスなメモ化でぎりぎり一発合格。
他の人のコード実行速度見るとなんだかレベルが高い。
どうやってコード実行速度を上げるのだろうか？
#include<stdio.h>
#include<map>
#include<string.h>
int memoRows[1001][1001][3];
int main(){
int sx,sy,ex,ey,w,h,k;
char type,text[1001];
scanf("%d %d %d",&h, &w, &k);
memset(memoRows,0,sizeof(memoRows));
for(int r=1;r<=h;r++){
scanf("%s",text);
for(int c=1;c<=w;c++){
type=text[c-1];
type=(type=='J'?0:type=='O'?1:2);
for(int i=0;i<3;i++)memoRows[r][c][i]=memoRows[r][c-1][i];
memoRows[r][c][type]++;
}
}
for(int i=0;i<k;i++){
scanf("%d %d %d %d",&sy,&sx,&ey,&ex);
int ans[3]={0,0,0};
for(int r=sy;r<=ey;r++){
ans[0]+=(memoRows[r][ex][0]-memoRows[r][sx-1][0]);
ans[1]+=(memoRows[r][ex][1]-memoRows[r][sx-1][1]);
ans[2]+=(memoRows[r][ex][2]-memoRows[r][sx-1][2]);
}
printf("%d %d %d\n",ans[0],ans[1],ans[2]);
}
}
