競技プログラミング～ABC157～

おはようございます。しほみんです。

今日は先日行われたABC157について話していこうと思います。単純な実装力と知識が問われるセットで優良なセットだと思いました。会社の業務でプログラムを書いている以上、これぐらいはきちんと解いていきたいです。

atcoder.jp

自分の競技プログラミングへのスタンスです。

＜自分のプログラミング力＞

・レートは650前後の茶色です。まずは750目指します。

＜Atcoderでのスタンス＞

・アルゴリズムについては未学習。問題を通じて学習中。

・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約35回参加、8か月。

・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。

 今回は30分でABCの3完でした。D問題はそもそもアルゴリズムを知らないと厳しいところがあったので、3完でも十分にパフォを稼げました。パフォーマンスも1082で、レートも695→741と緑も目指していけるなって感じまで来ました。ここまで9か月たっているので、参加していない割には頑張れているかなと思います。

今回B,Cの実装が重かったのですが、思ったよりてきぱき解けました。実装力は上がっているなって感想です。D問題も方法さえ知ればきちんと解ける問題なので、今回で復習すればよいかなと思います。

今日はD問題まで復習して終わりにしようと思います。

ではここから振り返ります。

A問題

 全Nページの書類を両面印刷します。最低何枚必要か答えなさい。

奇数のときは(N+1)/2,偶数のときはN/2です。

ただし、intの世界では切り捨てなので偶数のときに(N+1)/2でもN/2と同じです。

よって(N+1)/2で出力します。

（構成例）

int n = int.Parse(Console.ReadLine());

Console.WriteLine((n+1)/2);

B問題

ビンゴの問題です。

ビンゴが与えられます。それで数字をいくつか言っていくので言われた数を開けます。すべての数を言われたとき、ビンゴしているかどうか確認してください。

実装としては3行3列でまずは、行列を作ります。

あとは数が代入されたとき、1つずつ確認して、穴があけていきます。

最後に縦横斜めで穴が開いているか見て判定します。

実装がひたすら面倒ですが、愚直に書けばできます。詳しくはコードを参照ください。

C問題

 以下の条件の数の最小を求めます。満たさない場合は-1を出します。

・N桁の数

・si桁目はciである。

これはまず条件に注目します。

Nは1,2,3のみ、iもたかだか5なので、最大5条件しかないです。

よって、高々5条件から満たす数の最小を探せばよいです。

さらに言えば、1つの桁に2条件が入ればそもそも満たさないです。

例えば、2桁目は1であると、2桁目は3であるは同時に満たさないです。

ただし、2桁目は1であると、2桁目は1であるは同時に満たします。

よって、まずは-1とかいれておいて、1回目に入ったらとりあえず代入、2回目は同じ数かどうか見ればよいです。

(N=1の実装例）

int judge = -1;

for(条件数）

    temp = (読み込んだ条件）;

    if(judge == -1)

        judge = a;

    if(judge != temp)

　    Console.WriteLine("-1");

       return;

if(judge == -1)

    judge = 0;

Console.WriteLine(judge);

あとはどう実装するかですが、

方法は2つあるかなと思います。

・N = 1,2,3で場合分け

・Nに関係なく、共通化して最後に分離

自分は前者の方が分かりやすかったのでそれで実装しました。

くわしくはコードを参照ください。

D問題

 N人の人がいます。友だち関係とブロック関係があります。

このうちで、友だち候補が何人いるかそれぞれ求めなさい。

友だち候補は

・友だち関係ではない。

・ブロック関係でもない。

・友だち同士でつながっている場合、候補となりうる。

まあ、やることは単純で、友だちの輪みたいなのをまずは作ります。するとその友だちの輪から友だち候補の人数は出ます。後はブロック関係を引くと答えは出ます。

このときはUnion-Find法が有効です。つまり、集合としてとらえられるものをそれぞれ分別して分ける方法です。集合を木としてつくり、複数の木を生成して、判別していく手法です。

今回の場合、その集合の要素数が必要です。これは最初に親の配列を-1にして、親の根に-(要素数)を出す工夫が必要なので難易度は地味に高めです。

Union-Find自体は以下のコードです。その使い方や数え方はコードを見てください。

C#でもクラス化しちゃう方がやりやすいです。

/*UnionFind法のクラス*/

    class UnionFind

    {

 

        public int par;

        public int temp;

        //マイナスは根を示す。

        public void reset(int n)

        {

            for(int i = 0;i < n;i++)

                par[i] = -1;

        }

        //マイナスならそれはまだ属していないので根である。そうでないならさかのぼる

        public int root(int x)

        {

            if(par[x] < 0)

                return x;

            else

                return root(par[x]);

        }

        //根の併合を行い、根には要素数を足す（マイナスの値）

        public void unite(int x, int y)

        { // xとyの木を併合

            int rx = root(x); //xの根をrx

            int ry = root(y); //yの根をry

            if (rx == ry) 

                 return; //xとyの根が同じ(=同じ木にある)時はそのまま

            if(par[ry] > par[rx])

            {

                 int temp = ry;

                 ry = rx;

                 rx = temp;

            }

            par[ry] += par[rx];

            par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける

        }

        // 2つのデータx, yが属する木が同じならtrueを返す

        public bool same(int x, int y) 

        { 

            int rx = root(x);

            int ry = root(y);

            return rx == ry;

        }

        

        //根の元に入っている

        public int size(int x)

        {

            return -par[root(x)];

        }

    }

最後に...

Union-Find法は理解してしまえばわかりやすい方法と感じます。後は次出たときにミスしないようにしたいと思います。ではでは。