AtCoder Beginner Contest 233

A. 10yen Stamp

10엔 스탬프를 모아서 현재 $X$에서 목표치 $Y$를 달성할 때까지 몇 번을 봉투에 넣어야 하는지 계산하는 문제이다.
$X$가 $Y$보다 큰 경우 0을 출력해주는 예외처리만 해주면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#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 int INF = 1e9;

int main() {
  fastio
  //freopen("input.txt", "r", stdin);
  int a,b; cin>>a>>b;
  if(a>=b) {
    cout<<0;
    return 0;
  }
  cout<<ceil(double(b-a)/10);
  return 0;
}

B. A Reverse

문자열 $S$에서 $L$번째부터 $R$번째까지 부분문자열을 뒤집어 출력하는 구현 문제이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#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 int INF = 1e9;

int main() {
  fastio
  //freopen("input.txt", "r", stdin);
  int a,b; cin>>a>>b;
  string s; cin>>s;
  string t=s.substr(a-1,b-a+1);
  reverse(t.begin(),t.end());
  cout<<s.substr(0,a-1)<<t<<s.substr(b)<<endl;
  return 0;
}

C. Product

$i$번째 가방에 $L_i$개의 공이 있고 각 공은 $a_{ij}$의 숫자가 적혀있다.
모든 가방에서 공을 하나씩 선택하고 각 공에 적힌 수의 곱이 $X$인 경우의 수를 계산하는 문제이다.
중요한 정보로 $\sum_{i}^N L_i = 10^5$ 이라는 조건이 문제에 있다. 그래서 dp처럼 접근하는 것도 가능할 것 같아서 다음과 같이 접근했다.
map을 사용해서 위에서부터 어떤 공을 선택했을 때 이전 값에 나눈 몫을 다음 값으로 저장하는 방법을 사용했다.
current는 위에서 선택한 수를 나누어 현재 필요한 수를 의미하고 ball은 $i$번째 가방에서 꺼낸 어떤 공에 적힌 수를 의미한다.
그렇다면 current를 ball로 나누어 떨어질 때 m[i][current/ball] += m[i-1][current]와 같은 식을 사용할 수 있게된다.
나중에 editorial을 보니까 dfs로 접근하여 문제를 해결하고 있다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#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 int INF = 1e9;

int main() {
  fastio
  //freopen("input.txt", "r", stdin);
  ll n,x; cin>>n>>x;
  vector<ll> bag[100001];
  for(ll i=0;i<n;i++) {
    ll l; cin>>l;
    while(l--) {
      ll a; cin>>a;
      bag[i].push_back(a);
    }
  }
  map<ll,int> m[100001];
  for(int i=0;i<bag[0].size();i++) {
    if(x%bag[0][i]==0) m[0][x/bag[0][i]]++;
  }
  for(int i=1;i<n;i++) {
    for(auto it : m[i-1]) {
      for(int j=0;j<bag[i].size();j++) {
        if(it.first>=bag[i][j] && it.first%bag[i][j]==0) {
          m[i][it.first/bag[i][j]]+=m[i-1][it.first];
        }
      }
    }
  }
  cout<<m[n-1][1]<<endl;
  return 0;
}

D. Count Interval

어떤 수열 $A$가 주어졌을 때, 연속된 구간의 부분합이 $K$가 되는 경우를 모두 계산하는 문제이다.
수열의 길이가 $2 \times 10^5$이므로 $O(N)$에 문제를 해결해야 한다.
어떤 구간합을 구하기 위해서는 $K = prefix[i] - prefix[j]$ 를 찾아야 한다. 이걸 다시 바꾸면 $prefix[i]$와 $prefix[i] - K$가 있는지 확인하면 된다.
보통 누적합을 사용해서 문제를 풀 수 있는데 $O(1)$의 접근을 위해 map을 사용하려고 한다.
2중 for문으로 $1≤i≤N, 1≤j≤i$를 찾으려고 하면 TLE이므로 map을 사용하여 2중 for문 결과와 같게 할 수 있다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#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 int INF = 1e9;

int main() {
  fastio
  //freopen("input.txt", "r", stdin);
  ll n,k; cin>>n>>k;
  vector<ll> a(n), prefix(n+1);
  for(auto &it : a) cin>>it;
  for(int i=0;i<n;i++) prefix[i+1]=prefix[i]+a[i];
  map<ll,ll> m;
  ll ans=0;
  for(ll i=1;i<=n;i++) {
    m[prefix[i-1]]++;
    ans+=m[prefix[i]-k];
  }
  cout<<ans;
  return 0;
}