AtCoder Beginner Contest 147のコンテストに参加して、どのように考え解いたのか、なぜ解けたのか、なぜ解けなかったのかを反省として書き残しておきたいと思います。

はじめに

コンテストへのリンク

atcoder.jp

解いた問題

A,B,Cを解きました。Cが解けなかったので解説を確認して実装しました。(この記事はC問題の解説がメインです)

解答説明

A問題

if文で22点以上とそれ以外で分ければOK。

実装 AtCoder/A.cs at master · chittai/AtCoder · GitHub

B問題

仮に与えられた文字列に頭から番号をつけたとします。

例 : abcdabc → 0123456

これが回文であるためには、0=6,1=5,2=4,である必要があります。これをif文で判定すればOKです。

実装 AtCoder/B.cs at master · chittai/AtCoder · GitHub

C問題

C問題ですが、ここは問題から振り返ってみましょう。

問題概要

1からNまでの番号がついた人がいる
それぞれ、正直者か不親切な人
それぞれ、証言をしている( x が y(0->不親切、1->親切)である)
このN人の中に、最大で何人の正直者が存在し得るか

解法

bit全探索ですべてのパターンを調べます。Nが最大で15なので2¹⁵(= 32768)通りなので計算量的にはこの時点では問題なさそうです。

ただ、今回はbit全探索であるかどうかはそんなにポイントだとは思っておらず、その後の処理がポイントだと思います。

実際、コンテスト中にbit全探索の可能性は思いついたのですが、その後の”正直者に矛盾がないか調べる方法”の実装がどうしても思いつかず解答しきれなかったからです。(このあたりは人によると思いますが)

なので、今回はそのあたりの考え方と実装方法を振り返ってみようと思います。

実装

先に実装のリンクを載せておきます

実装 AtCoder/C.cs at master · chittai/AtCoder · GitHub

bit全探索の基礎

下記の記事で紹介しています。 c-taquna.hatenablog.com

正直者に矛盾がないか調べる方法

先程書いたように、bit全探索で調べる場合に正直者に矛盾がないか調べる必要があります。これはbit全探索する時に、N人がそれぞれ正直者(1)か不親切(0)かをbitのフラグ管理で実装します。

for (int i = 0; i < N; i++) 
{
    if ((bit & (1 << i)) <= 0) continue; // i番目のフラグが立っていなければ次の i へ
    count++; // 正直者の数をカウントしている
    for (int j = 0; j < A[i]; j++) // ここから、正直者の証言の内容を検証する
    {
        if ((bit & (1 << (x[i, j] - 1))) > 0) // bit のx[i,j] -1 番目のフラグが立っているか調べる。
        {
            if (y[i, j] == 0) ok = false;  // ※
        }
        else
        {
            if (y[i, j] == 1) ok = false;
        }
    }
}

上記の様になるのですが、*と書いた場所は下記の様に理解すればOKです。

if ((bit & (1 << (x[i, j] - 1))) > 0)
{
    if (y[i, j] == 0) ok = false;
}

x[i,j]-1の人が正直な場合の処理です。正直なのに、y[i,j] == 0 となっている。つまり、正直者と仮定した人(i番目のフラグの人)が、別の正直者と仮定した人(x[i,j]-1)を不親切(y[i,j]==0)といっているため矛盾が生じています。つまり、このパターンは不成立です。逆に、このbool ok が trueのままだったらOKです。あとは、正直者が最大となる場合の値を出力します。

最終的なポイント

今回の問題は制約から、bit全探索であることは推測ができる。ただ、その後の処理が思いつかないため実装できなかったので単純な論理思考力が不足しているが実装力の不足が原因かなと

感想

間違いなく考察の幅は広がっているが、まだ緑をコンスタントにACできるレベルではないのでこれからも精進あるのみ

たくあんポリポリ

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

【AtCoder】【C#】AtCoder Beginner Contest 147 の反省