-
threecourse
- 895
- 0
- 0
- 0
-
- いいね！0
harurun🌹偶奇はmod2
@harurun_p
#AHC004 twitter.com/harurun_p/stat…
2021-06-26 19:06:33
harurun🌹偶奇はmod2
@harurun_p
簡単な解法(47ちょうどくらい) 文字列長で降順ソート siのなかにsjが含まれるかで重要度を決める(sj in si でsj--,si++) 重要度で降順ソート 高い順に左上から当てはめる このとき重なりも考慮する 残りの時間を使ってこれをもとに 上下のシャッフルと横をランダムでずらす 一回ずつ点数数えて比較
2021-06-26 19:06:18
Yuichi Sayama
@xyz600600
部分文字列を消して、重複度合いが高そうな文字列からビームで詰めてみました。 極端に点が低いやつがどうしてなのかの考察をしてたり、バグを追ってたら終わってた
2021-06-26 19:06:37
ぬるから
@nullkara
AHC004お疲れ様です。 2189102389点でした。 atcoder.jp/contests/ahc00… 貪欲(siを並べるだけ順に並べて)して焼きなまし(雑)をしてました。 #AHC004 #Atcoder
2021-06-26 19:06:42
じろーしょー
@Jirosho111
#AHC004 4.8Bilくらいで、152/603くらい。 atcoder.jp/contests/ahc00… 「かぶり文字が大きい箇所におく」だけで4.1Bil まで出ました。(21ms) そこからランダム性を少し持たせて4.8Bil。 焼きなませなかった…。
2021-06-26 19:07:08
makibishi
@0xff00ff00
#AHC004 文字数が長い順に置いていく。置く場所はすでに配置されている文字が一番多いところにする。(複数ある場合はランダムな一つ) この方法はランダム性があるので、これを制限時間まで繰り返す。
2021-06-26 19:07:15
sumoru
@sumoooru
お疲れ様でした。難しかった・・・ やったこと Lが６以下だったら焼きなまし、そうでなければ山登り 盤面上の文字列の全通りをunordered_mapに入れて判定 最終提出でギリギリ5Gに届いた #AHC004 pic.twitter.com/JphU67yjiT
2021-06-26 19:07:15
拡大
midri1784
@midri1784
v2 (1.9M) 行→列の順番を列→行にしてより充填されるようにする．余ったところはランダムにして祈る v3 (2.2M) 他の文字列と等しい，もしくは他の文字列に包含されている文字列を考えるは無駄なので除く．
2021-06-26 19:07:22
こたつがめ
@kotatsugame_t
#AHC004 5.88G 文字列同士の重なり具合をすべて調べる。完全に覆われているものは吸収しておく。 長さ20、トーラス無視で（吸収ぶんも含め）最大いくつ文字列を含められるかをdpで計算し、復元。これを1行とし、トーラスと列方向を考慮して部分列となったものをチェックして次回以降使わないようにした
2021-06-26 19:07:36
ネギ坊主
@negibose2020
AHC004お疲れ様でした。 最後バグり散らかして伸びず。 以下方針、 同じ文字列は同じものとして扱う。uf使用。 共通部分は伸ばしていく。 伸ばせるかは、各文字の先頭や末尾に付け加えて整合性が保てるか。 保てるならufでくっつける。 各rootのsize順に書き込む sizeが小さいものは縦でカバーする。
2021-06-26 19:07:45
ネギ坊主
@negibose2020
最後の縦でカバーするためのローテートがうまく行かずにもったいないことした。 書き込めるなら余ったところにでも書いとけば少しは点数上がったかもなのに。
2021-06-26 19:07:45
かわてぃー
@kawatea03
5位で初めて一桁順位が取れた。 貪欲で一行の文字列を作って横に並べるのに加えて2つか3つの列を二部マッチングで揃えるようにした。
2021-06-26 19:07:51
takumi152💉💉💉💉
@takumi152
#AHC004 やったこと(51位, 6.15G) ・文字列が他の文字列に完全に含まれているなら消す ・2つの文字列のprefixとsuffixが一致して、かつ他にsuffixが一致するものがない+マージ後に20文字以内ならマージ ・あとは重みを付けた文字列を配置する焼きなましをする
2021-06-26 19:07:53
あずりえる🌸
@poyothon
#AHC004 4.34Mで187位/622人 単純な貪欲。 まずsを(-多重度, 長さ)でソート。 まだ置いてないsについて、グリッド全探索して.を塗り替える最小回数をコストとしたとき (コスト) <= (上限) * (多重度) なら塗る。 上限をいい感じに変えてこれを繰り返す。 本当はここから焼きなましをかけたかった。
2021-06-26 19:07:57
satanic@研究💪
@satanic0258
5.56Gで96位？ 多点スタート山登りと焼きなまし書いて比較したらL<7か否かでいい感じに分かれたのでmax取るようにしたくらい pic.twitter.com/9P3mcRmVIi
2021-06-26 19:08:08
拡大
recta
@recta_001
AHC004お疲れ様でしたー。4315931436点、193位です。 ・文字列を長いのから順に、被りが多くなるようにおいていく ・盤面上で文字列の出現回数が少ない所をリセット→上記の操作を実行のループ
2021-06-26 19:08:15
岡竜之介
@agajo
#AHC004 断片を含むことができた率57.5%で74位でした！ 繋げるだけ繋いでから、そのうち21本を配置。 実際のDNAアセンブリをイメージして繋げられる断片は先につなげてから、含む断片が多い順に横向きに20行配置した。 最後の30分で、縦方向にも一つ断片を含むように配置を調整。悪くない結果だな？
2021-06-26 19:08:17
tomerun
@tomerun
#AHC004 1桁順位streamを続けられたのでよかった。最初1.5時間くらいは完全解を狙って盤面全体を最適化する焼きなまし系を試してたけど全然だめそうだったので、無難なことをして無難な結果を取った感じ
2021-06-26 19:08:34
kimiyuki@うさぎ🐇
@kimiyuki_u
お疲れ様でした。1 点更新の愚直焼きなまし (+ 1% の割合で s[i] をそのまま書き込む遷移) を書いてそれをただひたすら高速化していました。6408108055 点 29 位 #AHC004 github.com/kmyk/atcoder-h…
2021-06-26 19:08:39
phocom
@_phocom
37位 できるだけ共通させるよう貪欲に行を20本つくる 縦方向でダメ押しするために激重ビームサーチで上から行を配置していく 要求を途中まで達成していると嬉しくて、完成させたらメッチャ嬉しい感じの評価関数
2021-06-26 19:08:40