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;
    }
  }
};

2012-08-12

Daily Coding と Project Euler Problem 1~5

18:15 |  Daily Coding と Project Euler Problem 1~5 - capythm@TopCoder を含むブックマーク はてなブックマーク -  Daily Coding と Project Euler Problem 1~5 - capythm@TopCoder  Daily Coding と Project Euler Problem 1~5 - capythm@TopCoder のブックマークコメント

最近Daily Codingというのを知りました。1日1問Project Eulerの問題を

解いて投稿するシステムのようです。

http://daily-coding.herokuapp.com/

最近知ったので、最初の18問が未解答のままなので、

Project Eulerの最初の方の問題を解き始めることにしました。

http://projecteuler.net/

最初の問題はいわゆる「やるだけ」が多いので、ソースコードだけメモしておきます。

Project Euler Problem 1

#include <iostream>
using namespace std;
int main( void )
{
  int ret=0;
  for( int i=1; i<1000; i++ ){
    if( i % 3 == 0 || i % 5 == 0 ) ret += i;
  }
  cout << ret << endl; // => 233168
}

Project Euler Problem 2

#include <iostream>
using namespace std;
int main( void )
{
  int d0=1,d1=2,d,ret=2;
  while( (d=d0+d1) < 4000000 ){
    if( d % 2 == 0 ) ret += d;
    d0=d1; d1=d;
  }
  cout << ret << endl; // => 4613732
}

Project Euler Problem 3

#include <iostream>
typedef long long ll;
using namespace std;
int main( void )
{
  ll a = 600851475143LL;
  ll b = 2;
  while( 1 ){
    while( a % b == 0 ) a /= b;
    if( a == 1 ) break;
    b++;
  }
  cout << b << endl; // => 6857
}

Project Euler Problem 4

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
using namespace std;
int main( void )
{
  int ret=0;
  for( int i=100; i<=999; i++ ){
    for( int j=i; j<=999; j++ ){
      int d = i*j;
      stringstream ss;
      ss << d;
      string s = ss.str();
      bool flag=true;
      for( int i=0; i<=s.size()/2; i++ ){
        if( s[i] != s[s.size()-i-1] ){
          flag=false; break;
        }
      }
      if( flag ) ret = max( ret, d );
    }
  }
  cout << ret << endl; // => 906609
}

Project Euler Problem 5

#include <iostream>
using namespace std;
int main( void )
{
  int d = 2520;
  while( 1 ){
    bool flag= true;
    for( int i=2; i<=20; i++ ){
      if( d % i ){ flag=false; break; }
    }
    if( flag ){
      cout << d << endl; // => 232792560
      break;
    }
    d += 2;
  }
}

2012-08-07

Codeforces Round #132 (Div. 2)

14:56 | Codeforces Round #132 (Div. 2) - capythm@TopCoder を含むブックマーク はてなブックマーク - Codeforces Round #132 (Div. 2) - capythm@TopCoder Codeforces Round #132 (Div. 2) - capythm@TopCoder のブックマークコメント

4ACで5位でした。とても調子が良かった。

A. Bicycle Chain

問題概要

数列\{a_i\}, \{b_j\}が与えられる。b_j/a_iが最大となる組み合わせは何通りあるか?

解法

全探索

ソースコード
#include <iostream>
using namespace std;
int main( void )
{
  int a[64],b[64],n,m;
  cin >> n;
  for( int i=0; i<n; i++ ) cin >> a[i];
  cin >> m;
  for( int i=0; i<m; i++ ) cin >> b[i];

  int maxratio=0;
  int ret;
  for( int i=0; i<n; i++ ) for( int j=0; j<m; j++ ){
    if( b[j] % a[i] == 0 ){
      int ratio = b[j] / a[i];
      if( maxratio < ratio ){
        ret = 1;
        maxratio = ratio;
      } else if( maxratio == ratio ){
        ret++;
      }
    }
  }
  cout << ret << endl;
}

B. Olympic Medal

問題概要

f:id:capythm:20120807140237p:image

解法

m_{out},m_{in}r_1,r_2,p_1,p_2で表して、その比がA/Bとなることからr_2を導出する。

\frac{m_{out}}{m_{in}}=\frac{\pi(r_1^2-r_2^2)p_1}{\pi r_2^2p_2}=\frac{A}{B}

Bp_1(r_1^2-r_2^2)=Ap_2r_2^2

r_2^2=\frac{Bp_1}{Ap_2+Bp_1}r_1^2

r_2=r_1\sqrt{\frac{Bp_1}{Ap_2+Bp_1}}=r_1\sqrt{\frac{1}{\frac{A}{B}\frac{p_2}{p_1}+1}}

