AtCoder Heuristic Contest 004（抽出版）

1010 @1010thinkreed

入力から同一文字列と包含関係の文字列を整理して、この文字列を配置すると入力のうちいくつを包含するかを数値化。その数値の大きい順に行方向だけを考えて並べる。このとき、部分一致の文字列を貪欲で追加していく。 #AHC004

iwashi31 @iwashi31

途中で L が十分に大きければ 40 個の文字列から元のテーブルを復元する問題になるということに気付いてアルゴじゃん…て言いながら泣いてた（結局 30 分かけて全探索するものしか組めなかった…）

いなにわ @inani_waon

#AHC004 おつかれさまでした。 被る文字を最大化する貪欲をしました。 あとは重複や部分文字列になっているものを前処理したくらい。 色々出来そうなことはあったけど技術と気力が足りなかった。

そすうぽよ @_primenumber

AHC004お疲れ様でした 文字列をなるべく被らせるの、天下一 Game Battle Contest 2021 Springでやった… 行だけ頑張って、列は知らんぷりした 最初は乱数付きの貪欲をいっぱい試して、そのあとあまり良くない行を壊して再構築 #AHC004

ymatsux @ymatsux_ac

#AHC004 まだテスト中の人が多いから多少変動するかもしれないですが、暫定23位です。短期間ヒューリスティックコンテストで2桁順位が取れたのは初めてかな pic.twitter.com/R9ILIZUzaS

拡大

merom686 @merom686

自分がAHCやるときのコンセプトは「最高の自明解を作る」。これで6時間使い切れる。

Risen @risenafis

5.7G 共通部があるシーケンスを1次元で適当に結合，その後貪欲で2次元に配置． #AHC004

りあん @rian_tkb

適当に繋がりそうな文字列を繋いだ後それらを適当に横向きに置いといて、適当に行を rotate したり swap したり、適当に適当なところに文字列を置いたりする山登りをした スコア計算が重いので trie を使ったけどもう少し定数倍軽くなりそう？（ループ回数が足りてないのでスコアに直結しそう）

有為 @uwitenpen

横にならべるだけで6e9はとれるけど、それ以上がどうしても・・縦の1，2列揃えるのも書いたけど時間切れ

shibh308 @shibh308

AHC004 お疲れ様でした 6315180495でたぶん41位 一部が重複している文字列 (EABCDとABCDFみたいな物) を繋げて長さ20近くにした文字列をたくさん取得し、それらの担当に被りがないように20個用意して横に並べました 横に並べた後は適当にシフトさせて縦を1列だけ合わせる、みたいな事をしました pic.twitter.com/zwBa6Wfw2M

拡大

ymatsux @ymatsux_ac

@uwitenpen え、満点解出せるんですね、狙おうとして全然うまくいかなかったです

iwashi31 @iwashi31

5 文字以上の重複があれば繋げる前処理をした後、長い文字列から順に配置していく乱択貪欲をやりました

なすび @Anko_nasubi

#AHC004 全部一致させたときのボーナス点は捨てる 10 文字以下の文字列のうち、連続部分文字列により多く他の文字列を含むものを列挙する それらをランダムに並べ替えて 2*20 に並べた後隙間をいい感じに埋めるのを繰り返す で 3.47G pic.twitter.com/kfvpeAxlxQ

拡大

Yoichi Iwata @wata_orz

想定解としてはs[i]をマージして長さNの文字列を2N個作り、配置を探索して満点を狙う。無理なら適当に貪欲で配置するという感じでした 上位の人々は何個か満点獲得したのかな？ #AHC004

𝗅𝗈𝗇𝗀𝗋𝗎𝗇 @1on9run_zun1027

貪欲！他の文字列を部分文字に持つやつから取る。'.' をなるべく減らさないように入れる。 #AHC004

そすうぽよ @_primenumber

6,325,164,928点で40位にはいれないくらい？ 寝坊したせいで最後に列をちょっと頑張るのをやる時間がなかった… #AHC004

ひとあれ @hitoare1

5.48B 103位 焼き鈍し法 各文字列に対して位置と向きを定める 同じ場所で異なる文字を使うペアの総数+使ったマスの個数を評価関数にする 3文字以上共通する文字列を事前に結合しておくと一気に点数が上がった #AHC004

和解 @rsat__m

長さの平均が結構デカいと完全に復元できるんだけどTLEが取れなくて閉店 #AHC004

EvbCFfp1XB(C7BMkOO7Qbmcwck7) @EvbCFfp1XB

Alien's Genome Assembly はこんな感じ。 ビームサーチを使いました。 文字列：他の文字列の部分になるものは使わない。 埋め方：1行づつ埋める。列はインデックスが１のときだけ埋める。 幅：300 #AHC004 pic.twitter.com/xslX7yqU3f

gobi @gobi_503

#AHC004 事前に重複削除や端を重ねる合成をしておいて、 その後敷き詰めるって感じのことをした。 なんかいい感じのアルゴリズムありそうだよなあとか思いながら、どのフェーズも貪欲でやった。

titia @titia_til

AtCoder Heuristic Contest 004 ・文字列をマージしていく。たとえば"abcd"と"bcde"があったら"abcde"を作る。できた集合をSとする。 ・Sに含まれる文字列を上から置いていく。その際、縦方向の部分文字列がSに含まれる回数が多いものを採用。 これで6.05点、60位くらいでした。#AHC004

TERRY @terry_u16

AHC004、6.62G点で16位でした。 一番被りの多いところに置けるだけ置いていく貪欲をしました。置く順番と向きを山登りで改善。 最初に3～4文字以上被ってる文字列を長い方から貪欲にマージできるだけマージしたら5.0G点から6.3G点に伸びたのでかなり本質だったっぽい？ #AHC004 pic.twitter.com/PLz2j1M05J

拡大

ボンド@競プロ @bond_cmprog

#AHC004 頭のいい方法考えるのが無理だったので、ランダムなS_iをランダムな(h,w)に置く山登りで3.64g n-gramとかうまく使えたら面白いなーってなったけど面白いなーで終わった（あほ）

midri1784 @midri1784

AtCoder Heuristic Contest 004参加．最終スコア5.7Mでした． #AtCoder #AHC004 2桁順位とれたからまあよかった...かな? 大まかな方針とスコア： v1 (1.8M) まずはtrivialな解を出して正のスコアを目指す．小さいものから順に横方向に敷き詰めていき．右側に余っている列があればそこにも敷き詰める．

dn6049949 @dn6049949

Z-algorithm使って文字列をいい感じにまとめるなどして、あとは盤面を埋める数が少なくなるように貪欲に埋めて70位くらいだった 今回初めてPyPyで完走してみた #AHC004