プログラミング初心者の勉強日記

情報科学専攻です. 機械学習と競技プログラミングについて日々勉強しています.

MENU

AtCoder Beginner Contest 112に参加しました

競技プログラミング

AtCoder Beginner Contest 112に参加したので記録を残したいと思います.

問題のタイトルは以下のようになっています.

  • A - Programming Education
  • B - Time Limit Exceeded
  • C - Pyramid
  • D - Partition

A - Programming Education

問題の概要

入力が N = 1ならば'Hello World'を出力し、N = 2ならば更に整数の入力A, Bを受け取り、A + Bの結果を出力する.

解法

N = 1のときとN = 2のときで条件分岐してあげます.

最初に整数A, Bを受け取るのではなく、 N = 2のときにのみ入力を受け取るように気をつけます.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    if(N == 1) {
        cout << "Hello World" << endl;
    } else {
        int A, B;
        cin >> A >> B;
        cout << A + B << endl;
    }
}

B - Time Limit Exceeded

問題の概要

N個の経路のなかで、時間T以内に帰宅できる経路のうちコストが最小となる経路のコストを出力する.

ただし、i番目の経路はコストc_iかけて時間t_iで帰宅できる.

解法

全探索します. 時間T以下のt_iに対応するコストc_iの中で最小のものを出力することで目的を果たせます.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, T;
    cin >> N >> T;
    vector<int> c, t;
    rep(i, 0, N) {
        int tmp_c, tmp_t;
        cin >> tmp_c >> tmp_t;
        c.push_back(tmp_c);
        t.push_back(tmp_t);
    }

    int rsl = 1e9;

    rep(i, 0, N) {
        if(t[i] <= T) rsl = min(rsl, c[i]);
    }
    if(rsl == 1e9) cout << "TLE" << endl;
    else cout << rsl << endl;

}

C - Pyramid

問題の概要

ピラミッドには中心座標(C_X, C_Y)と高さHが定まっている. 座標(X, Y)の高度はmax(H - |X - C_x| - |Y - C_Y|, 0)である.

(x_i, y_i)の高度はh_iであるという情報がN個与えられるので、その情報をもとに中心座標と高さを求める.

解法

最初はなんのこっちゃ分からなかったのですが、入力例2のC_X, C_Yが0以上100以下の整数であるとわかっていることに注意せよ.という一文を見て閃きました.

C_XとC_Yが100以下の整数ならそれらに対して全探索しちゃえば良いのでは？と考えました. (制約を見た時点で思いつくべきでしたが、なぜかこの一文を見た時に解法を思いつきました.)

そうすると、残るHをどうするかが問題になってきます. 残るHを定めてしまえば、適当に定めたC_X, C_Y, Hを用いてN個の情報に矛盾しないか一つずつ試していけば良いことになります.

Hの定め方はh_0が0のときとそうでないときで場合分けしました.

  • h_0が0でないとき

    max(H - |X - C_X| - |Y - C_Y|, 0)という定義より、ある中心座標の候補であるC^{\prime}_{X}, C^{\prime}_{Y}を用いて、h_0 = H^{\prime} - |x_0 - C^{\prime}_{X}| - |y_0 - C^{\prime}_Y|が成り立ちます. したがって、H^{\prime} = h_0 + |x_0 - C^{\prime}_X| + |y_0 - C^{\prime}_Y|となります.

    これで、あるC^{\prime}_{X}, C^{\prime}_{Y}に対するH^{\prime}を一つ定めることができました. このH^{\prime}を用いたとき全ての情報に矛盾が生じなかったとき、そのC^{\prime}_{X}, C^{\prime}_Y, H^{\prime}が答えとなります.

  • h_0が0のとき

    h_0が0のときは、H^{\prime} - |x_0 - C^{\prime}_{X}| - |y_0 - C^{\prime}_{Y}| \leq 0となります. したがって、H^{\prime}の値は、1 \leq H^{\prime} \leq |x_0 - C^{\prime}_{X}| + |y_0 - C^{\prime}_{Y}|に絞ることができます. したがってこの範囲の中で情報に矛盾の生じないH^{\prime}が存在すれば、そのC^{\prime}_{X}, C^{\prime}_Y, H^{\prime}が答えとなります.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> x, y, h;
    rep(i, 0, N) {
        int tmp_x, tmp_y, tmp_h;
        cin >> tmp_x >> tmp_y >> tmp_h;
        x.push_back(tmp_x);
        y.push_back(tmp_y);
        h.push_back(tmp_h);
    }

        rep(xi, 0, 101) rep(yi, 0, 101) {
            if(h[0] != 0) {
                int H = h[0] + abs(x[0] - xi) + abs(y[0] - yi);
                bool flag = true;
                rep(i, 0, N) {
                    if(h[i] != max(H - abs(x[i] - xi) - abs(y[i] - yi), 0)) {
                        flag = false;
                        break;
                    }
                }
                if(flag) {
                    cout << xi << " " << yi << " " << H << endl;
                    return 0;
                }
            } else {
                int max_h = abs(x[0] - xi) + abs(y[0] - yi);
                rep(hi, 0, max_h + 1) {
                    bool flag = true;
                    rep(i, 0, N) {
                        if(h[i] != max(hi - abs(x[i] - xi) - abs(y[i] - yi), 0)) {
                            flag = false;
                            break;
                        }
                    }
                    if(flag) {
                        cout << xi << " " << yi << " " << hi << endl;
                    }
                }
            }
        }
}

D - Partition

問題の概要

整数N, Mが与えられる.

\sum_{i = 1}^{N} a_{i} = Mとなる整数からなる長さNの数列aにおいて、a_1, a_2, \cdots, a_Nの最大公約数の取り得る最大値を求める.

解法

整数問題苦手ですね... またしても時間内に解けませんでした.

例えば数列aの最大公約数をdとしたとき、a_i, (i = 1, 2, \cdots, N)はdの倍数となります. したがって、それらの和であるMもdの倍数となります.

Mがdの倍数、つまりdはMの約数であることに注意すると、dの候補を全部列挙することができます. (約数を列挙するライブラリを持っていると便利です.)

a_1, a_2, \cdots, a_N \geq dであることに注意すると、M \geq N \times dとなります.

M \geq N \times dを満たすdを用いて、a_1 = a_2 = \cdots = a_{N - 1} = d、a_N = M - (N - 1) \times dとすることで、最大公約数がdとなる数列aを作ることができます.

したがって、Mの約数でありかつ、M \geq N \times dを満たすdの中の最大値を結果として出力してあげれば良いことになります.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

vector<ll> divisor(ll n) {
    vector<ll> res;
    for(int i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            res.push_back(i);
            if(i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;

    vector<ll> v = divisor(M);
    ll max_v = 1;

    rep(i, 0, v.size()) {
        if(v[i] * N <= M) max_v = max(max_v, v[i]);
    }
    
    cout << max_v << endl;
}

感想

C問題に関しては制約を見逃すことが多く、4WA1ACという結果でした...

ここら辺の正確性をどうにかすればもう少し良いレートになれるかなと感じています.

また、整数問題もリアルタイムで解けることが少ないので、練習していく必要がありますね...