桁DP入門 - ペケンペイのブログ
$A$ 以下の非負整数のうち「3の倍数または3の付く」かつ「8の倍数でない」数がいくつあるか求めてみよう。でもいきなりこの問題を解くのは難しいと思うので、 $A$ 以下の非負整数の総数を求める $A$ 以下の非負整数のうち、3の付く数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」の数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」かつ「8の倍数でない」数の総数を求める という4つの問題を順に解くことにしよう。 A以下の非負整数の総数を求める 左から順に数字を決めていこう。 左から 4175 と決めたあとの状況を考えてみる。 ? に入りうる数字は何だろう。これは 0 から 9 のどれでもいい。上から 2 桁目が $A$ より小さいので ? に何を選んでも $A$ 以上にはならないからだ。次の場合はどうだろう。 この場合 ? に入りうるのは 0
動的計画法入門（数え上げ） - ペケンペイのブログ
数え上げ系の DP について説明する。 この記事は DP 初心者を対象にしている。DP やるだけみたいなことを一度でも考えたことがある人は対象にしていない。 例題 次の問題を考えてみよう。 N 桁以下の 3 の倍数はいくつあるか。 N が小さければ全列挙できる。i 桁の数がすべて列挙できていれば、その後ろに 0～9 を付け足せば i+1 桁の数をすべて列挙できることを使う。 dp[i] := leading zero を含めて i 桁のすべての非負整数の集合 #include <iostream> #include <string> #include <vector> using namespace std; int modulo(string s, int mod) { int ret = 0; for (char c : s) ret = (ret * 10 + (c - '0'))
約数の個数を O(n^1/3) で求める - ペケンペイのブログ
約数列挙は $O(\sqrt{n})$ 掛かるが、約数の個数を求めるだけなら $O(\sqrt[3]{n})$ でできる。 以下のページを参考にした。 codeforces.com まず $\sqrt[3]{n}$ 以下の素数を用いて $n$ を素因数分解する。 $$ n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r} X $$ $p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ と $X$ は互いに素なので、約数の個数を $d(n)$ と書くことにすると、 $$ d(n)=d(p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r})d(X) $$ が成り立つ。そのため $d(X)$ を求めれば $d(n)$ も求まる。 $X$ は次のいずれかの形をしている。 $$ X=1, \qquad X=p, \qquad X
ラグランジュの定理（群論） - ペケンペイのブログ
この記事では群論の重要定理であるラグランジュの定理の簡単な説明と、 群論を用いたCodeforces 334 (Div. 1) B. Moodular Arithmeticの解法について説明する。 この記事は 群の定義 部分群の定義 群の位数の定義 既約剰余類群 を知っている人を対象として書いた。 さて、ラグランジュの定理とは次の定理のことである。 有限群\(G\)の部分群\(H\)がある。このとき\(|H|\)は\(|G|\)の約数である。 この定理の証明方法と、応用方法を順に説明する。 ラグランジュの定理 ラグランジュの定理を導くのに必要な2つの定理を紹介する。 1つ目の定理は次のようなもの。 定理1：有限群\(G\)の部分集合\(A=\{g_1,g_2,\ldots,g_n\}\)の各元に\(g\in G\)を掛けた集合を \(gA=\{gg_1, gg_2,\ldots,gg_n\
HL分解 (Heavy-Light Decomposition) - ペケンペイのブログ
HL 分解 (heavy-light decomposition) についてではなく、パスクエリを複数の列クエリに分解するという考え方について説明する。HL 分解は木が与えられて次の二種類のクエリを処理する問題等で用いられる。 uv パス上のすべての頂点にxを加算する uv パス上の値の総和を求める 総和クエリの例。この場合は 2+3+4+9+6+4+7+1=36 が答えになる 木ではなく列であれば segment tree によって効率的に処理できる。HL 分解は木をパスに分解することで、木の問題を列の問題に還元する。木をパスに分解するとはどういうことだろうか。例えば次の図のようなものが木をパスに分解した例になっている。 冒頭で例に出したクエリは次の形に分解できる。 このクエリはsum[16..16] + sum[13..14] + sum[0..1] + sum[6..8]で計算できる
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
