Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

天下一プログラマーコンテスト2013予選B B - 天下一後入れ先出しデータ構造 (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

スタックのシミュレーションを行う問題.
ただし,1回の命令で,同じ数字をたくさん入れたり,たくさんPopしたりできる.
また,スタックに入っている数の数や,スタックのトップの要素を答えたりするクエリが混じっている.
また,スタックのサイズが決まっており,サイズを超えたり,空のスタックからPopしたりトップの要素を参照すると途中でエラーを出して止める.
詳細は問題文を参照.

解法

シミュレーションをやるだけ.
たくさん追加するのは,1つずつやるとTLEになるので,まとめて処理して,何が何個入っている,という形で保存する.
スタックのサイズが,符号付き32ビット整数で表せる限界まで来るので,オーバーフローに注意.(素直に64ビット整数使って気にしないのが楽)

C++によるスパゲッティなソースコード
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
#include<cassert>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

ll read_int(ll mn, ll mx, char next){
  ll c, fg = 1, res = 0;
  c=getchar();
  if(c=='-') fg = -1, c = getchar();
  assert('0'<=c && c<='9');
  res = c - '0';
  for(;;){
    c = getchar();
    if(c==next) break;
    assert(res!=0);
    assert('0'<=c && c<='9');
    res = res * 10 + (c - '0');
  }
  res *= fg;
  assert(mn<=res && res<=mx);
  return res;
}

string read_string(int mx_len, char *next){
  int c;
  string res;

  for(;;){
    c = getchar();
    if(c==' ' || c=='\n'){ *next = c; break; }
    assert(c != EOF);
    res += c;
    assert( res.size() <= mx_len );
  }

  return res;
}


int main(){
  int Q; ll L;

  int i, j, k;
  static int st[100000], num[100000]; int depth; ll size;
  string query;
  int N, M;
  int fin = 0;
  char c;

  Q = read_int(1, 100000, ' ');
  L = read_int(1, 2147483647, '\n');

  depth = size = 0;

  while(Q--){
    query = read_string(10, &c);
    if(query == "Push"){
      assert(c == ' ');
      N = read_int(1, 100000, ' ');
      M = read_int(-(1<<20), 1<<20, '\n');
      if(fin) continue;
      if(size + N > L){ fin = 2; continue; }
      st[depth] = M;
      num[depth] = N;
      size += N;
      depth++;
    } else if(query == "Pop"){
      assert(c == ' ');
      N = read_int(1, 100000, '\n');
      if(fin) continue;
      if(size < N){ fin = 1; continue; }
      size -= N;
      while(N && num[depth-1] <= N){
        N -= num[depth-1];
        depth--;
      }
      if(N) num[depth-1] -= N;
    } else if(query == "Top"){
      assert(c == '\n');
      if(fin) continue;
      if(size==0){ fin=1; continue; }
      printf("%d\n",st[depth-1]);
    } else if(query == "Size"){
      assert(c == '\n');
      if(fin) continue;
      printf("%d\n", size);
    } else {
      assert(0);
    }
  }

  if(fin==0) puts("SAFE");
  if(fin==1) puts("EMPTY");
  if(fin==2) puts("FULL");

  {
    char c;
    assert( scanf("%c",&c)!= 1 );
  }
  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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