AtCoder Beginner Contest 237

A - Not Overflow

O(1)
桁数を考えなくて良い言語があります。
そう、pythonならね。

2^31=2147483648です。
long longならできます、本番中は計算が大変なので思考を停止してpythonを使いました。

python

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N = int(input())
    l = -2**31
    r = 2**31

    if l<=N and N<r:
        print("Yes")
    else:
        print("No")

# エントリポイント
if __name__ == '__main__':
    main()

B - Matrix Transposition

O(N)
行列の問題です。
９０度の回転。

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;
    cin >> H >> W;

    vector<vector<int>> A(H, vector<int>(W));
    vector<vector<int>> B(W, vector<int>(H));
    rep(i, H) rep(j, W) cin >> A[i][j];

    rep(i, H) rep(j, W){
        B[j][i] = A[i][j];
    }

    rep(j, W){
        rep(i, H){
            cout << B[j][i] << " ";
        }
        cout << endl;
    }

    return 0;
} 

C - kasaka

O(N)
愚直にシミュレートを行うとTLEになります。
左右のaの数を計測し差分を計算。
足りない分を加算し、左右のaを合わせることで計算量を減らすことができます。

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() {
    string s;
    cin >> s;
   
    int n = s.size();
    int l=0, r=0, a_add=0;

    rep(i, n/2){
        if(s[i] == 'a') l++;
        else break;
    }
    for(int j = n-1; j>=0; j--){
        if(s[j] == 'a') r++;
        else break;
    }
    if(r-l>0){
        a_add = r-l;
    }

    string temp;
    rep(i, a_add){
        temp += 'a';
        n++;
    }
    s = temp + s;

    int low = 0;
    int high = n-1;
    int ok = 1;
    while (high > low){
        if(s[high] != s[low]){
            ok = 0;
            break;
        }
        low++;
        high--;
    }
    if(ok) cout << "Yes" <<endl;
    else cout << "No" <<endl;

    return 0;
} 

D - LR insertion

O(N)
シミュレートするとTLEになります。
最後からシミュレートするとO(N)になります。

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;
    string s;
    cin >> N >> s;

    deque<ll> dqu{N};
    for(int i=N-1; i>=0; i--){
        if(s[i] == 'L'){
            dqu.push_back(i);
        }else{
            dqu.push_front(i);
        }
    }

    for(auto d:dqu){
        cout << d << ' ';
    }

    return 0;
}