Electro Reminiscence

クイズの問題作ってたら飽きたので問題解いてた。一大学クイ研の会長として色々とダメな気がする。アレです。気分転換です。気分転換のほうが時間かかったけど。 問題は ここ 。まずある大きさの int 配列を受け取って、後で指定されたインデックスから終端までのスライスの unique を取った時のサイズを返す。 自分の正解答案は以下。 注目すべきは 8 行目以降。ていうかぶっちゃけこの部分は他の人の答案パクりました。最後の言い逃れとして一応 D 言語以外の答案を見るようにしました。というかフィルタかけたら僕以外に D 言語の答案無かったし。だいたいみんな C++ で解いてた。でも僕の上のプログラムでも 78ms だし十分匹敵する速度は出せてた。 閑話休題。ソートされてない配列のユニークを取りたければ連想配列を作る。で何も考えずに端っこから順番に連想配列に突っ込んでいく。んで ans[i] には後ろから i 個分のスライスをユニークにした配列のサイズを入れておく。これで、この問題で求められうる全ての場合の解答が O(n) で用意できる。よく分かんないから値はブーリアンにしました。でもメモリはめっちゃ（7300KB）使ってた。まあ範囲内だし気にしない。 最初 std.algorithm.uniq を使ったら全然意図しない配列が返ってきた（Ruby 脳なので Array#uniq 的な動作を期待してた）。よく考えてみたらどうも隣り合う要素が一致してるかどうかしか判定してないみたいで、こういう実装の仕方は C++ でも同じらしい。何でこういう風にするかというと O(n) で終わるので速いから。で、これを使うとき配列はソートされてなければいけないので、arr.sort.uniq みたいにして使いなさいよと。std.algorithm.sort は O(nlog(n)) で終わるので、Ruby Array#uniq みたいに O(n^2) かかるよりはさっきみたいにしたほうが速いということか。でも知らないと分からないよね……情弱辛い。 ちなみに僕は最初はインデックスを求められる度に後ろから l 個のスライスのユニークを求めてたので、大きさ 10^5 の配列のユニークを 10^5 回調べたら 10^10 だからそりゃあ TLE で死ぬのも当然だわなあと。また 1 個勉強にな

プログラミングがしたくなったけど特にすることがなかったので適当に競プロの問題を解いていた。ら、めっちゃ時間かかった。でも最終的にはかなり可読性の高い感じのするプログラムに。UFCS っょぃ。アルゴリズム自体は何でもないただの貪欲法（だよね……？）だけど D 言語的に得るところが結構多かったのでメモしておく。 解いていたのは こちらの問題 。 自分の解答はこちら。 L4：配列の宣言。大きさの決まっていない配列は宣言することが出来ない。Ruby 脳なのでハマってしまった。要素数の分からないデータを配列に取り込む時ってどうすればいいんだろう。1 個ずつ length を広げながら代入するとか、予め十分大きな配列を用意しといて init なままの要素を消すとか？ L5：foreach で配列の中身を初期化する。1 個目の elem は配列の中の要素の代表を表す。配列の中身を変更するような操作をする時は、ref を付けて参照にしないといけない。 L6：std.array.map の返り値は MapResult とかいう謎の型で、これは map を評価する前の中間物みたいなもの。つまりこの時点で map はまだ評価されてない。ということなのだと思う。この型に直接 sort とかするためには std.array.array を送る。そうすると map を評価させて int[] とかが得られる。 L10：これも上のと同じ。ちなみに std.array.sort は SortedRange を返す。困ったら typeid(var).writeln; すれば型名が分かる。 L16, 18：std.array.reduce は先行評価らしい。ちゃんと最終的な結果をすぐに返す。 ところで UFCS の関数呼出し演算子の省略っていつから出来るようになったんですかね？　もしかして最初から？　実行したら普通に動いて後から括弧忘れてたのに気付いた。Ruby は基本的にメソッドチェーンで書くことが多いけど writeln とかにも UFCS が使えるのはいいですよね。括弧よりもピリオドのほうが断然打ちやすいし。ジェネリック引数の括弧も省略できるみたいだけどそこまでするとかなり見づらい感じがしそうなのでしない。ていうかラムダ式みたいなのを文字列で送るって一体どうなってるんだろう……。

