AOJいちもん

eclatはrustが難しすぎてはげたので、
go langで実装しました。

https://github.com/carushi/Reimplementation/blob/master/eclat.go

コマンドライン引数でminimum supportとアイテムセットが入ったファイル名を渡すと動きます。
わりときれいに書いた♥︎ʕ◔ϖ◔ʔ
あとは最近ずっと頭の中で考えていた....



地図集めの問題を....



ついに解いた.....！！

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011


n人がバラバラに地図を持っていて、
スケジュールが空いている日には集まって誰かに地図を手渡せる。
最短ですべての地図が一人に集まる日はいつかという問題。






グラフで考えたり、距離行列みたいな感じでランクを求めて解こうかといろいろ考えてみたけど、
そこまでややこしいことをする必要はまったくなかった！＼(^o^)／

イメージはあみだくじ！




で、やったのは

  1. 最終日を決定
  2. その日に集合できるメンツにフラッグをたてる＆空いている日にフラッグをたてる
  3. フラッグがたっている日に集まれるメンツかつまだフラッグが立っていないメンツに対して「フラッグをたてる＆空いている日にフラッグを立てる」
  4. 3をフラッグが立っている最終日に近い方から繰り返しながら順番になめていく
  5. 全員にフラッグがたったらその日数で可能、たっていなかったら最終日を延ばして繰り返し

という感じ。
できるだけ後ろの日数で渡せる人に渡すことでパターンをつくす感じ？
日数はMaxが30になっているので日数をなめる行程はあまり計算量に影響しないのがポイントですね。


データを読み込むときに適当に日数範囲の枝刈りはしています。



Rankは92位/442なのでまぁまぁきれいに書けたでしょうか。


うむーん(´・ω・)

コメント

コメントを投稿

このブログの人気の投稿

旧姓を失った研究者が海外でも活躍するためには

イメージ
突然ですが結婚しました！ そして苗字の珍しさで負けたので、夫の姓にすることに話し合いで決まりました。 今まで名前と生年月日という情報をもとに個人が識別されていたのに、名前が変わるって大丈夫なの！？と思ったらやっぱり大変でした。 ということで、それに伴う名前変更作業などについて記録しておきます。 （これを参考にして何か問題が起きても責任はとれませんので悪しからず） 　 　 そもそも仕事での名前をどうするか？ 研究者にとって、今までの名前で検索して業績がひっかからないというのは致命的です。 私は一応生物系（？？？）の研究者なので基本的にPubmedを参照することが多いですが、 知り合いの研究者の名前をPubmedで検索してみると、論文誌によって保持される著者名情報が違うためミドルネームの情報ではヒットしない場合が多く、苗字の変更はクリティカルになります。 ↑ 姓名などについて詳しく条件づける検索方法は特にないようです 例えばHetta HaraさんがHetta Okaneさんになったとき こんなとき、名前をどうするかについては知り合いの（主に女性の）研究者の人たちをみるといくつかのパターンがありました。 旧姓のまま（Hetta Hara） メリット　当然楽 であり、今までの活動をまるっとそのまま引き継げる。 デメリット　戸籍名を強制する表記があったときに、それらを統合する術がない。また、その本人であることを証明することも難しくなる。税金関係や未確認だが卒業論文、証明などは戸籍名になるという説がある。パスポートも原則戸籍名です。 新姓に変更する（Hetta Okane） メリット　戸籍名と一致するため本人確認で身分証を必要するときにも問題なし デメリット　もしそれまでに研究活動をしていたらそれらを統合する術がない。医師免許や博士号などの名前と異なるので、証明が難しい。 ミドルネームに旧姓を入れる（Hetta Hara Okane） メリット　一応公式の名前は戸籍名と一致しており、旧姓の情報もわかるので親切な人であれば昔の論文も検索してくれるかもしれない。 デメリット　Pubmedの検索では名前とミドルネーム情報はイニシャルでしか含まれないことが多い（Pubmedの仕様なのか元の...
続きを読む

再現性なんてないさ（？）

イメージ
※この投稿は 「今年読んだ一番好きな論文2016」 Advent calendar の12月21日の記事です。 （わざわざ手描きにしたのに結局著作権が危うい絵を描いている） どうもこんにちは、 博士論文（仮）を提出したばかりのぴちぴちのD3、@calicolicali です。学生最後ということで、院生しか登録できないAdvent calendarに登録させていただきました！ ʕ◔ϖ◔ʔ 　「統計について」という事前コメントをしましたが、 私の専門はアルゴリズム寄りの Computational Biology で、これまではRNA二次構造予測ソフトウェア ParasoR の開発や、配列アラインメントソフトウェア LAST の開発に関わらせていただいたりしてきました。 （ご興味あればぜひ！） しかしこの分野では「網羅的な遺伝子データや配列情報を扱うためには統計や機械学習が必要！」ということで、日々これらの分野の勉強をしております。 　そんな私が紹介する、今年読んだ一番好きな論文はこちら(｀・ω・´)つ "Estimating the reproducibility of phychological science" Open Science Collaboration. Science 349.6251 (2015): aac4716. 去年の８月にサイエンス誌に投稿された論文ながら、Google scholarではすでに652本のサイテーションがなされています。 ざっくり解説  　この論文は心理学の分野の3つのジャーナルに2008年に出た 約100の実験的な相関解析に対して再実験を行い 、どのような実験・結果であれば再現性が得られるのかということを調べた論文です。元論文の97%で有意なp値が得られていたものに対して、 再現実験では有意とされたものは37% 、95%信頼区間に入ったものが47%、元論文のデータと組み合わせても 最終的に68%までしか有意性を確かめられなかった 、という報告がなされました。 　この論文は発表後様々な研究者によって正当性を検証するコメントや論文がでており、そして、最近Natureなど大手の雑誌でも心理学に加えて生物学など様々な分野での Reprod...
続きを読む

WLSのssh

WLS上でのsshが以下のように突然拒否される病にかかった。 ssh: connect to host xxx port 22: Resource temporarily unavailable おそらくWindows updateでFirewall設定が変更になるかしたからだと思われるが、 ~/.ssh/configに Host *              ProxyCommand nc %h %p %r と入れて、 chmod 600 ~/.ssh/configにしておいたところうまくいった。 回答をよく読むとFirewall設定ではなく、内部でのProxyを利用したjumpがうまくいっていない模様？ サーバーの方でRAMを追加するかなにかしたらしいので、内部でどこかに飛ばされる仕様になったのだろうか。 わたしはふいんきでsshをしている。 参考： https://superuser.com/questions/1098526/windows-10-linux-subsystem-ssh-client-resource-temporarily-unavailable
続きを読む