サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
大谷翔平
pekempey.hatenablog.com
https://atcoder.jp/contests/abc169 C問題 decimalを使えば10進数の小数計算は(28桁まで)誤差なしにできる。使い方を忘れてたので調べた。 from decimal import * A, B = map(Decimal, input().split()) print(int(A * B)) D問題 p,p^2,p^3,...の順に使うのが最適。 E問題 Aの中央値とBの中央値の間はすべて作れる。奇数個なら1刻み、偶数個なら0.5刻みなので注意。無証明。 F問題 組合せ的な方法があるのかもしれないけど式変形で解いた。dp[いくつ見たか][総和][使った個数]=組合せ数で解けるのは良くて、最終的な答えはすべての$k$に対して$dp[i][j][k] 2^{n-k}$の総和。$ep[i][j][k]=dp[i][j][k]2^{n-k}$と置きなおして
注意:議論が洗練されておらず、真面目に読むべき記事ではありません。信頼できそうなグラフ理論の書籍を読んだほうが良いと思います。ウェブ上で閲覧できる資料としては以下があり、そこの References を辿ると良いでしょう。 http://mathworld.wolfram.com/GraphCenter.html 中心が高々 2 個であることと、2 個あるならばそれらは隣接していることは F. Harary の ''Graph Theory'' に証明があります。p. 35 の Theorem 4.2 Every tree has a center consisting of either one point or two adjacent points. がそれです。頻繁に参照される記事ではありませんので、この記事を改訂する予定は今の所ありませんが、幾らか思うところがあるので希望があれば
数え上げ系の 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(\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
Mo’s algorithm について説明します。 Mo’s algorithm の動作の様子をアニメーションにしてみました。アニメーションを見れば、計算量解析パートは自明でしょう。IE以外なら見れると思います。 https://pekempey.github.io/mo_algorithm/mo.html Mo’s algorithm とは 区間クエリ系の問題を解くためのアルゴリズム。次のようなクエリに対して有効。 要素が更新されない クエリの先読みが可能 区間 [L,R] の結果から [L-1, R], [L+1, R], [L, R-1], [L, R+1] の結果が容易に得られる Mo’s algorithm の流れ まず区間を平方分割し、左端をキーにしてクエリをバケットに入れる。その後、各バケット内で右端をキーにしてソートする。 結局のところ上の操作は次の比較関数でソートすること
$A$ 以下の非負整数のうち「3の倍数または3の付く」かつ「8の倍数でない」数がいくつあるか求めてみよう。でもいきなりこの問題を解くのは難しいと思うので、 $A$ 以下の非負整数の総数を求める $A$ 以下の非負整数のうち、3の付く数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」の数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」かつ「8の倍数でない」数の総数を求める という4つの問題を順に解くことにしよう。 A以下の非負整数の総数を求める 左から順に数字を決めていこう。 左から 4175 と決めたあとの状況を考えてみる。 ? に入りうる数字は何だろう。これは 0 から 9 のどれでもいい。上から 2 桁目が $A$ より小さいので ? に何を選んでも $A$ 以上にはならないからだ。次の場合はどうだろう。 この場合 ? に入りうるのは 0
この記事では群論の重要定理であるラグランジュの定理の簡単な説明と、 群論を用いた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 分解は木が与えられて次の二種類のクエリを処理する問題等で用いられる。 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]で計算できる
このページを最初にブックマークしてみませんか?
『pekempey's blog』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く