RCO presents 日本橋ハーフマラソン 本戦

RCO presents 日本橋ハーフマラソン 本戦: http://rco-contest-2017-final.contest.atcoder.jp/ Standings - RCO presents 日本橋ハーフマラソン 本戦: 続きを読む
0
前へ 1 ・・ 27 28
宇宙ツイッタラーX @kenkoooo

問題の面白さも不可欠ですが、ビジュアライザが重要だったっぽくて、これによって複雑な問題設定でも参加者を取り込めた気がします。ブラウザで実行できる形式にしたのも敷居を下げたみたいですし、非競プロ勢が競プロ勢に興味をもつきっかけにもなりそうな気がしています。 #rco_procon

2017-03-22 11:06:38
koyumeishi @koyumeishi_

バグってたところ直して、余った時間で何手か戻ってもっといい手がないか探索(お粗末)するようにしたら 130 手平均位になった。 引っかかってるやつがあるっぽいから、これ解決するとまだ減らせそう(ビジュアライザ楽しすぎる) pic.twitter.com/jeAPnVY08b

2017-03-22 12:37:11
koyumeishi @koyumeishi_

天才過ぎて70手ぐらいまでになった。 最初と最後、市松にするのに合計10手ぐらいかかるから、間は60手ぐらいでほぼほぼ理論値。これ以上はもう無理でしょ #rco_procon …st-2017-final-open.contest.atcoder.jp/submissions/al… pic.twitter.com/qUQ9CYLzIv

2017-03-22 14:28:56
koyumeishi @koyumeishi_

解説 1. 最小費用流+復元で初期状態と最終状態を市松模様にする ( 初期->初期市松 ==> 最終市松<-最終 ) 2. 車のある各セルから隣接するセルへ min( 1,(next_score-prev_score)*prev_score) のコストの辺を貼って最小費用流(続)

2017-03-22 14:40:52
koyumeishi @koyumeishi_

ここでコスト計算に使う最終状態は最終市松の方。 目的地まで遠い方から優先的に使うように重みづけしてる。 3. 2に合わせてたまにランダムウォークっぽいものを取り入れつつ、 時間が余ったら何手か戻ってもうちょいといい手がないか探す。 おしまい。

2017-03-22 14:43:54
koyumeishi @koyumeishi_

辺の重みの種類が少ないからか知らないけど、 dijkstraベースの最小費用流よりSPFAベースのやつが速く動いた。 振り返ってみると最初っから最後まで最小費用流の問題でした

2017-03-22 14:46:03
有為 @uwitenpen

市松模様にする最小費用流って普通に隣接セルにコスト1の辺を貼ってsource,sinkをやっただけのやつなのか・・これで10手以内で遷移できるんか

2017-03-22 15:18:36
有為 @uwitenpen

迂回路は除去できるけど直感的にはウーンって感じだ

2017-03-22 15:19:46
kuuso @kuuso1

結構前からだけど、koyumeishiさんがおもむろにフローで殴ってくるのめっちゃすき

2017-03-22 15:42:43
しさし @shisashi

@koyumeishi_ ビジュアライザ改造していただいていて、感激です。 距離を線の太さで表すというアイデア凄く良いですね。70手のも凄すぎる……。

2017-03-22 15:49:25
yowa @yowa

ずっとハーフマラソンB問題:日本橋大渋滞やってる(スコアが出せるとは言ってない)。 思いついた方針を試す→どうしてうまくいかないのかを考察する、のループが楽しい

2017-03-22 16:56:08
ツカモ @tsukammo

最小費用流とやら、最近よく聞くのでものにしたい。

2017-03-22 23:30:57
ツカモ @tsukammo

一般的に、マラソンマッチは要する期間が長いので布教に不向きだが、最近のAtcoderのハーフマラソン系は確かにマラソン問題なのに数時間で出来るのでもってこい。(数時間でできるとは言ってない)

2017-03-23 00:36:14
koyumeishi @koyumeishi_

@shisashi ビジュアライザがなかったらここまで詰められませんでした。 ありがとうございます。 ところでこのビジュアライザのコード、一部改変して解説記事に埋め込んだりしても大丈夫でしょうか…?

2017-03-23 22:36:31
しさし @shisashi

@koyumeishi_ ぜひぜひ、よろしくお願いします〜。

2017-03-23 23:13:22
tomerun @tomerun

最近chokudaiさんやたらMarathon強いアピール多いので今年のTCOはやってくれると信じている

2017-03-26 17:44:57
tomerun @tomerun

どうにか決勝まで行ければあとは日本橋ハーフマラソンで培った短時間マラソン力で無双や!!

2017-03-26 17:46:34
koyumeishi @koyumeishi_

書いたはいいけど想像以上に中身がない気がする。 ビジュアライザ動かせます。 日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 - koyumeishiのブログ koyumeishi.hatenablog.com/entry/2017/03/…

2017-03-26 19:33:13
koyumeishi @koyumeishi_

@shisashi そういえば件のビジュアライザ、記事に埋め込んで使わせてもらいました。 ありがとうございます。 また楽しいコンテスト期待しております。 twitter.com/koyumeishi_/st…

2017-03-27 23:40:31
コルン @colun

ビジュアライザ付きって素晴らしい。RTが捗る。

2017-03-28 04:07:27
tomerun @tomerun

この問題ここまで行けるとは正直思っていなかった。あと車の密度がちょうど半分なのは市松を想像していたわけではなくて偶然です twitter.com/koyumeishi_/st…

2017-03-29 10:14:11
前へ 1 ・・ 27 28