なので、r_2を最大化するには、r_1,p_1の最大値、p_2の最小値を選択すれば良い。

ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
int main( void )
{
  int n,m,k,d;
  double A,B;
  vector<int> x,y,z;
  cin >> n;
  for( int i=0; i<n; i++ ){ cin >> d; x.push_back(d); }
  cin >> m;
  for( int i=0; i<m; i++ ){ cin >> d; y.push_back(d); }
  cin >> k;
  for( int i=0; i<k; i++ ){ cin >> d; z.push_back(d); }
  cin >> A >> B;

  double p2 = *min_element( z.begin(), z.end() );
  double p1 = *max_element( y.begin(), y.end() );
  double r1 = *max_element( x.begin(), x.end() );
  double r2 = r1 * sqrt( B * p1 / ( A * p2 + B * p1 ) );
  printf( "%.12lf\n", r2 );
}

C. Crosses

問題概要

グリッド上に色を塗ることで十字型を作る。

6つ組(a,b,c,d,x_0,y_0)は以下いずれかを満たす図形を表す。

  • |x_0-x|\leq a かつ |y_0-y|\leq b
  • |x_0-x|\leq c かつ |y_0-y|\leq d

グリッドの大きさがn\times m (n,m≦500)の場合、面積がsとなるような6つ組は何通りあるか?

解法

f:id:capythm:20120807142952p:image

図の4隅の黄色い部分はすべて同じ面積になることを利用して全探索する。

全体を囲む長方形の面積をA、隅の小さい長方形の面積をBとすると、4B+s=Aが成立する。

AのパターンはN^2 (N=249)なので、この回数分全探索し、A-sを計算したときに4の倍数でなければ枝刈りする。

4で割ってBを算出し、Bを2つの数の積で表現して十字型になるかどうかをチェックしてパターンを数える。このとき、x0,y0が変化するパターンも忘れずに計算する。

あと、十字型でなく結果的に長方形になってしまうパターン(A=s)も数えておく。

ソースコード
#include <iostream>
using namespace std;
typedef long long ll;
int main( void )
{
  ll n,m,s,ret=0;
  cin >> n >> m >> s;
  for( ll i=1; i<=n; i+=2 ) for( ll j=1; j<=m; j+=2 ){
    ll a = i*j;
    if( a < s ) continue;
    if( a == s ){
      ll pt = 2*(i+1)*(j+1)/4-1;
      ret += pt * (n-i+1) * (m-j+1);
      continue;
    }
    // a > s
    a = a - s;
    if( a % 4 != 0 ) continue;
    a /= 4;
    for( ll k=1; k*k<=a; k++ ){
      if( a % k ) continue;
      ll pt=0;
      ll l = a / k;
      if( k < (i+1)/2 && l < (j+1)/2 ){
        pt++;
      }
      if( k != l && l < (i+1)/2 && k < (j+1)/2 ){
        pt++;
      }
      ret += pt * 2 * (n-i+1) * (m-j+1);
    }
  }
  cout << ret << endl;
}

D. Hot Days

問題概要

バスに児童を乗せて観光地巡りをする。観光地の気温はtだが、バスの中では児童が乗っている人数分気温が上昇する。

バスの気温がTを超えると各児童にx円補償する必要がある。

補償金を抑えるために、複数台バスを出すこともできるが、バス1台あたりc円かかる。バスを何台出すかは観光地ごとに設定できる。

児童の人数がm人のときの最小コストを求めよ。

解法

バスの台数ごとにいくらかかるかをまず計算してみる。

(a)バスを1台だけ出す場合:

 t+m>T のとき: xm+c

 t+m<=Tのとき: c

(b)バスをN台だして補償金が0円になる場合:

 cN

(c)バスをN台だして児童の何人かに補償金を出す場合:

この場合、補償金を出さないバスをN-1台作って、残りの1台で補償金を出すように偏らせるのがよい。

補償金を出さない児童の数は(T-t)(N-1)なので、総コストは以下の式になる。

x(m-(T-t)(N-1))+cN=x(m+T-t)+(c-x(T-t))N=A+BN

Nの一次式なので、Nは極力小さくするか大きくするかのどちらかになる。

結局のところ、(c)のパターンは意味がなく、(a),(b)のそれぞれのパターンを計算して小さい方を

選択すれば良い。

ソースコード
#include <iostream>
#include <algorithm>
using namespace std;
int main( void )
{
  long long n,m;
  long long t,T,x,cost;
  long long ret=0;
  cin >> n >> m;
  for( long long i=0; i<n; i++ ){ 
    cin >> t >> T >> x >> cost;
    // case 1
    long long tk1   = t + m;
    long long x1    = (tk1>T) ? m*x : 0;
    long long cost1 = cost + x1;
    // case N
    if( t < T ){
      long long num_bus = m/(T-t) + ((m%(T-t))?1:0);
      long long cost2   = cost * num_bus;
      ret += min( cost1, cost2 );
    } else {
      ret += cost1;
    }
  }
  cout << ret << endl;
}

