komlowのブックマーク - はてなブックマーク

累積和を何も考えずに書けるようにする！ - Qiita
0. はじめに最近では AtCoder がコーディング面接の文脈でも有効なものとしての認識が広まってきています。AtCoder の登竜門といわれる水色を目指すにあたって多くの方が「勉強した」と報告している代表的なアルゴリズム的手法の一つに累積和があります。今回はそんな累積和をストレスなく機械的に書けるようになることを目標とします。累積和は、そのコンセプト自体は簡明で決して難しくないのですが、添字の扱い方など、頭がゴッチャになりがちである応用範囲が非常に広いということから、整理する価値の高い手法です。僕自身、累積和を用いる問題に対して、毎回添字の扱いに神経を尖らせながら頑張っていたのですが、一度実装テンプレートを決め込んでしまえば何も考えなくても書けるようになりました。そうなってからは累積和を実装することにストレスが無くなりました。そんな体験を共有できたらと思います。 1. 累積
komlow 2021/06/17
リンク
「998244353 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜 - Qiita
1. なぜ 998244353 で割るのか？最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。なぜ 9982443
komlow 2018/08/02
リンク
ビット演算 (bit 演算) の使い方を総特集！〜マスクビットから bit DP まで〜 - Qiita
はじめにはじめまして。 NTTデータ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 C や C++ を使用しているとしばしばビット演算を行う場面が出て来ます。計算機リソースが限られている状況では、ビットを用いることでデータ量を少なく済ませたり、計算コストを小さく抑えたりすることができるメリットがあります。本記事では、ビット演算を用いて実現できる処理について、簡単なものから高度なものまで集大成します。極力わかりやすく頑張って執筆しました。特に前半 4 つはビットの説明の中でもかなりわかりやすい方だと思います。後半の 7 つのテーマは比較的高度なアルゴリズムの話題ですので、フラグ管理やマスクビットについて詳しく学びたい方は前半 4 つを中心に読んでいただいて、後半 6 つは必要に応じて読んでいただければと思います。反対にビットの知識はあってビットを用いたアルゴリズ
komlow 2018/02/20
algorithm
リンク
‪実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬ - Qiita
0. はじめに --- 二部マッチング問題は実世界で超頻出はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実問題で登場する二部マッチングは以下のように多岐にわたります: マッチングアプリで男女のペアを最適化する (「男」と「女」) インターネット広告分野で、ユーザの興味に合う広告を出す (「ユーザ」と「広告」) 企業検索サービスなどで、ユーザの検索履歴に合う企業を
komlow 2018/02/02
Programming

Algorithm
リンク
1