2017年2月23日

ポン引きリクルータ

 業界説明会で、京都に行ってました。
 学生さん少ないなあ・・ということでキャッチ開始。
 けっこう話を聞いてくれました。

 

2017年2月19日

葉っぱ様来訪

 植物を導入した!
 思ったよりデカかった。

 

2017年2月 4日

ニモナイゼーション

 煮物化。
 卵・蒟蒻・人参・牛蒡・鳥モモ、が自分のヘビロテ。
 この組み合わせこそ志向だと信じて疑いません。

2016年12月29日

焦がし醤油仕立て

 角煮の大量生産。
 これで勝つ。
 焦がし醤油仕立てなのです(「焦がしてしまった」の婉曲的表現)。

 

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手後の状態でグループ分けしつつ、さらに変則的な再帰コード+メモ化、ということで、慣れてる人には楽ですが、そうでない人には厳しかったのではと思います。

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 という等式へのプラス(+)マイナス(-)の入れ方の数を問う問題。
典型的な動的計画法の問題だと思います。きわめてまっとう。

2016年6月 5日

電気工作ビギナーズ

 工作シリーズ。
 ホームセンターで適当に材料を集めて、「懐中電灯」が完成しました。
 豆電球とか触るの、いつ以来だろう。

 

 でも子どもには、ついでに買ってきたモーターの方がウケてた感ある。

2016年1月18日

ビールおいしい

 去年末のぎりぎりに申し込みをしたふるさと納税の返礼品がきた。
 「もともと自分の居住地の環境整備とかに使われるはずだったお金を、私利私欲のために縁もゆかりもない町に流すのはどうなのか」と疑問が頭をよぎりつつも、「まあそれを言ったら節税全般だってそうか」と自分に言い聞かせ、あれこれ申し込み。

 ビールおいしいです。
 

2015年12月 7日

合コンにいく

 先週に引き続き、今週も勉強会。渋谷。
 Goというプログラミング言語のカンファレンスなので、GoCon→通称合コンなのだそうです。
 先週のJavaのとは、明らかに客層が違うね。

 

 それはそうと、渋谷に行くと、あまりの人の多さにいつも「今日って祭りか何かあったっけ?」と思ってしまう。

2015年11月28日

たまにこういうの行く

 勉強会で新宿へ。ずーっと、まる一日。

 帰り道、イングレスで適当なポータルを強化してたら、自宅周辺でよく見る人の名前のポータルがあって超びびった。

 

最近のコメント

月別 アーカイブ