Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2012-08-26

SRM 553 練習

21:46 | SRM 553 練習 - capythm@TopCoder を含むブックマーク はてなブックマーク - SRM 553 練習 - capythm@TopCoder SRM 553 練習 - capythm@TopCoder のブックマークコメント

PlatypusDuckAndBeaver (SRM 553 Div.2 Easy)

問題概要

アヒル(アヒルのくちばし1、足2本)、ビーバー(ビーバーのしっぽ1、足4本)が農場にいる。

アヒルのくちばし、ビーバーのしっぽ、足のそれぞれの総数がわかるので、どの動物が何匹いるか、今までは簡単に数えられた。

だが、platypus(カモノハシ)が農場に増えた。カモノハシはアヒルのくちばし1、ビーバーのしっぽ1、足4本を持つ。

アヒルのくちばし、ビーバーのしっぽ、足のそれぞれの総数がわかるとき、農場にいる動物の総数を求めよ。

答えは一意であることが保証される。

解法

カモノハシの数を未知数として全探索する。

(3変数の連立方程式を解いてもいいが、めんどくさい)

ソースコード
class PlatypusDuckAndBeaver{
public:
  int minimumAnimals(int webbedFeet, int duckBills, int beaverTails){
    for( int i=0; i<1000; i++ ){
      int w = webbedFeet - 4*i;
      int d = duckBills - i;
      int b = beaverTails - i;
      int w2 = d*2 + b*4;
      if( w == w2 ) return d+b+i;
    }
    return -1;
  }
};

Suminator (SRM 553 Div.1 Easy/Div.2 Medium)

問題概要

Suminator というプログラミング言語は0以上の整数で構成されており、

以下の動作をする。スタックは初期状態では空である。

  • 0以外の数字の場合:push
  • 0の場合:2数popして足した後push。popしたときに要素がないときは0がpopされたものとする。

プログラムが終端まで来ると、スタックの先頭要素を返す。

Suminator のプログラムがあるが、の一部が欠けて-1になってしまった。返値が wantedResult

の場合、欠けた要素の考え得る最小値を求めよ。ただし、どの値でもwantedResultにならない場合は-1を返せ。

解法

シミュレーションで解く。

欠けた要素が0の場合(s1)、正の数の場合(s2)のそれぞれでシミュレーションする。

ただし、先頭要素が欠けた要素に依存するかどうかについては判定しないといけない。

もし依存していない場合、欠けた要素がどんな値だったとしてもwantedResultにならない or なる。

依存しているかのチェックについては、コーディング上のテクニックになるが、依存している場合は要素が負になるようにスタックに積んだ。こうすることで依存性チェックのための新たなスタックは必要とならない。

ソースコード
#include <vector>
#include <stack>
using namespace std;
class Suminator{
  void add( stack<int>& s ){
    int d1,d2;
    if( s.empty() ) d1=0;
    else { d1 = s.top(); s.pop(); }
    if( s.empty() ) d2=0;
    else { d2 = s.top(); s.pop(); }
    if( d1 < 0 ) s.push( d1-d2 );
    else if( d2 < 0 ) s.push( d2-d1 );
    else s.push( d1+d2 );
  }
public:
  int findMissing( vector<int> program, int wantedResult ){
    stack<int> s1,s2;
    for( vector<int>::iterator it=program.begin(); it != program.end(); ++it ){
      if( *it > 0 ){
        s1.push( *it );
        s2.push( *it );
      } else if( *it < 0 ) {
        // -1 -> 0 ???
        add( s1 );
        // -1 -> positive num
        s2.push( -1 );
      } else {
        add( s1 );
        add( s2 );
      }
    }
    if( s1.empty() ){
      if( wantedResult == 0 ) return 0;
      else return -1;
    } else if( s2.empty() ){
      if( wantedResult == 0 ) return 1;
      else return -1;
    } else if( s1.top() == wantedResult ) {
      return 0;
    } else {
      if( s2.top() > 0 ) return -1;
      int d = wantedResult + s2.top() + 1;
      if( d > 0 ) return d;
      else return -1;
    }
  }
};