2012-08-05

ColorfulChocolates (SRM 551 Div.1 Easy, Div.2 Medium)

14:29 |  ColorfulChocolates (SRM 551 Div.1 Easy, Div.2 Medium) - capythm@TopCoder を含むブックマーク はてなブックマーク -  ColorfulChocolates (SRM 551 Div.1 Easy, Div.2 Medium) - capythm@TopCoder  ColorfulChocolates (SRM 551 Div.1 Easy, Div.2 Medium) - capythm@TopCoder のブックマークコメント

問題概要

'A'~'Z'を含む文字列 chocolates がある。

隣接する文字同士を交換してできる限り同じ文字が連続するようにしたい。

連続する文字はどれでもいい。

最大でmaxSwaps回交換できる場合、最大で何文字連続するか出力せよ。

http://community.topcoder.com/stat?c=problem_statement&pm=12137&rd=15173&rm=313853&cr=22881961

解法の例

A~Zを同時に考えるとややこしいので、連続させる文字をAからZのそれぞれの場合で考える

(注:それぞれの文字の場合で考えなくても、一気に考える方法もある)。

すると、対象文字とそれ以外の文字の2種類の文字に分類できる。

例えば"ABCDCBC"の場合

  • A: "oxxxxxx"
  • B: "xoxxxox"
  • C: "xxoxoxo"
  • D: "xxxoxxx"

このo,xの文字列をN回スワップした場合にoがどれだけ連続するかをカウントし、その最大値を出力すればいいが、これが結構ややこしい。

考え方としては、全ての部分文字列において、oをくっつけるには最低何回スワップが必要かを計算し、それがmaxSwapsを

超えていなければ、oの数が解の候補になる、という方法が普通である。

部分文字列の両端にxが含まれる場合は無視してもよいので、両端がoの場合のみ考える。

例えば、"oxxoxoxo" という文字列の場合を以下では考える。

スワップ回数の算出方法として2つ例を挙げる。

方法1

全探索する。

"ooooxxxx", "xooooxxx", "xxooooxx", "xxxoooox", "xxxxoooo"

のそれぞれの場合で何回スワップが必要かをカウントして、その最小値が答え。

この場合、スワップ回数=oの移動量と考えることができるので、移動前と移動後でのoの距離の総和がスワップ回数となる。

他の人のソースコードを見ると、方法1の方が簡単で、ほとんどの人がこちらで解いたようだ。

方法2

xを追い出すにはどれだけコストがかかるか、を考える。

"oxxoxoxo" 中のそれぞれのxを左に追い出す場合と右に追い出す場合の飛び越えるoの数を数えて、少ない方に追い出させる。

index=1,2のxは左に追い出すと1、右に追い出すと3なので、左に追い出す(スワップ回数=1)

index=4のxは左に追い出すと2、右に追い出すと2なので、左か右に追い出す(スワップ回数=2)

index=6のxは左に追い出すと3、右に追い出すと1なので、右に追い出す(スワップ回数=1)

全てのxでカウントすると、合計スワップ回数は5となる。

私はこちらの考え方でコーディングしたが、この方法を思いつくのに時間もかかったので、通常は方法1の方がいいかもしれない。

ただし、メモ化などを駆使すれば方法2の方が早くカウントできるような気がする(個人的見解)。処理時間の制限がシビアな場合は方法2がいいかもしれない。

ソースコード

#include <string> 
#include <cstring> 
#include <algorithm> 
#include <iostream> 
using namespace std; 
class ColorfulChocolates{ 
public: 
  int maximumSpread(string chocolates, int maxSwaps){ 
    int N = chocolates.size(); 
    string s = chocolates; 
    int ret=1; 
    for( char c='A'; c<='Z'; c++ ){ 
      for( int i=0; i<N; i++ ){ 
        if( s[i] != c ) continue; 
        int d[64]; 
        memset( d, 0, sizeof(d) ); 
        d[i] = 1; 
        for( int j=i+1; j<N; j++ ){ 
          if( s[j] == c ){ 
            d[j] = d[j-1] + 1; 
            int sw=0; 
            for( int k=i; k<=j; k++ ){ 
              if( s[k] != c ){ 
                sw += min( d[k] - d[i] + 1, d[j] - d[k] ); 
              } 
            } 
            //cout << i << j << d[j] << sw << endl; 
            if( sw <= maxSwaps ) ret = max( ret, d[j] ); 
          } else { 
            d[j] = d[j-1]; 
          } 
        } 
      } 
    } 
    return ret; 
  } 
};