投稿

2月, 2019の投稿を表示しています

自作AtCoderツールをリファクタリングした

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 ### 何やったの 自作AtCoderツールをリファクタリングしました。 GitHubリポジトリはこちら <a href="https://github.com/habroptilus/atcoder-tools">habroptilus/atcoder-tools</a> ### 経緯 以前、AtCoderでよくやる処理を自動化したいな、みたいな気持ちになって、とりあえず簡単にツールを作りました。 以下の記事がそれにあたります。 AtCoderを始めてみて面倒に感じた作業をシェルスクリプトにしてみたAtCoderで使えるコード自動テストツールを作った やったこととしては * 指定したコンテストのディレクトリと雛形コードを作ってくれる * サンプルケースを取得してきて自分のコードを手元でテストする * すべてサンプルを通っていたら自動で提出する という機能を実装しました。 が 最初はpythonだけで競技プログラミングをしていましたが、C++に手を出したり他の言語で書いてみたりすることもあり、その度にコードをコピーして言語によるところだけ書き換えて、、、としていてとてもイケていませんでした。 * 人様に見せられる最低限のコードにしたい * 今後対応する言語を増やす際に簡単に増やしたい * 自動提出するかどうかもオプションとして指定したい などなどいろんなお気持ちが重なったので、リファクタリングするに至りました。 あと、最近研究でデータパイプライン構築でluigiを使う機会があり、せっかくだしAtCoderツールにも導入したい!と思ったのも動機の一つです。 ### 改修前 改修前は、以前記事に書いた通り、サンプルケースをスクレイピングする部分やコードをテストする部分、提出する部分をpythonで書いていて、それらをシェルスクリプトで動かしていました。 ただ、それぞれ引数はargparseを使ってもなくてとても分かりづらかったり、そもそも言語の情報は引数になくすべてベタ書き(提出時に言語の…

AtCoder:ABC118-D(Match Matching)を復習する

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 コンテスト自体には参加していないですが、練習のため解きました。 ABC118回はCまではすんなりいけて、Dでつまったので、復習。 自分でこのレベルも解けるようになりたい。 ### 問題 マッチが$N$本与えられた時に、作れる数字の最大値を求める問題。 数字`1,2,3,4,5,6,7,8,9`を 1つ作るには、それぞれちょうど `2,5,5,4,5,6,3,7,6`本のマッチ棒を使うという設定。 デジタル表示みたいなあれだと思う。 問題ではさらに、使っていい数字が$M$個指定されます。 使っていい数字列は$$A_1,A_2,A_3,...,A_M$$と与えられます。 ### 考察 #### 自分で考えたこと なるべく桁数は多い方がいいから、本数のコストが少ない数字を使いまくればいいのか〜、じゃあ1を作りまくればいいのでは、と考えた 使える数字も指定されているから、その中で一番コストが小さいものを貪欲に。。。と思ったけどn本ちょうど使わないといけないから貪欲には無理なのか。じゃあDPで解くのかな。 本数をxとして 「$DP[x]$:ぴったり$x$本使った場合の最大値」として更新していけばいいのかな、と考えましたが、保持しておく数字が大きすぎて難しいかなと思いました。 リストとして持っておいて、新しく数字を追加する際に毎回降順ソートする、桁数はリストの長さとして取得するなどしていくのでできるのかも?と思いましたが、結局数値の比較の際にリストの要素を全部結合しないといけないのでだめそう。 #### 解説をよんで 途中まではあってて、DPに入れるものが「作成できる数字の最大値」ではなく「最大桁数」でした。 **DPに保持していく値は必ずしも求める答えではない**、肝に銘じておきたい 最大桁数ならDPできます。 桁数が決まったら、なるべく大きい数字を左から埋めていけばおっけーですが、ここもちょっとわからず。 解説を見るとわかったのですが、 その数字が一番左に入りうるかは、つくったDPテーブルを見ていけば確認できるのですね。 ある数字を作るのに必要な…

AtCoder:ABC119に参加した

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 AtCoderのABC119に参加しました。 全完は出来なかったですがレートはちょっとだけあがってました。笑 本番後に通したDも含めて、参加記録です。 ### A 問題文をよく読んでいないので実在するものをちゃんと考えてしまいました、、、 2019年しか入力されないんですね。。 ```python y, m, d = map(int, input().split("/")) if y >= 2020: print("TBD") elif y <= 2018: print("Heisei") elif m >= 5: print("TBD") else: print("Heisei") ``` ### B ```python N = int(input()) s = 0 for i in range(N): m, u = input().split() if u == "BTC": s += float(m) * 380000 else: s += float(m) print(s) ``` これは大丈夫だと思います。 intとかにしないようにってところでしょうか ### C これで時間を取られてDが間に合わずでした。 Nが小さいから全探索なんだろうなーと思って書き始めたのですが、途中でいろいろバグらせてかなしでした。 竹を`(group1,group2,group3,unused)` の四つのグループに分けます。 $4^8=2^{16}$なので、グループ分けを全通りためしても間に合います。 同じグループになったものは合成し、合成だけでA,B,Cを目指して作ったものが下のコードのtempです。 tempをつくるときの合成魔法のcostを計算し、targetであるA,B,Cとtempを比較して足りない分を残りの魔法で微調整します。…

SentencePieceをpythonスクリプトから使ってみる

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 modelの学習はコマンドラインからやるのが普通、みたいな記事をみましたが、pythonからでもできるのでそちらでやります。 他の記事ではわざわざsubprocessを使ったりしていますが、普通にpythonライブラリにtrainerを用意してくれているのでありがたく使えばよいです。 日本語の記事がなかったので一応書きます ### sentence pieceとは 文章をいくつか区切ってそれらを機械学習モデルに食わせる、みたいなことはよくやります。 MeCabを使って形態素解析するのがよくやられる手法です。 Mecabでは対応する辞書を使って文章を分割します。辞書にはneologdとかがよく使われます。 これでも上手くいくことも多いですが、語彙数が大きくなってしまうことや、分割の仕方が分割したいデータセットに適していないこともあり、問題点だったりします。 分割の仕方もこれから分割する文書から学習したほうがいい気がするのはわりと直感的な気がします。 sentence pieceでは、与えた文書の中で高い頻度で現れるフレーズは、多少長くても一つの単位として認識します。 逆に短いフレーズでもあまり高頻度で現れない場合はフレーズを分割し、よく出現する単位まで細かく分割します。 mecabで辞書を使って分割するとなんでも細かく分割されますが、sentence pieceではその文書ではよく使われる言い回しなどは一つの単位として認識されるようになり、よりタスクのドメインに適している分割が得られると期待できます。 また、語彙数を指定することで、語彙数が膨大になることを防ぐことができます。分割したフレーズにidをふってモデルの入力とする場合には、入力の次元が語彙数になるので小さいと嬉しいです。 ハフマン符号みたいです。よく現れる文字列には短い符号長を割り当てる、みたいなところが似ています。 ### インストール ```bash pip install sentencepiece ``` ### pythonスクリプトで使う importします ```pyt…

GitHub PagesとHugoでポートフォリオサイトを作った

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 就活やらバイトやインターンなど、面接する機会が多くなってきたこともあり、自分の経歴やアウトプットをまとめる場が欲しくなりました。 このブログは特に名前など出していないので、ここにポートフォリオ的なものを載せるのはちょっとあれだし、ということから、別にポートフォリオサイトを作ろうと思いました。 他にも、知人のエンジニアにGitHub Pages + 静的ページジェネレータで技術ブログなりポートフォリオなり作るのがイケてるんだぜ、って言われて使ってみたかったという理由も大きいです。 ブログはBloggerで結構カスタマイズしちゃったし、まあ困ってはないので乗り換える気にもならず。 GitHub Pages + 静的ページジェネレータを試す場としてポートフォリオは手軽で良さそう!と思って始めました。 ### 技術選定 選定といっても大したことはせず。 GitHub Pages + 静的ページジェネレータは多くの人がやっていて、記事とかもたくさん転がっているのでそれらをざーっと眺めてみました。 静的ページジェネレータにもいろいろ種類があって、今回僕がつかったHugoのほかにも、GitHub Pagesの標準としてJekyllというものや、node.jsで作られているHexoというものもあるらしいです。 自分の好きなReactを使ったGatsbyというものも最近注目されているなど、気になるものはいろいろありましたが、 * 良さげなテーマデザインがある(テーマが豊富) * 解説記事が多い * ブログ用ではなく自己紹介ページ用のテーマがある あたりを基準に選びました。 ### 開発の流れ HugoはGo言語で作られているらしいですが、Go言語はインストールする必要がなかったです。手軽。 1. 雛形となるディレクトリを作る 1. themeをダウンロードしてくる 1. ダウンロードしたテーマのファイル,ディレクトリをディレクトリ直下の対応するところにコピーしてくる 1. ローカルにサーバーを立ててプレビューを見ながら開発(直下の方をいじる) 1. ある程度できた…

AtCoder:ABC117-Dに苦戦したので復習した

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 AtCoder:ABC117に参加しましたが、前回の記事に書いた通りDが嘘解法でした。 悔しいので復習していたら苦戦したので備忘録に載せておきます。 前回の記事はこちらになります。 AtCoder:ABC117に参加した 先頭からいくつかの桁はKと同じで、ある桁でKが1、Xが0になって、その後ろは貪欲にやる、というのをKの桁が1になってる全ての桁について調べてmaxをとる、という解法が想定解法っぽいので、それで書き直す。 前処理部分は前書いたのと同じです。 ```python N, K = map(int, input().split()) A = list(map(int, input().split())) binary = [bin(a) for a in A] bin_K = bin(K) ma_len = max([len(e) for e in binary] + [len(bin_K)]) - 2 B = [e[2:].zfill(ma_len) for e in binary] bin_K = bin_K[2:].zfill(ma_len) ``` ```python def latter(div, ma_len, B, bin_K): X = [] for i in range(div, ma_len): num_0 = 0 num_1 = 0 for j in range(len(B)): if B[j][i] == "0": num_0 += 1 else: num_1 += 1 if num_1 >= num_0: X.append("0") else: X.append("1") return X ``` サン…

