ABC105 C問題+D問題

C問題 (-2)進数

C - Base -2 Number

10進数を2進数に変換する方法(素因数分解)の流れで解く。
ただし、(-2)で割らないといけないため、(-2)で割り切れない場合、
1. もともとの数が負の数の場合、次に割る数を+1補正する
例) (-9) ÷ (-2) = 5 あまり 1 （ (-9)÷(-2)は本来4だが、4にするとあまりの数が-1になってしまうので、あまりを正の数になるように補正する)
2. もともとの数が正の数の場合は次に割る数の補正は行わない。
例 9 ÷ (-2) = (-4) あまり 1

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>

#define DEBUG 0

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)

using namespace std;

string calc(lli num){
	string str="";

	while(num!=0){
		if(DEBUG)cout<<"num="<<num<<endl;
		lli flag=0;
		if(num < 0){
			if(num%2==0){
				num /= (-2);
			}
			else{
				flag = 1;
				num /= (-2);
				num += 1;
			}
		}
		else{
			flag = num % 2;
			num /= (-2);
		}
		if(flag){
			str = "1"+str;
		}
		else{
			str = "0"+str;
		}
	}
	if(str==""){
		str = "0";
	}
	return str;
}


int main(){

	lli num;
	cin>>num;

	cout<<calc(num)<<endl;

	return 0;
}

D問題

D - Candy Distribution

この問題は自力では解けなかった。

基本的には解説通り実装する。
B mod M の個数がx個数のとき、加算スべき数は x(x-1)/2であることと、
(i,r)=(0,0)の時のmod M を予め加算しておくことに気をつける。

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>

#define DEBUG 0

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)

using namespace std;

int main(){

	lli n,m;
	cin>>n>>m;
	vector<lli> a;
	map<lli,lli> b;
	lli sum = 0;
	b[0]++;
	for(lli i=0;i<n;i++){
		lli tmp;
		cin>>tmp;
		a.push_back(tmp);
		sum += tmp;

		b[sum%m]++;
	}

	lli ans = 0;

	for(auto itr = b.begin();itr != b.end(); itr++){
		lli cnt = itr->second;
		ans += ((cnt -1)*(cnt)/2);
	}

	cout<<ans<<endl;

	return 0;
}