AtCoder Beginner Contest 273

## [A - A Recursive Function](https://atcoder.jp/contests/abc273/tasks/abc273_a)

O(N)
再帰処理です。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int dfs(int N){
    if(N==0) return 1;
    return N * dfs(N-1);
}

int main() {
    int N;
    cin >> N;
    cout << dfs(N) << endl;
    return 0;
} 
```

## [B - Broken Rounding](https://atcoder.jp/contests/abc273/tasks/abc273_b)

O(N)
問題文の日本語が難しいです。
0<=i<=N、としてNまで四捨五入しました。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll X, K;
    cin >> X >> K;

    ll cnt=0, r=10, res=0, XX=X, ans=0;
    while(K>cnt){
        if(XX % r > 4 * powl(10,cnt)){
            XX = (XX - XX%r)+r;
        }else{
            XX -= XX%r;
        }
        r*=10;
        cnt++;
        ans = XX;
    }
    cout << ans << endl;

    return 0;
} 
```

## [C - (K+1)-th Largest Number](https://atcoder.jp/contests/abc273/tasks/abc273_c)

O(NlogN)
種類を格納したvectorを、A[i]の値で二分探索します。
二分探索で計測した種類数をmapに格納します。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<int> A(N), AA;
    rep(i, N) cin >> A[i];
    set<int> st;
    rep(i, N) st.insert(A[i]);
    for(auto s:st) AA.push_back(s);
    map<int, int> mp;
    rep(i, N){
        int t = A[i];
        auto itr = upper_bound(AA.begin(), AA.end(), t);
        int r = AA.size() - distance(AA.begin(), itr);
        mp[r]++;
    }
    rep(i, N) cout << mp[i] << endl;
    return 0;
} 
```

## [D - LRUD Instructions](https://atcoder.jp/contests/abc273/tasks/abc273_d)

O(NlogN)
愚直にシミュレーションするとTLEします。

```
map<int, vector<int>>型で、縦の'#',横の'#'をそれぞれ持つと処理できます。
vector<int>に格納された'#'の位置を二分探索します。
難しいのは、'L', 'U'の時です。
例)
..#.#..T
```

L 5の時に8→6にする必要があります。
単純にlower_boundだと8→4になります。
イテレータをデクリメントする必要があります。

```C++:C++
auto itr = lower_bound(it->second.begin(), it->second.end(), cs);
if(itr != mpx[rs].begin()) itr--, dl = (*itr);
```

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    int H, W, rs, cs;
    cin >> H >> W >> rs >> cs;
    int N;
    cin >> N;
    map<int, vector<int>> mpx, mpy;
    rep(i, N){
        int r, c;
        cin >> r >> c;
        mpx[r].push_back(c);
        mpy[c].push_back(r);
    }
    for(auto& m:mpx) sort(m.second.begin(), m.second.end());
    for(auto& m:mpy) sort(m.second.begin(), m.second.end());
 
    int Q;
    cin >> Q;
    char d;
    int l;
    rep(i, Q){
        cin >> d >> l;
        if(d=='L'){
            int dl = 0;
            auto it = mpx.find(rs);
            if(it != mpx.end()){
                auto itr = lower_bound(it->second.begin(), it->second.end(), cs);
                if(itr != mpx[rs].begin()) itr--, dl = (*itr);
            }
            cs = max(cs-l, dl+1);
        }
        if(d=='R'){
            int dl = W+1;
            auto it = mpx.find(rs);
            if(it != mpx.end()){
                auto itr = upper_bound(it->second.begin(), it->second.end(), cs);
                if(itr != mpx[rs].end()) dl = (*itr);
            }
            cs = min(cs+l, dl-1);
        }
        if(d=='U'){
            int dl = 0;
            auto it = mpy.find(cs);
            if(it != mpy.end()){
                auto itr = lower_bound(it->second.begin(), it->second.end(), rs);
                if(itr != mpy[cs].begin()) itr--, dl = (*itr);
            }
            rs = max(rs-l, dl+1);
        }
        if(d=='D'){
            int dl = H+1;
            auto it = mpy.find(cs);
            if(it != mpy.end()){
                auto itr = upper_bound(it->second.begin(), it->second.end(), rs);
                if(itr != mpy[cs].end()) dl = (*itr);
            }
            rs = min(rs+l, dl-1);
        }
        cout << rs << ' ' << cs << endl;
    }
    return 0;
} 
```