たくあんポリポリ

勉強したことを載せていきます。最近、技術系の記事はZennに書いています。(https://zenn.dev/chittai)

【C#】 第二回全国統一プログラミング王決定戦予選 の反省

AtCoder C# アルゴリズム プログラミング 自分用

最近コンテストに参加しても反省ができていなかったのと、今回は解法までわかったが、実装がうまくいかず解けなかった問題があるので、忘れないように反省メモを残しておきます。完全自分用メモです。

atcoder.jp

B問題の実装

実装を載せておきます。 github.com

B問題での考え方

問題は上記リンクをたどってもら得ればよいので、どのように考えたか書きます

  1. 問題を読んで内容と条件を把握。

  2. 図に書き出してみて、少ないパターンを調べてみる。下記は、入力例 3を使用して、3段目までの組み合わせを調べてみました。f:id:c_taquna:20191110013617j:plain:w400

  3. これで三段目までは8通りあることがわかります。ここで図をみていると、三段目の各値は親が2しか取れないことがわかるので、23でパターンを計算できると考えました。つまり、i段目を調べた時に一つ上の親となる頂点の数をi段目の要素の数乗してあげればよいと考えました。そして、それをかけ合わせれば答えが出ると考えました。

long parent = 1;
for (int i = 1; i < N; i++)
{
    if (DCount[i] != 0) parent = (parent * (long)Math.Pow(DCount[i - 1], DCount[i]) % MOD) % MOD;
}

こんな感じで実装しましたが、これだと5ケースがNGとなりました。
4. コンテスト終了後に下記実装に変えてみたたところ、ACできました。

long parent = 1;
for (int i = 1; i < N; i++)
{
    if (0 < DCount[i])
    {
        for (int j = 0; j < DCount[i]; j++)
        {
            parent = (parent * DCount[i - 1]) % MOD;
        }
    }
}

今回の問題の特性として、剰余演算があったのですが、Math.Powなど使用してしまうと、この計算の中で桁数超えが起きてしまったりしているかもしれないので、できるだけfor文で回すようにするなど、計算単位を分割していったほうがいいのかもしれないと思いました。

感想

300点問題がとけなかったのはかなりしんどいけど、解法はあっていたし、実装力をもっとつけるのと、各パターンにおいてこうした方が良い、といった城跡を積んでいけばもっと安定するのではないかと思う。