というわけで解いてみました．とりあえず F# で．Scala で書いても Ruby とほとんど同じになりそう（ひどい）． どうでもいいけど，いつも通り SyntaxHighlighter でハイライトしようとしたら案の定 F# が対応してませんでした．ということで苦肉の策で gist．ちゃんと埋め込み用の js 用意されてたよ．神か． 1 行目．いきなり標準入力で躓く．標準出力は printfn があるけど標準入力は F# のライブラリには無い？　調査不足ではありますが．まあでも副作用（最近覚えた）だししかたないね．ということで .NET です． 2 行目．タプルを使った束縛は Ruby の多重代入に似てる．めちゃ便利．F# で型キャストはどうやるのかな，と思って調べてみたら，変換したい変数に変換先の方の修飾子をつけるだけでいいっぽい．これは int.Parse より楽．あと地味にインデックスの指定でつまづきました．括弧の前にドットが要るのはどうなんだろう．外せなかったんだろうか．fsi にダメ出しされまくりました． 3 行目．ごく普通の条件分岐です．これぐらいの短さだったら三項演算子使いたいんだけど実装されてないっぽい．ここは C# に軍配． 5-10 行目．関数型っぽく再帰を使って書いてみました．ちなみにここはコンパイラの警告で網羅されてないパターンに (1, 5) が挙げられてたんだけど，5 で割った剰余って 0-4 しかないからありえないよね，と思うんですがどうなんだろう．僕の気付いてない落とし穴があるんだろうか． 12 行目．F# の出力はどうも整形形式しかないっぽい． print x とかやりたいよなあ．まあ引数に直接関数の返り値を渡せるのは便利かな（関数型はみんなそうだが）（ていうかオブジェクト指向もだけど）（もしかしたら C でも出来る？）（コンパイル型もちゃんと勉強しましょう）． 一番の大きな壁は入出力だけど，これ 1 回の実行で多ケース実行されるパターンの問題だったらどうするんだろう？　いちおう立場上はマルチパラダイムだから再代入可能な変数を使えばいいんだろうけど，何か負けた気がする．Scala なら var を使えばいいけど Haskell とかだとどうするんだろう． まとめ：全体的に勉強不足でした．

まあ学年は自動で上がるんですが．ということで近況報告です．2 ヶ月も間を空けて何が近況なのか． タイトルの通り，年度が変わって学年が 1 つ上がりました．1 年次の修得単位数は 36.5 単位です．はい．6 単位落としました．落ち込んだりもしたけれど，私は元気です．必修の英語は 3 年次で 2 つとも回収する予定だから大丈夫なのです． プログラミングですが，最近は Ruby は全然書いてません．むしろオブジェクト指向の言語自体全然書いてません．その代わりに関数型プログラミング寄りの言語を少しかじっています．家の MBP で Erlang，家の Win8 でF#，学校の計算機で Scala というぐちゃぐちゃな生活を送ってますが，とりあえず Erlang は構文が謎（甘え）なのと，この言語自体がもともと並列処理だとか分散処理だとかサーバ向けの言語で，自分が書きたいのはそっちじゃないよな，ということで一旦やめになりそうです．進めたら進めたで新しい見地が広がりそうなのですが．やはりまだオブジェクト指向が残ってないと分かりづらい，ということでマルチパラダイムの Scala と F# を続けてみたいと思います．大学図書館の蔵書で，Scala は『Scalaスケーラブルプログラミング第2版』があるのでいいんですが F# はオライリーの『プログラミングF#』ぐらいしかないので困ったなあと．ブログとか見てるといわゆる『実践F#』が有名らしいんですが．置いてくれないかなあ． 音ゲーについて．弐寺は☆ 12 がポチポチとつき始めました．が，まあまだ☆ 11 を進めるしかないかなと．十段を受けたらクッキーの前半癖地帯を抜けたのでびっくりしております．九段は強欲で 20% 残るようになったのでそれなりに成長したかなと．ポップンはコンチェ EX は初見でクリア出来ました．ワラベステップまだ出してません．弐寺のやりすぎです．ドラムは最高が 7.15 とかになりました．目標の 8.00 までもう少し．ギターは依然判定が合わない．ボルテは neu リミ EXH を初見でクリアできた，とはいえラストノートでボーダーに乗ったぐらいなので修業がやはり必要．ダンエボ最近やってません．ルカルカ難しい．恋愛サーキュレーション覚えるかどうか迷いどころ． クイズ研究会は新入生が5人ぐらい入りそうです．4

