0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 436

Posted at

A - o-padding

問題文

O(N)
for文の問題です。
mをs.size()とした時に、

n - m

だけ先頭にoを追加しましょう。

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

    int m = s.size();
    for(int i=0; i<n-m; i++){
        s = 'o' + s;
    }
    cout << s << endl;

    return 0;
}

上が実際のコンテストのコードです。
しかし、n - mが入らなかったなと思います。

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

    while(s.size() < n){
        s = 'o' + s;
    }
    cout << s << endl;
  
    return 0;
}

B - Magic Square

問題文

O(N)
マスの座標が(0, 2 * N − 1)から初めて、左下に移動しながらk+1の値を書き込みしていきます。
問題文の通りにシミュレーションしましょう。

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<vector<int>> graph(n, vector<int>(n, 0));

    int r = 0;
    int c = (n-1) / 2;
    int k = 1;
    graph[r][c] = k;

    while(k<n*n){
        int rr = (r-1) % n;
        int cc = (c+1) % n;
        if(rr<0) rr += n;

        if(graph[rr][cc] == 0){
            graph[rr][cc] = k + 1;
        }else{
            rr = (r+1) % n;
            cc = c;
            graph[rr][cc] = k + 1;
        }

        r = rr;
        c = cc;
        k++;
    }

    rep(i, n){
        rep(j, n){
            cout << graph[i][j];
            if(j < n-1) cout << ' ';
        }
        cout << endl;
    }

    return 0;
}

上記は実際のコンテストのコードですが、

C++
        if(graph[rr][cc] == 0){
            graph[rr][cc] = k + 1;
        }else{
            rr = (r+1) % n;
            cc = c;
            graph[rr][cc] = k + 1;
        }

が良くなかったです。

C++
    while(k<n*n){
        int rr = (r-1) % n;
        int cc = (c+1) % n;
        if(rr<0) rr += n;

        if(graph[rr][cc] != 0){
            rr = (r+1) % n;
            cc = c;
        }

        graph[rr][cc] = k + 1;
        r = rr;
        c = cc;
        k++;
    }

と書くことで余分なコードを減らせます。

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<vector<int>> graph(n, vector<int>(n, 0));

    int r = 0;
    int c = (n-1) / 2;
    int k = 1;
    graph[r][c] = k;

    while(k<n*n){
        int rr = (r-1) % n;
        int cc = (c+1) % n;
        if(rr<0) rr += n;

        if(graph[rr][cc] != 0){
            rr = (r+1) % n;
            cc = c;
        }

        graph[rr][cc] = k + 1;
        r = rr;
        c = cc;
        k++;
    }

    rep(i, n){
        rep(j, n){
            cout << graph[i][j];
            if(j < n-1) cout << ' ';
        }
        cout << endl;
    }

    return 0;
}

綺麗なコードになりました。

C - 2x2 Placing

問題文

O(M)
誓約がN<10^9のために配列を用意できません。
このような時はハッシュを使用します。
データ構造の問題です。

map<int, map<int, int>> mp;

を使用すると解くことができます。

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, m;
    cin >> n >> m;

    int ans = 0;
    map<int, map<int, int>> mp;
    for(int i=0; i<m; i++){
        int r, c;
        cin >> r >> c;
        r--; c--;
        if(mp.find(r) != mp.end()){
            if(mp[r].find(c) != mp[r].end() || mp[r].find(c+1) != mp[r].end()){
                continue;
            }
        }
        if(mp.find(r+1) != mp.end()){
            if(mp[r+1].find(c) != mp[r+1].end() || mp[r+1].find(c+1) != mp[r+1].end()){
                continue;
            }
        }
        mp[r][c]++;
        mp[r+1][c]++;
        mp[r][c+1]++;
        mp[r+1][c+1]++;
        ans++;
    }
    cout << ans << endl;

    return 0;
}

上記は実際のコンテストのコードですが、

C++
        if(mp.find(r) != mp.end()){
            if(mp[r].find(c) != mp[r].end() || mp[r].find(c+1) != mp[r].end()){
                continue;
            }
        }
        if(mp.find(r+1) != mp.end()){
            if(mp[r+1].find(c) != mp[r+1].end() || mp[r+1].find(c+1) != mp[r+1].end()){
                continue;
            }
        }

