2018年3月アーカイブ

2018年3月 4日

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

 リクルートキャリアのプログラマ向け転職サイト「CodeIQ」で出題した問題の感想です。
 先月をもってCodeIQでの出題は終了することになりました。これまで40問目までについては解説記事を書いたので、この記事では41~47問目について書きます。
 それ以前については、1~10問目11~20問目21~30問目31~40問目

3年前に、Project Eulerの開発の負荷がちょっとしんどいなあ・・と思っていたところにたまたまCodeIQの方から声をかけて頂きました。それからわりと好き勝手に出題させてもらえました。どれだけ集客に貢献できたのかは正直自信ないですが、つまらないという感想はほとんど目にしなかったのはよかったです。あとProject Eulerのときと違って、広く楽しんでもらえるような視点で問題を考えるのはおもしろい体験でしたね。

今後は・・特に出題先のアテはないので、どうするかなーという感じです。

「ディバイド・アウト」問題 問題文・解説 みんなのコード
ウィルソンの定理の話題を出したいなあと思って、定理の内容からアレコレひねくり回しているうちに出来上がった問題です。
定理を使うことで計算量がグーンと一気に削減! というのが理想的なパターンだったのですが、今回は計算量のオーダー自体はほとんど変わらず、コードがいくらかシンプルに書けるという程度でした。
みんなの解答を見てると、それなりの方が意図を見抜いていてうれしかったです。


「カウント・スリー」問題 問題文・解説 みんなのコード
久しぶりに二分探索の問題を作りたいなあという動機で作りました。二分探索の問題は過去にも出しました(これ)が、逆関数の存在を露骨に匂わせる、なんだか不自然な問題になってしまったなあ、という反省がありました。今回はわりと自然な感じの問題にできたのでよかったです。


「ループ・トラッキング」問題 問題文・解説 みんなのコード
ロジスティック写像を題材にした問題を出したくてずっと温めてたネタです。自分の出身の複雑系科学専攻という分野で、まず最初に学習する写像です。F(x)=ax(1-x)という写像において、パラメータa=0から始めて次第にa=4まで増やしていくと、xに写像を繰り返し適用させた軌道がどんどんランダム的になっていくというもの。
CodeIQの問題として成立させるために、離散化させて、循環検出のアルゴリズムの話に結び付けました。問題自体もさることながら、出題後にいろいろ可視化してみる遊びが楽しかったです。


「ストレート・ラインズ」問題 問題文・解説 みんなのコード
ノートにペンでごちゃごちゃ書き戯れているときに思いついた問題です。解説記事では、総当たりの解と、公式を使う解の2種類の解き方を紹介しました。後者のほうが圧倒的に高速ですね。公式自体はOEISに載っており、実際の挑戦者にも、OEISのページのリンクをコードのコメントで書いて下さった方がいました。ただ自分的には、この公式の意味するところを理解するのに苦労し、解説記事を書くのにものすごく時間がかかりました。


「ペア・ドロップ」問題 問題文・解説 みんなのコード
ババ抜きをテーマにした、ド直球な確率の問題です。高速化のためのトリックは必要ないですが、確率の問題としてはかなりハードではないかなと思います。いろんな解き方ができそうだなと思ったので、nの上限はだいぶ緩めにしました。


「タワー・ビルディング」問題 問題文・解説 みんなのコード
動的計画法の問題は定期的に出しましょうね、ということで、ちょっとネタ切れ感は否めないですが作りました。
とはいえ別解の方では、剰余の逆元の話ができたり、階乗n!の逆元の配列を作る話ができたりと、けっこう話題を膨らませることができました。


「LCM・パレード」問題 問題文・解説 みんなのコード
いい問題だったと思います。等差数列の和の公式を使う解き方と、包除原理を使う解き方の2通りを想定しました。後者のほうが高速でカッコイイです。が、自分自身、後者の解き方を編み出すのには相当苦労しました。ルノアールで数時間ねばってて、ようやくたどり着けたときは嬉しかったです笑。
ちなみに別のクリア可能な解として、GCDの値を配列にキャッシュすることで、O(n)のコードでもぎりぎり正解できたのは想定外でした。

月別 アーカイブ

このアーカイブについて

このページには、2018年3月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2017年11月です。

次のアーカイブは2018年7月です。

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