« 山下定例 | ホーム | マイクロソフトへの課金が止まらない »

2015年5月20日

CodeIQで出題した問題が10問になりました

 リクルートキャリアが提供しているIT技術者向けサイトの「CodeIQ」で、数学の出題者をやらせてもらっています。
 このたび出題した問題が10問になったので、背景のこととかを書きます。


■ 出題方針について
 これまで自分は、プロジェクトオイラーで出題者を務めていました。
 プロジェクトオイラーのチームでは、出題に当たっていくつかのルールがあります。その中でも重要なのが、オリジナルな問題であること。初期の問題の多くは、いわゆる典型問題と呼ばれるものですが、ここ数年で出される問題はほぼ全てチームで独自開発した問題です。ウィキペディアやOEISなどで、ずばりの解答が載ってないことが必須の要件です。
 一方で、こちらのCodeIQでは、そのあたりは特に深くこだわらず出題することにしました。競技プログラミングのサイトではないためです。それよりも、挑戦者の方に、新しいテクニックや数学の概念を知ってもらうことを目的にしました。
 どの問題も、いわゆる愚直解(ブルートフォース解、ゴリ押し解)では長い時間がかかってしまう問題を、いかに短い時間で解けるようにアルゴリズムを改良できるか、という視点で作っています。


「リターン・ナンバー」問題 難易度★ 問題文
 初出題にも関わらず190名という多くの方に挑戦して頂き、思い出になった問題です。
 Automorphic Numberという数学の概念を題材にしました。10^9に対する剰余系で、2乗したときに元の数に戻るような整数を求めよ、という問題。
 一番下の桁の数字から1桁ずつ数字を確定していくやり方を想定しました。
 それとは別の方法として、n(n-1) mod 10^9 = 0 の形に持ち込んで n と n-1 が互いに素であることを利用する解法も考えられます。実際には3分の1ほどはそちらの解法でした。
 おそらく最速解は、n mod 2^9 = 0 と n mod 5^9 = 1 の連立合同式(あるいはその0,1の入れ替わり)に変換して中国剰余定理に持ち込むやり方だと思います。


「ビリオン・ダラー」問題 難易度★★ 問題文
 「超階乗」をテーマにした問題です。
 超階乗の値そのものを計算する必要はなく、2の素因数がどのような規則で並ぶかを観測すれば解けます。
 ただ、本問では、C/C++言語+高速PCの組み合わせだと、いわゆるブルートフォース解でも数秒以内という制約条件でもそれなりに解けてしまうというのが出題者の盲点でした。
 ブルートフォース解を拒絶し、かつプログラミング言語間の速度差を考慮しつつ、さらに64ビット整数の範囲で解けること、などの条件を同時に満たすような設計って難しいなあ、と思い知らされた問題です。


「デジタル・タブー」問題 難易度★ 問題文
 0, 3, 6, 9 の数字を使わずに整数を数えたときの 10^7 番目の項を求める問題。
 6つの数字で数を数えるのだから、元の数を6進数に変換すればそれでOK? と思いきや、それではうまくいかないというイジワルな問題でした。
 「0」が使えないので、実際には単純な6進数とはいかず、けっこうややこしい桁の進み方になります。
 難易度は★1つかな、と思ってましたが、想像以上にややこしかったようで、挑戦者数は54人と少なかったです。


「ピッキング・カード」問題 難易度★★ 問題文
 某数学書で紹介されていた問題です。
 3種類の解き方を想定しました。
 一つは、103枚のカードから8枚を選ぶ選び方を全て列挙するやり方(NG解)。
 一つは、競技プログラミングでよく使われる動的計画法(DP)で解くやり方(通常解)。
 一つは、103と8が互いに素であることを利用して、Binomial(103,8)÷103 で一発で求解してしまうやり方(上級解)。
 思惑どおり、ほとんどの挑戦者が通常解で解いておられ、上級解に気付いた挑戦者は約1割ほどでした。


「パワー・オブ・フィボナッチ」問題 難易度★ 問題文
 べき乗とフィボナッチ数を組み合わせた巨大数の下6桁を求める問題です。
 周期性をうまく利用して、巨大数そのものの計算を避けることがポイントです。
 ちなみに検討当初は、「3^3^3^3^3^3^3 の下6桁を求めよ」という問題にするつもりでした。が、手の出しようのない挑戦者が多いのでは、と思い改めて作り直しました。


「ブラック・ブロック」問題 難易度★★ 問題文 みんなのコード
 30個の碁石を並べたときの、最長の黒石の連続数が5となる並べ方の数を求める問題です。
 k次のフィボナッチ数に帰着させる解き方を想定していましたが、実際にはそれで解いた人はごく少数で、大半がDPで解いていました。
 おそらくいろんな解き方があり得るだろうとは思っていましたが、自分の解き方がここまで少数派だとなんだか修行不足だなという気になりますねえ。


「フィーバー・ナンバー」問題 難易度★ 問題文 みんなのコード
 答えが正解かどうかを挑戦者自身がかんたんにチェックできる問題ってウケるんじゃないか、と思って作問しました。
 整数を一つ一つ調べるのでなく、「最終形から逆算する」ことを学んでもらうために出題しました。一応オリジナル。
 とはいえ、本問では、ごく一部の挑戦者から、度肝を抜くような上級解を提示され、ひっくり返りそうになりました。詳細は みんなのコード を見てください。
 こういうことはプロジェクトオイラーでも度々ありましたが、ここまで鮮やかだとぐうの音も出ません。


「コモン・マルチプル」問題 難易度★ 問題文 解説 みんなのコード
 プロジェクトオイラーでも定番な、整数を素因数分解された形で考える問題です。
 ただこの問題は解き方がワンパターンでほぼ全員が同じ方針で解いてました。
 ちょっとつまらない問題になってしまったかな・・・と思っていたら、Twitter上ではコードゴルフ(より少ないバイト数でコーディングすることを目指す遊び)が繰り広げられ、なんというか、この人たちすごいよ、って思いました。


コード・トライアスロン 難易度★★ 問題文 解説 みんなのコード
 CodeIQのリニューアル記念ということで出しました。
 単品の問題として出題するにはインパクト不足だなあ・・と思っていた問題ネタが自分のアイデア帳にいくつかあったので、うまいことくっつけました。
 1問目の答えを使って2問目を解き、さらにその答えを使って3問目を解く、というのは新しい試みだったと思います。
 ただこの問題はパラメータの選び方に相当苦労しました。Ideoneで5秒以内の実行時間で解けることを制約条件としたため、ほどよい大きさがパラメータが各問に渡るよう、問題の順序や最初のパラメータなど、かなり試行錯誤しながら選びました。たぶんもうやらない。


「バイナリ・カウント」問題 難易度★ 問題文 解説 みんなのコード
 2進数の1の個数を数える問題ということで、定番ネタだったかもしれません。
 やはりこの問題もTwitterでゴルフ祭りが始まりました。
 短いものはRubyで60バイト程度ということで、ゴルフ苦手な自分にはなんというか未知すぎる領域です。

月別 アーカイブ

このブログ記事について

このページは、riverplusが2015年5月20日 22:32に書いたブログ記事です。

ひとつ前のブログ記事は「山下定例」です。

次のブログ記事は「マイクロソフトへの課金が止まらない」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。