Mist16's Dev Blog

//Backjoon Problem No.2467
//https://www.acmicpc.net/problem/2467

#include <iostream>

using namespace std;

int main()
{
	int N;
	int liquids[100000] = { 0, };
	int idxA, idxB;
	int minValue = 2000000001;
	int answerA, answerB;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> liquids[i];

	idxA = 0;
	idxB = N - 1;

	while (idxA != idxB)
	{
		int temp;
		temp = liquids[idxA] + liquids[idxB];
		if (temp > 0)
		{
			if (temp < minValue)
			{
				minValue = temp;
				answerA = liquids[idxA];
				answerB = liquids[idxB];
			}
			idxB--;
		}
		else if (temp < 0)
		{
			temp = temp * -1;
			if (temp < minValue)
			{
				minValue = temp;
				answerA = liquids[idxA];
				answerB = liquids[idxB];
			}
			idxA++;
		}
		else
		{
			minValue = 0;
			answerA = liquids[idxA];
			answerB = liquids[idxB];
			break;
		}
	}

	cout << answerA << " " << answerB;

	return 0;
}

#include <iostream>
#include <memory.h>
using namespace std;

unsigned int stickerMap[100000][2];
unsigned int maxPoint[100000][3];

int testCases = 0;
int N = 0;

void run()
{
	maxPoint[0][0] = stickerMap[0][0];
	maxPoint[0][1] = stickerMap[0][1];
	maxPoint[0][2] = 0;

	for (int i = 1; i < N; i++)
	{
		//up
		if (maxPoint[i-1][1] > maxPoint[i-1][2])
		{
			maxPoint[i][0] = maxPoint[i - 1][1] + stickerMap[i][0];
		}
		else
			maxPoint[i][0] = maxPoint[i - 1][2] + stickerMap[i][0];
		//down
		if (maxPoint[i - 1][0] > maxPoint[i - 1][2])
		{
			maxPoint[i][1] = maxPoint[i - 1][0] + stickerMap[i][1];
		}
		else
			maxPoint[i][1] = maxPoint[i - 1][2] + stickerMap[i][1];
		//none
		if (maxPoint[i - 1][0] > maxPoint[i - 1][1])
			maxPoint[i][2] = maxPoint[i - 1][0];
		else
			maxPoint[i][2] = maxPoint[i - 1][1];
	}

}

int main()
{
	int numb, temp;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> testCases;

	for (int i = 0; i < testCases; i++)
	{
		unsigned int tempMaxValue = 0;
		//input
		cin >> N;
		for (int j = 0; j < N; j++)
		{
			cin >> stickerMap[j][0];
		}
		for (int j = 0; j < N; j++)
		{
			cin >> stickerMap[j][1];
		}
		//run
		run();

		for(int j = 0; j < 3; j++)
		{
			if (tempMaxValue < maxPoint[N-1][j])
				tempMaxValue = maxPoint[N-1][j];
		}
		cout << tempMaxValue << "\n";
	}
	return 0;
}

//Backjoon Problem No.1036
//https://www.acmicpc.net/problem/1036
#include <iostream>
#include <string>
#include <queue>

using namespace std;

struct decimal36
{
	unsigned int cipher[60] = { 0, };
	int maxDigit = 0;

	bool operator<(const decimal36& t) const
	{
		if (maxDigit != t.maxDigit)
			return maxDigit < t.maxDigit;
		for (int i = maxDigit; i >= 0; i--)
		{
			if (cipher[i] != t.cipher[i])
				return cipher[i] < t.cipher[i];
		}
		return false;
	}
};

priority_queue<decimal36> decQueue;

decimal36 byCipher[36];
decimal36 total;

void arrangeCipher(decimal36 &de)
{
	for (int i = 0; i < 60; i++)
	{
		if (de.cipher[i] > 0)
		{
			de.maxDigit = i;
			if (de.cipher[i] > 35)  //
			{
				de.cipher[i+1] += (int)(de.cipher[i] / 36);
				de.cipher[i] = de.cipher[i] % 36;
			}
		}
	}
}

int charTode36(char c)
{
	int a = (int)c;
	if (a < 60) //0 = 48, 9 = 57;
		return a - 48;
	else //A = 65; Z = 90;
		return a - 55;
}
char cipherTochar(int i)
{
	if (i < 10)
		return (char)(i + 48);
	else
		return (char)(i + 55);
}

int N, K;

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		string temp;
		cin >> temp;
		if (temp.size() == 1 && temp.at(0) == '0')
			continue;
		for (int j = 0; j < temp.size(); j++)
		{
			int target = charTode36(temp.at(j));
			byCipher[target].cipher[temp.size() - j - 1] += 35 - target;
			total.cipher[temp.size() - j - 1] += target;
		}
	}

	for (int i = 0; i < 36; i++)
	{
		arrangeCipher(byCipher[i]);
		decQueue.push(byCipher[i]);
	}
	cin >> K;

	for (int i = 0; i < K; i++)
	{
		decimal36 temp = decQueue.top();
		for (int j = 0; j < 60; j++)
		{
			total.cipher[j] = temp.cipher[j] + total.cipher[j];
		}
		decQueue.pop();
	}
	arrangeCipher(total);

	for (int i = total.maxDigit; i >= 0; i--)
	{
		cout << cipherTochar(total.cipher[i]);
	}

	return 0;

