AtCoder Beginner Contest 232

##A - QQ solver

O(1)
0文字目と2文字目をint型に変換する。
変換した整数を掛け算する。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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 a = s[0] - '0';
    int b = s[2] - '0';
 
    cout << a * b << endl;
 
    return 0;
}

##B - Caesar Cipher

O(25*N)
s==tか判定。
異なるならばsの文字列の文字に対して、次のアルファベットの文字へ変換する。
'a'はint型で97、'z'はint型で122。
122を超えた場合は97の'a'にする。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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, t;
    cin >> s >> t;
    int N = s.size();
    rep(i, 26){
        if(s == t){
            cout << "Yes" << endl;
            return 0;
        }
        rep(j, N){
            s[j]++;
            if((int)s[j]>122) s[j] = 'a';
        }
    }
    cout << "No" << endl;
 
    return 0;
}

##C - Graph Isomorphism

O(N!)
N<=8なので順列全探索ができます。
問題文にヒントがあります。
「P は (1,…,N) を並べ替えて得られる。
任意の 1 以上 N 以下の整数 i,j に対し、以下が成り立つ。
高橋君のおもちゃにおいてボール i,j がひもで繋がれていることと、青木君のおもちゃにおいてボール Pi,Pjがひもで繋がれていることは同値である。」

なぜ形が同じになるのかは、私自身はわかっていません。
ルールをそのままプログラミングしました。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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 graph2[8][8];
 
int main() {
    int N, M;
    cin >> N >> M;
 
    vector<int> order(N);
    rep(i, N) order[i] = i;
 
    vector<P> graph1;
    rep(i, M){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph1.push_back(P(a,b));
    }
    rep(i, M){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph2[a][b]=1;
        graph2[b][a]=1;
    }
 
    int res=0;
    do{
        bool ok=true;
        for(int i=0; i<M; i++){
            int from = graph1[i].first;
            int to = graph1[i].second;
 
            if(graph2[order[from]][order[to]] != 1) ok=false;
        }
        if(ok) res++;
    }while(next_permutation(order.begin(), order.end()));
 
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;
 
    return 0;
}

##D - Weak Takahashi

O(N)
BFSです。
（１、１）をスタート地点にします。
H＊Wと同じサイズの配列Dを用意して、マス毎に歩数をカウントできるようにします。
キューに進めるマスを追加して、配列Dには現在の歩数＋１を代入します。
歩数の最大値が答えになります。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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 dist[101][101];
 
int dx[2] = {1, 0};
int dy[2] = {0, 1};
 
int main() {
    int H, W;
    cin >> H >> W;
 
    rep(y, H){
        rep(x, W){
            cin >> graph[y][x];
        }
    }
 
    queue<P> que;
    que.push(P(0,0));
    dist[0][0] = 1;
 
    int res=1;
    while(que.size()){
        P p = que.front();
        que.pop();
        for(int i=0; i<2; i++){
            int ny = p.first + dy[i];
            int nx = p.second + dx[i];
 
            if(W<=nx || H<=ny) continue;
 
            if(graph[ny][nx] == '.' && dist[ny][nx] == 0){
                dist[ny][nx] = dist[p.first][p.second] + 1;
                que.push(P(ny, nx));
 
                res = max(res, dist[ny][nx]);
            }
        }
    }
    cout << res << endl;
 
    return 0;
}