2009-02-08
拙作bignumライブラリを使って昨日のMedium問題を解いてみる
library | | 
string replace(const string s, int a, int b){
stringstream ss;
int l=s.size();
for(int i=0;i<l;i++){
int c=s[i]; ss << (char)((c==a)? b : c);
}
return ss.str();
}
char en(int c){
if (c<10) return '0'+c;
else return 'A'+(c-10);
}
class HexatridecimalSum {
public:
string maximizeSum(vector<string> numbers, int k) {
vector<bignum> ofs(36);
rep(i,36) ofs[i]=0;
bignum sum;
tr(numbers,it){
string orig_str = *it;
bignum b(orig_str,36); sum += b;
rep(i,36){
bignum b_(replace(orig_str,en(i),'Z'),36);
ofs[i] += (b_ - b);
}
}
sort(all(ofs)); reverse(all(ofs));
rep(i,k) sum += ofs[i];
return sum.to_s(36);
}
};
System Testも難なく通りました。
bignumライブラリの自作
- bignum同士の加減乗算（※除算は未実装）
- bignumに(signed)intを足したり引いたり掛けたり割ったり
- bignumと文字列との間の変換（基数指定可）
とか。とりあえず、昨日のMedium問題が解ける程度まで実装できたので晒します。
内部では65536進法で演算しています。2^32進法だと（bignum同士の加算や乗算をする際に）キャリーの計算が面倒くさいかなと思っての愚行です。
ご利用は計画的に。
//
// bignum library ver 0.1 by naoya_t - 使うなら自己責任で
//
#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <iostream>
using namespace std;
class bignum {
int sign;
int size;
vector<int> values;
int default_radix_;
int remainder_;
public:
bignum(int val=0){set(val);default_radix_=10;}
bignum(string val, int radix=10){set(val,default_radix_=radix);}
bignum(const bignum& num){set(num);}
bignum(int sg,const vector<int> &vals,int radix=0){set(sg,vals,radix);}
void operator=(int val){set(val);}
void operator=(string val){set(val,default_radix_);}
void operator=(const bignum& num){set(num);}
void set(int val);
void set(string val, int radix=10);
void set(const bignum& num);
void set(int sg,const vector<int> &vals,int radix=0);
private:
bool is_zero() const { return (size==1 && values[0]==0)? true : false; };
void set_zero();
void normalize();
char enc(int n) const { return n<10 ? '0'+n : 'A'+(n-10); }
int dec(int ch) const { return ch<='9' ? ch-'0' : 10+ch-'A'; }
public:
void set_default_radix(int radix){default_radix_=radix;}
int get_default_radix(){return default_radix_;}
string sdump() const;
void dump() { cout << sdump(); }
bignum abs() const;
bignum minus() const;
int cmp(const bignum &n) const;
int cmp_abs(const bignum &n) const;
int to_i();
string to_s(int radix=10) const;
bignum operator+(const bignum& rop){ bignum num(*this); num += rop; return num; }
bignum operator-(const bignum& rop){ bignum num(*this); num += rop.minus(); return num; }
bignum operator*(const bignum& rop){ bignum num(*this); num *= rop; return num; }
bignum operator+(int rop){
bignum num(*this); num += rop; return num; }
bignum operator-(int rop){
bignum num(*this); num -= rop; return num; }
bignum operator*(int rop){
bignum num(*this); num *= rop; return num; }
bignum operator/(int rop){
bignum num(*this); num /= rop; return num; }
bool operator==(const bignum& rop) const { return cmp(rop)==0; }
bool operator!=(const bignum& rop) const { return cmp(rop)!=0; }
bool operator>(const bignum& rop) const { return cmp(rop)>0; }
bool operator>=(const bignum& rop) const { return cmp(rop)>=0; }
bool operator<(const bignum& rop) const { return cmp(rop)<0; }
bool operator<=(const bignum& rop) const { return cmp(rop)<=0; }
void operator+=(const bignum& num);
void operator-=(const bignum& num){ operator+=(num.minus()); }
void operator*=(const bignum& num);
//void operator/=(const bignum& num);
void operator+=(int n);
void operator-=(int n){ operator+=(-n); }
void operator*=(int n);
void operator/=(int n);
//void operator%=(int n);
int remainder(){ return remainder_; }
bignum add(const bignum& n){ bignum num(*this); num += n; return num; }
bignum sub(const bignum& n){ bignum num(*this); num += n.minus(); return num; }
bignum mul(const bignum& n){ bignum num(*this); num *= n; return num; }
//bignum div(const bignum& n){ bignum num(*this); num /= n; return num; }
bignum add(int n){ bignum num(*this); num += n; return num; }
bignum sub(int n){ bignum num(*this); num += (-n); return num; }
bignum mul(int n){ bignum num(*this); num *= n; return num; }
bignum div(int n){ bignum num(*this); num /= n; return num; }
};
void bignum::set(int val){
if (val == INT_MIN) {
values.resize(size = 2);
sign = -1;
values[0] = 0; values[1] = 0x8000;
} else {
if (val < 0) { sign = -1; val = -val; } else sign = 1;
if (val >= 65536) {
values.resize(size = 2);
values[0] = val % 65536; values[1] = val >> 16;
} else {
values.resize(size = 1);
values[0] = val;
}
}
}
void bignum::set_zero(){
values.resize(size = 1);
size = 1; sign = 1; values[0] = 0;
}
void bignum::set(const bignum& num){
values.assign(num.values.begin(), num.values.end());
sign = num.sign; size = num.size; default_radix_ = num.default_radix_;
}
void bignum::set(int sg,const vector<int> &vals,int radix){
if (radix == 0) {
size=1;
for(int i=0,s=vals.size();i<s;i++) if (vals[i]>0) size=i+1;
values.assign(vals.begin(), vals.begin()+size);
sign = is_zero()? 1 : sg;
} else {
set_zero();
}
}
int bignum::to_i() {
switch(size){
case 1:
return sign * values[0];
case 2:
if (values[1]<=0x7fff)
return sign * ((values[1]<<16) | values[0]);
else if (values[1]==0x8000 && values[0]==0 && sign==-1)
return INT_MIN;
else
; // else ; thru
default:
return INT_MAX+1;
}
}
string bignum::sdump() const {
stringstream ss;
ss << ((sign > 0) ? "+" : "-") << hex << uppercase;
for (int i=0;i<size;i++) {
if (i>0) ss << ":";
ss << values[size-i-1];
}
ss << "<" << size << ">";
return ss.str();
}
bignum bignum::abs() const {
bignum num(*this);
num.sign = 1;
return num;
}
bignum bignum::minus() const {
bignum num(*this);
if (!is_zero()) num.sign = -num.sign;
return num;
}
int bignum::cmp(const bignum &n) const {
if(sign != n.sign) return (sign - n.sign)/2;
return sign * cmp_abs(n);
}
int bignum::cmp_abs(const bignum &n) const {
if(size!=n.size)
return size - n.size;
for(int i=size-1;i>=0;i--)
if(values[i]!=n.values[i]) return values[i] - n.values[i];
return 0;
}
void bignum::operator+=(const bignum &n){
if(n.is_zero()) return;
if(sign == n.sign) {
if(size < n.size) {
values.resize(n.size);
for(int i=size;i<n.size;i++) values[i]=0;
size = n.size;
}
// simple addition
for(int i=0;i<n.size;i++) values[i] += n.values[i];
} else {
if(cmp_abs(n) >= 0) {
for(int i=0;i<n.size;i++) {
if (values[i] >= n.values[i]) {
values[i] -= n.values[i];
} else {
int pl=i+1;
for(int j=i+1;j<n.size;j++) if(values[j]>0){ pl=j; break; }
for(int j=pl;j>i;j--) { values[j]--; values[j-1]+=65536; }
values[i] -= n.values[i];
}
}
} else {
bignum t(n);
set(t + *this);
}
}
normalize();
}
void bignum::operator*=(const bignum &n){
if(is_zero()) return;
if(n.is_zero()){ set_zero(); return; }
sign *= n.sign;
vector<int> tmp(size + n.size, 0);
for(int i=n.size-1;i>=0;i--){
int ni = n.values[i];
for(int j=size-1;j>=0;j--){
unsigned int ij = (unsigned int)ni * values[j];
tmp[i+j] += ij % 65536;
tmp[i+j+1] += ij >> 16;
}
}
values.assign(tmp.begin(), tmp.end());
size += n.size;
normalize();
}
void bignum::operator+=(int n){
if (n==0) return;
if (sign*n<0){
int m=this->to_i();
if (m!=INT_MAX+1){
set(m + n);
return;
}
}
if(sign==-1) n=-n;
values[0] += n;
normalize();
}
void bignum::operator*=(int n){
if(n==0){ set_zero(); return; }
if(n==1){ return; }
if(n==-1){ sign=-sign; return; }
if(n<0){ sign=-sign; n=-n; }
for(int i=0;i<size;i++) values[i]*=n;
normalize();
}
void bignum::operator/=(int n){
if(n==0){ set_zero(); return; } // NaN
if(n==1){ return; }
if(n==-1){ sign=-sign; return; }
if(n<0){ sign=-sign; n=-n; }
int r = 0;
for(int i=size-1; i>=0; i--){
int v = (r << 16) + values[i];
r = v % n;
values[i] = v / n;
}
normalize();
remainder_ = r;
}
void bignum::normalize(){
unsigned int overflown=0;
int sz=1;
for(int i=0;i<size;i++){
if (values[i]>0) sz=i+1;
if (values[i]<0) {
if (i==size-1) {
// underflow
sign=-sign;
values[i]=-values[i];
for (int j=i-1;j>=0;j--){
//...
}
} else {
// borrowable
int b=-values[i];
values[i+1] -= (b >> 16);
if (b&0xffff){
values[i+1]--;
values[i] = 65536 - b;
} else {
values[i] = 0;
}
}
}
if (values[i]>=65536){
if (i==size-1) overflown = values[i] >> 16;
else values[i+1] += values[i] >> 16;
values[i] %= 65536;
}
}
if (overflown == 0) {
if (sz<size) values.resize(size=sz);
if (is_zero()) sign=1;
} else if (overflown < 65536){
values.resize(size+1);
values[size++] = overflown;
} else {
values.resize(size+2);
values[size++] = overflown % 65536;
values[size++] = overflown >> 16;
}
}
string bignum::to_s(int radix) const {
if (is_zero()) return "0";
if (radix < 2 || 36 < radix) return "?";
stack<char> s;
bignum tmp(*this);
while(!tmp.is_zero()){
tmp /= radix;
s.push(enc(tmp.remainder()));
}
stringstream ss;
if (sign == -1) ss << "-";
while(!s.empty()){
ss << s.top();
s.pop();
}
return ss.str();
}
void bignum::set(string val, int radix){
set_zero();
if (radix < 2 || 36 < radix) return;
default_radix_ = radix;
int l=val.size();
int start=0, sg=1;
if(val[0]=='-'){ sg = -1; start++; }
else if(val[0]=='+') start++;
for(int i=start,s=val.size();i<s;i++){
operator*=( radix );
operator+=( dec(val[i]) );
}
normalize();
sign = sg;
}
googletestつけとくよ
using namespace std;
// #include "bignum.cc"
#include <gtest/gtest.h>
TEST(BignumTest, sdump)
{
bignum num; vector<int> v(1,0);
num.set(1,v); EXPECT_EQ("+0<1>", num.sdump());
num.set(-1,v); EXPECT_EQ("+0<1>", num.sdump());
v[0]=1;
num.set(1,v); EXPECT_EQ("+1<1>", num.sdump());
num.set(-1,v); EXPECT_EQ("-1<1>", num.sdump());
v[0]=65535;
num.set(1,v); EXPECT_EQ("+FFFF<1>", num.sdump());
num.set(-1,v); EXPECT_EQ("-FFFF<1>", num.sdump());
v.resize(2);
v[0]=v[1]=0;
num.set(1,v); EXPECT_EQ("+0<1>", num.sdump());
num.set(-1,v); EXPECT_EQ("+0<1>", num.sdump());
v[0]=65535; v[1]=1;
num.set(1,v); EXPECT_EQ("+1:FFFF<2>", num.sdump());
num.set(-1,v); EXPECT_EQ("-1:FFFF<2>", num.sdump());
v[1]=65535;
num.set(1,v); EXPECT_EQ("+FFFF:FFFF<2>", num.sdump());
num.set(-1,v); EXPECT_EQ("-FFFF:FFFF<2>", num.sdump());
v.resize(3);
v[2]=1;
num.set(1,v); EXPECT_EQ("+1:FFFF:FFFF<3>", num.sdump());
num.set(-1,v); EXPECT_EQ("-1:FFFF:FFFF<3>", num.sdump());
v[2]=65535;
num.set(1,v); EXPECT_EQ("+FFFF:FFFF:FFFF<3>", num.sdump());
num.set(-1,v); EXPECT_EQ("-FFFF:FFFF:FFFF<3>", num.sdump());
}
TEST(BignumTest, to_i)
{
bignum num; EXPECT_EQ(0, num.to_i());
num=1; EXPECT_EQ(1, num.to_i());
num=2; EXPECT_EQ(2, num.to_i());
num=-1; EXPECT_EQ(-1, num.to_i());
num=-2; EXPECT_EQ(-2, num.to_i());
num=65535; EXPECT_EQ(65535, num.to_i());
num=-65535; EXPECT_EQ(-65535, num.to_i());
num=65536; EXPECT_EQ(65536, num.to_i());
num=-65536; EXPECT_EQ(-65536, num.to_i());
num=65537; EXPECT_EQ(65537, num.to_i());
num=-65537; EXPECT_EQ(-65537, num.to_i());
num=INT_MAX; EXPECT_EQ(INT_MAX, num.to_i());
num=-INT_MAX; EXPECT_EQ(-INT_MAX, num.to_i());
num=INT_MIN; EXPECT_EQ(INT_MIN, num.to_i());
// overflow case
//...
}
TEST(BignumTest, ctor_from_signed_int)
{
bignum num; EXPECT_EQ(0, num.to_i()); EXPECT_EQ("+0<1>", num.sdump());
bignum num0(0); EXPECT_EQ(0, num0.to_i()); EXPECT_EQ("+0<1>", num0.sdump());
bignum num1(1); EXPECT_EQ(1, num1.to_i()); EXPECT_EQ("+1<1>", num1.sdump());
bignum num2(2); EXPECT_EQ(2, num2.to_i()); EXPECT_EQ("+2<1>", num2.sdump());
bignum num_1(-1); EXPECT_EQ(-1, num_1.to_i()); EXPECT_EQ("-1<1>", num_1.sdump());
bignum num_2(-2); EXPECT_EQ(-2, num_2.to_i()); EXPECT_EQ("-2<1>", num_2.sdump());
bignum numIMAX(INT_MAX); EXPECT_EQ(INT_MAX, numIMAX.to_i()); EXPECT_EQ("+7FFF:FFFF<2>", numIMAX.sdump());
bignum num_IMAX(-INT_MAX); EXPECT_EQ(-INT_MAX, num_IMAX.to_i()); EXPECT_EQ("-7FFF:FFFF<2>", num_IMAX.sdump());
bignum numIMIN(INT_MIN); EXPECT_EQ(INT_MIN, numIMIN.to_i()); EXPECT_EQ("-8000:0<2>", numIMIN.sdump());
}
TEST(BignumTest, assign_signed_int)
{
bignum num;
num=0; EXPECT_EQ(0, num.to_i()); EXPECT_EQ("+0<1>", num.sdump());
num=1; EXPECT_EQ(1, num.to_i()); EXPECT_EQ("+1<1>", num.sdump());
num=2; EXPECT_EQ(2, num.to_i()); EXPECT_EQ("+2<1>", num.sdump());
num=-1; EXPECT_EQ(-1, num.to_i()); EXPECT_EQ("-1<1>", num.sdump());
num=-2; EXPECT_EQ(-2, num.to_i()); EXPECT_EQ("-2<1>", num.sdump());
num=1000000; EXPECT_EQ(1000000, num.to_i()); EXPECT_EQ("+F:4240<2>", num.sdump());
num=-1000000; EXPECT_EQ(-1000000, num.to_i()); EXPECT_EQ("-F:4240<2>", num.sdump());
num=INT_MAX; EXPECT_EQ(INT_MAX, num.to_i()); EXPECT_EQ("+7FFF:FFFF<2>", num.sdump());
num=-INT_MAX; EXPECT_EQ(-INT_MAX, num.to_i()); EXPECT_EQ("-7FFF:FFFF<2>", num.sdump());
num=INT_MIN; EXPECT_EQ(INT_MIN, num.to_i()); EXPECT_EQ("-8000:0<2>", num.sdump());
}
TEST(BignumTest, abs)
{
bignum num; EXPECT_EQ(0, num.abs().to_i()); EXPECT_EQ("+0<1>", num.abs().sdump());
num=1; EXPECT_EQ(1, num.abs().to_i()); EXPECT_EQ("+1<1>", num.abs().sdump());
num=2; EXPECT_EQ(2, num.abs().to_i()); EXPECT_EQ("+2<1>", num.abs().sdump());
num=-1; EXPECT_EQ(1, num.abs().to_i()); EXPECT_EQ("+1<1>", num.abs().sdump());
num=-2; EXPECT_EQ(2, num.abs().to_i()); EXPECT_EQ("+2<1>", num.abs().sdump());
num=INT_MAX; EXPECT_EQ(INT_MAX, num.abs().to_i()); EXPECT_EQ("+7FFF:FFFF<2>", num.abs().sdump());
num=-INT_MAX; EXPECT_EQ(INT_MAX, num.abs().to_i()); EXPECT_EQ("+7FFF:FFFF<2>", num.abs().sdump());
num=INT_MIN; EXPECT_EQ(INT_MIN, num.abs().to_i()); EXPECT_EQ("+8000:0<2>", num.abs().sdump());
vector<int> v(2,65535);
num.set(1,v); EXPECT_EQ("+FFFF:FFFF<2>", num.abs().sdump());
num.set(-1,v); EXPECT_EQ("+FFFF:FFFF<2>", num.abs().sdump());
}
TEST(BignumTest, minus)
{
bignum num; EXPECT_EQ(0, num.abs().to_i()); EXPECT_EQ("+0<1>", num.minus().sdump());
num=1; EXPECT_EQ(-1, num.minus().to_i()); EXPECT_EQ("-1<1>", num.minus().sdump());
num=2; EXPECT_EQ(-2, num.minus().to_i()); EXPECT_EQ("-2<1>", num.minus().sdump());
num=-1; EXPECT_EQ(1, num.minus().to_i()); EXPECT_EQ("+1<1>", num.minus().sdump());
num=-2; EXPECT_EQ(2, num.minus().to_i()); EXPECT_EQ("+2<1>", num.minus().sdump());
num=INT_MAX; EXPECT_EQ(-INT_MAX, num.minus().to_i()); EXPECT_EQ("-7FFF:FFFF<2>", num.minus().sdump());
num=-INT_MAX; EXPECT_EQ(INT_MAX, num.minus().to_i()); EXPECT_EQ("+7FFF:FFFF<2>", num.minus().sdump());
num=INT_MIN; EXPECT_EQ(INT_MAX+1, num.minus().to_i()); EXPECT_EQ("+8000:0<2>", num.minus().sdump());
vector<int> v(2,65535);
num.set(1,v); EXPECT_EQ("-FFFF:FFFF<2>", num.minus().sdump());
num.set(-1,v); EXPECT_EQ("+FFFF:FFFF<2>", num.minus().sdump());
}
TEST(BignumTest, to_s)
{
bignum num; EXPECT_EQ("0", num.to_s());
num=1; EXPECT_EQ("1", num.to_s());
num=2; EXPECT_EQ("2", num.to_s());
num=-1; EXPECT_EQ("-1", num.to_s());
num=-2; EXPECT_EQ("-2", num.to_s());
num=INT_MAX; EXPECT_EQ("2147483647", num.to_s());
num=-INT_MAX; EXPECT_EQ("-2147483647", num.to_s());
num=INT_MIN; EXPECT_EQ("-2147483648", num.to_s());
num=15;
EXPECT_EQ("15", num.to_s());
EXPECT_EQ("1111", num.to_s(2));
EXPECT_EQ("F", num.to_s(16));
num=100;
EXPECT_EQ("100", num.to_s());
EXPECT_EQ("64", num.to_s(16));
num=35;
EXPECT_EQ("35", num.to_s());
EXPECT_EQ("100011", num.to_s(2));
EXPECT_EQ("23", num.to_s(16));
EXPECT_EQ("Z", num.to_s(36));
num=65537;
EXPECT_EQ("65537", num.to_s());
EXPECT_EQ("10000000000000001", num.to_s(2));
EXPECT_EQ("10001", num.to_s(16));
num=1; for(int i=0;i<30;i++) num*=10;
EXPECT_EQ("1000000000000000000000000000000", num.to_s());
num=1; for(int i=0;i<30;i++) num*=16;
EXPECT_EQ("1000000000000000000000000000000", num.to_s(16));
}
TEST(BignumTest, add_eq_signed_int) // testing operator +=
{
bignum num;
num=0; num+=2; EXPECT_EQ("+2<1>", num.sdump());
num=0; num+=-2; EXPECT_EQ("-2<1>", num.sdump());
num=1; num+=2; EXPECT_EQ("+3<1>", num.sdump());
num=1; num+=-2; EXPECT_EQ("-1<1>", num.sdump());
num=-1; num+=2; EXPECT_EQ("+1<1>", num.sdump());
num=-1; num+=-2; EXPECT_EQ("-3<1>", num.sdump());
num=50000; num+=50000;
EXPECT_EQ(100000, num.to_i()); EXPECT_EQ("+1:86A0<2>", num.sdump());
num=50000; num+=-50000;
EXPECT_EQ(0, num.to_i()); EXPECT_EQ("+0<1>", num.sdump());
num=-50000; num+=50000;
EXPECT_EQ(0, num.to_i()); EXPECT_EQ("+0<1>", num.sdump());
num=-50000; num+=-50000;
EXPECT_EQ(-100000, num.to_i()); EXPECT_EQ("-1:86A0<2>", num.sdump());
num=567890; num+=432100;
EXPECT_EQ(999990, num.to_i()); EXPECT_EQ("+F:4236<2>", num.sdump());
num=567890; num+=-432100;
EXPECT_EQ(135790, num.to_i()); EXPECT_EQ("+2:126E<2>", num.sdump());
num=-567890; num+=432100;
EXPECT_EQ(-135790, num.to_i()); EXPECT_EQ("-2:126E<2>", num.sdump());
num=-567890; num+=-432100;
EXPECT_EQ(-999990, num.to_i()); EXPECT_EQ("-F:4236<2>", num.sdump());
num=567890; num+=567889;
EXPECT_EQ(1135779, num.to_i()); EXPECT_EQ("+11:54A3<2>", num.sdump());
num=567890; num+=-567889;
EXPECT_EQ(1, num.to_i()); EXPECT_EQ("+1<1>", num.sdump());
num=-567890; num+=567889;
EXPECT_EQ(-1, num.to_i()); EXPECT_EQ("-1<1>", num.sdump());
num=-567890; num+=-567889;
EXPECT_EQ(-1135779, num.to_i()); EXPECT_EQ("-11:54A3<2>", num.sdump());
num=432100; num+=567890; EXPECT_EQ("+F:4236<2>", num.sdump());
num=432100; num+=-567890; EXPECT_EQ("-2:126E<2>", num.sdump());
num=-432100; num+=567890; EXPECT_EQ("+2:126E<2>", num.sdump());
num=-432100; num+=-567890; EXPECT_EQ("-F:4236<2>", num.sdump());
}
TEST(BignumTest, sub_eq_signed_int) // testing operator -=
{
bignum num;
num=0; num-=2; EXPECT_EQ("-2<1>", num.sdump());
num=0; num-=-2; EXPECT_EQ("+2<1>", num.sdump());
num=1; num-=2; EXPECT_EQ("-1<1>", num.sdump());
num=1; num-=-2; EXPECT_EQ("+3<1>", num.sdump());
num=-1; num-=2; EXPECT_EQ("-3<1>", num.sdump());
num=-1; num-=-2; EXPECT_EQ("+1<1>", num.sdump());
num=50000; num-=50000; EXPECT_EQ("+0<1>", num.sdump());
num=50000; num-=-50000; EXPECT_EQ("+1:86A0<2>", num.sdump());
num=-50000; num-=50000; EXPECT_EQ("-1:86A0<2>", num.sdump());
num=-50000; num-=-50000; EXPECT_EQ("+0<1>", num.sdump());
num=567890; num-=432100; EXPECT_EQ("+2:126E<2>", num.sdump());
num=567890; num-=-432100; EXPECT_EQ("+F:4236<2>", num.sdump());
num=-567890; num-=432100; EXPECT_EQ("-F:4236<2>", num.sdump());
num=-567890; num-=-432100; EXPECT_EQ("-2:126E<2>", num.sdump());
num=567890; num-=567889; EXPECT_EQ("+1<1>", num.sdump());
num=567890; num-=-567889; EXPECT_EQ("+11:54A3<2>", num.sdump());
num=-567890; num-=567889; EXPECT_EQ("-11:54A3<2>", num.sdump());
num=-567890; num-=-567889; EXPECT_EQ("-1<1>", num.sdump());
num=432100; num-=567890; EXPECT_EQ("-2:126E<2>", num.sdump());
num=432100; num-=-567890; EXPECT_EQ("+F:4236<2>", num.sdump());
num=-432100; num-=567890; EXPECT_EQ("-F:4236<2>", num.sdump());
num=-432100; num-=-567890; EXPECT_EQ("+2:126E<2>", num.sdump());
}
TEST(BignumTest, mul_eq_signed_int) // testing operator *=
{
bignum num;
num=0; num*=2; EXPECT_EQ("+0<1>", num.sdump());
num=0; num*=-2; EXPECT_EQ("+0<1>", num.sdump());
num=1; num*=2; EXPECT_EQ("+2<1>", num.sdump());
num=1; num*=-2; EXPECT_EQ("-2<1>", num.sdump());
num=-1; num*=2; EXPECT_EQ("-2<1>", num.sdump());
num=-1; num*=-2; EXPECT_EQ("+2<1>", num.sdump());
num=3; num*=5; EXPECT_EQ("+F<1>", num.sdump());
num=3; num*=-5; EXPECT_EQ("-F<1>", num.sdump());
num=-3; num*=5; EXPECT_EQ("-F<1>", num.sdump());
num=-3; num*=-5; EXPECT_EQ("+F<1>", num.sdump());
num=1000; num*=1000; EXPECT_EQ("+F:4240<2>", num.sdump());
num=1000; num*=-1000; EXPECT_EQ("-F:4240<2>", num.sdump());
num=-1000; num*=1000; EXPECT_EQ("-F:4240<2>", num.sdump());
num=-1000; num*=-1000; EXPECT_EQ("+F:4240<2>", num.sdump());
}
TEST(BignumTest, div_eq_signed_int) // testing operator /=
{
bignum num;
num=0; num/=2;
EXPECT_EQ("+0<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
num=0; num/=-2;
EXPECT_EQ("+0<1>", num.sdump()); //EXPECT_EQ(0, num.remainder());
num=1; num/=2;
EXPECT_EQ("+0<1>", num.sdump()); EXPECT_EQ(1, num.remainder());
num=1; num/=-2;
EXPECT_EQ("+0<1>", num.sdump()); //EXPECT_EQ(1, num.remainder());
num=-1; num/=2;
EXPECT_EQ("+0<1>", num.sdump()); //EXPECT_EQ(1, num.remainder());
num=-1; num/=-2;
EXPECT_EQ("+0<1>", num.sdump()); //EXPECT_EQ(1, num.remainder());
num=13; num/=5;
EXPECT_EQ("+2<1>", num.sdump()); EXPECT_EQ(3, num.remainder());
num=13; num/=-5;
EXPECT_EQ("-2<1>", num.sdump()); //EXPECT_EQ(3, num.remainder());
num=-13; num/=5;
EXPECT_EQ("-2<1>", num.sdump()); //EXPECT_EQ(3, num.remainder());
num=-13; num/=-5;
EXPECT_EQ("+2<1>", num.sdump()); //EXPECT_EQ(3, num.remainder());
num=1000000; num/=1000;
EXPECT_EQ("+3E8<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
num=1000000; num/=-1000;
EXPECT_EQ("-3E8<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
num=-1000000; num/=1000;
EXPECT_EQ("-3E8<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
num=-1000000; num/=-1000;
EXPECT_EQ("+3E8<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
}
TEST(BignumTest, add_eq_bignum) // +=
{
bignum a, b;
a=0, b=0; a+=b; EXPECT_EQ(0, a.to_i());
a=0, b=2; a+=b; EXPECT_EQ(2, a.to_i());
a=2, b=0; a+=b; EXPECT_EQ(2, a.to_i());
a=1, b=2; a+=b; EXPECT_EQ(3, a.to_i());
a=1, b=-2; a+=b; EXPECT_EQ(-1, a.to_i());
a=-1, b=2; a+=b; EXPECT_EQ(1, a.to_i());
a=-1, b=-2; a+=b; EXPECT_EQ(-3, a.to_i());
a=50000, b=50000; a+=b; EXPECT_EQ(100000, a.to_i());
a=50000, b=-50000; a+=b; EXPECT_EQ(0, a.to_i());
a=-50000, b=50000; a+=b; EXPECT_EQ(0, a.to_i());
a=-50000, b=-50000; a+=b; EXPECT_EQ(-100000, a.to_i());
a=567890, b=432100; a+=b; EXPECT_EQ(999990, a.to_i());
a=567890, b=-432100; a+=b; EXPECT_EQ(135790, a.to_i());
a=-567890, b=432100; a+=b; EXPECT_EQ(-135790, a.to_i());
a=-567890, b=-432100; a+=b; EXPECT_EQ(-999990, a.to_i());
a=567890, b=567889; a+=b; EXPECT_EQ(1135779, a.to_i());
a=567890, b=-567889; a+=b; EXPECT_EQ(1, a.to_i());
a=-567890, b=567889; a+=b; EXPECT_EQ(-1, a.to_i());
a=-567890, b=-567889; a+=b; EXPECT_EQ(-1135779, a.to_i());
a=432100, b=567890; a+=b; EXPECT_EQ(999990, a.to_i());
a=432100, b=-567890; a+=b; EXPECT_EQ(-135790, a.to_i());
a=-432100, b=567890; a+=b; EXPECT_EQ(135790, a.to_i());
a=-432100, b=-567890; a+=b; EXPECT_EQ(-999990, a.to_i());
}
TEST(BignumTest, mul_eq_bignum) // testing operator *=
{
bignum a, b;
a=0; b=0; a*=b; EXPECT_EQ(0, a.to_i());
a=0; b=2; a*=b; EXPECT_EQ(0, a.to_i());
a=2; b=0; a*=b; EXPECT_EQ(0, a.to_i());
a=1; b=1; a*=b; EXPECT_EQ(1, a.to_i());
a=1; b=2; a*=b; EXPECT_EQ(2, a.to_i());
a=2; b=1; a*=b; EXPECT_EQ(2, a.to_i());
a=2; b=2; a*=b; EXPECT_EQ(4, a.to_i());
a=3; b=-2; a*=b; EXPECT_EQ(-6, a.to_i());
a=-3; b=2; a*=b; EXPECT_EQ(-6, a.to_i());
a=-3; b=-2; a*=b; EXPECT_EQ(6, a.to_i());
a=10000; b=10000; a*=b; EXPECT_EQ(100000000, a.to_i());
a=100000000; b=100000000; a*=b; EXPECT_EQ("10000000000000000", a.to_s());
a=65535; b=65535; a*=b; EXPECT_EQ("FFFE0001", a.to_s(16));
a=65536; b=65536; a*=b; EXPECT_EQ("100000000", a.to_s(16));
}
TEST(BignumTest, add) // +
{
bignum a, b;
a=0, b=0; EXPECT_EQ(0, (a+b).to_i());
a=0, b=2; EXPECT_EQ(2, (a+b).to_i());
a=2, b=0; EXPECT_EQ(2, (a+b).to_i());
a=1, b=2; EXPECT_EQ(3, (a+b).to_i()); EXPECT_EQ(1, a.to_i()); EXPECT_EQ(2, b.to_i());
a=1, b=-2; EXPECT_EQ(-1, (a+b).to_i());
a=-1, b=2; EXPECT_EQ(1, (a+b).to_i());
a=-1, b=-2; EXPECT_EQ(-3, (a+b).to_i());
a=50000, b=50000; EXPECT_EQ(100000, (a+b).to_i());
a=50000, b=-50000; EXPECT_EQ(0, (a+b).to_i());
a=-50000, b=50000; EXPECT_EQ(0, (a+b).to_i());
a=-50000, b=-50000; EXPECT_EQ(-100000, (a+b).to_i());
a=567890, b=432100; EXPECT_EQ(999990, (a+b).to_i());
a=567890, b=-432100; EXPECT_EQ(135790, (a+b).to_i());
a=-567890, b=432100; EXPECT_EQ(-135790, (a+b).to_i());
a=-567890, b=-432100; EXPECT_EQ(-999990, (a+b).to_i());
a=567890, b=567889; EXPECT_EQ(1135779, (a+b).to_i());
a=567890, b=-567889; EXPECT_EQ(1, (a+b).to_i());
a=-567890, b=567889; EXPECT_EQ(-1, (a+b).to_i());
a=-567890, b=-567889; EXPECT_EQ(-1135779, (a+b).to_i());
a=432100, b=567890; EXPECT_EQ(999990, (a+b).to_i());
a=432100, b=-567890; EXPECT_EQ(-135790, (a+b).to_i());
a=-432100, b=567890; EXPECT_EQ(135790, (a+b).to_i());
a=-432100, b=-567890; EXPECT_EQ(-999990, (a+b).to_i());
}
TEST(BignumTest, sub) // -
{
bignum a, b;
a=0, b=0; EXPECT_EQ(0, (a-b).to_i());
a=0, b=2; EXPECT_EQ(-2, (a-b).to_i());
a=2, b=0; EXPECT_EQ(2, (a-b).to_i());
a=1, b=2; EXPECT_EQ(-1, (a-b).to_i()); EXPECT_EQ(1, a.to_i()); EXPECT_EQ(2, b.to_i());
a=1, b=-2; EXPECT_EQ(3, (a-b).to_i());
a=-1, b=2; EXPECT_EQ(-3, (a-b).to_i());
a=-1, b=-2; EXPECT_EQ(1, (a-b).to_i());
a=50000, b=50000; EXPECT_EQ(0, (a-b).to_i());
a=50000, b=-50000; EXPECT_EQ(100000, (a-b).to_i());
a=-50000, b=50000; EXPECT_EQ(-100000, (a-b).to_i());
a=-50000, b=-50000; EXPECT_EQ(0, (a-b).to_i());
a=567890, b=432100; EXPECT_EQ(135790, (a-b).to_i());
a=567890, b=-432100; EXPECT_EQ(999990, (a-b).to_i());
a=-567890, b=432100; EXPECT_EQ(-999990, (a-b).to_i());
a=-567890, b=-432100; EXPECT_EQ(-135790, (a-b).to_i());
a=567890, b=567889; EXPECT_EQ(1, (a-b).to_i());
a=567890, b=-567889; EXPECT_EQ(1135779, (a-b).to_i());
a=-567890, b=567889; EXPECT_EQ(-1135779, (a-b).to_i());
a=-567890, b=-567889; EXPECT_EQ(-1, (a-b).to_i());
a=432100, b=567890; EXPECT_EQ(-135790, (a-b).to_i());
a=432100, b=-567890; EXPECT_EQ(999990, (a-b).to_i());
a=-432100, b=567890; EXPECT_EQ(-999990, (a-b).to_i());
a=-432100, b=-567890; EXPECT_EQ(135790, (a-b).to_i());
a.set("H",36); b.set("H",36); EXPECT_EQ("0", (a-b).to_s(36));
a.set("HZ",36); b.set("HE",36); EXPECT_EQ("L", (a-b).to_s(36));
a.set("HZL",36); b.set("HEL",36); EXPECT_EQ("L0", (a-b).to_s(36));
a.set("HZLO",36); b.set("HELO",36); EXPECT_EQ("L00", (a-b).to_s(36));
a.set("HZLLO",36); b.set("HELLO",36); EXPECT_EQ("L000", (a-b).to_s(36));
}
TEST(BignumTest, mul) // *
{
bignum a, b;
a=0; b=0; EXPECT_EQ(0, (a*b).to_i());
a=0; b=2; EXPECT_EQ(0, (a*b).to_i());
a=2; b=0; EXPECT_EQ(0, (a*b).to_i());
a=1; b=1; EXPECT_EQ(1, (a*b).to_i());
a=1; b=2; EXPECT_EQ(2, (a*b).to_i());
a=2; b=1; EXPECT_EQ(2, (a*b).to_i());
a=2; b=2; EXPECT_EQ(4, (a*b).to_i());
a=3; b=-2; EXPECT_EQ(-6, (a*b).to_i());
a=-3; b=2; EXPECT_EQ(-6, (a*b).to_i());
a=-3; b=-2; EXPECT_EQ(6, (a*b).to_i());
a=10000; b=10000; EXPECT_EQ(100000000, (a*b).to_i());
a=100000000; b=100000000; EXPECT_EQ("10000000000000000", (a*b).to_s());
a=65535; b=65535; EXPECT_EQ("FFFE0001", (a*b).to_s(16));
a=65536; b=65536; EXPECT_EQ("100000000", (a*b).to_s(16));
}
TEST(BignumTest, comparison) // == != < <= > >=
{
bignum a, b;
a= 0, b= 0;
EXPECT_TRUE(a==b); EXPECT_FALSE(a!=b);
EXPECT_FALSE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_TRUE(a<=b);
a= 1, b= 1;
EXPECT_TRUE(a==b); EXPECT_FALSE(a!=b);
EXPECT_FALSE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_TRUE(a<=b);
a=-1, b=-1;
EXPECT_TRUE(a==b); EXPECT_FALSE(a!=b);
EXPECT_FALSE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_TRUE(a<=b);
a= 1, b=-1;
EXPECT_FALSE(a==b); EXPECT_TRUE(a!=b);
EXPECT_TRUE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_FALSE(a<=b);
a=-1, b= 1;
EXPECT_FALSE(a==b); EXPECT_TRUE(a!=b);
EXPECT_FALSE(a>b); EXPECT_FALSE(a>=b); EXPECT_TRUE(a<b); EXPECT_TRUE(a<=b);
a=1, b=0;
EXPECT_FALSE(a==b); EXPECT_TRUE(a!=b);
EXPECT_TRUE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_FALSE(a<=b);
a=10000000, b=0;
EXPECT_FALSE(a==b); EXPECT_TRUE(a!=b);
EXPECT_TRUE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_FALSE(a<=b);
}
TEST(BignumTest, assign_by_string)
{
bignum num;
num.set(""); EXPECT_EQ(0, num.to_i());
num.set("0"); EXPECT_EQ(0, num.to_i());
num.set("1"); EXPECT_EQ(1, num.to_i());
num.set("-1"); EXPECT_EQ(-1, num.to_i());
num.set("111"); EXPECT_EQ(111, num.to_i());
num.set("111",2); EXPECT_EQ(7, num.to_i());
num.set("-111"); EXPECT_EQ(-111, num.to_i());
num.set("-111",2); EXPECT_EQ(-7, num.to_i());
num.set("12"); EXPECT_EQ(12, num.to_i());
num.set("-12"); EXPECT_EQ(-12, num.to_i());
num.set("12",16); EXPECT_EQ(18, num.to_i());
num.set("-12",16); EXPECT_EQ(-18, num.to_i());
num.set("ZZ",36); EXPECT_EQ(1295, num.to_i());
num.set("-ZZ",36); EXPECT_EQ(-1295, num.to_i());
}
int main(int argc, char** argv)
{
testing::InitGoogleTest(&argc, argv);
return RUN_ALL_TESTS();
}
SRM434 Div1 Medium: HexatridecimalSum
時間切れから６分後に出来たやつでそのままSysTest通った件（無念）
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mset(arr,val) memset(arr,val,sizeof(arr))
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define forr(var,from,to) for(int var=(from);var<=(to);var++)
#define found(s,e) ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())
#define lastc(str) (*((str).end()-1))
class HexatridecimalSum {
int de(int c){
if('0'<=c && c<='9') return c-'0';
else return 10+(c-'A');
}
int en(int c){
if (c<10) return '0'+c;
else return 'A'+(c-10);
}
public:
string maximizeSum(vector<string> numbers, int k) {
vvi m(52);
rep(i,52) m[i].resize(0);
tr(numbers,it){
string ns=*it;
int l=sz(ns);
rep(i,l) m[i].pb(de(ns[l-i-1]));
}
int maxk = 0;
rep(i,52){
if(sz(m[i])>0) maxk=i;
sort(all(m[i]));
}
vvi di(36),id(36);
rep(i,36) {
di[i].resize(maxk+3);
id[i].resize(maxk+3);
rep(j,maxk+3) di[i][j] = id[i][j] = 0;
}
vi sum(maxk+3,0);
for(int i=maxk;i>=0;i--){
tr(m[i],it) {
int c = *it;
di[c][i] += (35-c);
sum[maxk+2-i] += c;
}
}
rep(c,36) {
rep(i,maxk+2){
if(di[c][i] >= 36) {
di[c][i+1] += di[c][i]/36;
di[c][i] %= 36;
}
}
}
rep(c,36){
rep(i,maxk+3){
id[c][maxk+2-i] = di[c][i];
}
}
sort(all(id)); reverse(all(id));
rep(i,k){
rep(j,maxk+3){
sum[j] += id[i][j];
}
}
for(int i=maxk+2;i>0;i--){
if(sum[i] >= 36) {
sum[i-1] += sum[i]/36;
sum[i] %= 36;
}
}
bool left=true;
stringstream ss;
rep(i,maxk+3){
if (left && sum[i]==0) continue;
left=false;
ss << (char)en(sum[i]);
}
return ss.str();
}
};
SRM434 Div1 Easy: FindingSquareInTable
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define found(s,e) ((s).find(e)!=(s).end())
class FindingSquareInTable {
set<int> psqs;
bool psq(int n){ return found(psqs,n) ? true : false; }
public:
int findMaximalSquare(vector<string> table) {
for(int i=0;i<=31622; i++) psqs.insert(i*i);
int maxn = -1;
int h=sz(table), w=sz(table[0]);
vector<vector<int> > t(h);
rep(i,h) { t[i].resize(w); rep(j,w) t[i][j] = table[i][j] - '0'; }
rep(j0,h) rep(i0,w){
for(int sy=-(h-1);sy<=h-1;sy++){
for(int sx=-(w-1);sx<=w-1;sx++){
int j=j0, i=i0;
int n=t[j][i];
if(sx==0 && sy==0) goto jm;
while(true){
i+=sx; j+=sy;
if (i < 0 || w <= i || j < 0 || h <= j) break;
n = n*10 + t[j][i];
if (psq(n)) maxn = max(maxn,n); // ←この１行
}
jm:
if (psq(n)) maxn = max(maxn,n);
}
}
}
return maxn;
}
};
SRM434
| 
02.08.2009
1問submit、1問沈没。0点＞＜
| DIV | level | 問題名 | 競技中 | 後で | System Test | 通過率 | 備考 |
|---|---|---|---|---|---|---|---|
| 1 | 250 | FindingSquareInTable | 撃沈 | ◎ | 0.0 | ||
| 1 | 500 | HexatridecimalSum | 間に合わず | ◎ | |||
| 1 | 1000 | - | - |
250点問題: FindingSquareInTable
- 撃沈
- テーブルの途中で数字列が終わってもいい
- そこが撃沈ポイント
500点問題: HexatridecimalSum
- ６分ほど足りない。
- →６分余分にかけて解いたやつがすんなりSysTestパスした。くやしい
- Bignum実装しておくべし。あるいはJava
1000点問題:
- 開かず。
0点。447/684位... レーティングまた落ちた
1487→1405
順調な下がりっぷり
全く歯が立たないわけではないので引き続き頑張る
SRM356 Div1 Easy: AverageProblem
- 丸め誤差に泣く問題。再投稿×2
class AverageProblem {
public:
int numberOfParticipants(vector<string> marks) {
set<int> s;
tr(marks,it){
vector<string> m_ = split(*it);
tr(m_,jt) s.insert((int)(1000 * atof(jt->c_str()) + 0.5));
}
for(int ps=1;;ps++){
set<int> s_;
double u = 1000.0 / ps;
for(int i=0;i<=ps*10;i++)
s_.insert((int)(u*i+0.0000001));
tr(s,it) if (!found(s_,*it)) goto next;
return ps;
next:;
}
}
};
SRM357 Div1 Easy: Hotel
久しぶりに練習。201.66points。(14.65min) ... 時間かかりすぎ
- DPですね。下(0)から行きます
#define sz(a) int((a).size())
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
class Hotel {
public:
int marketCost(int minCustomers, vector<int> customers, vector<int> cost) {
int n=sz(customers);
int maxc = minCustomers + *max_element(all(customers));
vector<int> v(maxc+1, INT_MAX); v[0] = 0;
rep(mc,minCustomers) {
if (v[mc] == INT_MAX) continue;
rep(i,n){
int c=customers[i], ct=cost[i];
v[mc+c] = min(v[mc+c],v[mc]+ct);
}
}
int ct = INT_MAX;
for(int mc=minCustomers; mc<=maxc; mc++) ct = min(ct,v[mc]);
return ct;
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090208