AtCoder ABC135の振り返り

復習のためにABC135の振り返りをしたいと思います。

A問題

方針、感想

AとBのちょうど真ん中にすればよいことは直感的にわかったので、偶奇で場合分けしてさくっといきました。

#include <iostream>

using namespace std;
typedef long long ll;

int main() {
    int a, b; cin >> a >> b;
    if ((a + b) % 2 == 0) {
        cout << (a + b) / 2 << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

B問題

方針、感想

Nがかなり小さかったので、全通り愚直に調べました。入れ替えた配列について、新しい配列を用意するのかとかうまいやり方がわからなくて、かなり汚い書き方になってしまいました．．．全通り調べて、昇順の確認でO(N^3)かかる？？ので、入れ替えのたびに配列をコピーするとO(N^4)になる？？とか色々考えた結果こうなりました。解答は、配列の（インデックス+1）と中身が違うものの個数を調べるやり方でした。たしかにそうですね．．．こういう基本的な問題はもっとさくっと行きたいです。

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

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

    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            for (int k = 0; k < N-1; k++) {
                int tmp = k;
                int tmp1 = k + 1;
                if (tmp == i) {
                    tmp = j;
                } else if (tmp == j) {
                    tmp = i;
                }

                if (tmp1 == i) tmp1 = j;
                else if (tmp1 == j) tmp1 = i;

                if (v[tmp] > v[tmp1]) break;
                if (k == N - 2) {
                    cout << "YES" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "NO" << endl;
    return 0;
}

C問題

方針、解答

１番目の街の怪獣は１番目の勇者しか倒せないことは割とすぐわかったので、そのまま芋づる式に決まっていくのかなと思って実装しました。厳密な証明はわからなかったのですが、まぁそうだろうということで提出したらACでした。

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
    int N; cin >> N;
    vector<ll> a(N+1), b(N);
    for (int i = 0; i < N+1; i++) cin >> a[i];
    for (int i = 0; i < N; i++) cin >> b[i];

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        if (a[i] > b[i]) ans += b[i];
        else {
            ans += a[i];
            if (b[i] - a[i] > a[i+1]) {
                ans += a[i+1];
                a[i+1] = 0;
            } else {
                ans += b[i] - a[i];
                a[i+1] = a[i+1] - (b[i] - a[i]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

D問題

方針、感想

解けませんでした．．．最小の場合と最大の場合の間でーとか最初に思いましたが、間に固定されてる数字があるし、そもそも桁が大きすぎてlong longにも入らない？？し諦めました。

そのあと、各桁ごとにmodを計算できることに気づいて、あら？これは動的計画法を使うのかな？？と思った時には残り１０分くらいになってました。まぁもう少し早く気づいてもダメだったと思いますが．．．以下、解説を見てからの振り返りです。

１桁ずつ見ていったとき、それ以前の桁までのmod13の値がわかればよいので、dp[100005][13]でループ回してボトムアップに埋めていけば良いのかな．．．とかいう方針で考えていったらいいんですかね？？

桁を上から見ていくか、下から見ていくかでmod 13の計算方法が違って
１の位から見ていく場合、例えば12345を考えると、

ここで300とかのmod 13は
とかに分解できるので、桁をずらすごとに100とか1000とかのmod 13を用意しておくと計算できそうです。

一番上の位から見ていく場合は

みたいな感じで分解してmod 13をとると、今の桁の10倍と次の桁を足してmod 13をとっていくと、最終的に全体のmod 13が計算できることがわかります。

書いて見たコードは後者のほうです。

#include <iostream>
#include <string>

#define MOD 1000000007LL

using namespace std;
typedef long long ll;

ll dp[100005][13];
int main() {
    string s; cin >> s;

    dp[0][0] = 1;
    for (int i = 0; i < s.size(); i++) {
        int c;
        if (s[i] != '?') c = s[i] - '0';
        else c = -1;
        for (int k = 0; k < 13; k++) {
            for (int j = 0; j < 10; j++) {
                if (c != -1 && c != j) continue;
                dp[i+1][(k * 10 + j) % 13] += dp[i][k];
                dp[i+1][(k * 10 + j) % 13] %= MOD;
            }
        }
    }

    cout << dp[int(s.size())][5] << endl;
    return 0;
}

まとめ

まだまだD問題も解けないので、とりあえずD問題までを固めたいです。DPなどの典型的な問題は確実に解けるようにしたい．．．