백준 12966 - 턴 게임 2

https://www.acmicpc.net/problem/12966

 

 

이 포스트는 12934 - 턴 게임으로부터 얻을 수 있는 통찰을 포함하여 설명하도록 한다.

등차수열로의 전환과 등차수열의 합

$i$턴에 이긴 사람은 $2 \times i - 1$ 점으로, 이는 모두 홀수이다.

 

초항을 $a$, 공차를 $d$인 등차수열로 표현할 때, 등차수열의 합은 $S_{n} = \frac{n}{2}(2a + (n - 1)d)$이고,

$a = 1, d = 2$이므로 $S_{n} = \frac{n}{2}(2 \times 1 + (n - 1) \times 2)$ = $n^{2}$이다.

 

따라서, $x + y$는 제곱수가 되어야 한다. $x + y$가 제곱수가 아니라면, 나올 수 없는 경우니 답은 $-1$이다.

문제를 $k$ 찾기로 전환하기

윤호가 $k$번 이긴다고 할 때, $i$를 각각 이긴 턴의 원소라고 하면 윤호가 이긴 턴의 집합 $S$에서 $i \in S$ 관계를 갖게 된다.

 

그러면

 

$$x = \sum_{i \in S}(2i - 1) = 2 \sum_{i \in S}i - k$$

 

로 나타낼 수 있다.

 

따라서,

$$Z = \frac{x + k}{2} = \sum_{i \in S}i$$

 

로 식을 정리할 수 있고, 식을 만족하는 $min(k)$를 찾는 문제로 전환할 수 있다.

$Z$가 가능한 부등식 찾기

그런데, $k$개의 수를 뽑는다고 하면 여기서 나타날 수 있는 합의 최소와 최대가 있다.

합의 최솟값

1부터 $k$까지의 합을 구한다면 $\frac{k(1 + k)}{2}$로, $k$개의 수를 더한 합의 최소가 된다.

합의 최댓값

$n$부터 1씩 감소하여 연속된 $k$개의 정수의 합을 구한다면 $nk - \frac{(k - 1)(1 + (k - 1))}{2} = \frac{k(2n - k + 1)}{2}$가 합의 최대가 된다.

 

따라서, $Z$가 가능한 합이 되려면 다음 부등식을 만족해야 한다.

 

$$ \frac{k(1 + k)}{2} \leq Z \leq \frac{k(2n - k + 1)}{2} $$

 

1부터 $n$까지 모든 $k$에 대해, $x$와 $k$의 패리티가 동일하며, 위 부등식을 만족하는 $min(k)$ 혹은 -1을 출력하면 된다.

 

전체 코드 - CPP

#pragma GCC target("avx,avx2,fma,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
using pii = pair<int, int>;
using ll = int_fast64_t;
 
ll is_square(ll val)
{
  ll lo = 0, hi = 1 + sqrt(val);
 
  while (lo <= hi)
  {
    ll mid = lo + (hi - lo) / 2;
    if (mid * mid == val) return mid;
 
    if (mid * mid < val)
    {
      lo = mid + 1;
    }
    else
    {
      hi = mid - 1;
    }
  }
  return -1;
}
 
void solve()
{
  ll a, b;
  cin >> a >> b;
 
  ll sum = a + b;
 
  auto n = is_square(sum);
 
  if (n == -1)
  {
    cout << -1;
    return;
  }
 
  if (a == 0)
  {
    cout << 0;
    return;
  }
 
  for (int i = 1; i <= n; i++)
  {
    if ((i & 1) != (a & 1))
    {
      continue;
    }
 
    ll t = (a + i) / 2;
    ll l_val = (ll)i * (i + 1) / 2;
    ll r_val = (ll)i * (2 * n + 1 - i) / 2;
 
    if (l_val <= t and t <= r_val)
    {
      cout << i;
      return;
    }
  }
 
  cout << -1;
}
 
int main()
{
#ifdef LOCAL
//  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
 
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}