【競プロ基礎パターン】重複のない組み合わせをプログラムで表現する。

内容

競プロ、初心者向けの内容
プログラムで重複のない組み合わせを作り出すにはどうすればよいか。

背景

AtCoder Beginner Contest 175のB問題を提出できなかった弱弱な僕。

B問題
この問題の解説というより、その前段階の解説になります。

例題.

問1. 数字が書かれた5種類のカードから3つを選んだ組み合わせはいくつですか？

高校生なら確実に解けるであろう問題
答えは$ _5C_3$ = 10

しかし、競プロで求められるのは組み合わせの総数より、各組合せが条件に合うかについてということのはず。

問2. 各組合せのカードの和が10以下になるのは、何通りですか？
まず、全組み合わせを得る必要があるが、上記公式だけでは、組み合わせの数は分かるが、どんな組み合わせが実際に存在しているのかは分からない。一度中学生に戻って、樹形図を書いてみることにする。

これを一つ一つ確かめていけばいいことになる。

問3.それをプログラムで表してください
競プロなので当然こうなる

a.そんなの余裕だとプログラムへ変換出来る人
b.まったく分からないという人
c.余裕だと思って書き始めて、止まる人(僕)

a.の人はこれ以上読む必要はありません。

なぜプログラムへ変換できないのか

樹形図を紙に書くに際には規則性があるため、慣れればシステマチックに書ける。

しかし言葉で説明しようとすると。初めにAを選んだ場合、A以外のB,C,D,Eを組み合わせられる。その次のBに対してはAとB以外を組み合わせられる。・・・・1つ目にDを選んだ場合に組み合わせられるののはEだけど、その次の3つ目に組み合わせられるものがないので、最後の組み合わせはC-D-Eになる。

結構複雑でプログラムでどうやって表現するのか、と呆然とする僕だけではないと思う。

解法

解法1

全数ループ内を作り、重複しないための条件を追加( if(i>j && j>k)の部分)

for(int i = 0; i < 5 ; i++){
  for(int j = 0; j < 5 ; j++){
　　for(int k = 0; k < 5 ; k++){
　    if(i>j && j>k){
　　　　 //重複のない組み合わせが出来上がる
        //和が10以上か確認する
      }
    }
  }
}

解法2

ループの条件で対応する。(内側のループのj<iとk<jが重要)

for(int i = 0; i < 5 ; i++){
  for(int j = 0; j < i ; j++){
　　for(int k = 0; k < j ; k++){
      //重複のない組み合わせが出来上がる
      //和が10以上か確認する
    }
  }
}

なるほど、作ってみればとっても簡単。でも、競プロの緊張した中でゼロからこれを考え出せるか。僕には無理。

解法以上に大切なこと。

1つのパターンを身に付けたこと。

組み合わせから、条件に合うものを探す問題だと気づいたら、上記の解法を思い出し、簡単なループを作れる。これで、樹形図は書けるけどどう表現すれば、とオロオロしていた僕とはおさらば。

実際に上記解法を見ればすごく簡単。人によっては、上記のパターンを事前に知らなくてもいきなりプログラムへ変換できる人はいるかもしれない。でも、みんながみんなそうではないと思う。少なくと僕には難しい、なのでこういった簡単な所からパターンを身に付けていくことが大切だと思う。

残る問題

全組み合わせをループで作って解いていいのかどうか、
こっちの方が切実な気がする。

100の3重ループぐらいなら大丈夫、と解説していた。
1000000回だと考えれば、それぐらい大丈夫な気もしてきた。慣れが必要？

樹形図的な順番に合っている方法

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {