2週間連続でRatedなコンテストに出ました。本日はBeginnerの方です。
atcoder.jp
先週はスパッと500点問題が解けたので本日も5完するぞと意気込むも・・・残念ながら4完で終わりました。しかもペナルティ2回。そのうち1回はとてもしょうもないミス。悔しい・・・
3問目まではScheme、4問目のみJavaで解きました。
続きを読むAtCoder Regular Contest 118 に出ました
久々にRatedなコンテストに出ました！しかもレギュラーコンテストです。
atcoder.jp
得点がA-300、B-400、C-500ということで、
・WAやTLEなしでBまでをなるべく早く解く
・できればCも解きたい
・D以降は高得点問題だが、時間内は粘りたい
という方針でした。
結果としては、無事にA〜Cの3問をミスなくACでき、それぞれ開始から
A問題-15分後
B問題-45分後
C問題-85分後
にACとなりました。
B問題が、考え違いでのやり直し＆実装＆ミスないかチェックに時間がかかりました・・・
全体を通して問題の中に出てくるのは数列くらいとかのシンプルな問題文が多く、苦手である「なんか知らんデータ構造を使うんやろな・・」みたいな問題がなくて新鮮でした。とはいえC問題を解いたあとに取り組んだDもFもさっぱり糸口が見えませんでしたが・・・
では、A〜C問題の解答の方針とコードをまとめていきます。
全てracket(scheme)で解きました。
本当にどうでもいいことですが、全問題を通して、racketで提出したのは僕一人でした。嬉しい。
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)
で簡単に使えることがわかりました！
今回はその使い方について書いていきます。
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で書く方が楽だと感じます。
続きを読む