Ark's Blog

引っ越しました→ https://blog.arkark.dev/

ようこそ

半環上の最大部分配列問題とKadane's algorithm

この記事はSunrise Advent Calendar 2019の9日目の記事です。

adventar.org

内容はごった煮ということなので、アルゴリズムと代数について書きます。

TL; DR

  • Kadane's algorithmと呼ばれる最大部分配列問題を O(n)で解くアルゴリズムがある。
  • このアルゴリズムはトロピカル半環上で動作する。
  • つまり、半環上に一般化できる!
続きを読む

ハル研究所プログラミングコンテスト2019 参加記

ハル研究所プログラミングコンテスト2019 に参加しました!

www.hallab.co.jp

結果は暫定9位 *1 でした!

賞金圏内に入れなかったのは残念ですが、記念品のプロコン2019オリジナル“カメデザイン”モバイルバッテリーがもらえそうでうれしいです。

https://github.com/ArkArk/competitive-programming/blob/main/src/HALLab-ProCon/hpc2019/demo/Total%20turn:%2055,818.gif?raw=true

*1:これから提出コードのチェックなどが行われ、11/8に正式な順位結果が発表されます。

続きを読む

全順序集合に対するimos法の拡張

AtCoder Beginner Contest 128のE - Roadworkで、imos法を拡張したアルゴリズムを思いついたのでメモ。

前提

  • imos法を知らない人はこちら
  • imos法は可換群に対して特定のクエリを高速に処理するアルゴリズム
  • 今回は全順序集合への拡張を考えた
続きを読む