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なのでまぁまぁきれいに書けたでしょうか。


うむーん(´・ω・)

コメント

このブログの人気の投稿

再現性なんてないさ(?)

特に収穫がない日

jupytherにチャレンジ