デジタルの日特別イベント「HACK TO THE FUTURE for Youth+」

olphe @_olphe

Cのサンプル [Visualizer共有] img.atcoder.jp/future-fif-dig… #HTTF pic.twitter.com/CPLhBTsYKc

拡大

毎日修論 @pu__Ne

どうやって最小全域木するんや

krps @krps_v

[Visualizer共有] img.atcoder.jp/future-fif-dig… #HTTF pic.twitter.com/W4mqfXX8Es

拡大

takumi152💉💉💉💉 @takumi152

#HTTF やったこと 1. 連結成分を無視して、1x1以外のポリノミオの配置を焼きなまし。評価関数は配置したポリノミオと印マスを1x1ブロックだけで貪欲に接続したときのコスト値とした 2. 印マスと配置したポリノミオを1x1ブロックで貪欲に接続する 3. 全体が連結になるように1x1ブロックを貪欲に配置する

はむれー @cltacelreapdu

#HTTF A: 真心を込めて配置 B, C: 1*1を使って最小全域木を雑に求めた後, 必要最低限の辺だけ取り出す. 残った辺について1*1以外のポリオミノを置いたときの利益の差分を見て, 大きい順に配置していく(B: 1364469, C: 1411211)

takumi152💉💉💉💉 @takumi152

最小全域木解法、なんだろう

たき(=ﾟωﾟ)ﾉ @takytank

みんなのを見てる感じ、最初に1x1で最小全域木を作ってから置き換えじゃ無くて、最初にデカいのを置く方がCはいいのか。#HTTF

heno @heno_code

連結にするの、最小全域木だと計算量が大きすぎてやめたんだけどB問題に関しては最小全域木の方が良いっぽい？ #HTTF

tashikani @4000Tashikani

やったこと * 各印マス上にポリオミノを配置する * 連結は考えない * 一つのポリオミノで多くの印マスを覆うように * 全てのポリオミノが連結するまでポリオミノを追加していく * 連結できないときはできるだけ他の島に近づくように どちらも全パターン調べて貪欲に配置していく #HTTF

krps @krps_v

ダイクストラ法か～～～～～～～～～～～ なるほどな～～～～～～～ でも実装きつそう...

TERRY @terry_u16

全部のミノ使ってダイクストラ、こんなの被りがよく分からんし実装破滅すると思って捨ててしまった…… #HTTF