ABC192 反省と感想 - 文学徒が競プロをするブログ

Dがいまいちピンと来ず(そもそも題意を完璧に把握しないまま進めたのがまずかった)、Eを解きに行ったのは結果的に良かったですね。

Dの誤読云々については思うところはあれど、そもそも二分探索が出るまでかなりかかったので、誤読しないような問題構成になっていた場合僕のレートは恐らく下がっていたと思います。
まあ、実質的な敗北と言っても差し支えないでしょう。そのことを胸にこれからも頑張ります。

A問題 Star

int ans = 100-(x%100);

B問題 uNrEaDaBlE sTrInG

// 小文字判定
if ('a' <= s[i] && s[i] <= ''z) {

}
// 大文字判定
if ('A' <= s[i] && s[i] <= 'Z') {

}

これ確か仕様的には結構怪しくて、非推奨であるようなことを読んだ覚えがあります。しかしAtCoderで動くのはわかっていたので書きました。C/C++で競プロするならまあ許される程度の小技ですかね。

C問題 Kaprekar Number

ll g1(ll n) {
    vector<int> x;
    while (n > 0) {
        int tmp = n%10;
        x.push_back(tmp);
        n /= 10;
    }
    sort(x.begin(), x.end(), greater<>());
    string s;
    rep(i,x.size()) s.push_back('0'+x[i]);
    ll ret = stoi(s);
    return ret;
}

ll g2(ll n) {
    vector<int> x;
    while (n > 0) {
        int tmp = n%10;
        x.push_back(tmp);
        n /= 10;
    }
    sort(x.begin(), x.end());
    string s;
    rep(i,x.size()) s.push_back('0'+x[i]);
    ll ret = stoll(s);
    return ret;
}

ll f(ll n) {
    if (n == 0) return 0;
    return g1(n)-g2(n);
}

int main(int argc, char const *argv[]) {
    ll n,k; cin>>n>>k;
    ll ans = n;
    rep(i,k) {
        ll cur = f(ans);
        ans = cur;
    }
    cout << ans << '\n';
    return 0;
}

関数を定義してしまうのが楽だと思います。

D問題 Base n

反省点が二点あります。

二分探索であることがわかるまで30分以上かけている
求めるものをきちんと理解していなかった

1の方がヤバいです。誤読云々で他の参加者が失敗していなければ、自分だけが失敗するところでした。

問題を見て、よくわからないながら、とりあえず各進数表現について決め打ってMを超えるかどうか判定する処理を書きました。この処理自体は、1桁目から見ていくことでオーバーフローを回避する工夫を盛り込むなど、及第点だったと思います。

最初は問題の意味がそもそもわからなかった(10進数まで見るだけかと思っていた)ので、とりあえず10進数まで見ればいいのかな～みたいなコードを書き、サンプルに12進数なんかが出てきていたので100進数くらいまで見ればいいかと思うなどしていました。

ここ本当に頭が悪いし、「探索する範囲はそんなに広くないだろう」という意識を持ってしまい、二分探索を思考に乗せるのに時間がかかってしまいました。本当に反省しています。まず問題をしっかりと読んで、最大 ${10}^{18}$ 進数まで見ることが分かっていれば、さっと二分探索が出せただろうに....。大反省です。

結局二分探索に気づいたのはEを通して10分くらい更に考え込んだ後でした。愚かですね。

2についても「題意をしっかりと最初に把握していない」ことが招いた失敗でした。反省します。WAの件数的に、ずっとオーバーフローを疑っていました...。

E問題 Train

見た瞬間「大体やるだけかな～」と思いながらとりあえず半信半疑でダイクストラを書き、サンプルが通るもWA。更新時の式をよく見るとバカなミスをしていたので投げ直すと通りました。

本質はA問題と同じなので、A問題が解ける人でダイクストラ法を知っている人なら通せるんじゃないでしょうか。でもこれが緑diffはおかしいと思うの。

F問題 Potion

流石にD問題よりもずっと通されていなかったのでFは捨てたのですが、この判断はどうだったんでしょうね...。どうせK固定して頑張るタイプの問題でしょという見た目で方針は立ちやすかったので、特攻してもよかったかもしれません。Dを通せなかった結果論ですが。
後からやった感想だと、自力でわりとすんなり通せたので、うーんという気持ち。まあ全体の計算量が4乗でdpを使うという大ヒントを得ていたのでそんなもんかな。

まずぱっと見ですが、時刻を $d$ 、合成したポーションの値を $s$ として表すと、

$k \times d + s = x$

関係式は上記のように表すことができ、 $k \times d = x - s$ となります。求めたいのはこれが最小の $d$ ですから、ポーションの組み合わせを全探索すれば答えを出すことができます。

しかし問題はここからです。当然全ての組み合わせを試すのは時間がかかりすぎるので、高速化したいです。最初に思いつくのは部分和問題的なDPですが、 $x$ の制約が大きすぎます。ここからもう一つ進展させたいです。

こういうときはとりあえず先ほどの関係式を吟味します。

$k \times d = x - s$ ということは、 $x - s$ は $k$ の倍数です。よって $x-s \equiv\ 0 (mod\ k)$ と表せて、これは脳死で移項して $x \equiv s\ (mod\ k)$ にできます。

ということは？先ほどの部分和問題的なDPという解法を却下したのは、 $x$ の制約が大きすぎるためでした。しかし $x \equiv s\ (mod\ k)$ という関係式が導き出せたので、 $k$ を固定して $x \% k$ と $s \% k$ が一致するもののみを考えれば良いということがわかったのです。

$k$ の範囲は最大でも $1 \leq k \leq n$ なので、十分DP出来る制約になりました。

$dp(i, j, l) :=$ $i$ 番目の数まで見て、そこまでの和を $k$ で割ったあまりが $j$ で、それまでに $l$ 個の数を足している、 $x$ を超えない範囲で最大の和

と定義します。

memset(dp,-1,sizeof(dp));
dp[0][0][0] = 0;
rep(i,n) {
    rep(j,k) {
        rep(l,k+1) {
            if (dp[i][j][l] == -1) continue;
            ll tmp = dp[i][j][l]+a[i];
            // 今見ている数を加える場合は和がxを超えないかどうかチェック
            if (tmp <= x) chmax(dp[i+1][(j+a[i])%k][l+1], tmp);
            // 今見ている数を加えない場合は何もせず遷移
            chmax(dp[i+1][j][l], dp[i][j][l]);
        }
    }
}

遷移は上のような感じで。

あとはこれを $k$ を $1$ から $n$ まで全部回して $d$ を求めてやればいいです。dbの初期化は $k$ 回しましょう！それで答えが合わずに首をかしげていました。

青diffかって言われるとうーん？って感じ。D問題がアレじゃなかったらFも結構通されるような問題に見えます。