Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

2010 Qualification Round C問題 - Theme Park (この記事を編集する[管理者用])

Source

Google code jam 2010 Qualification Round C問題
Problem Statement
2010 Qualification Round 自分の参加記録

問題概要

ジェットコースターの列に,
 a1, a2, a3, ..., aN
人のグループが並んでいる.
ジェットコースターの定員はK人で,前から乗れるグループのみ乗る.追い越してのることはない.
終わったら,また列の後ろに並ぶ.
R回ジェットコースターを運行したら,のべ何人の人が乗ったことになるかを求める問題.
large: Rは1000以下,Kは100以下,Nは10以下.
large: Rは10^8以下,Kは10^9以下,Nは1000以下.

解法

どのグループが先頭だったら,次はどのグループが先頭になって,何人乗る,ってのを最初に計算しておくと,1ステップあたりO(1)でシミュレーションできるようになる.これでlargeも通る.(以下のコードではこれはやってない)
他は,Nが小さいので,同じグループが2回以上先頭に来たら後はループする.ループを検出して一気に処理してやることでも高速化できる.(以下のコードではこれをやっている)

Cによるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int main(){
  ll i,j,k,l,m,n,r,add,st;
  ll in[2000], tm[2000], now[2000];
  ll res;
  ll interval, gain, skip;
  int size,count;

  scanf("%d",&size);
  while(size--){
    scanf("%lld%lld%lld",&r,&k,&n);
    rep(i,n) scanf("%lld",in+i);
    rep(i,n) tm[i]=-1; res=0;

    st=0;
    rep(m,r){
      if(tm[st]>=0){
        interval = m-tm[st]; gain = res-now[st];
        skip = (r-m-1)/interval;
        if(skip>1){
          m += interval*skip;
          res += gain*skip;
        }
      }
      tm[st]=m; now[st]=res;
      add=0;
      rep(i,n){
        if(add+in[st]>k) break;
        add+=in[st]; st=(st+1)%n;
      }
      res+=add;
    }
    printf("Case #%d: %lld\n",++count,res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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