が良くなかったです。
綺麗なコードに修正しましょう。

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, m;
    cin >> n >> m;

    int ans = 0;
    map<int, map<int, int>> mp;
    for(int i=0; i<m; i++){
        int r, c;
        cin >> r >> c;
        r--; c--;
        if(mp[r][c] > 0 || mp[r+1][c] > 0 || mp[r][c+1] > 0 || mp[r+1][c+1] > 0) continue;

        mp[r][c]++;
        mp[r+1][c]++;
        mp[r][c+1]++;
        mp[r+1][c+1]++;
        ans++;
    }
    cout << ans << endl;

    return 0;
}

D - Teleport Maze

問題文

O(H*W)
BFSの問題です。
a-zのワープは一度だけしか使用しません。
ワープ後はmapのフラグを開放してワープしないようにしましょう。

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 INF = 1e9+7;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    map<char, vector<P>> mp;
    rep(i, h){
        rep(j, w){
            if(s[i][j] != '.' && s[i][j] != '#'){
                mp[s[i][j]].push_back({i, j});
            }
        }
    }

    vector<vector<int>> graph(h, vector<int>(w, 0));
    queue<P> que;
    que.push({0, 0});
    graph[0][0] = 0;

    while(que.size()){
        auto [y, x] = que.front();
        que.pop();

        for(int i=0; i<4; i++){
            int yy = y + dy[i];
            int xx = x + dx[i];

            if(yy < 0 || h <= yy || xx < 0 || w <= xx) continue;
            if(s[yy][xx] == '#') continue;
            if(graph[yy][xx] != 0) continue;

            graph[yy][xx] = graph[y][x] + 1;
            que.push({yy, xx});
        }

        if(s[y][x] != '.' && s[y][x] != '#'){
            vector<P> v = mp[s[y][x]];

            for(int j=0; j<v.size(); j++){
                if(v[j].first == y && v[j].second == x) continue;
                if(graph[v[j].first][v[j].second] != 0) continue;
                graph[v[j].first][v[j].second] = graph[y][x] + 1;
                que.push(v[j]);
            }

            mp.erase(s[y][x]);
        }
    }

    if(graph[h-1][w-1] == 0) cout << -1 << endl;
    else cout << graph[h-1][w-1] << endl;

    return 0;
}

上記は実際のコンテストのコードですが、よく見るとmapを使用する必要がなく改善の余地があります。

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 INF = 1e9+7;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    vector<vector<P>> c(26);
    rep(i, h){
        rep(j, w){
            if(s[i][j] != '.' && s[i][j] != '#'){
                int k = s[i][j] - 'a';
                c[k].push_back({i, j});
            }
        }
    }

    vector<vector<int>> graph(h, vector<int>(w, INF));
    vector<bool> used(26);
    queue<P> que;
    que.push({0, 0});
    graph[0][0] = 0;

    while(que.size()){
        auto [y, x] = que.front();
        que.pop();

        for(int i=0; i<4; i++){
            int yy = y + dy[i];
            int xx = x + dx[i];

            if(yy < 0 || h <= yy || xx < 0 || w <= xx) continue;
            if(s[yy][xx] == '#') continue;
            if(graph[yy][xx] != INF) continue;

            graph[yy][xx] = graph[y][x] + 1;
            que.push({yy, xx});
        }

        if(s[y][x] != '.' && s[y][x] != '#'){
            int k = s[y][x] - 'a';

            if(used[k]) continue;
            used[k] = true;

            for(auto cc:c[k]){
                if(cc.first == y && cc.second == x) continue;
                if(graph[cc.first][cc.second] != INF) continue;
                graph[cc.first][cc.second] = graph[y][x] + 1;
                que.push({cc.first, cc.second});
            }
        }
    }

    cout << (graph[h-1][w-1] == INF ? -1 : graph[h-1][w-1]) << endl;

    return 0;
}

問題文

C++
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?