« ジョイントへ | ホーム | 出汁巻きマスター Lv.1 »

2017年8月12日

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

 リクルートキャリアのプログラマ向け転職サイト「CodeIQ」で数学の問題を出題しています。
 これまでの出題数が通算40問になったので、問題の背景とか感想とかを書きます。
 この記事では31~40問目についてです。
 それ以前については、1~10問目11~20問目21~30問目

出題回数を重ねると、「もっと凝った問題を出したい」「数学的な背景のある問題を出したい」という気持ちが強くなって、作問のペースが落ちてくるのがこの頃の悩みですね。気負いしないで続けていきたいと思います。


「ディビジョン・サム」問題 問題文・解説 みんなのコード
(n!)^n という非常に大きな数の約数の和を求める問題。プロジェクトオイラーや自分の出題で典型的な解法パターンである「素因数分解した形で考える」話をしたくて出題しました。nの上限がそこまで大きくないので、素因数分解した形で表せれば、比較的シンプルなコードでクリアことができます。
この問題にはさらなる高速化トリックを仕込みました。等差数列の和の公式と、剰余の逆元の知識を使うことで、出題よりずっと大きなnに対しても答えを出せます。この頃から、こういう複数段階の高速化ができるという出題のスタンスが固まりました。1段階目の高速化ができればクリア自体はできて、そこから先の高速化は解き手にまかせてTwiterで語りましょう、というスタンスです。


「スパイラル・ウォーク」問題 問題文・解説 みんなのコード
格子路をらせん状に歩く距離に関する問題。①問題の条件を定式化して、②コードで解きやすい形に変形し、③コーディング、④高速化、という、自分の出題ではよくあるパターンです。
本問は①と④が難しいですね。①については、それなりにシンプルにしたつもりの考え方を解説記事に書いたつもりでしたが、後になってもっとずっとシンプルな考え方に気づいてしまいました。(進んだ距離)=(通過した交差点の数)+1 なんだから、交差点の数を数えるだけの話ですよね、という。こういうのがスッと思いつかないところがまだまだだなあと思います。


「キャリー・オーバー」問題 問題文・解説 みんなのコード
問題ネタを探すときによくやるのが、数学用語を片っぱしから思い浮かべてみるというもの。意外と、小学校の教科書にある用語からでも、発想はふくらむものです。「筆算のくり上がり」のキーワードから広げてできた問題です。解法は動的計画法で、ちょうどいい難易度のものができました。


「ルーム・アンド・ルーフ」問題 問題文・解説 みんなのコード
数学プログラミング業界?の有名問題です。代表的なのは、2008年のGoogle Code Jamの Round 1A C でしょうか。そのまま出すのも芸がないなあ、ということで、前半の数学パートとして図形問題が差し込まれました。無理くりに足した感じはどうしても否めないですね。


「プライム・ペア」問題 問題文・解説 みんなのコード
オイラーのトーティエント関数といえば、プロジェクトオイラーでは頻出中の頻出といえる関数です。たくさんの話題と関連してます。これまで一度もトーティエント関数を出題してないのは自分的にだめよね、ということで作りました。ただ、関数の定義を述べるだけでそれなりの分量が必要 & 自分の出題ポリシーとして問題文はできるだけ簡単にしたい、ということで、まずはφ(n!)を求める易しい問題にしました。今後、もっと進んだ問題を出したいです。


「クロッシング・ワード」問題 問題文・解説 みんなのコード
自分の出題の定番ネタのひとつに、行列のべき乗に帰着させる、というのがあります。複数の変数の漸化式が、一つ前の変数の線形結合で書き下せるなら、線形結合の係数行列のべき乗を計算することで高速に変数の値が求められるというものです。過去にも何回か出しました。
このネタを使った問題をまたそろそろ出したいなー、ということで題材を長らく考えていて、ようやくピンと閃いたのがクロスワード。ルールはみんなが知ってるのでかなりコンパクトな問題文にできました。が、一筋縄ではいかない問題で、かなりの難問になりました。


「ロンリー・ルーク」問題 問題文・解説 みんなのコード
期待値の線形性を使った問題を出したいなあ、と思って作りました。...といいつつも、実際は京大の入試問題(1998年前期 第5問)の設定をそのまま使いました。
もともとは、nの上限を10^5にしていたのですが、出題ディレクターの方から「難度を下げた方がよいのでは」とコメントが入りました。けっきょく、いわゆる総当たりの方法でクリアできるようにして、期待値の線形性を使った解法は、出題後のお楽しみネタにすることにしました。


「タンジェント・フラクション」問題 問題文・解説 みんなのコード
今年の京大の入試問題(2017年前期 第3問)から発想を広げて作りました。基本的なアプローチは多項式の因数分解なのですが、問題文をできるだけ図形問題に見せかけて、ギャップを楽しんでもらえるように工夫しました。どこまでうまくできたかなあ。
さらに本問では、定番ネタである、r^2+1 型の素数をふるいで見つけるアルゴリズムの紹介をすることもできました。


「ウッド・キーパー」問題 問題文・解説 みんなのコード
そろそろ数え上げの問題を何か出題したいなあ、と思い、丸だの四角だのをノートにあれこれ書きならべて試行錯誤した末にできあがりました。とはいえOEISではとっくにカバーされていました(A005169)。「fountains of coins(コインの噴水?)」と呼ばれているようですね。問題自体は、漸化式を出してメモ化再帰でコーディング、という典型的なパターンでした。


「キャンディ・アンド・チョコレート」問題 問題文・解説 みんなのコード
数学の数え上げの分野で有名なヤング図形の話をしたくて出題しました。キャンディの分け方とチョコレートの分け方のそれぞれを求める問題です。一見は独立した問題ですが、実は2つはまったく同じ値になります。その背後にあるのが、ヤング図形を介して2つが互いに共役な関係にあるという事実。この事実に気が付かなくてもクリア自体は可能ですが、ぜひその理由を考えてみて下さいね、というのが真の出題意図でした。

月別 アーカイブ

このブログ記事について

このページは、riverplusが2017年8月12日 12:11に書いたブログ記事です。

ひとつ前のブログ記事は「ジョイントへ」です。

次のブログ記事は「出汁巻きマスター Lv.1」です。

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