앳코더90 - 024 - Select +／- One（★2）

https://atcoder.jp/contests/typical90/tasks/typical90_x

024 - Select +／- One（★2）

 

길이가 N인 두개의 배열 A, B가 있다. 배열 A에서 특정 index의 원소를 선택하여 +1, 또는 -1 하여 배열 B를 K번 이내에 만들 수 있는가?를 판별하는 문제이다.

 

+1 또는 -1 한다는 것은 어떻게든 값을 만들 수 있는 것이고 K번 이내에 가능한지 만 판별하면 되는 것이다. 0번째 원소가 3, 5라고 할때 3을 5로 만들기 위해서는 2번 수행해야한다. 반대인 5를 3으로만드는 것도 2번 수행한다. 즉, abs(v1[0] - v2[0]) 값을 다 더해서 K와 같은지 판별하면 되는 것이다. 하지만, 이때 주의해야될 사항이 있다. 지금 구한 것은 A배열을 B배열로 만드는 최소 횟소이다. 우리가 구하는것은 최소횟수가 아니라 K번 이내에 가능 한지 이다. K번이내에 불가능한 경우는 어떤 경우가 있는지 보면 +1 -1 했을 때는 변화가 0인데 K값을 2번 소모한다. 이동의 최소 횟수와 K값의 차이가 홀수이면 만들기 불가능한 경우의수가 되는 것이다.

 

해당 내용을 코드로 만들면 아래와 같다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>
#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;
using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int N, K;
int tmp;
vi vA;
vi vB;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int val = 0;

	cin >> N >> K;
	vA.resize(N);
	vB.resize(N);

	rep(i, N)
	{
		cin >> vA[i];
	}

	rep(i, N)
	{
		cin >> vB[i];
		val += abs(vA[i] - vB[i]);
	}

	if (K >= val && (K - val) % 2 == 0)
		cout << "Yes";
	else
		cout << "No";

	return 0;
}