AtCoder ABC214

ABC214参加しました。

atcoder.jp

A - New Generation ABC

解説 - AtCoder Beginner Contest 214

Nで場合分けするだけです。

B - How many?

解説 - AtCoder Beginner Contest 214
和の等式から、明らかに$a,b,c$は最小が0,最大がSで抑えられます。以下のような3重for文を書きました。 100はSの最大値です。cはa,b,Sが決まれば上限が確定するので、少しだけ回す回数が減ります。

for(int a = 0; a <= 100; ++a)
{
    for(int b = 0; b <= 100; ++b)
    {
        int cMax = Math.Max(0, S - a - b);
        for (int c = 0; c <= cMax; ++c)
        {
            if (a + b + c <= S && a * b * c <= T)
            {
                ++ans;
            }
        }
    }
}

C - Distribution

解説 - AtCoder Beginner Contest 214
提出 #25062806 - AtCoder Beginner Contest 214

公式解説がわかりやすいので、あまり書くことはないのですが... 自分の回答は、DPの方式、ダイクストラ法を使う方式の２つで実装してみました。

DPのほうがわかりやすいし、コードも短いです。

dp[i] = i人目が宝石を受け取る最短時間　と定義します。
まず明らかに、全員高橋さんから宝石を受け取ることはできるので、「初めて宝石を受け取る時間」の候補として、T[i]で初期化できます。

後はこのdpテーブルを、前のすぬけさんからのパス時間を考慮してどんどん値を小さくしていけばよさそうです。 　　 N人目から一人目へのパスは i % N, (i + 1)% Nで簡単にできます。

まとめ

Cは解きたかった。図を書いてもよくわからなかったので、愚直にやって最適化していこうとしてました。
やっぱりdpかなと嗅ぎつける嗅覚がほしいです。 DPに慣れるためにEDPCをやっても、「DPを解法方針にする」部分は事前にわかっていますからね。