学生向けFixstars高速化コンテスト参加記

この記事は木更津高専 Advent Calendar 2024の13日目です

prev -> [初心者向け]クリーンなPython環境の構築方法 by @kokastar
next -> 920MHzに比べると国技館のBluetoothはカスや by @kokastar

投稿日を忘れていたため非常に内容が薄いです，ｽﾐﾏｾﾝ

学生向け Fixstars 高速化コンテスト 2024に参加しました
最終18.268点で17位でした

解法

Kが16か256かで場合分けをしました
並列化については，全体を通してなんとなくomp parallel forを書いたくらいです...

K = 16

概要

• 宝石の種類ごとに，巡回畳み込みを用いて「ちょうどi回円盤を回したときに宝石が何個一致するか?」を求める
• 求まった数列を足し合わせて出来た数列の最大値が答え

高速化

• 畳み込みを書くのが初めてだったのでac-libraryを参考にしました
• IDFTは最後に一度だけ（線形性を用いた高速化）
  • 参考: https://noshi91.hatenablog.com/entry/2024/05/26/060854

K = 256

• 種類ごとに愚直に一致するところを列挙する

高速化

• 必要なところだけを見る
  • k = 0, 1, 2, ..., K - 1について，A[i] == kとなるiをそれぞれ求めておく

反省

雰囲気でOpenMPを触っていました，SIMDとかキャッシュのこととかは何も考えていません...