0-1ナップサック問題入門(if文とfor文と配列を前提とする)

この記事ではナップサック問題を解くプログラムをPythonで実装します。 再帰関数も動的計画法も使わず、if文とfor文と配列を使って解くことを目指します。 ナップサック問題とは ナップサック問題とは次のような問題です。 いくつかのアイテムと1つのナップ…

ゆるふわ競技プログラミングオンサイト@FORCIAを開催しました

ゆるふわ競技プログラミングオンサイト @FORCIAという競技プログラミングの有志オンサイトイベントを開催したので、企画者目線で振り返りを書きます。

8:30起床を支える技術

8:30起床を支える技術 研究者を目指す普通の学生諸君にに影響されて、朝8:30起床を頑張っている。今の所、成功率100%なので方法を紹介したい。 まとめ 自分は自力で朝起きられるという幻想を捨てる さっさと寝る アデッソ MY-96とNature Remoを使う

Matplotlibで間隔が疎らな時系列データを可視化する

クリスマス前後でしばらく寝込んでいたのですが、今週は体調が戻りました。 折角なので寝込んでいた時期の体温の変化を可視化してみます。 等間隔になっていないデータをどうプロットするか 体温はずっと測っていたわけではないので、時間軸の感覚が不揃いで…

2次元の凸包を求めるアルゴリズムと応用について

