AtCoder Beginner Contest 250

A. Adjacent Squares

(H, W) 크기의 행렬이 주어졌을 때 위치 (R, C)에서 인접한 원소의 수를 출력하는 문제이다.
H와 W가 1인 경우를 예외처리해주면 쉽게 풀 수 있다.

#include <bits/stdc++.h>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9+1;
 
int main() {
  fastio
  //freopen("input.txt","r",stdin);
  int h,w; cin>>h>>w;
  int r,c; cin>>r>>c;
  int ans=4;
  if(h==1) ans-=2;
  if(w==1) ans-=2;
  if(h>1 && (r==1 || r==h)) ans--;
  if(w>1 && (c==1 || c==w)) ans--;
  cout<<ans;
  return 0;
}

B. Enlarged Checker Board

B번 ‘.’출력하고 B번 ‘#’출력하면서 전체 길이 $N \times B$를 $N \times A$번 출력하면 된다.
단, A번 마다 먼저 출력하는 ‘.’와 ‘#’의 순서가 바뀐다.
테스트케이스를 보면 쉽게 이해할 수 있다.

#include <bits/stdc++.h>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9+1;

void foo(int n, int b, int flag) {
  bool f=0;
  if(!flag) {
    for(int i=0;i<n*b;i++) {
      if(i%b==0) f^=1;
      if(f) cout<<".";
      else cout<<"#";
    }
  }
  else {
    for(int i=0;i<n*b;i++) {
      if(i%b==0) f^=1;
      if(f) cout<<"#";
      else cout<<".";
    }
  }
}

int main() {
  fastio
  //freopen("input.txt","r",stdin);
  int n,a,b; cin>>n>>a>>b;
  bool f=0;
  for(int i=0;i<n*a;i++) {
    if(i%a==0) f^=1;
    if(!f) foo(n,b,1);
    else foo(n,b,0);
    cout<<endl;
  }
  return 0;
}

C. Adjacent Swaps

$2 ≤ N ≤ 2 \times 10^5$ 범위를 가진 N이 주어졌을 때, 1부터 N까지 적혀있는 공이 일렬로 정렬되어 있다.
$x_i$인 쿼리가 입력될 때 해당 숫자가 적혀있는 공의 위치와 오른쪽에 있는 공의 위치를 교환한다. 가장 오른쪽에 있는 공의 경우 왼쪽 공과 바꿔준다.
$1 ≤ Q ≤ 2 \times 10^5$ 인 쿼리가 들어오면서 시간 복잡도 $O(Q)$에 문제를 해결해야 한다.
숫자가 적혀있는 공의 위치를 저장하는 배열(v2p)과 어떤 위치에 있는 공의 번호를 저장하는 배열(p2v)을 두어 $O(1)$의 시간복잡도로 두 공의 위치를 찾을 수 있다.

#include <bits/stdc++.h>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9+1;

int main() {
  fastio
  //freopen("input.txt","r",stdin);
  int n,q; cin>>n>>q;
  map<int,int> v2p,p2v; // idx->lo, lo->idx
  for(int i=1;i<=n;i++) v2p[i]=i, p2v[i]=i;
  while(q--) {
    int x,y; cin>>x;
    if(v2p[x]==n) y=p2v[n-1];
    else y=p2v[v2p[x]+1];
    swap(p2v[v2p[x]],p2v[v2p[y]]);
    swap(v2p[x],v2p[y]);
  }
  for(auto it : p2v) cout<<it.second<<' ';
  return 0;
}

D. 250-like Number

$1 ≤ N ≤ 10^{18}$인 $N$이 주어졌을 때 아래 조건을 만족하는 $k$의 개수를 출력하는 문제이다.

• $k = p \times q^3$, ($p < q$ 를 만족하는 소수 $p$, $q$)
• $k ≤ N$ 조건에서 $p \times q^3 ≤ N \rightarrow q^3 ≤ N/p$을 알 수 있다.

따라서, $p^3 < X ≤ N/p$인 $X$의 개수를 upperbound로 세어주면 된다.

#include <bits/stdc++.h>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9+1;

int main() {
  fastio
  //freopen("input.txt","r",stdin);
  ll n; cin>>n;
  // k<=n -> p * q^3 <= n -> q^3 <= (n/p) -> upperbound?
  vector<int> temp(1e6+1,1);
  vector<ll> mul;
  set<ll> prime;
  for(ll i=2;i<=1e6;i++) {
    if(temp[i]) {
      prime.insert(i);
      if(i*i*i<n) mul.push_back(i*i*i);
      for(ll j=i+i;j<=1e6;j+=i) temp[j]=0;
    }
  }
  sort(mul.begin(),mul.end());
  ll ans=0;
  for(auto i : prime) {
    if(i>=n) break;
      ll lim=n/i;
      ll uidx=upper_bound(mul.begin(),mul.end(),lim)-mul.begin();
      ll lidx=upper_bound(mul.begin(),mul.end(),i*i*i)-mul.begin();
      if(uidx>lidx) ans+=uidx-lidx;
  }
  cout<<ans;
  return 0;
}