最終順位143位で自己ベスト更新でした。そして、レートが水色に乗ったらしいです。
とはいえ、今回は解法が全然浮かばずゆるふわに近い参加となりました。
時系列まとめ
今回はgitでちゃんと世代管理してました。大まかな流れはこんな感じ。
第0世代
とりあえず問題を読んで、正の点数を得ることを試みます。今回はすべて'A'で提出。
〔AtCoder Heuristic Contest 004 実況〕
— AtCoder コンテスト実況 Bot (@cpcontest_bot) 2021年6月26日
mdstoy さんが 6 位から 3 位に浮上しました！https://t.co/JHYPoXNHPF
2021/06/26 13:02 pic.twitter.com/G0yKq7EECH
華麗にスタートダッシュを決めましたｗ
第1世代
とりあえず何も考えず受け取った文字列を順に敷き詰めて提出。スコアが2Gに到達します。
これとても簡単に実装できるから、初手で出しておけば暫定1位取れたのではとちょっと後悔しましたｗ
第1.1世代
最後に置いた文字の末尾の一文字と次に置く文字の最初の一文字を合わせて重ねたりとか、単に長さでソートしたりとか、思い切ってランダムに文字列を生成してから一致度を調べるを時間一杯やるとか試行錯誤していました。どれもだめでした。
第1.5世代
ある文字列が他の文字列の中に含まれている場合、両方使うのは無駄なので小さい方を省くようにしました。0.2Gくらい伸びたような。
無の時間
3時間くらい何も浮かばず・・・。考える合間にYouTube見たり散歩にでかけたりして気分転換を図ります。
第1.9世代
前処理で各文字列のprefixを全てmapにぶち込んで、できるだけ重なる範囲を大きくするという方針にしました。
かなり期待していたのですが0.2Gくらいしか伸びず。
第2世代
なぜ伸びなかったかというと、添字を一箇所間違っていたからでしたｗ
不具合を修正して4Gに到達。一気に倍近く伸びました。
第2.1世代
第1.5世代で包含チェックをしたときに、他の文字列を多く含むものから優先的に使うとか、文字数でソートしておくとか細かい修正でちょっとだけ伸び。
第3世代
ひとつ目の文字列を置いた後、常に重なり判定をしていたのですが、各列で最初に置く文字列にはそれがいらないという衝撃の？事実に気づき、ロジックを修正。
これが想像より効いて4.9Gまで伸びました。
ここで、アイデアが尽きてタイムアップとなりました。
できなかったこと
最後まで横に並べることしか考慮できず、縦をどうしたらいいのかが全く浮かびませんでした。
また、焼きなまし的なことも今回全くできず。やり方の想像もつかず。（そもそもスコア計算のロジックも書いていない時点で・・・）
まとめ
ちょっと中だるみしてしまったのですけど、今回も面白い問題で楽しめました。
