Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2256-54cdcaa5
この記事にトラックバックする(FC2ブログユーザー)

2012 Round 1A B問題 - Kingdom Rush (この記事を編集する[管理者用])

Source

Google code jam 2012 Round 1A B問題
Problem Statement

問題概要

Nステージからなるゲームがある.
ステージiは,
 すでにa[i]個の☆を獲得していれば,簡易クリア可能
 すでにb[i]個の☆を獲得していれば,完全クリア可能.
最初は☆を持っていない.
ステージを簡易クリアすると☆が1個もらえる.
ステージを完全クリアすると☆が2個もらえる.ただし簡易クリアしているステージに対しては追加で☆1個のみもらえる.
ステージは好きな順番にプレイできる.
☆を2N個集めるまでにステージをプレイしなければいけない回数の最小値を求める問題.
smallはNは10以下,largeはNは1000以下.

解法

Greedy.
完全クリア可能なステージに対しては,すぐクリアすれば良い.
そのうちクリアしなければならないし,クリアすることで不利になることもないから.
簡易クリアのみ可能なステージだけになったら,完全クリア可能な閾値の高いものから簡易クリアしていく.
完全クリア可能な閾値が低いものは,それによって,完クリか可能になり,プレイ回数が節減できるかもしれないから.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n,res,now,ok;
  int a[1200], b[1200], alr[1200];
  int size, count = 0;

  scanf("%d",&size);
  while(size--){
    printf("Case #%d: ",++count);
    
    scanf("%d",&n);
    rep(i,n) scanf("%d%d",a+i,b+i);
    rep(i,n) alr[i] = 0;

    res = 0;
    now = 0;
    for(;;){
      if(now==2*n) break;

      ok = 0;
      rep(i,n) if(alr[i]!=2 && b[i]<=now){
        res++;
        now += 2 - alr[i];
        alr[i] = 2;
        ok = 1;
      }
      if(ok) continue;

      k = -1;
      rep(i,n) if(alr[i]==0 && a[i]<=now){
        if(k==-1){ k = i; continue; }
        if(b[i] > b[k]) k = i;
      }
      if(k==-1){res=-1; break;}

      alr[k]=1;
      res++;
      now++;
    }

    if(res==-1) puts("Too Bad"); else printf("%d\n",res);

  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2256-54cdcaa5
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。