2次元の凸包(convex hull)を求めるアルゴリズムについてまとめました。また、凸包の応用先を列挙し、凸包を使って解ける競プロ問題を集めました。ギフト包装法(Gift wrapping algorithm),QuickHull,グラハムスキャン(Graham's scan),Monotone Chain,Chan's a…

『WE ARE LONELY,BUT NOT ALONE. ~現代の孤独と持続可能な経済圏としてのコミュニティ~ 』の読書メモ

『WE ARE LONELY,BUT NOT ALONE. ~現代の孤独と持続可能な経済圏としてのコミュニティ~ 』を読んだ。ファンコミュニティについて多くのキーワードを使って説明している。とても読みやすい。

『アウトプット大全』の読書メモ

学びを結果に変えるアウトプット大全 (Sanctuary books)作者: 樺沢紫苑出版社/メーカー: サンクチュアリ出版発売日: 2018/08/03メディア: 単行本(ソフトカバー)この商品を含むブログを見る 基本法則、話し方、書き方、やり方、トレーニング法の5章。根性…

Bashでタブ補完を自作する(同じオプションを2回サジェストしない実装付き)

Bashのタブ補完って便利ですよね。 私の一押しはgitのコマンドを補完してくれるgit-completion.bashです。 めっちゃ便利なので使ってない人は是非使いましょう。 さて、Bashの補完が作れるということなのですが、実際どう作るのか気になったので調べながら実…

Bashで配列の積集合・差集合を求める

Bashで文字列の差集合を求める関数を実装しました。 結構つまりながら実装したのでブログに書いておきます。 考え方 集合Aと集合Bの積集合(共通要素の集合)を求める。 集合Aと「1. 集合Aと集合Bの積集合」で重複していない要素を求める。 実装 except() { …

Pythonで文章から複合名詞や「〇〇の〇〇」といったフレーズを抽出する

複合名詞や「〇〇の〇〇」といったフレーズを、文章から取り出したい場面は多くあります。 この記事ではPythonを使ってそれらを抽出する方法を2つ紹介します。 janomeのTokenFilterを使う negimaを使う janomeのTokenFilterを使う Janomeは@moco_betaさんが…

「Rust LT #2 〜いま使う!Rust〜」のイベントレポート

最近仕事でRustも書いているので、LT会行ってみようということでRust LT #2 〜いま使う!Rust〜に参加枠で参加しました。記念にブログを書きます。 トーク2本とLT5本と、盛りだくさんな内容でした。 会場 主催のどらやき(@dorayaki_kun)さんさんの勤務先で…

n-ominoの列挙(Redelmeier's algorithm)

n-ominoとはn個の正方形で構成されるポリオミノ(Wikipedia)。 n-ominoの列挙を行うRedelmeier's algorithmをPythonで実装した。 速度検証 反転・回転を考慮しないn-ominoを列挙し、個数を数えた。所要時間は下記の通りだった。 n n-omino elapsed[s] 1 1 0.0…

ポリオミノの敷き詰め問題をDancing LinksとKnuth's Algorithm Xを使って解く

ポリオミノの敷き詰め問題を解くプログラムを書いた。効率的に解くためにDancing Linksというデータ構造を実装し、Knuth's Algorithm Xを使用した。 ポリオミノの敷き詰め問題とは こういうパズルがAmazonで売っている。結構難しい。 Amazon | 明治ミルクチ…

『選択しないという選択』のメモ

『選択しないという選択』を読んだ。デフォルトをおいてオプトイン・オプトアウト(選択しないという選択)にするか能動的選択を迫るか、どっちがどういうときにいいのか、更にパーソナライズを進めるとどうなるのか書かれている。 選択しないという選択: ビ…

urllibとBeautifulSoupでスクレイピングするときに調べたこと

Python3.6でリクエスト部分にurllib、パース部分にBeautifulSoup4を使って、スクレイピングをするときに調べたことを中心に使い方をまとめた。

メモ: 集合知プログラミング2章 推薦を行う

2章 - 推薦を行う 協調フィルタリングについての章 類似度を求める関数 入力 どのユーザーが、どのアイテムに、何点付けたか。 どのユーザーとどのユーザーの類似度を計算するか。 pref = [ {'A':5, 'B':4, 'C':1, 'D':0}, {'C':1, 'D':0}, {'A':4, 'B':2, '…

Competitive Programming Advent Calendar 2015, 2016まとめ

Competitive Programming Advent Calendar 2015, 2016を中心に、言及されている記事を集めました。 私が特に「いいね」と思ったものについては★を付けています。

Python3, C++11, JavaScriptでの実行時間計測

Python3,C++11,JSの実行時間計測まとめ

Anacondaで環境構築するときの一例

Anaconda便利ですね。WindowsでPython使うとインストールが不便なパッケージがたくさんあって困ります。 Anaconda使いましょう。 今回はソースコードを整形してくれるautopep8を使いたかったので環境を新しく作ってインストールしてみました。 conda create …

ツイート時刻から生活リズムの可視化をする

もう10年も前の映画になるらしいですが、デスノートでLが被害者の死亡時刻を重ねると容疑者が大学生であることを割り出すシーンがあったのを覚えていますか? あるいはGitHubでPunch cardって出るじゃないですか。なんとなく格好良くて好きです。 同じような…

もっと気持よくyukicoderで遊ぶためにテストケースを自動実行する。

solorab.net このブログを読んだんですが、謎の呪文が1行だけ貼ってあって????ってなりました。 テストケースは自動で確かめる ちょうどTwitterでも強い人はテストケースを自動実行しているようだということを見ていたので、自分もオシャレに自動でテス…

素数は通れませんの裏話

Advent Calendar Contest Advent Calendar(以下ACCAC) 2015でNo.308 素数は通れません - yukicoderを出題させていただきました。 www.adventar.org 自分はyukicoderの★3を解くのにヒーヒー言う僕が、ACCACの初日に★4の問題を作れてしまったので、 作るときに…

そのミスはどう処理しましょうか?

この記事は、Board Game Design Advent Calendar 2015の10日目の記事ですが、26日目に書かれました。 僕は週に8時間ほどボードゲームで遊びます。 ボードゲームで遊ぶのは楽しいです。 もう一回もう一回と夜通し遊んでしまうことも多々あります。 遊ぶだけの…

シフトを自動で組むプログラムをPythonで書いた

アルバイトのシフトを組むのって大変らしいですね。 調べてみると「ナーススケジューリング問題はNP困難」などと出てきます。 ただ、頭のなかで考えていた問題は労働者ごとの職能に差がないものだったので、ナーススケジューリング問題よりは簡単かもしれな…

paizaのプログラミングで彼女を作るやつを全クリアした

paiza.jp 彼女欲しいって言ってたら友達にオヌヌメされたので解いた。全体的に制約が超ゆるいので何でも通っちゃう。 一応水着も手に入れたけど、僕がほしいのは生身の彼女なんだ! 「めがね」ゲットチャレンジ! 本当にやるだけ。制約が小さいので全部見れ…

普段競技プログラミングばっかりやってる僕がSiv3Dを触ってみた話

この記事はSiv3D Advent Calendar 2015 - Qiitaの14日目の記事です。 普段はプログラミングといえば競技プログラミングというレベルで競技プログラミング大好きな僕のSiv3D体験記です。 Siv3Dとは Siv3D は C++ で楽しく簡単にゲームやメディアアートを作れ…

SymPyで辛い計算をちょっと辛い計算にする

この記事はPython Advent Calendar 2015 - Adventarの7日目の記事です。 SymPyというシンボル計算ライブラリを使ったことがありますか? 最近、卒論のお手伝いをしてもらっているライブラリです。 日本語の情報が少なくて困ったので自分用にという意味も込め…

Brainfuckの処理を書いてみた

Brainfuckとは Brainfuck - Wikipedia 命令が8個(><+-.,[])しかないプログラミング言語 def brainfuck(s): a = [0] * 10 ptr = 0 i = 0 l = len(s) while i < l: if s[i] == '>': ptr += 1 elif s[i] == '<': ptr -= 1 elif s[i] == '+': a[ptr] += 1 elif s…

スペース区切りの文字列をリストに格納する方法の比較

競技プログラミングの入力では、一行にいくつかの数字がスペース区切りで並んでいるケースをよくみる。 例えば、No.16 累乗の加算 - yukicoderの Python3でこれらを一つのリストに格納したい時、一番早い方法はなんだろうか。 map関数を使ってからlistにする…

川渡りパズルを解く

川渡りパズル(男が狼、ヤギ、キャベツを持って川を渡るが船には1つしか積めないみたいなやつ)をPython3で解いてみました。