正解者だけが投票できるCodeIQプログラミング言語★総選挙

こんにちは、Ozyです。

CodeIQ プログラミング言語★総選挙 予選・本選問題に挑戦していただきありがとうございました。

単なる人気投票とは異なり、実際に問題を解き、正解した方にのみ投票権が得られるということと、いわゆる”Hello World”的な誰でもすぐにできそうな易しい問題ではないということで、実際に投票するには、見た目の印象に反してかなり大変だったと思います。

それでも予選150名、本選106名もの方が、短い期間内でしっかりとコードを書き、熱い1票を投じてくださいました。

順位表

最終的な順位は、次のようになりました。

順位	有効得票数	言語
1位	21	Ruby
2位	13	Java
3位	11	Python3
4位	10	C
5位	9	Haskell、C#
7位	7	C++

予選と同じく、Rubyが完勝でした。2位以下は混戦でした。挑戦者数だけを見ると、

言語	挑戦者数
Ruby	27
Java	16
C++	14
Python3	12
C	12
Haskell、C#	11

で、C++は3番目に多かったのですが、不正解率が高かったため、最下位となってしまいました。

強力な言語ではありますが、バグを埋め込みやすいのも事実ですから、しっかりとテストしておかなければなりませんね。

HaskellとC#は、得票数だけでなく挑戦者数も同じでした。

解説

ここからは実際に問題に挑戦した方、あるいは挑戦したかったけれども何らかの理由でできなかった方向けに、簡単に解説をしておきます。

予選・本選のポイント

予選問題は、欠席者が最大1という制約でペアを作る問題でした。欠席者が0か1であれば、次のようなルールで判別することができます。

生徒の位置によって、ABのグループに分けると、Aのグループの人数とBのグループの人数が等しくなった場合にペアを作ることができます。

の場合はAもBも4ずつになり、うまくペアを作ることができますが、

の場合はAが5でBが3となり、数が等しくなくなりますので、ペアを作ることができません。

この性質を利用すれば、単純に出席者をグループ毎に数えるだけで済みます。

ところが本選の問題になると、そう簡単にはいきません。欠席者が複数の場合、

のように、複数の欠席者によって出席者の領域が分断されてしまうと、先程の判定方法が使えなくなります。

生徒同士が隣り合った領域ごとに調べることで、ある程度対応ができますが、完全ではありません。

たとえば、次のようなケースをご覧ください。

AとBの数はそれぞれ5ずつで等しいにもかかわらず、完全にペアを作ることができません。

①と②は、ペアを作ることのできる相手が③のみですので、いずれかはペアを作ることができません。

仮に②と③でペアを確定させてしまうと、①が孤立することになります。

ペアを作る相手が1人しかいない場合はペアを確定させ、出席者リストから除外してしまうことで問題を縮小することができます。

孤立する生徒が現れれば、ペアを作ることが不可能であるとすぐに判定することができますね。

この例以外でも、ペアが確定する部分を繰り返し取り除いてしまうことで、問題の規模を縮小できる場合があります。

では、次の場合はどうでしょうか。

ABの数は等しく、領域が分断されているわけでもありませんが、完全にペアを作ることができません。

このように中央部でペアを作ると、左右共に奇数人数になってしまい、明らかにペアを作ることができません。だからといって、

のように1つずらすと、左側はAが5、Bが3となり、右側はAが4、Bが6となり、左右いずれもペアを完成させることができません。

ここまでくると、実際にペアを作ることができるか、探索を行う必要が出てきます。

ペアを作ることができない場合を容易に見つける方法はあるけれども、万能ではないということが重要です。

前処理として、出席者をグループ分けした後、明らかにペアを作ることができない場合は’no’、そうでなければ即’yes’ではなく、まだ’yesかもしれない’というだけですので、実際にペアを作っていく作業が必要です。

ここまで示した、「ペアができない場合」を調べておくと、ほとんどのケースでペアを作ることができます。

今回はペアの作り方を列挙する必要はありませんから、深さ優先の探索アルゴリズムを用いれば、それほど時間はかかりません。まれにペアができないケースもあります。その場合は、それなりにきちんとした探索プログラムを書く必要があります。

サンプルで用意したものより難しいextracase.zipを用意しましたので、興味のある方はすべてのケースで正解が得られるか、試してみてください。

今回の挑戦者の中で、これらのケースも完璧に正解した方が、19名もいらっしゃいましたので、紹介させていただきます。

みけCATさん
ae89jca0bさん
atohさん
Shuntさん
mamekinさん
naoki_kpさん
mattyaさん
hshimizuさん
ウッキー竹脇さん
mkothaさん
negitronicsさん
sekiyeさん
nmasさん
Ｒ修行中さん
masahiko_of_joytoyさん
haruyaさん
はにゃわさん
Mooanさん
a992571さん
（上から提出の早かった順で掲載しています）

特に景品等はなく、単なる名誉しかありませんが、おめでとうございます！
すばらしい解答でした！！

正解・不正解の判定

