« CodeIQで出題した問題が20問を超えてました | ホーム | 焦がし醤油仕立て »

2016年12月23日

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

 前回の記事から引き続き。「CodeIQ」で出題した問題の背景とか感想とかです。
 この記事では21~30問目について書きます。
 1~10問目はこちら、11~20問目はこちらです。


「ロング・ロング・ストリング」問題 問題文・解説 みんなのコード
CodeIQ MAGAZINEで解説記事を書き始めたこともあり、定番トリックをひととおり紹介しようと思いました。そこでネタ帳にあった「常用対数」と「二分法」を組み合わせたらできたのがこの問題。常用対数なんて日常生活でほぼ使わないから、数の桁数とリンクしてるなんて、忘れてるよね。


「ディビジョン・ナイン」問題 問題文・解説 みんなのコード
プロジェクトオイラーで過去に提案した問題(#491)を少し易しめにアレンジし直しました。O(log n) で解けるため n は相当大きくできるのですが、今回は上限を 20 とかなり小さ目に設定しました。理由はいくつかあって、このぐらいの上限でも愚直解をじゅうぶん排除できること、これ以上大きくすると変数の桁あふれが生じてしまうこと、他の想定解ではそこまで n を大きくできないこと、を考慮しました。ちなみに自分が考え付いただけでも3通りの解き方が可能です。この解説記事ははてなブックマークで結構な数のブックマークがつき、教育的に価値があったのかなあと思っています。


「コード・トライアスロン2」問題 問題文・解説 みんなのコード
3つの問題を出題。1つ前の問題の答えを次の問題の入力として、3問続けて最終的な答えを出すという問題でした。ネタ帳に、出題するほどの出来でない問題ネタがいくつかあって、それを一気に消化。・・・という企みだったのですが、このタイプの問題は作るのが非常に難しい。前の問題の答えが、次の問題でちょうどよい大きさの値になってないといけないし、初めの問題が誤答ならちゃんと最終的な答えもズレるようにしないといけない。そんなわけで非常に苦労した問題。
しかもこの問題では1つ目のラングレーの問題でやらかしてしまいました。入力値によっては、double 型で解くと精度が十分でなく、間違った値を出してしまうのです。テストケースの入力値では問題ないのですが。浮動小数点数を使う問題は鬼門だなあと思い知らされたのでした。


「レッド・アンド・ホワイト」問題 問題文・解説 みんなのコード
1次元セルオートマトンを題材にしました。シェルピンスキーのギャスケットを生成するルール90というパターンです。この問題がリリースされる3日ほど前に、CodeIQで別の出題者さんの出した問題(これ)が本問と非常によく似てました。ぱっと見は別の問題なんですが、どちらも入力値 n を2進表記したときの 0 と 1 の並び方で答えが得られるというものでした。いったん自分の出題を取り下げてもらおうか迷うほどでした。が、見た目の全然違う問題が根っこのところでかなり近いところにある、というのはそれはそれで面白いんじゃないか、ということでそのまま出しました。


「マイナー・ゲーム」問題 問題文・解説 みんなのコード
漫画「ライアーゲーム」で登場した少数決ゲームが元ネタ。投票回数の期待値を求める問題です。ある意味、出オチともいえる問題でした。なんやかんやで複雑な問題になったのは仕方ないかなあ。


「アフター・ドット」問題 問題文・解説 みんなのコード
a÷bが有限小数となる(a,b)の組の個数を求めるというシンプルな設定の問題。自分の問題ネタの発掘法はおよそ4パターンほどあって、①大学の入試問題から、②有名な定理から、③有名なアルゴリズムから、④日常ネタから、というのが多いです。これはしいて言えば②ですが、むしろ④の方が近いかも。高校数学のサイトで目にとまって、そこから考えを膨らませてたどり着きました。


「プライム・ホッパー」問題 問題文・解説 みんなのコード
上の分類の、③有名なアルゴリズムから、のパターンで考え付いた問題です。要は幅優先探索の話が出したくて出題しました。数学的な要素はほとんどないと思います。


「マルチプル・テーブル」問題 問題文・解説 みんなのコード
かけ算の九九表を使った問題って作れないかなーというところから始まって出来上がりました。掲載後のコード公開で、素因数分解の結果をつかったシンプルな公式が得られたのは面白かったです。


「トライアングル・メイズ」問題 問題文・解説 みんなのコード
フラクタル図形を題材にした問題が出したいなあと思い、試行錯誤の結果できたのがこれ。漸化式を出してコーディングするだけだと簡単すぎるので、剰余の周期性のネタと重ねてまともな難易度にしました。
このころから、「F(n) を 1000003 で割った余りを求めよ」という出題の仕方をするようになりました。個人的には、XXX で割った余りを求めよ、という問題は、何を計算してるのか実感が湧かないからあまり好きではないです。できれば、F(n) の値そのものを求めさせる問題の方が好き。それが無理でも、下6桁とかを求めさせる方がまだまし、という気持ちです。本問は、10^6 など 10 のべき乗の数での剰余が非常に小さい周期しか持たなかったので、やむなく 1000003 を選んだのでした。


「デジタル・ルート」問題 問題文・解説 みんなのコード
個人的にはかなり難しい問題だと思いますが、ここ数問では最多の 162 名の方に挑戦して頂きました。やっぱり難易度の読みは難しい。1手後の状態でグループ分けしつつ、さらに変則的な再帰コード+メモ化、ということで、慣れてる人には楽ですが、そうでない人には厳しかったのではと思います。

月別 アーカイブ

このブログ記事について

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

ひとつ前のブログ記事は「CodeIQで出題した問題が20問を超えてました」です。

次のブログ記事は「焦がし醤油仕立て」です。

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