CodeIQ プログラミング言語☆総選挙の初心者的解法
CodeIQ プログラミング言語★総選挙｜CodeIQ の件です。
問題と公式解説は、
「CodeIQ プログラミング言語★総選挙」予選・本選問題の解説公開！#CodeIQ｜CodeIQ MAGAZINE にあるのですが、アカウント登録しないと見れないので、
まだのかたは、是非是非、アカウント登録してみてください。
私は、予選はPythonに投票したのですが、落選したので、
本選はPython3に投票しました。
一応、完璧な正解者の中に名前が載ってましたので、
それはそれで嬉しいのですが、もっと良い方法があるのかも知れず、
考え方を公開しておけば、
どこかで、親切な誰かに、もっと良い方法を教えてもらえるかも。。
なんて考えて、記事として書くことにしました。
「ドミノ敷き詰め問題」？ グラフ理論の「完全マッチング」の問題？
という用語が公式解説にも出てきてますが、私はそのことは解っていません。
グラフ理論のページはいくつか読みましたが、
ちょっと私には敷居が高すぎて。。なんだかよく解りませんでした。
１．予選
予選は欠席者がいないか、１名きりなので、
単純な分岐処理だけで解答を出すことができます。
以下の法則です。数学的に何故なのかの証明は聞かないでください（笑
・人数が奇数 → 必ずno
・人数が偶数 → 部屋の広さが偶数（6*4=24など） → 必ずyes
部屋の広さが奇数（5*7=35など） → タテヨコの座標の片方が奇数であればno
そうでなければyes
２．本選
予選を横着してしまったので、欠席者が複数いるとなると、
やっぱりペアを作りながら深さ優先で全探索するしか無いかと、
考えていたのですが、私なりの良い方法を思いつきました。
例として、次のパターンで考えます。
OXOO
OOOO
OOOO
OOOX
各生徒のペアになれる候補人数をカウントします。
欠席者は-1としておきます。
以下の表が初期の2次元配列の状態です。
| 1 | -1 | 2 | 2 |
| 3 | 3 | 4 | 3 |
| 3 | 4 | 4 | 2 |
| 2 | 3 | 2 | -1 |
もし、候補者が「1」になる生徒がいた場合は、
この時点でペア確定です。
ペアは、欠席者として、-1にしてしまいます（赤い文字の箇所）。
(普通の考えだとペア番号を付けて行って再帰をすると思うのですが、
この問題の場合は、誰と誰がペアになるのかを残す必要が無いため、
これでいいのです。)
| -1 | -1 | 2 | 2 |
| -1 | 3 | 4 | 3 |
| 3 | 4 | 4 | 2 |
| 2 | 3 | 2 | -1 |
変化があった場合は、ペア候補者数を再計算します。
変化がおこらなくなるまで、これを繰り返します。
| -1 | -1 | 2 | 2 |
| -1 | 2 | 4 | 3 |
| 2 | 4 | 4 | 2 |
| 2 | 3 | 2 | -1 |
変化が無くなった段階で、もし、候補者の人数が0人となっている
生徒がいれば、必ず、ペアは作成できないので、「no」として終了します。
↑閉じ込められているこんなパターンですね。
ここではじめて再帰をします。
仮にどれか2人をペアにします。
出来れば、ペア候補が少ない人を優先したほうが早く判定できそうなので、
候補者が2人の人＆隣の人を選びます（そうでなくても良いかも。。）。
角のほうから中心に向かって、ペアが確定していくことになります。
| -1 | -1 | -1 | -1 |
| -1 | 2 | 4 | 3 |
| 2 | 4 | 4 | 2 |
| 2 | 3 | 2 | -1 |
※赤い文字の2人をペア（というか欠席者）にしました。
以下、処理を繰り返します。赤字の箇所が変化した部分です。
（候補者を再カウント）
| -1 | -1 | -1 | -1 |
| -1 | 2 | 3 | 2 |
| 2 | 4 | 4 | 2 |
| 2 | 3 | 2 | -1 |
↓
（ペアの仮作成） ※ここで再帰
| -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | 2 |
| 2 | 4 | 4 | 2 |
| 2 | 3 | 2 | -1 |
↓
（候補者を再カウント）
| -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | 1 |
| 2 | 3 | 3 | 2 |
| 2 | 3 | 2 | -1 |
↓
（候補者1人のみなので、ペアの確定）
| -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | -1 |
| 2 | 3 | 3 | -1 |
| 2 | 3 | 2 | -1 |
↓
（候補者を再カウント）
| -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | -1 |
| 2 | 3 | 2 | -1 |
| 2 | 3 | 2 | -1 |
↓
（ペアの仮作成） ※ここで再帰
| -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | -1 |
| -1 | -1 | 2 | -1 |
| 2 | 3 | 2 | -1 |
↓
（候補者を再カウント）
| -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | -1 |
| -1 | -1 | 1 | -1 |
| 1 | 2 | 2 | -1 |
↓
（候補者1人のみなので、ペアの確定）
| -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | -1 |
以上、全生徒を欠席者（-1）にすることが出来たら、
「yes」と表示します。
もし、余る人（候補者が0人の生徒）が出てくるのであれば、
ペアの仮作成の選び方が良く無かった可能性があるため、
再帰の呼び出し元に戻って、違う生徒をペアとして、
もう一度計算をやり直します。
全パターン試しても余る人が出てくるのであれば、
ペア作成が出来ないことが確定なので、「no」と表示します。
ということで、全体的には深さ優先探索ではあるのですが、
この方法であれば、部屋が少々大きくても、
あまり何度も深く再帰呼び出しをすることなく判定が出来ます。
私の中では、
「マインスイーパでいっきにブロックが空くときのイメージのような処理法」
と勝手に（心の中で）呼んでいます。
（長いし、しょうもない例えだし、とにかく伝わらなかったら、ごめんなさい。。）
実際は、何か名前があるのかも知れません。これも枝刈り？。。なのかも
ソースは、以下ですが、非常にキタナいです。
Python3もはじめて触りました。
意外と、Python2と違うところがあって、その点も少し悩みました。
map関数がリストではなくて、イテレータを返すとか。。
何もPython特有の特別なことはしてませんので、
概念的には他の言語にも移植しやすいと思います。（関数型言語はよく解りませんが。。）
ちなみに公式解説にある拡張ケースのデータを、
ideone.comで試した処理時間の結果は以下でした。
（数回試してます）
a ・・・0.05～0.12s
b ・・・0.05～0.12s
c ・・・0.03～0.11s
d ・・・0.03～0.11s
e ・・・0.04～0.12s
たぶん、まぁまぁかな。。
実は当初より、問題点に気付いていて、ペアの仮確定は、
再帰から戻ったときに、元に戻しているのですが、再帰の中での本確定は、
元に戻していません。
これでも処理がなりたっているっぽく見えるのですが、
もしかしたら、もしかしたら、ダメなパターンがあるのかも知れません。。
ですが、ダメになるパターンを見つけきれずにいるので、
これで良いか。と思っています。
