Hatena::Grouptopcoder

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

2010-10-06SRM 484 DIV2

遅くなったけど更新。

NumberMagicEasy

21:02 | NumberMagicEasy - capythm@TopCoder を含むブックマーク はてなブックマーク - NumberMagicEasy - capythm@TopCoder NumberMagicEasy - capythm@TopCoder のブックマークコメント

実装するだけ。

他の人のソースを見ると、ビット演算でも計算できたようだ。

#include <string> 
#include <iostream> 
using namespace std; 

class NumberMagicEasy{ 
public: 
  int theNumber(string answer){ 
    string a[] = { "YYYY", "YYYN", "YYNY", "YYNN", "YNYY", "YNYN", "YNNY", "YNNN", 
                   "NYYY", "NYYN", "NYNY", "NYNN", "NNYY", "NNYN", "NNNY" }; 
    for( int i=0; i<15; i++ ){ 
      if( answer == a[i] ){ 
        return i+1; 
      } 
    } 
    return 16; 
  } 
};

RabbitNumber

21:02 | RabbitNumber - capythm@TopCoder を含むブックマーク はてなブックマーク - RabbitNumber - capythm@TopCoder RabbitNumber - capythm@TopCoder のブックマークコメント

実装するだけなら簡単だったが、TLE になってしまう。

標準出力に出してみて、法則性から0~3の数字だけだったが、

どう実装すればいいかわからずに submit 前に時間切れ。10重ループはないだろうし 笑

後日考えて、ビット演算でフルサーチできることを思いついたので実装。

うまく動くかは未確認。

using namespace std; 
class RabbitNumber{ 
  int rabit(long long a){ 
    int ret=0; 
    while( a > 0 ){ 
      ret += a % 10; 
      a /= 10; 
    } 
    return ret; 
  } 
  int bit2int( int n ){
    int ret=0, i=1;
    while( n ){
      ret += (n & 0x03) * i;
      i *= 10;
      n >>= 2;
    }
    return ret;
  }
  int int2bit( int n, int m ){
    int ret=0, i=0;
    int flag=0;
    while( n ){
      int a = n % 10;
      if ( a > 3 ){
        flag=1;
        a = 3;
      }
      ret |= ( a << i );
      i += 2;
      n /= 10;
    }
    return ret+flag*m;
  }
public: 
  int theCount(int low, int high){ 
    int ret=0; 
    for( int i=int2bit(low,1); i<=int2bit(high,0); i++ ){ 
      long long a = bit2int(i);
      int b = rabit( a );
      a = a*a;
      if( rabit( a ) == b * b ){ 
        ret++; 
      } 
    } 
    return ret;
  } 
};

レート

21:02 | レート - capythm@TopCoder を含むブックマーク はてなブックマーク - レート - capythm@TopCoder レート - capythm@TopCoder のブックマークコメント

1101→1125

1問しか解けなかった分、Challenging Phase で550点問題のTLEをがんばった。