たくあんポリポリ

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

【AtCoder】【C#】組み合わせのすべてのパターンを利用する方法

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

n個からr個取り出すパターンを計算する時は、nCrで計算が可能です。例えば、5個の中から3個取り出すときは10通りです。今回は、このように10通りの組み合わせをすべて出力するための方法を説明します。

はじめに

問題へのリンク

atcoder.jp

問題の概要

  • N個の文字列が与えられる
  • 与えられた文字列で、先頭の文字が"MARCH"のいずれかで始まるものを3つ選ぶ
  • 何通りあるか求める。制約は、選択した文字列の中に、同じ文字から始まる文字列を入れてはいけない(ex. Mxxx , Axxx, Axxx はNG)

本題

解法

まず、解法についてです。同じ文字から始まる文字列は選べないので、M A R C H の中から3つ選ぶ必要があります。これは5C3で10通りとなります。

ただ、与えられた文字列において、MARCHから始まる文字列は1つとは限りません。ですが、これは簡単に処理できます。具体例で試してみましょう。

下記のように文字列が与えられたとします。

MZxx
Axxx
MYxx
RZxx
Cxxx
RYxx

Mから始まる文字列は2個、Aは1個、Rは2個、Cは1個となります。これを下記のように整理します。

long m = 2;
long a = 1;
long r = 2;
long c = 1;
long h = 0;

ここで、M・A・Rを選んだ場合について考えます。上記のように、複数個ある場合、その数だけ選択のパターンがふえるので、m x a x r で何通り作れるか計算できます。

これを利用して、最初に書いた10通りのパターンすべてについて計算して足すことで答えが求められます。この実装方法がアイデアとして使えるのではないかと思い記事にしました。

実装

int[] P = { 0, 0, 0, 0, 0, 0, 1, 1, 1, 2 };
int[] Q = { 1, 1, 1, 2, 2, 3, 2, 2, 3, 3 };
int[] R = { 2, 3, 4, 3, 4, 4, 3, 4, 4, 4 };
long[] D = new long[] { m, a, r, c, h };
long res = 0;
for (int i = 0; i < 10; i++)
{
    res += D[P[i]] * D[Q[i]] * D[R[i]];
}

このように、PQRという配列を用意して、すべてのパターンを用意します。(P[0], R[0], Q[0]で1パターンを表現)そして、marchを配列に格納します。あとは実装の通り、D[P[i]]〜と呼び出せば完了です。

この様に配列を利用してすべてのパターンを書き出すことで実装がきれいかつ簡単になると思います。ただ、すべてのパターンを書き出す労力を考えるとできれば10パターンぐらいが実用的かなと思います。