//Backjoon Problem No.1562
//https://www.acmicpc.net/problem/1562
//Mist16, 2022-03-08

#include <iostream>

using namespace std;

unsigned int answerBitmask = 0b1111111111;

unsigned long answerBoard[1024][101][10] = { 0, };

void initialize()
{
	for (int i = 0; i <= 9; i++)
	{
		answerBoard[answerBitmask][0][i] = 1;
	}
}


unsigned long run(int lastDigit, int idx, unsigned int cBitMask)
{
	unsigned long answer = 0;
	if (answerBoard[cBitMask][idx][lastDigit] != 0)
		return answerBoard[cBitMask][idx][lastDigit];
	if (idx == 0)
		return 0;
	//+1
	if (lastDigit < 9)
	{
		answer += run(lastDigit + 1, idx - 1, cBitMask | (1 << (lastDigit + 1)));
	}
	//-1
	if (lastDigit > 0)
	{
		answer += run(lastDigit - 1, idx - 1, cBitMask | (1 << (lastDigit - 1)));
	}	
	answer = answer % 1000000000;
	answerBoard[cBitMask][idx][lastDigit] = answer;
	return answer;
}

int main()
{
	unsigned long long tAnswer = 0;
	unsigned long answer = 0;
	int N;
	cin >> N;

	initialize();

	for (int i = 1; i <= 9; i++)
	{
		answer += run(i, N - 1, (1 << i));
		answer = answer % 1000000000;
	}
	cout << answer;
	return 0;
}

//Backjoon Problem No.1043
//https://www.acmicpc.net/problem/1043
//Mist16, 2022-03-01
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int M = 0, N = 0;

int isAffected[51] = { 0, };

vector<set<int>> vParty;
vector<int> vAffected;

int main()
{
	int numb, temp;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> numb;
	//진실을 아는 사람
	for (int i = 0; i < numb; i++)
	{
		cin >> temp;
		vAffected.push_back(temp);
		isAffected[temp] = 1;
	}
	//파티 입력
	for (int i = 0; i < M; i++)
	{
		set<int> cParty;

		cin >> numb;
		for (int j = 0; j < numb; j++)
		{
			cin >> temp;
			cParty.insert(temp);
		}
		vParty.push_back(cParty);
	}

	while (!vAffected.empty() && !vParty.empty())
	{
		int aPerson = vAffected.back();

		vAffected.pop_back();

		for (auto iter = vParty.begin(); iter != vParty.end(); iter)
		{
			if (iter->find(aPerson) != iter->end())
			{
				for (int i : *iter)
				{
					if (isAffected[i] == 0)
					{
						isAffected[i] = 1;
						vAffected.push_back(i);
					}
				}
				iter = vParty.erase(iter);
			}
			else
				iter++;
		}

	}
	cout << vParty.size();
	return 0;
}

//Backjoon Problem No.10830
//https://www.acmicpc.net/problem/10830
//Mist16, 2022-02-05
#include <iostream>
#include <map>

using namespace std;

unsigned int N = 0;
unsigned long long B = 0;

struct matrix
{
	unsigned int mat[5][5];

	matrix()
	{
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				mat[i][j] = 0;
	}
};

map<unsigned long long, matrix> dices;

matrix matrixMulti(const matrix& a, const matrix& b)
{
	matrix temp;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			unsigned int tempv = 0;
			for (int k = 0; k < N; k++)
			{
				tempv = tempv + (a.mat[i][k] * b.mat[k][j]);
			}
			tempv = tempv % 1000;
			temp.mat[i][j] = tempv;

		}
	}
	return temp;
}

matrix getNSquare(unsigned long long n)
{
	auto iter = dices.find(n);

	if (iter == dices.end())
	{
		unsigned long long a, b;
		a = n / 2;
		b = n - a;
		matrix tempmat;
		tempmat = matrixMulti(getNSquare(a), getNSquare(b));
		dices.insert(pair <unsigned long long, matrix>(n, tempmat));
		return tempmat;

	}
	return iter->second;
}

void run()
{
	matrix result = getNSquare(B);
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << result.mat[i][j] % 1000 << " ";
		}
		cout << endl;
	}
	return;
}

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	matrix temp;
	
	cin >> N >> B;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> temp.mat[i][j];
		}
	}

	dices.clear();
	dices.insert(pair <unsigned long long, matrix>(1, temp));

	run();

	return 0;
}