4-1 「より複雑な数学的問題」の続きです。 連立線形合同式 ai*x = bi (mod mi) (1 中国余剰定理 連立線形合同式の ai を全て 1、mi を互いに素とする 合成数を法とする式はその素因数を法とする式に分解できる n! mod m n! = a p^e (p 素数) とした時 e = Σ…

4-1 「より複雑な数学的問題」からです。 連立一時方程式 Gauss-jordan 消去法 期待値と連立方程式 mod の世界 N を法とした世界で ay = 1 (mod N) となる a の逆元 ax - Nk = 1 となる x を探せばよい フェルマーの小定理 任意の素数 p について x^(p-1) ==…

3-7 GCJ の問題です。 Numbers - (3+√5)^n の整数部下3桁を求める 一般項を求めて共役な式の一般項も求めると、一般項の整数項だけ求めればいいことがわかります 一般項の漸化式から行列の累乗を繰り返し二乗法で求めることで計算できる No Cheating - 椅子…

3-6 ネットワークフローの続きです。 最小費用流 最小コスト通信 - 通信費用が辺毎に決まっている時に費用を最小にする(転送量は決まってる) 最短路を求めつつ貪欲法で解く フロー f が最小費用 残余グラフに負の閉路が存在しない 最短路を求めるためにダイ…

3-6 ネットワークフローの続きです。今日も時間がなくて1トピックだけ。 一般マッチング 二人組 「はーい 2人で組をつくってー」という回答者の心をえぐりかねない問題 「各生徒間の友人関係が与えられるので、最大でいくつの友人同士のペアが作れるか」与え…

3-6 ネットワークフローの続きです。今日は1トピックだけ。 二部マッチング 「仕事の割りあて」 ノードが2つの種類に分かれていて、それぞれの種類の間の対応を辺で表現 端点(ノード)を共有しない辺の集合を「マッチング」といいその要素数が最大なものを「…

第3章 3-6 「水を流して問題を解く "ネットワークフロー"」からです。この節は長いので数日に渡って読むことになりそうです。 最大流 最大通信量 グラフの問題なんだけど特定の経路のコストを注目するのではなくて全体で(可能な全ての経路を利用して)どのく…

第3章 3-5 の途中からです。 行列累乗 フィボナッチ数列 - フィボナッチ数列の n 項目の mod 1000 を求める問題 さらっとフィボナッチ数列の一般項が出てきてる。けど桁があふれるのでこのまま解くのは難しい 漸化式を行列とベクトルの積で表現する → 行列の…

再開します。第3章 3-4 の途中からです。 バケット法と平方分割 セグメント木でも(より効率的に)実現可能 次に 3-5 動的計画法を極める! に進みます 巡回セールスマン問題 漸化式を立式 dp[V][0] = 0 dp[S][v] = min{dp[S + {u}][u] + d(v,u) | u is not inc…

第3章 3-4 さまざまなデータ構造からです。 セグメント木 RMQ(Range Minimum Query) のために使う Crane Binary Index Tree (BIT) 区間の和が求めたい時に使える バブルソートの交換回数 A Simple Problem with Integers 今日はここまで。今週は都合があって…

第3章 3-3 頻出テクニックの続きです。 弾性衝突 同じ質量の球が弾性衝突した時はそのままお互いがすりぬけたように扱えばよい 半分全列挙 全体の場合の数を計算するのは無理なので半分の組み合わせで計算して残りは制約条件を元に計算 巨大ナップサック 品…

第3章 3-2 二分探索からです。二分探索というと木やヒープからの探索をまっさきに想像しますが、本章では「○○という条件を満たす最大(最小)の N を求めよ」という問題で「n が ○○を満たすか」は高速に判定できるような場合に n について二分探索する方法が主…

第3章 3-1 「数学的な問題を解くコツ」からです。 ユークリッドの互除法で最大公約数を求める 2つの格子点の間を結ぶ線分状にのる格子点の数を求めるのに平面ベクトルの x, y 要素の最大公約数を用いる 拡張ユークリッドの互除法 ax + by = 1 となる a, b を…

第2章 最後のGCJの問題を読みます。 Minimum Scalar Product ベクトル2つの要素をそれぞれ昇順、降順にソートすればいい 内積計算時のオーバフローに注意 Crazy Rows まず各行のもっとも右側の 1 の位置を計算しておく Bribe the Prisoners Millionaire (200…

第2章後半2-5 グラフを読みます。まずグラフの一般的な話 有効グラフと無向グラフ 友人関係のグラフは無向グラフ、と書いてあるけど人物相関図は通常有向グラフで描かれるような 重みつきグラフ 連結グラフ 全ての節のあいだにパスが存在する 閉路を持たない…