Codeforces Round 674 (Div.3)

A. Floor Number

먼저, $n$≤2이라면, 답은 1이다.

나머지는 $\frac{n-3}{x}+2$를 만족한다. (왜냐하면 3층 이후부터 $x$만큼 차지하기 때문)

#include <iostream>
#define endl '\n'
using namespace std;

void solve() {
  int n,x;
  cin>>n>>x;
  if(n<=2) {
    cout<<1<<endl;
    return;
  }
  cout<<(n-3)/x+2<<endl;
  return;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt", "r", stdin);
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

B. Symmetric Matrix

먼저, $m$이 홀수일 경우 매트릭스를 만들 수 없다.

또한, 타일의 왼쪽 상단과 오른쪽 하단의 값은 중요하지 않는 것을 알 수 있다. (왜냐하면 타일은 대칭이어야 하기 때문)

그래서 오른쪽 상단과 왼쪽 하단의 타일이 같은 경우만 체크하는 것이 필요하다.

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

void solve() {
  int n, m;
  cin>>n>>m;
  int mat[100][2][2];
  for(int i=0;i<n;i++) {
    for(int a=0;a<2;a++) {
      for(int b=0;b<2;b++) {
        cin>>mat[i][a][b];
      }
    }
  }
  bool ok=false;
  for(int i=0;i<n;i++) { // 가능한 경우가 한 번이라도 있다면 ok는 true
    ok|=mat[i][0][1]==mat[i][1][0];
  }
  ok&=(m%2==0); // m이 홀수일때 불가능
  if(ok) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return;
}

int main() {
  ios::sync_with_stdio(0);
  //freopen("input.txt","r",stdin);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

---

C. Increase and Copy

문제에 주어진 두 가지 연산을 이용하여 배열의 합이 $n$이상이 되게 하는 최소 연산 횟수를 구하는 문제이다.

직관적으로, 가장 먼저 해야할 것처럼 보이는 것은 increase $a$ by 1연산인 것같다. 왜냐하면 결과값을 최대한 크게하기 위해 increase연산을 우선적으로 하고 copy연산을 할 것이다.

이때, $n$의 범위가 $1 ≤ n ≤ 10^9$이기 때문에 $2 \times 10^5$이면 원하는 $n$을 충분히 구할 수 있다.

• 두 연산(increase, copy)이 존재하기 때문에 $n$을 대략적인 제곱근 값인 $10^5$의 두 배면 충분하다.
• 즉, $O(\sqrt{n})$이면 가능하다.

하나의 element를 증가한 수 $x$가 있다고 가정하면, $x-1$만큼 increase를 진행해야하고(x ≤ $\sqrt{n}$) $\frac{n-x}{x}$만큼 copy를 진행해야 한다.

따라서, $1 ≤ x ≤ min(10^5,n)$ 범위 내에서 $(x-1)+(\frac{n-x}{x})$의 최솟값을 찾으면 된다.

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

typedef long long ll;

void solve() {
  int n;
  cin>>n;
  int ans=(int)1e9;
  for(int x=1;x<=100000 && x<=n;x++) { // min(10^5,n)만큼 i탐색
    // for(int x=1;x*x<=n;x++) 도 가능
    ans=min(ans,(x-1)+((n-1/x)));
  }
  cout<<ans<<endl;
}

int main() {
  ios::sync_with_stdio(0);
  //freopen("input.txt","r",stdin);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

---

D. Non-zero Segments

editorial을 봐도 이해가 잘 안가는 문제다.

배열 $a$에 대해 어떠한 subsegments에 대해서도 0이 되게 하지 않는 수를 찾는 문제이다.

먼저, $p_i$를 처음부터 $i$번째까지의 합이라 하자.

구간 $[l;r]$에서의 누적합이 0이라면, $p_r-p_{l-1}$이 0이고 또는 $p_{l-1}=p_r$이다.

왼쪽에서 오른쪽으로 원소들을 돌면서 모든 누적합들을 set에 저장한다.

만약, 현재 누적합이 set에 이미 저장되어 있다면, 합이 0이되는 누적합이 존재하는 것을 알 수 있다.

• $a+b+c = b+c+d$ 라면, $b+c$는 0임을 알 수 있다.

현재 원소를 기준으로 왼쪽의 모든 누적합보다 크게 되도록 현재 원소 앞에 큰 숫자를 삽입한다. 이제 왼쪽의 모든 누적합 set들을 지우고 위 과정을 다시 반복한다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define endl '\n'
using namespace std;

typedef long long ll;

void solve() {
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  set<int> d;
  d.insert(0);
  int cur=0;
  int ans=0;
  for(int i=0;i<n;i++) {
    cur+=a[i];
    if(d.find(cur)!=d.end()) {
      ans+=1;
      d.clear();
      d.insert(0);
      cur=a[i];
    }
    d.insert(cur);
  }
  cout<<ans<<endl;
  return;
}

int main() {
  ios::sync_with_stdio(0);
  //freopen("input.txt","r",stdin);
  solve();
  return 0;
}