いい名前が思いついたので，ブログ名とアドレスを変更してみました．元ネタは有機 EL の Electroluminescent です（調べてみたらこれで 1 語らしい）．最初は Tales Weaver の "Reminiscence" という曲が好きなのでそれに肖ろうと思ったのですが，Reminiscent と Luminescent って似てるよな，と連想したことからこうなりました．ちょうど意味的にも Blog っぽいし．やっぱこういうのはピンときた時に決めないと．今までの『足跡』なんてあってなかったようなものなので．というわけでこれからもよろしくお願いします．

タイトルめっちゃかっこつけたけども．最近このブログでプログラミングの話してなかったんで久しぶりに． そういえばバーコードの最後って誤り確認用の符号なんだよな，それぐらいのプログラムだったら自分でも書けそうだな，と思ってから一体何ヶ月が経ったのか．ようやく手を動かしました． まずは普通に書いたものから． jancode = gets.chomp sum = 0 jancode.reverse.each_char.with_index do |e, i| i.even? ? sum += e.to_i * 3 : sum += e.to_i end print "Check Digit is: ", (10 - sum.to_s[-1].to_i).to_s[-1], "\n" JANコードについて調べてみるとどうやらいろんな桁数のものがあるとのことだったので，普通にひっくり返して偶数桁と奇数桁で場合分けすることに．しかも 10 から引く数が 0 だったときにチェックディジットも 10 になってしまうので，余計なことは考えずに「計算結果の下 1 桁」にしておきました． で．ここまでなら誰でも書けるんですよ．たぶん．これをどうやって一行にまとめるかが勘違いプログラマーの腕の見せどころなわけで．見せる腕無いけど． puts (10 - gets.chomp.reverse.split("").map(&:to_i).each_with_object([]).with_index{|(e, arr), i| i.even? ? arr << e * 3 : arr << e}.inject(:+).to_s[-1].to_i).to_s[-1] で，出来たのがこれと． 標準入力から読み込み→改行文字取り除き→ 1 文字ごとに分割し→各要素を文字列から数字にし→それぞれの要素について→添字もつけて→偶数桁なら 3 倍して，奇数桁ならそのまま新しい配列にプッシュしていく→その配列の総和を取る→その数の 1 桁目を 10 から引いた数の下 1 桁がチェックディジット という流れでした． each_with_object の部分はいろいろ迷走しました．each

新年明けました．今年もよろしくお願いします． 前回の更新が約 2 ヶ月前なので，当時から今まで起こったことをとりあえず． 2 学期が終わって 3 学期が始まりました．筑波大学開校以来最後の 3 学期であります．感慨は特に無いです．早く終われ．2 学期の単位ですが，当然フル単でした．専門基礎科目は 5 つ受けたうち哲学だけ C で謎でしたが，その他の 4 つ（情報システム概説，基礎数学 A，情報リテラシ実習，プログラミング演習Ｉ）は 全て A だったのでまあいいです．3 回休んでリーチがかかってた科目も A が来ててそれも謎．その他一般教養とか英語とか二外とかは C は無く安泰． 音ゲーに関してはそれほど目立った進展は無いです．ポップンではゾディアックオラクル 7 EX を 6 回目ぐらいでようやくクリアしました．もう二度とやりません．弐寺は大晦日に Sun Field 穴イージーが点きました．Lincle 九段を初めて受けてから，この曲に何らかのランプを点けるのが一つの目標だったのでかなりうれしいです．DP も初めましたが全然進歩しないので辛いです． プログラミングは全然何もしてません．驚くほど何もしてません．強いて言うならば，大学の図書館にあるすごい H 本が空いたのでそれを頑張って読み進めてます．関数型言語けっこう面白いけど使いどろこが見出せないというか使いこなせそうにないというか．いや読むぶんには面白いんですが．オブジェクト指向はけっこう分かりやすかったしそこらへんの言語を結構書いてた（D 言語もそうだし）のでなかなか頭が固いです． また，12 月は初めてクイズのオープン大会に参加してきました．2 つ参加して両方とも学生オープンでしたが．Person of the Year ではその問題の難度とそれに易々と答えていく大学生を目の当たりにしてカルチャーショックを受け，STU the Seventh ではクイズ大会を観戦することの楽しさを味わいました．中でも印象的だったのは STU の得点表示プログラムで，久し振りに「あんなプログラム作ってみたい！！」と思わされました．家に帰って早速 CUI で実装してみたり．一念発起して D 言語の GUI 開発環境を整えようとしましたが Qt でも Gtk+ でもさっぱり上手く行きませんでした．やはり C# を勉強す