AtCoder Beginner Contest 250

## [A - Adjacent Squares](https://atcoder.jp/contests/abc250/tasks/abc250_a)

O(1)
問題の内容は、限界値チェックです。
（R,C）が下辺に接触しているなら、下側に隣接するタイルは存在しません。
（R,C）がどの辺に接触しているか判定を行います。

```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, R, C;
    cin >> H >> W >> R >> C;
 
    int ans = 0;
    if(R-1>=1) ans++;
    if(R+1<=H) ans++;
    if(C-1>=1) ans++;
    if(C+1<=W) ans++;

    cout << ans << endl;
    return 0;
}
```

## [B - Enlarged Checker Board](https://atcoder.jp/contests/abc250/tasks/abc250_b)

O(N^4)
4重ループの問題です。
10^2^2は10000なので間に合いますね。

最初のタイルの色は、
・縦が偶数の場合は白スタート
・縦が奇数の場合は黒スタート
です。
横の数字が増えるごとに白黒は切り替わっていきます。
これも奇数、偶数でパターン分けができます。

タイルの縦の位置は、縦のタイルi番目×Aで求めます。
タイルの横の位置は、横のタイルj番目×Bで求めます。
タイルの配置位置は以下のループで決定します。

```C++:C++
    //縦のタイルのループ
    for(int i=0; i<N; i++){
        //横のタイルのループ
        for(int j=0; j<N; j++){
            char m;
            //縦の偶数、奇数をパターン分け
            if(i%2==0){
                //横の偶数、奇数をパターン分け
                if(j%2 == 0) m = '.';
                else m = '#';
            }else{
                if(j%2 == 0) m = '#';
                else m = '.';
            }

            //縦のタイルi個の分だけ、i*Aマスを加算する
            //横のタイルj個の分だけ、j*Bマスを加算する
            for(int a=0; a<A; a++) for(int b=0; b<B; b++){
                graph[i*A + a][j*B + b] = m; 
            }
        }
    }
```

ここまでの考察からコーディングします。

```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; }

char graph[101][101];

int main() {
    int N, A, B;
    cin >> N >> A >> B;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            char m;
            if(i%2==0){
                if(j%2 == 0) m = '.';
                else m = '#';
            }else{
                if(j%2 == 0) m = '#';
                else m = '.';
            }

            for(int a=0; a<A; a++) for(int b=0; b<B; b++){
                graph[i*A + a][j*B + b] = m; 
            }
        }
    }

    for(int i=0; i<N*A; i++){
        for(int j=0; j<N*B; j++){
            cout << graph[i][j];
        }
        cout << endl;
    }
    return 0;
} 
```

## [C - Adjacent Swaps](https://atcoder.jp/contests/abc250/tasks/abc250_c)

単純に全探索を行うとO(N^2)、TLEになります。

O(Q)
ボールの座標を管理する配列、座標にあるボールの番号を管理する配列を用意します。
その２つの配列を同時に更新することで、更新時の計算量をO(１)にすることができます。

```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, Q;
    cin >> N >> Q;
    vector<int> ball_to_pos(N), pos_to_ball(N);

    for(int i=0; i<N; i++){
        ball_to_pos[i] = i;
        pos_to_ball[i] = i;
    }

    for(int i=0; i<Q; i++){
        int q;
        cin >> q;
        int p0 = ball_to_pos[q-1];
        int p1 = p0 + 1;
        if(p1 == N) p1 -= 2;
        int q2 = pos_to_ball[p1];

        swap(ball_to_pos[q-1], ball_to_pos[q2]);
        swap(pos_to_ball[p0], pos_to_ball[p1]);
    }

    for(int i=0; i<N; i++){
        if(i != N-1) cout << pos_to_ball[i] + 1 << ' ';
        else cout << pos_to_ball[i] + 1 << endl;
    }

    return 0;
} 
```