約 635,550 件
https://w.atwiki.jp/vivid_turtle/pages/11.html
グリッド上での数え上げを数える手法を紹介する。 何点か固定 これはグリッド上に任意にコマを配置して、そのすべての配置パターンについてうんぬん数え上げるとタイプに多い。 一見つかみどころがなさそうだけど、数か所固定して数え上げればうまく網羅できる場合が多い。 例 ABC127 - E(500) https //atcoder.jp/contests/abc127/tasks/abc127_e すべて数え上げろだなんて、突拍子もない話である。しかし、上記のことを頭の中で意識しておこう。 まずこの問題はx,yは独立して考えてよい。そして、x軸上の距離d((X_i) - (X_i+1) == d)の時、どれほどのパターンがあるかを考える。 全パターンを網羅するには、K - 2このコマを残ったN * M - 2か所に配置すればよい。これはcomb(N * M - 2, K - 2)である。 また、y軸は独立して考えるので、dを固定すると、 d * (N - d) * M ^ 2と全部のパターン数が出る。 内訳としては 長さ＊1行あたりの数＊固定する二つのコマをどの行におくかの二乗 である。 あとはこれを1からM - 1まで足し合わせばよい。 y軸もx軸とほぼ同じで、x,y軸の計算結果を足してからcomb(N * M - 2, K - 2)をかければAC。(2019/5/26)
https://w.atwiki.jp/vivid_turtle/pages/39.html
連続部分列はつぎのような手法と相性が良い。また、部分列に関しても下の記事の手法のほうが良いものもあるだろう。 ありうる全事象についての変換の和の数え上げ 部分列は数列と文字列両方ある。 文字列の部分列の数え上げはけんちょん先生の https //qiita.com/drken/items/a207e5ae3ea2cf17f4bd にある。 数列の部分列についてかく。 数列の部分列は、連続部分列の問題と違って一定のパターン化がしづらいと思われる。 というわけでこのページは出てきた解けなかったほぼすべてのパターンをまとめる。 ちなみに、数列の部分列は全くの空を1通りとして数えて、 長さNでは2^N通りある。(それぞれの番目について選ぶか選ばないかの2択) 部分列の相補性 数列から部分列Aを生成すると、空の列も部分列として許容するなら、必ずAの含まれなかった要素を全て持つ部分列Bが形成される。これを部分列の相補性ということにする。（僕が今名付けました。） この考えを利用すると、すべての部分列はペアをつくることができる。 例として、数列{1, 10, 100}なら ({}, {1, 10, 100}), ({1}. {10, 100}). ({10}, {1, 100}), ({100}, {1, 10}) となる。 この考え方を持っておくと解ける問題があった。 AGC020 C(700) Median Sum https //atcoder.jp/contests/agc020/tasks/agc020_c 上記の考え方を利用すると、空の列も部分列として数えるなら、2^N / 2の計2^(N-1)ペアできるとわかる。 また、相補性があるのでお互いのペアの和はかならず、数列の前項の和になるとわかる。 例えば、{1, 10, 100}の数列のペアの１つとして({1, 100}, {10})が存在するけど、それらの和は1 + 100 + 10 == 111で数列の前項の和に等しい。 中央値というキーワードに対する操作として、要素を大きい方と小さい方にわけるというのがある。普段ならばどの要素をどう振り分ければいいのか困るが、今回は上記の考え方を利用すると都合よくペアになってる。よって、ペアのうちでの大きい方と小さい方に分けることを考える。 そうやって各ペアについて大きい方と小さい方に分けると、相補性の特徴として、大小がはっきりとわかれる。なぜならば、和が一定でかつ小さい方の大きい方の差がどんどん縮まり、最終的には境界条件となる二つのペアの和が同じになるためである。 つまり、こう考えると、境界では二つの部分列ペアの和の差は0に一番近い状態になってる。 これは言い換えると、小さい方のペアは(全項の和)/2以下の最大、大きい方のペアは(全項の和)/2以上の最小になることである。 そしてこの問題は空の列を部分列としてみなさないため、中央値は大きい方のペアの一番小さいもの、つまり(全項の和)/2以上の最小のものである。 あとはこれを数え上げればよい。 boolのdp[i][j] = i項目まで見て、和がjが作れたかどうか で動的計画法をすればよい。計算量はO(n^3)、2000^3である。 まずいですね。でも動的計画法の手順としてはこれ以上計算量はおちません。 しかし計算するのは真偽の二値のDPなので、C++のbitsetを利用すれば64倍の定数倍高速が可能です！ bitsetでの定数倍改善
https://w.atwiki.jp/mjsen/pages/82.html
押し引きの考え方で取り上げた巡目毎の放銃率は、通っている牌がどの程度あるかによって変動します。基本的には講座37の巡目毎の放銃率と大差ない場合が多いですが、通っている牌が特に多い場合や、手出しでリャンメンターツを落としている等リャンメンテンパイの可能性が特に高い場合は、通ってないスジの数から無スジの放銃率を見積もる必要性が高くなります。 18分の１理論 スジは各色毎に６つずつあるので、（１－４ ２－５ ３－６ ４－７ ５－８ ６－９）合計18本存在します。仮に他家リーチに通っていないスジが12本あって、２－５ｐ、５－８ｐが通っていないとすると、リーチが必ずリャンメンテンパイであるなら、２ｐの放銃率は1/12（約8.3％）、５ｐの放銃率は1/6（約16.7％）と概算されます。リーチ全体のリャンメン率は約2/3なので、愚形待ちには放銃することが考えにくい場合（早い段階で６ｐが切られていれば５ｐはシャボやカンチャンでは当たりにくい）でも５ｐの放銃率は1/9（約11.1％）となります。講座36で取り上げたように、手出しで字牌等の安牌要因として持たれていた可能性が高い牌が切られた場合は、それ以前に切られた数牌をまたぐ待ちの放銃率は低いので、高く見積もっても半分程度とみなします。 １４７ ２５８ ３６９ 実戦で通っていないスジの本数を素早く数えるのは難しいですが、上のような３×３をイメージしながら行うとやりやすいと思います。通った牌を消していって、４７のように横２つが残れば１本、３６９のように横一線が全部残れば２本と数えます。４枚見えた牌については、５の場合は３と７（テンパイ者の河に赤５（リーチの場合はリーチするまでに）が切られている場合も同様）、４以下の場合は１つ下と２つ下（６以上の場合は１つ上と２つ上）がノーチャンスになるのでこれも消します（４枚見えた牌は情報として強く、４枚見えの牌が多い時はその分他の無スジの放銃率が高くなるので注意が必要です）。 押し引き判断の変化 第２章で取り上げた押し引き判断については、先行テンパイのリャンメン率が約2/3とした場合の基準なので、リャンメンテンパイの可能性が高いと読めるケースについては微妙な場合は降り（可能であれば回し打ち）が有力になります。逆にスジや手役、ドラ絡みでない字牌は通りやすいので押せますが、次巡以降無スジを引けば降り有利になる場合は、メンゼンテンパイであればダマにして危険牌を引けば降りるのが有力です。 また、リャンメン以外には放銃しないとして見積もっても明確に放銃率が15％を超えるような超危険牌に関しても基本は降り。良形３翻以上、愚形４翻以上でも、他の牌で当たるケースがどの程度あるかを判断して勝負するかどうか判断することになります。
https://w.atwiki.jp/vivid_turtle/pages/38.html
Atcoderなどで頻出の数学テクニックで、天才要素が強いと思われるありうる全事象についての数え上げについてパターン化できそうなものを纏める。 とりあえず大前提１、２をまとめた。 大前提１ 次の条件１を満たす者は、方法１で数え上げられる。 条件１ ある部分に着目した時、数え上げたいすべてのものはそれをただ１つもつ。 方法１ そのある部分(X_iとする)ごとに、X_iを持つもの数え上げる対象を計算して数え上げる。(掛け算するとか)このステップをf(X_i)とかく。 そして、それをsigma(1- N, i)f(X_i)する。 一見すべての事象をカバーできてるか怪しいけど、条件１は必要十分条件であるためできてる。ここが個人的にあまり直感的ではなく天才ポイントが高い。 いくつか例を挙げる 例 ABC127 - E(500) https //atcoder.jp/contests/abc127/tasks/abc127_e グリッド上での数え上げ もうすでに記事が出てるけど、この問題はこの原理でも考えられる。 共通してる部分をとにかく探すと、盤面を固定したときには、特に共通項はない。 しかし、考えるのはありうる盤面すべてなので、これを念頭にいれて考える。すると、「二つの点の座標の差の絶対値」は全部の考えうる置き方での共通部分と考えられる。 あとは、二点の置く今見てない軸で2乗、二点の場所以外のところですべてにおきうるということでコンビネーション、差がXということは、同じ行でありうる置き方をまたかける。これらを全部かけ合わせればとける。(コマを区別はしないので、左と右の入れ替えは考えなくてよい。コマを区別する場合は、答えに最終的にN!をかければよい。) ここからわかるように、大前提１を使った考えうるすべての数え上げは並べる物自体(物を並べるパターンに限るけど)の区別はいったん無視して、同じものと考えると見通しがよい。 例 ABC140 E(500) https //atcoder.jp/contests/abc140/tasks/abc140_e この問題はこの記事を書くきっかけにもなった。 すべての連続部分列に対しての、二番目に大きい要素を返す写像fをおき、すべての連続部分列をfに入れた合計をもとめればよい。 この場合、共通部分としては、すべての[L, R]は二番目に小さい値を必ず1つもつので、二番目に小さい値に着目すればいいとわかる。 着目すると、指定した数字が二番目に大きいとなる条件は、その数字の場所よりも大きい数字がある場所が、今見てる数字の場所の前後の二つさえわかれば、かけ算で計算できる。ここらへんは解説放送を見たほうが早い。 大前提２ 前から見て、新しく見た場所が末尾となる区間に関する計算が前から累積和的、もしくはセグ木的に一回の操作ごとにO(1), O(log n)くらいで求まるのなら、前から見てその末尾ごとに答えを加えればよい。 ちなみに書いてる途中に気づいたけど、この考え方の問題まだ出会ってないし、もしかしたら大原則１に完全カバーされるかもしれない。 例 ある長さNの数列(2 = N = 100000, -10^9 = A_i = 10^9)を与えられる。 1 = L R = Nを満たすすべての(L, R)のペアに対して、[L, R]の区間の和を足し合わせたものを求めよ。 この問題は大原則１で考えると、ある数に着目した時、それを含む区間の数は積で求まるのでそれを合算すればよい。よってとけた。 大原則２で考えようとしたけど無理っぽい。
https://w.atwiki.jp/vivid_turtle/pages/32.html
数え上げは数学的な規則性があまり見られない問題は動的計画法、もしくは数学と動的計画法の合わせ技でほとんど解ける。この際、詳しいことはDEGwerPDFにあるので省略する。でも、意外に思いつかないものをここに書く。 今までのじゃなくて、今のところだけのDP 動的計画法の基本的な配列設定として、ある状態までのすべての総和などが挙げられる。しかし、その考えを棄却することでとける問題もある。すなわち、ある状態においてのみのそれに対応するものである。 このような実装をするとき、総和という操作が遷移式に必要な場合、N次元累積和などが有効なテクニックだと思う。 例えば、二次元累積和の更新の式として、 S(i + 1, j + 1) = S(i + 1, j) + S(i, j + 1) - S(i, j) + value(i, j) を利用することができる。 ちなみに、このタイプのDPテーブルの定義は非常に文字列と相性がいい。 文字列と動的計画法 下の類題は↑のページにも載せる。 ABC130 E(500) Common Subsequence https //atcoder.jp/contests/abc130/tasks/abc130_e この場合、 dp(i, j) = Sのi文字目、Tのj文字目を最後尾として作れる共通部分列の場合の数 とするとうまくいく。動的計画法では珍しく、その状態のみをピンポイント指し、それ以外を含むということはない。 遷移としては、S(i) != T(j)は当然０となる。S(i) == T(j)ならば、dp(a, b)(ただし、a, bはそれぞれi - 1, j - 1まで計(i - 1) * (j - 1)通りすべて)の総和となる。これはSのi - 1文字目,Tのj - 1文字目までのすべての部分列と定義できる。それに最後にSもTにもあるS[i]とT[j]を足せば、新しい文字列となる。 また、今までの文字列を採用せず、S[i]のみで構成することも可能で、これは1通り。 之の実装で、上記の二次元累積和を使用すれば高速に更新できるので、この定義特有のデータ更新時のデータ取得の難しさを解決できる。
https://w.atwiki.jp/nasakenai/pages/126.html
633 ：無名草子さん：2009/02/20(金) 21 34 55 野崎昭弘『離散数学・数え上げ理論』読了。例によってダラダラ締まりのない長文にて詳しくしつこくレビューしマス。 「数え上げる」という「算数」を極めて数学へと至る、という感じの内容。 実際、この種の問題は名門私立中入試でよく出題されるようですね(ブルーバックス『算数100の難問・奇問』などを参照） 冒頭で出されている程度の問題をば算数を駆使してスラスラ解ける小学生というのは普通に存在するわけである。 (まぁそんなガキは泣かしたったらええんですけどね) 1章～3章は、順列・組合せ、パスカルの三角形、確率など。 どちらかというと確率は脇役で、いかに漏れなく効率的に数えられるかというところに重点がある。 4章～5章では、分割数とオイラーの定理、フィボナッチ数・カラタン数とその応用。 ここで「漸化式」と「閉じた公式」が出てきて、次第に算数から数学への橋渡しの様相を呈してくる。 6章からは第二部ということで、やや本格的な理論に足を踏み入れる。 6章では包除原理が扱われる。普通はわかりやすく説明するために、ベン図が用いられることが多いと思うのだが、ここではあえて使っていない。 イメージの助けを借りずに抽象的思考力を鍛えよということか。 7章では、賭博と差分方程式ということで、再び確率が主役となると共に、差分方程式の解法まで説明される。 賭博というネタは数学音痴でも興味を持続できる格好の餌である。そのせいか飽きずに読めた。 8章では自然数のｋ乗和を、最初は幾何的な方法で、次数が上がると代数的な方法で求め、さらに解析学の方法で鮮やかに求めて見せてその威力を知らしめる。 最後に母関数を使って統一的な公式を導き、多少数学らしい世界を垣間見せてくれる。 ⇒アマゾンリンク
https://w.atwiki.jp/tkonishi73/pages/427.html
(5).数え上げ ②－2次元平面の格子点を数える 2つの整数の組と自然数の対応付け 下図のように、対応付けを行う： すなわち、 とする。 例．は何番目？ は番目、正方形の右下の点で考えると、ちょうど２乗の位置にあるので、 は番目。は番目。 同様に、は番目。 この番号の数え方を「体系的」に考えてみましょう。 どの周回グループに属するか まず、点がどの周回グループに属するかを考えましょう。 すると、1週目の点を考えると、 であり、2週目の点は、 です。これらの点に共通する性質は何でしょうか？ 分かりましたか？ そうです。「座標の値の絶対値の大きい方」が何周目かを与えています。 例えば、は3周目、は4周目にあります！ あとは、が番目、 が番目になることが分かれば、 は番目になることが分かります。 以上の性質を使えば、数え上げは出来ます。 例題１、は何番目？ まず、は５周目であることが分かる。 は番目になる。 点の動き方を考えると、であるので、 は番目になる。 よって、は番目。ここで、上にあがっていくので、より、 番目になる。 例題２、は何番目？ は３周目である。 は番目になる。 はの左側にある点で、より、 で、番目になる。 例題３、は何番目？ は４周目である。 は番目になる。 はの右側にある点で、番目になる。ここから上にあがり、 は、だから、番目になる。 そして、はの次の点になるので、番目である。 例題４、は何番目？ は４周目である。 は番目になる。 はの右側にある点で、番目になる。ここから上にあがり、 は、だから、番目になる。 は、だから、番目である。 そして、はの次の次の点になるので、番目である。 例題５、は何番目？ は２４周目である。 は番目になる。 はの右側にある点で、番目になる。ここから上にあがり、 は、だから、番目になる。 そして、はの番目の点だから、番目である。
https://w.atwiki.jp/vivid_turtle/pages/10.html
様々な問題をアルゴリズムごとに区分して陳列する。 それぞれのページに検索用ラベルとしてABC,ARCなどの名前を入れる。 一覧 座標 座標での考えの大前提 座標での最近点 2次元座標と二部グラフ グラフ 数え上げ(数学系) グリッド上での数え上げ ありうる全事象についての変換の和の数え上げ 上のは簡単に言うと、ありうる全事象に変換fをさせた者の和の数え上げ 部分列に関する数え上げ 数学系(その他) 立式と同値の言いかえ 無限を有限に落とすには(数学編) 素数modの世界 同類項の妙技 幾何 包含の幾何 全探索 半分全列挙の各パターン 二分探索 中央値と二分探索 しゃくとり法 しゃくとりの大原則 さまざまなしゃくとり 動的計画法 数え上げのDPのさまざま（知らなかったこと） ナップサックの諸相 DPの加速方法(非データ構造) DPのメモリ節約方法 区間DP bitsetでの定数倍改善 文字列 文字列と動的計画法 貪欲 構築 グリッド上の構築 データ構造 データ構造と値の取得 クエリ処理でのデータ構造特有の手法 転倒数への帰着 実装 実装時にやりがちなミス 謎系 bitに関しての操作のいろいろ N個の集合の合併での最善手 ダブリングの使い所さん
https://w.atwiki.jp/a35taka/pages/16.html
Iteratorパターンとは、１つ１つを数えるためのパターンである。 配列などをfor文でループさせながら一つずつ数えていく処理と同様で、添え字で使用する変数を抽象化、一般化したものをIteratorパターンという。 for(int i = 0; i array.length; i++) { System.out.println(array[i]); } ※上記の「i」を指す Iteratorパターンを実装するには以下の４つのクラス、インターフェースが必要 Iterator 要素の数え上げを行うインターフェース ConcreteIterator 要素の数え上げを行う処理の実装クラス Aggregate 数え上げを行うものの集合を現すインターフェース ConcreteAggregate 数え上げを行うものの集合を現す実装クラス Iteratorパターンのメリット 実際に数える集合体の構造に左右されること無く数え上げの実装が行える。 数え上げを行うクラスが外だしされているため、異なる数え上げの方法がクラスを分けることによってバリエーションを作ることが出来る。 ちなみに、Javaの拡張for構文は内部的にIteratorを使っているらしい Javaではjava.util.Iterator（ConcreteIteratorクラス）とList（Aggregateインターフェース）を使って実装することも可能 Java1.5ではjava.lang.Iteratableインターフェースが追加されている 実装 Iteratorインタフェース package iterator; public interface Iterator { public boolean hasNext(); public Object next(); } Aggregateインタフェース package iterator; public interface Aggregate { public IteratorImpl iterator(); } Iteratorの実装 package iterator; public class IteratorImpl implements Iterator { AggregateImpl aggregate; int index = 0; /** * コンストラクタ。 * * @param aggregate Aggregate実装クラス */ public IteratorImpl(AggregateImpl aggregate) { this.aggregate = aggregate; } @Override public boolean hasNext() { if(this.index this.aggregate.getLength()){ return true; } return false; } @Override public Object next() { String data = this.aggregate.get(this.index); this.index++; return data; } } Aggregateの実装 package iterator; import java.util.ArrayList; import java.util.List; public class AggregateImpl implements Aggregate { List String list = new ArrayList String (); public void add(String data) { list.add(data); } public String get(int index) { return list.get(index); } public int getLength() { return list.size(); } @Override public IteratorImpl iterator() { return new IteratorImpl(this); } Main package iterator; public class Main { /** * メインメソッド。 * * @param args */ public static void main(String[] args) { AggregateImpl aggregate = new AggregateImpl(); aggregate.add("テスト１"); aggregate.add("テスト２"); aggregate.add("テスト３"); aggregate.add("テスト４"); Iterator ite = aggregate.iterator(); while (ite.hasNext()) { System.out.println(ite.next()); } } } Iteratorを使うメリット データの保持方法や数え上げの方法に依存せずにメインの実装が可能であること。 上記例の場合、Listの管理をVecterや配列に変えてもメインの実装には影響が無い。
https://w.atwiki.jp/todo314/pages/303.html
Efficient influence spread estimation for influence maximization under the linear threshold model Zaixin Lu, Lidan Fan, Weili Wu, Bhavani Thuraisingham and Kai Yang Computational Social Networks 2014 概要 LTモデルの影響拡散を厳密or精度良く計算 4hop以内の影響について厳密計算 4hopはRandom walkで近似 性質 $$ \sigma(S) = \sum_{\pi \in P(S)} \prod_{e \in \pi} w(e) + |S| $$ P(S) = S内の頂点から出てる単純経路 シードは入辺を選ばないからSからSへは到達しない 各ランダムグラフ上で各v∈Sから出る部分グラフは木でかつ他の木と交差しないから∑をとれる σ_T(v) T hop以内のvの影響拡散 Tが小さい例 σ_0(v) = 1 σ_1(v) = σ_0(v) + Σ_{u ∈ N+(v)} w_uv 一般には DFS O(Δ^T) T≦4の計算 アイデア C_l(v) = vから始まり閉路を含む長さlの経路の集合 正確には後で定義する奴で －$$ \varrho_T(v) = \sum_{2 \leq \ell \leq T} \sum_{\pi \in C_\ell(v)} \prod_{e \in \pi} w_e $$ $$ \sigma_T(v) = \sigma_0(vv) + \sum_{w \in N^+(v)} w_{vw} \cdot \sigma_{T-1}^{V-v}(w) $$ $$ \sigma_{T-1}^{V-v}(w) $$ = vを抜いたグラフでの$$ \sigma_{T-1}(v) $$の値 ※↑は決してvに到達する経路を数え上げないので等式が成立 $$ = \sigma_0(v) + \sum_{w \in N^+(v)} - \varrho_T(v) $$ 何をしているか？ グラフ全体の各頂点について入辺を確率的に選ぶ σ_{T-1}(w)にカウントされているある経路のがvを含んでいるとマズイ v→…→v→…→tみたいな経路 そういうのをρで除去する ρの計算 補題 T≦4なら$$ \varrho_T(v) $$はO(Δ^2)で計算可能 $$ \varrho_T(v) = \sum_{2 \leq \ell \leq T} \sum_{3 \leq \ell \leq \ell+1} \sum_{\pi \in C_{\ell}^{\ell }(v)} \prod_{e \in \pi} w_e $$ $$ C_\ell^{\ell }(v) $$ vから始まる長さlの経路であってl 番目がvの閉路を構成する (1)v→…→(l )v→…→(l)t $$ \sum_{\pi \in C_\ell^{\ell }(v)} \Pr[\pi] $$を計算したい 長さ4ならば以下の3種類 (Ⅰ) A→B→A→D→C (Ⅱ) A→B→C→A→D (Ⅲ) A→B→C→D→A ※A→B→A→B→Cみたいなのはいいのか？ B→A→Bの時点で除去される（左へと経路を伸ばすことに注意） 計算方法 (Ⅰ) 長さ2の単純経路と長さ2の閉路を前計算 ↑がv以外の共通部分を持たぬようにする 実際には無効なパターンを引く (Ⅱ) 三角形はO(Δ^3)で計算可 (Ⅲ) A→B→C→B→Aみたいなのは避けるように工夫 O(nΔ^2)時間で全頂点のσ_4(v)が計算できる T≧5の近似計算 Monte-Carloシミュレーションは遅いので，乱択アルゴリズム $$ \sigma_T(v) = \sum_{\pi \in P_T(v)}\prod_{e \in \pi} w_e $$ $$ = \text{arg}_{\pi \in P_T(v)} \left[ \prod_{e \in \pi} w_e \right] \times |P_T(v)| $$ 単純経路P_T(v)の数え上げがダルい 任意の経路を数え上げて[πが単純]Pr[π]を計算すると考える ↑の数え上げは漸化式書けば簡単 経路の総数が分かっていればランダムサンプリングして平均っぽいことをすればOK まとめ せやな，という結果 4の根拠とは… 多分そういう研究あるはずだけど，特に言及されていなかったなぁ オープンアクセスだし 影響拡散 影響最大化 情報拡散 2015/04/12 23 53