« 電気工作ビギナーズ | ホーム | CodeIQで出題した問題が30問になりました »

2016年12月 6日

CodeIQで出題した問題が20問を超えてました

 リクルートキャリアが提供しているIT技術者向けサイトの「CodeIQ」で、数学の出題者をやらせてもらっています。
 現時点で通算31問の問題を出題しました。
 したがってとっくに出題は20問を超えてるのですが、何も記事を書いてませんでした。
 この記事では、11~20問目の背景とかを書きます。10問目までのはこちら
 21問目以降についてはおいおい書きます。


「フィズ・バズ・エクストリーム」問題 問題文 解説 みんなのコード
 包除原理を学んでいただくために出題しました。包除原理を知らないとおそらく手も足も出ないので、難易度的にはやや高い問題なのではと思います。
 この手のいわゆる「知っていればすぐに解ける」タイプの問題は、知識ゲーなどと言われたりしますね。もちろんあまりよくない意味で。そういう意味では、もうちょっと気の利いた出し方があったのかも。まあ、質にこだわりすぎるとネタ切れになるし、これはこれで重要な話題なので出しました。


「カット・アンド・スクエア」問題 問題文 解説 みんなのコード
 偶数桁の数で、上半分と下半分の 2 乗の和が元の数に等しくなるものを探すという問題。
 自分の出題ではよくある、○○という条件をみたす数を探せという問題です。やみくもに候補を総当たりして探すのでなく、満たすべき条件から逆算して、探すべき範囲を絞り込むのが王道パターンです。うまくやると、下半分の総当たりだけで答えを見つけることができます。
 評価5を得るだけなら上の方法で十分ですが、本問には上級解が存在します。変数変換を行うことで、整数を2平方和で表す問題に帰着でき、既知のアルゴリズムを使って、もっと大きなnに対しても高速に答えを出すことができます(10^n+1 の素因数分解に依存しますが)。こういう2段オチで高速化ネタがあるのは良い問題と思います。


「スロット・マシン」問題 問題文 解説 みんなのコード
0~9の数字をランダムにn個選んだ時のもっとも多く出た数字の回数の期待値を求める問題です。けっこう難しい問題でした。
解法には、大きく分けて、自然数の分割との関連に着目するやり方と、動的計画法で解くやり方の2通りを想定しました。おおむね期待通りの傾向でした。同じ問題でもこういうふうに複数のやり方で解けるのは面白いです。


「ステップ・アップ・サム」問題 問題文 解説 みんなのコード
与えられた自然数を、連続する自然数の和で表す方法を求める問題です。
今回から、手動採点から自動採点に変わりました。テストケースを考えるというのは初めての経験なので色々と戸惑いました。巷には、テストケースにも強いものと弱いものがあるようです。不十分な解法でもクリアできてしまうものは弱いテストケースとされ、低品質とされているようです。強いテストケースを作るには、挑戦者がやるであろう不十分な解法をできるだけ幅広く予想して、それでNGとなる入力値を選ばなければなりません。これを一人の人間で読み切るのはかなり難しいですね。


「エース・ナンバー」問題 問題文・解説 みんなのコード
16進表記でAが最大 10^10 個並んだ数の、10進表記の下6桁を求める問題。
トリック自体は定番で、周期性を利用するのがひとつと思います。あとは今回ならではの方法として、等比数列の和の公式を用いるやり方。
本問から、CodeIQ MAGAZINE にて解説記事を書かせていただくことになりました。もともと速筆ではなく、作問よりも時間がかかることもありますが、やっぱりこういう解説をしっかり書くのって大事だよねと思い、今も続けています。


「セカンド・イクエイション」問題 問題文・解説 みんなのコード
二次方程式の解の条件に関する問題です。
CodeIQ MAGAZINE の解説記事とセットで問題ネタを考えるようになりました。とりあえず定番トリックをひととおり紹介しようと思い、まずは対称性を用いる問題を選びました。


「ツイン・トライアングル」問題 問題文・解説 みんなのコード
↑で対称性の話題を出したので、次はピタゴラス数の話題かな・・と考えて作りました。ピタゴラス数といえば直角三角形だよね、ということで平面幾何の問題に。
平面幾何の問題は、作るのが非常に難しいです。自分のテーマである「高速化」と結びつけにくいからです。今回はかなりうまくいきました。上級解として、ピタゴラス数を生成する魔法の3×3行列の話もすることができて、個人的にはたいへん満足している出題です。


「ルート・パワー」問題 問題文・解説 みんなのコード
(1 + √2 + √3 + √5)^n を展開したときの有理数の項を求める問題。有理数の項と √2、√3、√5、√6、√10、√15 の項からなる8変数の漸化式を導出します。定番なので、分かる人にはすぐ解けますが、そうでないとかなり厳しい問題だったと思います。
とはいえ漸化式の導出は骨の折れるところ。それだけではなく、さらに本問では行列のべき乗に落とし込んで、計算量を O(log n) まで落とさないとクリアできません。漸化式をそのまま O(n) で計算するやり方でもクリア可能にすべきだったかな・・と後になってから思いました。


「スクエア・カルテット」問題 問題文・解説 みんなのコード
2変数からなる不定方程式の解を求める問題です。一般にはディオファントス方程式と呼ばれています。王道的な解き方として、因数分解された形で考察することで、道筋が見えてきます。
いわゆる2段階の高速化ネタがある問題でしたが、1段階目の高速化を行った時点でクリアできる上限値としました。CodeIQ は競技プログラミングのサイトではないし、ほどほどのところでクリア可能にしておいて、発展的な話題は任意でおまかせしよう、というスタンスがようやく固まったと思います。


「プラス・マイナス・ゼロ」問題 問題文・解説 みんなのコード
□1□2□3□4...□n = 0 という等式へのプラス(+)マイナス(-)の入れ方の数を問う問題。
典型的な動的計画法の問題だと思います。きわめてまっとう。

月別 アーカイブ

このブログ記事について

このページは、riverplusが2016年12月 6日 23:48に書いたブログ記事です。

ひとつ前のブログ記事は「電気工作ビギナーズ」です。

次のブログ記事は「CodeIQで出題した問題が30問になりました」です。

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