本選の正解・不正解の判定は、問題発表時に公表したサンプルデータ(sample.zip)をそのまま使用しました。

もう少し厳しいデータセットでもよかったのですが、好きな言語に投票するという目的もあるということで、最低限のチェックを通っている解答は、有効票としています。

出題者としてひとこと

「ペアを作る問題」ということで出題しましたが、平面上で格子状に並んでいるということを考えると、本問はドミノ敷き詰め問題と同等の問題でした。

いわゆる「競技プログラミング」に慣れている方は問題を見た瞬間に気付いて、さらりと解いてしまったかもしれません。

グラフ理論の用語でいえば、「完全マッチング」の問題で、一度検索していただくとわかると思いますが、たくさんの情報が出てきます。本問を通して興味が出た方は、是非勉強してみてください。非常に奥深い内容です。

本選問題

◆プログラミング言語★総選挙　本選挙
「2人組を作って！〜欠席多くても頑張る編〜」

先生「はーい、それじゃあ今から2人組になってくださーい」
と言われて、辛い思いをしなくても済むように、隣り合った人同士で、ペアを作りたいと思います。

このように、横に3人、縦に2人の合計6人いる場合、

のように、ペアを作ることができます。
ただし、

のようなペアの作り方では、左下の人と右上の人が離れてしまいますので、このようなペアの作り方は避けます。

そうすると、合計の人数が偶数であるかぎり、あぶれる人が出ることなく、かならずペアを作ることができます。

…が、現実はそれほど優しくはありません。欠席者がいるときもあります。

人数が奇数になってしまうと、どう頑張っても1人残ってしまいます。
逆に、元々奇数人の場合はうまくペアを作ることができる場合もあります。

ただし、欠席者の場所によってはうまくペアが作れない場合もあります。

欠席者が多数いた場合でも、とにかく出席者だけでペアを作ります。

上記の場合はうまくペアを作ることができますが、次の場合はペアを作ることができません。

【問題】
出欠情報が、標準入力からアルファベットの文字列で与えられます。
隣り合う人同士でペアを作り、出席者全員をペアにできる場合は「yes」、できない場合は「no」と出力するプログラムを書いてください。

◎出欠を表すアルファベットはすべて大文字で、出席の場合は”O”、欠席の場合は”X”とします。

◎アルファベットの並びは、必ず矩形（各行の文字数が等しい）で与えられます。また、矩形のタテの長さをH、ヨコの長さをWとすると、入力データの範囲は1≦H≦10、1≦W≦10とします。

◎欠席者の数には制限がありません。つまり、全員欠席の場合もあり得ます。
全員欠席の場合は、「no」と出力してください。

【入出力例】
◎sample(1)
[input]
OOO
OOX

[output]
no

◎sample(2)
[input]
OOO
OOO
OOX

[output]
yes

◎sample(3)
[input]
OOO
OOO
OXO

[output]
no

◎sample(4)
[input]
XXX
XOO
XXX

[output]
yes

※sample.zip にこれらのデータをテキストファイルとしてまとめてあります。参考にしてみてください。

【提出方法】
プログラムのソースコードを、テキストファイルの形式でご提出ください。
その際、ソースコード内にコメントとして、言語の種類を記述してください。
つまりプログラムはそのままideone.com上で動かせるようにしておいてください、ということです。

【注意】
ideone.comで実行テストを行うので、提出前に必ず実行テストを行ってください。
上記の例以外にも、非公開のテストケース が用意されています。
すべてのテストケースで条件を満たす出力が得られれば、正解とします。
ご提出の前に、入念なテストを行ってください。

☆提出前のチェックリスト☆
(1)バグのない（と思われる）コードが書けた
(2)プログラムをideone.com上で実行してみた
(3)sample.zipをダウンロードして、サンプルデータでテストした
(4)問題に書かれている入力例以外も、テストケースを考えてテストした
(5)ソースコード内に、言語の種類を書いた

【投票言語】
予備選挙を勝ち抜いた下記7言語の中から、あなたが本当に好きな言語で解答してください。

- C    / C(gcc-4.8.1) と C99 strict(gcc-4.8.1)  
- C#  
- C++  / C++ 4.3.2(gcc-4.3.2) と C++ 4.8.1(gcc-4.8.1)  
- Haskell  
- Java / Java(sun-jdk-1.7.0_25) と Java7(sun-jdk-1.7.0_10)  
- Python3  
- Ruby  

CodeIQ運営事務局より

Ozyさんは他にもいろいろな問題を出題されています。
ぜひその他の問題にもご挑戦ください！！
Ozyさんの問題はこちら！

寄稿者プロフィール Ozy(本名 岡田佑一)
大阪府出身。ソースコードを短くする遊び“コードゴルフ”に魅せられたプログラマ。 『Short Coding ~職人達の技法~』執筆、『世界で闘うプログラミング力を鍛える150問』翻訳

twitter: @ozy4dm
blog: http://d.hatena.ne.jp/Ozy/