2018年7月 7日

船・飛行機・波

 遊覧船に乗って、羽田空港まで飛行機を見に行く。
 雨の予報で直前に大量のキャンセルが出たのだけど、奇跡的に持ち直したため、ほぼ貸し切り状態というリッチな状態。

 

 飛行機の写真って、意外と撮るのがむずかしいと思い知りました。

2018年7月 1日

富士山もみえる

高い所が好きなので、高い所に行きました。
文京シビックセンターの展望台。
ここから見える光景、全部でいくらぐらいで買えるんだろう・・とすぐにお金のことばかり考えます。

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)のコードでもぎりぎり正解できたのは想定外でした。

2017年11月25日

カラーパレット

 紅葉を探す旅。
 東京駅から後楽園まで。

 

 

2017年11月11日

あたらしい道楽

 おなかの調子が微妙だったので、気まぐれでカフェインレスコーヒーなんてのを買ってみた。
 某カフェで頼んだときは「何これこの出がらし?」みたいな味だったけど、これは普通にちゃんとしたコーヒーの味。
 そして何よりも、深夜にコーヒーが飲めるという生活変わる感じがすごい。

 

2017年9月16日

出汁巻きマスター 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つが互いに共役な関係にあるという事実。この事実に気が付かなくてもクリア自体は可能ですが、ぜひその理由を考えてみて下さいね、というのが真の出題意図でした。

2017年6月18日

ジョイントへ

 大学サークルの現役たちの演奏会でした。
 シーシャンティーは自分たちもやったので懐かしい。
 人数は減ってるけど減ってるなりにまとまってた感じ。

 

2017年6月17日

ひとつだけのアジサイ

 今年の庭のアジサイは、なんだか失敗。
 春先の枝刈りが不十分で栄養が散らばって、枝ばかりワサワサ伸びたんじゃないかと。
 咲いたの、ひとつだけ。

 

2017年6月11日

ソーヴィニヨンブラン!

 いまいちばん好きなのがこれ。オーストラリアのやつ。

 

 周りに植物を並べ、インスタ映えするレイアウト作りに余念がありません。

最近のコメント

月別 アーカイブ