KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)

Last Card

$K$개의 카드가 있고 1부터 $N$번호를 가진 사람이 있을 때 $A$번호부터 카드를 주게되면 맨 마지막 카드를 받는 사람의 번호가 무엇인지 찾는 문제이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <numeric>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e11;

int main(){
  fastio
  //freopen("input.txt","r",stdin);
  int n,k,a; cin>>n>>k>>a;
  for(int i=1;i<k;i++) {
    a++; a=a==n+1?1:a;
  }
  cout<<a;
  return 0;
}

KEYENCE building

N명의 사람이 제시한 숫자가 4ab + 3a + 3b 공식에 알맞게 떨어지는지 확인하여 a, b를 찾지 못한 사람의 수를 찾는 문제이다.

$1≤N≤20, 1≤ S_i ≤1000$ 이므로 $O(NS^2)$로 완전탐색으로 해결할 수 있다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <numeric>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e11;

pii foo(int c) {
  pii ret;
  for(int i=1;i<=1000;i++) {
    for(int j=1;j<=1000;j++) {
      if(4*i*j+3*i+3*j==c) {
        ret.first=i, ret.second=j;
        return ret;
      }
    }
  }
  return ret;
}

int main(){
  fastio
  //freopen("input.txt","r",stdin);
  int n; cin>>n;
  int ans=0;
  while(n--) {
    int c; cin>>c;
    pii tmp=foo(c);
    if(!tmp.first || !tmp.second) ans++;
  }
  cout<<ans;
  return 0;
}

ABC conjecture

$N$이 주어졌을 때, $A≤B≤C, ABC≤N$인 $(A, B, C)$ 쌍의 개수를 찾는 문제이다.

먼저, $A$가 1인 경우를 생각해보자.

$BC≤N$이고 $B≤C$이어야 하므로 $B$의 최대는 $\sqrt{B}$ 이다. 이때, $C$의 개수는 $B ≤ C$ 조건으로 인해 $\frac{N}{B} - B + 1$개가 되어야 한다.

이제, A가 가질 수 있는 최대 값은 $N^{\frac{1}{3}}$이다.

따라서, 시간복잡도는 $O(N^{\frac{2}{3}})$이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e11;

int main(){
  fastio
  //freopen("input.txt","r",stdin);
  ll n; cin>>n;
  ll ans=0;
  for(ll a=1;a*a*a<=n;a++) {
    for(ll b=a;b<=sqrt(n/a);b++) {
      ans+=(n/a/b)-b+1; // b<=c
    }
  }
  cout<<ans;
  return 0;
}