プログラミングを上達させたい

情報学専攻の大学院→放送局でCMの営業など@大阪→IT営業@東京

racketのmoduleでUnion-Find木が簡単に書ける(AtCoder競プロ典型 90 問 #12)

racketにハマって以降、AtCoder競プロ典型 90 問を簡単なものからracketで解いてます。
atcoder.jp

ちなみにracketにハマったときの記事はこちら。
frfrfrfr.hatenablog.com

racketのモジュール使って簡単に書けました!みたいなのがあるといいなぁと思いながらも、標準出力や2次元配列すら書きにくいracket・・・
解き方を考え、思いついたら「racket + 使うアルゴリズム」とかで調べていると、この12問目で解答に使う"Union-Find木"については

(require data/union-find)

で簡単に使えることがわかりました!
今回はその使い方について書いていきます。

続きを読む

AtCoderで"Racket"が使えるでんか!

記事名の「でんか」は僕の出身地である、香川県の方言(「さぬき弁」という)です。それも結構強めのさぬき弁です。
ざっくり言うと、東京での「じゃん」、関西での「やん」にあたります。
(東京)さっき食べてたじゃん
(関西)さっき食べてたやん
(香川)さっき食べとったでん
という感じです。
これを話したら「おでんくんみたい」と言われたことがあります。おでんくんみたいではなくない?


さて、AtCoderのルールのページを見ると、言語に"Racket"が追加されていました。

続きを読む

Twitterのbotを作った(竹原ピストルの親戚bot)

仕事でエンジニアの方々と接していると、普段の作業の自動化ツールやwebページなど、"実際に使えるもの"を作っているのを見る場面が多く、「自分ももっとそういうのができたら」と思ってしまいます。これまでそういうのにトライしたことはあるのですが、取り組んでみては途中で挫折、という感じでした。
でも、なんか急に思い立ったので、やってみます。

作るもの

俳優・歌手である竹原ピストルさんに似た名前を生成して呟くbotを作ります。

続きを読む

Schemeでの、組み合わせの生成などについて(AtCoder Regular Contest 114のA問題)

引き続き、生活に余裕があるときはAtCoderに取り組んでいます。この前あったヒューリスティックコンテストも出たかったのですが、スケジュールが合わず・・・
無理なくやれる範囲でやっていきます。

さて、今回解いていたのはこの問題です。
atcoder.jp
300点問題。答えが意外とでかくなるケースがあり、答えの候補を2,3,4...と探していくとTLEになってしまうという問題です。最大になってしまう場合というのは数列X内に50以下の全ての素数が出てくるケースで、その場合は2,3,5,,,41,47という50以下の素数(15個)をすべてかけた数が正解となり、6*10^17くらい大きくなります。よって候補を制限せずの全探索ではアウトですね。

この場合は、答えの候補として「50以下の素数のうちいくつか(1個のみ〜全部)を掛け合わせたものたち」に絞れば十分ということになります。これをSchemeで解く際に、色々トライしてみたので、その記録を残します。

続きを読む

Schemeの環境構築(vim)&Gaucheのツリーマップを使った

AtCoderProblemsのBoot camp for BeginnersをSchemeで解いていっています。
多種多様な問題があるし、解き進めているのが可視化されてモチベーションも上がるし。このサイトよすぎませんか?少し自分の税金が投入されても全然いいくらいです。

さて、その中で「数の探索、追加、削除をO(log_n)で行いたい」という問題がありました。こちらです。
atcoder.jp
そういう問題になるとJava〜といつもはしていたのですが、たまたまGaucheでTree-mapというデータ構造があるのを見つけました。
ツリーマップ (Gauche ユーザリファレンス)
これがあればできるじゃん、ということでコーディングしようとしたのですが、僕が使っているDrRacketという開発環境では、Gaucheが使えなさそうで・・・
※AtCoderのScheme処理系はGauche

また、最近自分のvim操作の遅さで仕事でも少しうまくいかなかったこともあり、
・vimでScheme(@Gauche)を書けるように
・数の探索、追加、削除をO(log_n)で行うようなコードを作成
してみることにしました。

続きを読む

AtCoder Beginner Contest 183 に出ました

2ヶ月ちょいぶりに、リアルタイムでコンテストに出ました。出ました達郎
atcoder.jp

前回、E問題(500点)、F問題(600点)が解けたので、今回もE以降を解くぞと意気込んだものの、結果としてはA〜D問題の4完(48分)でした。E問題、解けそうと思いながらも解けず・・・・Dはなんだかんだで(時間はかかったものの)一発ACだったので、D問題の速度をアップさせるのとE問題が解ける確率をあげるように進めていきたいです(AtCoder ProblemsのTrainingモードというのを知ったので、それ進めようと思います)。

それでは、解法とコードを書いていきます。A,C,DはSchemeで、BはJavaで解きました。最近は、文法の縛りが少ないSchemeで書く方が楽だと感じます。

続きを読む