輸送問題を近似的に行列計算で解く（機械学習への応用つき） - 私と理論
輸送問題と呼ばれる問題があります． この問題は，普通は線形計画法やフローのアルゴリズムを使って解かれます． この記事では，この輸送問題を近似的に行列計算で解くアルゴリズム（エントロピー正則化 + Sinkhorn-Knopp アルゴリズム）を紹介します． 輸送問題とは アルゴリズム 得られる解の例 なぜこれで解けるのか？ 競プロの問題を解いてみる 機械学習界隈における流行 まとめ 輸送問題とは 輸送問題とは以下のような問題です． 件の工場と 件の店舗からなる，ある商品の流通圏があるとする． 各工場には 個の在庫がある.． 各店舗では 個の需要がある． 在庫の総和と需要の総和は等しいとする （すなわち ）． 工場 から店舗 に商品を一つ運ぶためには の輸送コストがかかる． 各工場 から各店舗 への輸送量 を適切に決めて，各店舗の需要を満たしつつ輸送コストの総和を最小化せよ． 輸送問題は最適化
atcoder黄色になるために必要になるかもしれないし、ならないかもしれないライブラリ一覧 - hotmanの備忘録とライブラリ置き場
util modint: 二項係数系もつけておくと便利 ツェラーの公式: どちらかと言うとcodeforcesで使える 年月日を入力にとって曜日を出力する fastIO: どちらかと言うとcodeforcesで使える 入出力が本質な問題が時々ある iterator: あんまり使わない 自作イテレーターのテンプレート timer: 実行時間を図る ラムダ式で関数を渡す形にすると便利 平衡二分木 とりあえず、AVL木でset型、map型、配列型を持っておけばOK 永続遅延平衡二分木とか言うヤバがatcoderに出たことがあるので、持っておいたほうがいい(本当？)(僕は持ってないです) セグメント木 双対/遅延/通常を動的/通常の２つで持っておくといいかも 2Dセグ木もyukicoderではよく見る union-find UF:これはみんな持ってそう マージテクUF:データを乗せてくっつける(実
安全で爆速なRollingHashの話 - Qiita
要約 ロリハ(RollingHash)のModを$2^{61}-1$にすると安全で爆速になってむちゃくちゃ幸せになれます。 前提知識 bit演算に関する基礎的な知識を要求します。 また、RollingHashについては以下で解説しますが、分からない場合は別の記事を読んだほうがいいかもしれません。 RollingHashとは? 開く 「文字列を一つの大きな整数として見る」というのがRollingHashのアイデアです。 まず、0-9のみの数字を含んだ文字列s = "1234567890"を考えてみます。 ここで、この文字列のHash値を文字列を10進数と解釈したときの数値と定義します。 また、$s$の$a$文字目から$b$文字目の前までの部分文字列を$s[a..b]$と書くことにします。 例えば、s = "1234567890"について、$s[1..3]$は1文字目から3文字目の前までの部分
slope trick (1) 解説編 | maspyのHP
slope trick と競プロ界隈で呼ばれているものが近い気がします Rote, G. (2018). Isotonic regression by dynamic programming. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. かなり新しい論文ですが、これも近そうです — 熨斗袋 (@noshi91) March 13, 2021 ei1333 さんによる実装例 https://ei1333.github.io/library/structure/others/slope-trick.hpp https://ei1333.github.io/library/structure/others/generalize
【C++】可変引数関数と可変引数マクロで便利なテンプレートを作ろう【新歓ブログリレー4日目】
この記事は 新歓ブログリレー2021 4日目の記事です。 自己紹介 こんにちは、20B の tatyam です。 普段は競技プログラミングをしていて、AtCoder赤 だったり、AtCoder Beginner Contest を作っていたりします。 みんなも traP に入って競技プログラミングをしよう！ はじめに C++ で競技プログラミングをやっていると、こんな関数があったら良いな〜と思うことがあります。 {} の要らない可変引数 min / max 可変引数の入力 / 出力関数 引数の個数で機能の変わる rep マクロ これを、可変引数関数 や 可変引数マクロ を使って作ってみましょう。 なお、この記事では C++17 と using namespace std; を仮定します。 可変引数関数の作り方 試しに、引数をまとめて tuple で包む可変引数関数を作ってみましょう。 te
最小カットを使って「燃やす埋める問題」を解く
3. 2. 燃やす埋める問題 引用:Komakiさんのページ http://topcoder.g.hatena.ne.jp/CKomaki/20121019/1350663591 3. FoxAndGo3 引用:TopCoder - SRM594 Div1 Medium http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=15706 4. The Year of Code Jam 引用:Google Code Jam World Finals 2008 E （プログラミングコンテストチャレンジブック P357） https://code.google.com/codejam/contest/32011/dashboard#s=p4 5. Surrounding Game 引用:TopCoder - S
ACL の math の解説をするよ - えびちゃんの日記
ACL (AtCoder Library) の内部実装を知りたい人向けの記事です。 お友だちに「ねーね、ACL のこの関数ってどういう仕組みなの？ 知ってたりしない？」と聞かれたとき、「え... なんかほら、わかんないけど、魔法で動くからいいんだよ」としか言えないと情けない気がしません？ しました。なので書きます。 こういうシチュエーションはなくても、何かを実装したいときに「あ、これ ACL の実装のやつと同じ発想じゃん」となることはありえるので、知っていて損はないかなと思います。 めちゃくちゃ長くなったので、一度に全部読むのには適さないかもしれません。 数式部分の LaTeX コードなども含めて数えられていますが、26000 文字を超えています。 全体像 個別の説明 internal::safe_mod internal::barrett Barrett reduction の話 正当性
競プロerのための群論 (swapと順列と対称群) - little star's memory
お知らせ Zennに移植しました。今後こちらの記事は更新されず、Zennの方のみ更新します。 zenn.dev この記事では競技プログラミングと群論に関する解説をします。競技プログラミングの問題を群論という立場から見ることで、新たな視点を得ることができるようになると思います。また、群論の入門にもなればいいなと思っています。 swapと順列 競技プログラミングの問題に、swapと順列は多く登場します。swapとは、2つの要素を入れ替える操作のことです。例えば、次のような問題があります。 第二回全国統一プログラミング王決定戦予選 C - Swaps (問題ページ) $ N $ 要素からなる2つの整数列 $ A_1,\ldots,A_N $ および $ B_1,\ldots,B_N $ が与えられます。以下の操作を $ N-2 $ 回まで(0回でもよい)行うことで、1以上 $ N $ 以下のすべ
競技プログラミングにおけるXORのTips - Qiita
はじめに この記事はCompetitive Programming (1) Advent Calendar 2018の9日目の記事となります． 競技プログラミングの題材の裏表に時折登場する，論理演算ならびにその(非負)整数型へのビットごとの拡張であるところの排他的論理和(XOR)について基本的な事柄をまとめてみました． どうでもいいですが私のアイコンは競技プログラミングを始めた頃，あまりにXORが分からなかった哀しみからXORの回路記号を使用しています． 排他的論理和とは 論理演算としての排他的論理和は以下の真理値表であらわされます．0をfalse，1をtrueとして， 見慣れた論理積(AND)や論理和(OR)と比べると少し直感的には分かりにくいでしょうか． どうみるか Z/2Zの足し算 2で割った剰余の世界（ $\mathbb{Z} / 2 \mathbb{Z}$ ）の足し算と思うことが
DP 練習セット（EDPC編）
こんにちは、ふるやん（@fuurya1223）です。 先日、DP （動的計画法）の練習に関してこんなツイートをしました。 DPが苦手だったときにやってた練習法。DPっぽい問題が解けないときは問題名でググって、検索結果のページだけ見る。 「DPで解ける」ことと「DPテーブルの持ち方」だけが、検索結果の本文プレビュー部分で見えることがある — ふるやん (@furuya1223) October 29, 2019 この練習法は良いと思うのですが、検索結果という不確定要素に依存するのが微妙です。 ということで、本記事では DP 練習者向けに、いくつかの DP 問題について 状態（ DP 配列の添字）の持ち方（つまり DP 配列の定義） 出力するもの 初期化 のみを記載しました。 DP が苦手な方は、この記事を見て「漸化式を考える」もしくは「サンプルケースで DP 配列の表を直接埋めてみる」などの
セグメントツリーの抽象化（C++）
※注 終盤に「ARC008-D タコヤキオイシクナール」の解法のネタバレが存在します ■「セグメントツリーの抽象化ってしてる？」 ●「抽象化…… セクハラですか、先輩」 ■「ええっ」 ●「冗談はさておいて…… 抽象化というのは、セグ木自身に “区間和” や “指定要素を上書きして更新” などの具体的な情報を書かずに、それらを外部から与えることで、目的が変わっても同じコードを使えるようにすることですよね。はい、ある程度はしてますよ」 ■「そうなんだ。いまいちやり方が分からないから、参考にしたいなと思って」 ●「いいですよ、こんな感じです。”long long 型の値を持って区間minと一点上書きのクエリが与えられる” という場合、 “long long”、”区間min”、”一点上書き” という情報を外部から与えます」 template <class T> class SegTree { in
Heavy-Light Decomposition - beet's soil
この記事は 「競プロ!!」 競技プログラミング Advent Calendar 2017 - Adventar の13日目の記事として書いています。 はじめに 先にこっちを見て beet-aizu.hatenablog.com 実装はこれが綺麗 codeforces.com 【HL分解でできること】 HL分解では、木（あるいは森 ）上のパスを 個に分割することができます。 分割後のパスに対して操作を行った後にマージし直すことで、操作を高速に行うことができます。 HL分解を使えるかどうかの条件は、載せるデータ構造（セグ木、BIT）等のみに依存します。 つまり、ある単純な（一直線に並んでいるような）要素列に対しての問題が で解けるなら、 それが木の上のパスになった場合でも で解くことができます。 参考: mathさんのオーダー周りの記事 Heavy-Light Decomposition -
ICPC国内予選2019に出場しました - Joeの精進記録
4完24位でした。 感想 この一戦だけに絞って感想を言うなら、「Eをもう少し落ち着いて確実に合わせに行きたかった」となるのですが、さすがに今回のICPCは自分にとって最後のICPCであり、チームGirigiriとはこの一戦のみならず人としての付き合いが長いのでそれほどシンプルにまとめることができません。 やっぱりチームメンバーに一番伝えたい気持ちは感謝の気持ちです。team GIrigiriが競プロモードになったのは去年のICPC国内予選以来ですが、わりとそこから1年間、競プロ熱を一度も切らすことなく切磋琢磨してやってこれたのはチーム独特の雰囲気があったからだと思います。予選に通ることが人生の目標なら別のチームメンバーもありえたかもしれませんが、自分が最大限に成長できたのはやっぱりこのチームだったんじゃないかと思っています。 そんな大好きなチームメートと出た最後のICPCなので（海外Reg
modint 構造体を使ってみませんか？ (C++) - noshi91のメモ
2019/04/01 実装例の訂正などを行いました。 2019/04/13 実行時に法が決まる問題についての説明を追加しました。 modint is 何 競技プログラミングの問題で、答えを 1000000007 (あるいは他の素数) で割った余りを求める問題は頻出です。これらの問題ではアルゴリズムの過程で繰り返し mod を取りますが、modint は普通の整数型などと同じ感覚で扱うだけで自動的に mod を取ってくれるというものです。 使用例 単純ですが、以下の問題を解いてみることにします。 a, b, c, d が与えられます。a * b + c - d mod M (M は定数) を出力してください。 modint なし long long a, b, c, d; cin >> a >> b >> c >> d; cout << ((a * b % M + c) % M - d +
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
高難易度木問題を解くテクニック集
AtCoder Library (ACL) クイックリファレンス - naoya_t@hatenablog
整数論テクニック集 - kirika_compのブログ