AtCoder Beginner Contest 118

結果

　41分50秒(0WA)で全完、82位だった。全部解き切るまで順位表を一切見ていなくて、D問題には結構時間がかかったのでダメかなーと思ったら結構良かった。0WAというのも気持ちいいね。

A問題

　一瞬どっちがどっちの約数かみたいので混乱するなど。if文書き始めたけど結局三項演算子に書き換えるのもあって1分以上かかってしまった。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll A, B;
    cin >> A >> B;
    cout << (B % A == 0 ? A + B : B - A) << endl;
}

B問題

　各食べ物ごとに好きと言っている人の数を数えてに一致しているものの数をカウントすればいい。200点問題でこういう2重にカウントしなきゃいけないのって難しめでは？ これを書いている途中で思い立って調べたけど、こういうときはstd::countなるものを使った方が良さそうだなぁ(参考URL)。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> d(M, 0);
    for (ll i = 0; i < N; i++) {
        ll K;
        cin >> K;
        for (ll j = 0; j < K; j++) {
            ll A;
            cin >> A;
            d[A - 1]++;
        }
    }

    ll ans = 0;
    for (ll e : d) {
        if (e == N) {
            ans++;
        }
    }

    cout << ans << endl;
}

C問題

　なんか差を取ってるっぽいし勘で最大公約数だろうなという感じ。最大公約数を求めるプログラム自体も勘で書いておっかなびっくり提出してみたら通ってくれた。今はVidual Studioでやっているので使えないんだけど、gccだと確かgcdって組み込みであるんですよね。ちゃんと証明したりコーナーケースを考えたりしていないのでこの問題はWA出てもおかしくなかった。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll gcd(ll a, ll b) {
    return (b == 0 ? a : gcd(b, a % b));
}

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    ll ans = A[0];
    for (ll i = 1; i < N; i++) {
        ans = gcd(ans, A[i]);
    }
    cout << ans << endl;
}

D問題

　難しかった。前回のABCでもD問題で盛大に詰まった挙句嘘解法で通すなんてことをしてしまったので今回は400点だからと言って舐めずにちゃんと考察するぞという気持ちで立ち向かう。「ちょうど本」にならないといけないというのが厄介で、なかなか桁を決め打つことができなさそう。前回もDPだったしこれもDPじゃねという発想になる。

　

　を埋めていけばなんとかなりそう。答えは64bit整数で収まらないそうなのでstd::stringで管理。文字列の長さで比較して大きくなれば採用、文字列の長さが同じでも辞書順で大きくなっていれば採用として更新。数字を一個作るのに必要なマッチ棒が本だとして、の更新はからだけじゃなくて、同じ数字を連続して採用することもできるのでからも遷移してこなければならない。このあたりサンプルがきっちり指摘してくれる内容だったので良かった。サンプル弱かったらかなり厳しかったと思う。

　初期化も少し複雑。空文字列でマッチ棒をちょうど1本使うということができないので、空文字列から遷移するときは元がちょうど0本である(である)という条件分けをしなきゃいけない。こんな場当たり的な場合分けしないといけないの本当か？ と疑いつつとりあえず出したら通った。いやー難しい。多分もっとエレガントな実装があると思う。そもそもDPじゃない解法すらありかねないしなぁ。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

const ll num[] = { 2, 5, 5, 4, 5, 6, 3, 7, 6 };

int main() {
    ll N, M;
    cin >> N >> M;
    vector<bool> can_use(9, false);
    for (ll i = 0; i < M; i++) {
        ll A;
        cin >> A;
        can_use[A - 1] = true;
    }

    vector<vector<string>> dp(10, vector<string>(N + 1));
    for (ll i = 8; i >= 0; i--) {
        for (ll j = 0; j <= N; j++) {
            //追加なし
            if (dp[i + 1][j].size() > dp[i][j].size() || (dp[i + 1][j].size() == dp[i][j].size() && dp[i + 1][j] > dp[i][j])) {
                dp[i][j] = dp[i + 1][j];
            }

            if (!can_use[i] || j - num[i] < 0) {
                continue;
            }

            //一個前から追加
            if (j - num[i] == 0 || dp[i + 1][j - num[i]].size()) {
                string tmp1 = dp[i + 1][j - num[i]] + to_string(i + 1);
                if (tmp1.size() > dp[i][j].size() || (tmp1.size() == dp[i][j].size() && tmp1 > dp[i][j])) {
                    dp[i][j] = tmp1;
                }
            }

            //同じ数字内で追加
            if (j - num[i] == 0 || dp[i][j - num[i]].size()) {
                string tmp2 = dp[i][j - num[i]] + to_string(i + 1);
                if (tmp2.size() > dp[i][j].size() || (tmp2.size() == dp[i][j].size() && tmp2 > dp[i][j])) {
                    dp[i][j] = tmp2;
                }
            }
        }
    }

    cout << dp[0][N] << endl;
}