AtCoder:ABC117に参加した

イメージ
とりあえず参加したので記事を書きました。 コンテスト中はDまで解けましたが、Dがあやしいです。 今度またやり直そうと思います。とりいそぎこんなかんじで。。。 ### A ```python x, t = map(int, input().split()) print(x / t) ``` pythonだと`x//t`としない、とかそれぐらいですかね。 ### B ```python N = int(input()) L = list(map(int, input().split())) if sum(L) > 2 * max(L): print("Yes") else: print("No") ``` 定理の通り、Lの最大と残りの辺の和の大小を比べればよく、こんなかんじ。 ### C コマをうまく$X_i$をカバーするようにおく問題。 最初、$X_i$の固まっている集団の中心にコマをおいて行きたくなるけど、真ん中におくと行ったり来たりして無駄なので、一つのコマが担当する集団が決まったら、その集団の端っこにおくのが良いことがわかります。 集団に分けたらそれらの端っこにコマをおいて端から舐めていけばいいので、集団の端から端の長さ分だけコストがかかるわけです。 考えやすくするために$X_i$をソートします。 コマが一つだと、$X_i$の最小から最大までの長さ分動かないといけなくて、二つになるとその間のどこか一つの移動を省くことができます。 一般にコマが$N$個あれば$N-1$個の間の移動を省略できるので、ソートした後の$X_{i+1}-X_i$が大きいものから$N-1$個省いていけば残った部分が答えです。 ```python N, M = map(int, input().split()) X = list(map(int, input().split())) X.sort() sa = [X[i + 1] - X[i] for i in range(M - 1)] sa.sort() if N >= M: print(0) else: print(sum(sa[:M - N])) ``` $N\ge M$の部分を忘れて1WAでした。はあ。 ### …

AtCoder:ABC106-D(AtCoder Express 2)を解いた

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 解法も自分で思いつけなかったし、解説みてからもバグらせ続けて悲しい。 復習します。 ### 問題 D - AtCoder Express 2 電車が何本か走ってて、それぞれ走る区間が与えられている。 そこで、いくつかの質問に答える問題。 質問は、 ある区間の間に完全に含まれる電車の本数は? というもの。 ### 考察 問題の理解のために数直線みたいなものを書いて実験するも、よくわからず。 区間ごとに通る電車の本数をいもす法みたいな感じで足していったら何かに使えるんじゃ、とか考えたりしたけど全然違った。 今回の問題は、区間の端っこが重要な問題なので、区間に対して本数を足していくのは、その情報が失われるから使いそうにない、みたいにあたりをつけられるようになりたい。 解説を読んで、数直線ではなく二次元配列上で考えると簡単な問題に置き換わります、といわれて、はあそうですか、となった。 こんなん気付かんよ、、、と言いたくなりましたがぐっとこらえて精進。 昔から解説見てから復習として問題を解き直すときが一番メンタルやられてつらいので、やりたくないですが、次も間違えるのはもっと嫌なので復習。。。 二次元配列上に置き換えると、クエリは枠線に置き換えられて、この枠の中にある要素の和が答えになると。なるほど。 ### 実装 解説にあるように、各クエリに対して$O(N)$で答えたら$O(NQ)$ですが、今回の制約なら通る!と書いてあったのでそう書いたらTLEしました。 ```python N, M, Q = map(int, input().split()) A = [[0] * N for _ in range(N)] for _ in range(M): l, m = map(int, input().split()) A[l - 1][m - 1] += 1 questions = [] for _ in range(Q): p, q = map(int, input().split()) questions.…

Bloggerで技術ブログを書くためのカスタマイズ

イメージ
こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 Bloggerでブログを書いています。 技術ブログ的な側面が大きいブログなので、コードもたくさん載せる機会がありますし、機械学習的なことも多くやっているので数式も載せたりします。 markdownに慣れているので、markdownで記事が書けると嬉しいな、という気持ちもあります。 ということで、 * markdownが使える * シンタックスハイライトがかかる * 数式をtex形式で書ける あたりを実現するためにBloggerをカスタマイズしていきます。 (はてなブログでいいじゃんと言われそうですが。。。。) ### markdown `markdown.js`っていうものがあります。 markdownをhtmlに変換するもの。 以下の記事を参考に進めました。 <div class="separator" style="clear: both; text-align: center;display:none;"><a href="https://1.bp.blogspot.com/-TW8CahuaDYs/XFUIJjc4e1I/AAAAAAAAAdo/DUO2Gdv6x8gYEdJ_Njrj-zkRZem7BO-_ACLcBGAs/s1600/blogger.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-TW8CahuaDYs/XFUIJjc4e1I/AAAAAAAAAdo/DUO2Gdv6x8gYEdJ_Njrj-zkRZem7BO-_ACLcBGAs/s320/blogger.png" width="200" height="200" data-original-w…