0551 Icicles
解法
この問題は あるつららが伸び始めるタイムが隣の先に延び始めたつららが折れるまで伸びないという点に注目点があります。
つまりあるつららが折れる時間は 隣のつららが折れた時間+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;//p番目のつららが伸びることが出来るかのチェック
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();//tのつららが折れた
turaras.pop();
p=t.point;
map[p].spent=true;//tを親に左右のつららが伸びることが出来るかチェック
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
解法
この問題は貪欲法で片がつきます。
まずHPが0以下になるまでひたすらもぐり続けます。
HPが0以下になったら、ここまでの階に存在した最もHP回復できる階を選択し実はその階で回復していたのだ(子供の発想ですね)ということにします。
while(floors[nowFloor+1].nowHP<=0)内の処理。
まず最初にメモした最大回復量階でのHPの最大値を超えないように回復し、その階より深い階でのHPを更新します。
それでもまだ回復量が足らない場合 nextHealSearch関数で更新したHPで回復量の最大値となる階を探します。
後は同じノリで更新した階で回復してHPが0以上になったらWhileをぬけてまた地下への探索を進めます。
この発想の場合、地下1階でHP1000万、1Fから2Fへ行く過程で999万9999のダメージ受け、地下2階の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
解法
計算するだけです。
#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
解法
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
#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
解法
典型的なメモ化計算の問題ですので簡単にサクッと実装します。
#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
解法
この問題は気持高速に動作するコードときれいなコードどちらを掲載するか迷いました。
ほとんど速度差がないので綺麗なほうを掲載することにしました。
問題の本質はスタートからチーズ、チーズからチーズへのルートの探索だけです。
幅優先探索でチーズからチーズへの移動距離を求めます。
#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
解法仮説
この問題は直接解くのは大変なので別の形に翻訳して解くことにします。
左上から右下まで旗の各升目に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]);
}
}
最終更新:2012年03月08日 10:48