ankicho-example.in

[{"originalNumber":1,"problem":" (アルゴリズム)\n ピタゴラス数を列挙するアルゴリズムを答えよ。もちろん全部は不可能なので、a^2+b^2\u003dc^2でc\u003c\u003dNなるものを列挙するもので良い\n なお、brute forceは認めない。\n","answer":" (3,4,5)を根として3通りの行列をそれぞれかけることによって、それぞれ子として次の頂点へ遷移する、というような処理を続けていく。これで全てのピタゴラス数を列挙できる。(つまり、3分木の構造をしている)\n また、この木の構造上、a^2+b^2\u003dc^2 でc以下を列挙するためには適当に枝狩りをすればよい\n \n 具体的な行列は\n [[1,2,2], [2,1,2], [2,2,3]]\n [[-1,2,2], [-2,1,2], [-2,2,3]]\n [[1,-2,2], [2,-1,2], [2,-2,3]]\n Ab \u003d b\u0027 という感じでかけること。\n \n なお、他にもこれを達成する行列組が存在する。詳しくはリンクで\n \n http://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples#Pythagorean_triples_by_use_of_matrices_and_linear_transformations\n"},{"originalNumber":2,"problem":" (いろいろ)\n 二項係数の反転公式とは何か。答えよ\n","answer":" a(n) \u003d sum[i\u003d0,...,n] C(n,i) * b(i)とすれば、\n b(n) \u003d sum[i\u003d0,...,n] (-1)^(n-i) * C(n,i) * a(i) \n        \u003d sum[i\u003d0,...,n] (-1)^i * C(n,i) * a(n-i)\n \n が成立すること\n \n 例えば、b \u003d [1,1,1,1,1]　ならば\n a \u003d [1,2,4,8,16]である。A2 \u003d C(2,0) + C(2,1) + C(2,2) \u003d 4\n"},{"originalNumber":3,"problem":" (SRM473D1H)\n rows*columsの盤面があり、k種類のrook(飛車)がそれぞれcount[i]個ある。\n 異なる種類の飛車が互いに攻撃しない位置にあるように並べたい。\n このような並べ方は何とおりあるか。MOD10^9+7で求めよ\n \n rows\u003c\u003d30  ,colums \u003c\u003d 30\n k\u003c\u003d10\n","answer":" i種類目のrookがAi行とBi列だけの分を保持しているとする。このときに何通りあるかわかれば、したがってf(i,j,k) \u003d i列j行のなかに、空列空行が無いようにk個配置する置き方の数え上げ、とする。\n このとき、f( Ai , Bi , count[i] )を計算できたとして、メモ化再帰で答えを求めたとすると、30^4*10 \u003d 810万となり、答えを求めることができる。\n では、f(i,j,k)の計算に入る。\n f(i,j,k)はC( i*j , k) から、(x\u003c\u003di , y\u003c\u003dj , (x,y)!\u003d(i,j) の条件下で )f(x,y,k) * C(i,x) * C(j,y)　の総和を引けば求めることができる。\n これは30*30のDP表を10個作り、30^4*10\u003d810万程度の回数の計算が必要そうだとわかり、これも答えを求めれそうだとわかる。\n \n 以上により、答えを求めることができる。\n"},{"originalNumber":9,"problem":" (Codeforces172Div1C)\n 根付き木が与えられる。次の操作を行う。\n \"残っている木の頂点からランダムに一点択び、その頂点をルートとする部分木を消す\"\n \n 点が消滅するまでにかかる操作回数の期待値を求めよ\n","answer":" よくよく考えると、n!の順列で、あるところの番号を見た時、自分の直の祖先が既に選ばれていれば、カウントされない。よって、深さの逆数の総和が答え。\n"},{"originalNumber":4,"problem":" m*nでk個のrook(飛車)のnon-attackingな置き方を数え上げたい\n 何通り存在するか\n","answer":" m!n!/(m-k)!/(n-k)!/k! \n \n http://web.telecom.cz/vaclav.kotesovec/math.htm \n \n 結局C(m,k)*C(n,k)*k!のことである\n k*kの小さい行列の選びかた * どの順でそれをnon-attackingに置くか。\n"},{"originalNumber":5,"problem":" (Permutation / 完全順列の一般化)\n 1~nを一つずつ用いた長さnの数列がある。\n これを並び替えて、k(0\u003c\u003dk\u003c\u003dn)個の数字がもとの数字と同じ場所にあるのは何とおりあるか。\n \n 1\u003c\u003dk\u003c\u003dn\u003c\u003d100000\n が与えられた時にこれを処理することはできるか\n \n NOTE\n k\u003d0の時の数列はモンモール数と呼ばれており、長さnの完全順列の個数の総数である。\n \n 関係は薄いが、ググったら出てくるリンク。ここに書かれてある問題もチェックしたほうが良さそう\n http://techtipshoge.blogspot.jp/2011/05/blog-post_7571.html\n","answer":" このような数え上げをT(n,k)とする。\n T(0,0)\u003d1\n T(n,k) \u003d C(n,k) T(n-k,0)(k\u003e\u003d1)\n T(n,0) \u003d n! - sum[k\u003e\u003d1]( T(n,k) )\n のように表を作ることができる(一度手書きで作ろう)\n \n 次に、\n A(n) \u003d T(n,0)とすれば、\n A(n) \u003d (n-1) * (A(n-1) + A(n-2)) (n\u003e\u003d3)が成立する(これは比較的簡単にわかる)\n また、Aの値は包除原理で求めることが出来る。これをSumの形で書き換えた上で漸化式に落とすと\n A(n) \u003d A(n-1) * n + (-1)^n　--(1)  を得る\n ( A値の例を出すと, A(2)\u003d1, A(3)\u003d2, A(4) \u003d 9 など ) \n \n が出る。したがって、T(n, k)はこの式を用いれば、T(n,0)を始めに列挙することで求めることができるということがわかる。\n \n また、有名な話だが、確率の形 : [ (1)式 / n! ] に直して総和の形でAを含まないように書いた形はe^(-1)のマクローリン展開のn項ぐらいの数と一致するので、A(n)/n! は 1/eに収束する\n \n 参考ページ\n http://kroton1992.hatenablog.com/entry/2014/02/17/233208\n http://oeis.org/A000166, http://oeis.org/A098825 \n"},{"originalNumber":12,"problem":" (http://www.spoj.com/problems/DQUERY/)\n 長さNの整数列が与えられる。\n Q個の区間のQueryがあたえられるので、それぞれの区間の中にある数の集合の要素数を求めよ\n 例えば\n N\u003d5\n 1 1 3 2 1\n で[1,5]は1,1,3,2,1の数があり、{1,2,3}となるので、3.\n \n 制約\n N,Q\u003c\u003d50000\n","answer":" 解法。上記問題であれば、\n 区間を\n  1 1[3 2]1\n [1 1 3]2[1]\n [1 1]3[2 1]\n の5種類の区間を用意する。\n これらの区間に含まれる数を数え上げる。上の例だと0種類なので、3(全体)-0\u003d3という風に答える。\n 他に、[1,2]の区間を考えると、[1 1 3]と[1 1]の区間に囲まれており、3-2\u003d1である。実際、この区間には1しか数字が無いのでこれで正しい\n \n さて、この数の数え上げは、Queryも全部まとめて平面走査を行うことでできる。つまりx-y軸に(区間の左端、区間の右端)の情報でプロットをし、Query用の(x,y)が登場した時にはその平面の二つの直線で区切られた4領域のうち左上側の部分にある点の数を返す。\n"},{"originalNumber":6,"problem":" (AOJ2396, SkyLand)\n 空島がある。 島i の高度h_iを決めたい。\n h_i\u003e\u003d0\n sum(h_i)\u003e\u003dH\n の制約を持ち、\n sum_i bi hi +  sum_i sum_j  c_ij * | hi - hj | \n の関数を最小化するように決める。\n 最適なh_iの値を決めよ\n \n N\u003c\u003d100\n H\u003c\u003d1000","answer":" 補題 : 最適解の中に次のようなものが存在する\n ある島の集合Sで、S中の島の高さがH/|S|, それ以外の島は0\n \n したがって、\n min_(S, |S|\u003e0) (cost(S) + cut(S,T) ) * H/|S|  -- (0)を計算したい\n 二分探索で解くことを考え, (0)のt以下の解が存在したと仮定。\n このとき\n min_(S, |S|\u003e0) cost(S) + cut(S,T)) \u003c\u003d t * |S| / H\n min_(S, |S|\u003e0) [cost(S) -  |S| * t / H ]+ cut(S,T) \u003c\u003d0 --(1)\n min_(S) [cost(S) - |S| * t / H] + cut(S,T) \u003c\u003d0 --(2)\n (2)式のように |S|\u003d0の条件を入れると常に0以下になるので, 少し考察する必要がある。\n (1)を二分探索して得る答えをt\u003dansとして(2)の左辺の最小化問題では 0\u003ct\u003cansのときはこの最小化問題は0, ans\u003ctでは (2)の左辺は負をとる。\n \n さて、b_i \u003d b_i - t/Hをすることによって、\n minimize_(S) sum bi +  sum sum cij を求めれば良くなった。\n maximize_(S) sum (-bi) - sum sum cij --(3) はmaximum closure problemなので\n \n -bi\u003e0 \u003d\u003e s-\u003eiに辺をはる, bi\u003e0 \u003d\u003e i-\u003etに辺を張る, cijはi-\u003ejに張る\n (3)式 \u003d [ sum(i, -bi\u003e0) -bi ]  - max_flow(s,t)  \n ((3)の答え)\u003e0になる最小のtを求めるとこれが最適解となる \n \n NOTE\n 1. 正答データと長いことにらめっこをしていた。\n     バグっていた場所は traverseあたり。誤差の許容が難しかった。flow用のEPSと二分探索用のEPSとtraverse用のEPSを用意することになった。\n あと、doubleでやるとFord-Fulkersonがかなり遅かった。Dinicの方がずっと高速\n 2. …という経緯もあるので、有理数として二分探索をして、long longのフローを流すのが確実なのかなあという感じがする。"},{"originalNumber":7,"problem":" (Euler465)\n 多角形のカーネル (kernel) とは多角形のすべての境界線が見える点の集合と定義される. そのカーネルの内部(辺上を含まない)に原点が完全に含まれるような多角形を極多角形 (polar polygon) と定義しよう.\n \n この問題では, 多角形は同一線上となる隣接する頂点を持つことができる. またどんな多角形も自己交差を持たず, 面積がゼロの部分を持たない.\n \n 絶対値が n 以下となる整数座標 (x, y) を頂点とする極多角形の個数を P(n) としよう.\n \n 多角形は異なる辺の集合を持っていれば, それらがおなじ領域を取り囲むものであっても別のものとして数えることに注意. 例えば, 頂点 [(0,0),(0,3),(1,1),(3,0)] を持つ多角形は, 頂点 [(0,0),(0,3),(1,1),(3,0),(1,0)] を持つ多角形とは異なる.\n \n 例として, P(1) \u003d 131, P(2) \u003d 1648531, P(3) \u003d 1099461296175, そして P(343) mod 1 000 000 007 \u003d 937293740.\n \n P(7^13) mod 1 000 000 007 を求めよ.\n","answer":" 7^13は10^11程度。\n \n P(N)を変形することを考える。\n polar polygon と同値なものを考えると、反時計周りに見た時に原点からの角度が増加列になっていることである(同じ値は含まない)。\n なので、角度が同じ物をひとまとめにしてその個数+1を昇順に並べた数列Anを考える。\n このときP(N) \u003d mult_{i}(Ai) - sum_{1\u003c\u003di\u003cn , 1\u003c\u003dj\u003c\u003dn/2}((Ai -1)* (A(i+j) -1)* (A(i+1)からA(i+j-1)までの積)) - sum{i}Ai  - sum{i} (Ai-1)^2 + 1\n であることがわかる。実はこれの第二項を展開すると大部分が消え、次のようになる\n M \u003d mult_{i}Ai : Aiは第一象限のみをまとめる\n Q \u003d sum_{i}(Ai-1)^2  : 上に同じ　として\n P(N) \u003d M^4  - M^2*(2N+2)(2N) + 2Q -1とできる。\n \n またM,Qはtotient関数の総和を求める要領で計算することが出来る。特に、totient関数の総和を求める際のO(N^(2/3))のやり方の定数倍の時間計算量で実現できる。というのは、必要なのは結局Nに関するtotient関数をそのやり方で求めた時に保存されている値のみで十分だからである。\n \n したがってO(N^(2/3))で実現できる\n"},{"originalNumber":8,"problem":" (Wythoffの石取りゲーム)\n 3山の石があり、一つの山からk個取り除くことか、全ての山から同じ量kの石を取り除くことができる。\n 石の量が与えられるので、必勝状態かどうかを判定せよ\n \n 個数 \u003c\u003d 100\n","answer":" 普通に全部の状態を調べようとするとO(N^4)程度の時間がかかってあまりよろしくない\n \n しかし、一つの座標に対しては一つの必敗状態しか存在しないことを考えると、それを圧縮して、O(N^2)状態を持ち、高々O(N)で表を更新することができる。\n これでO(N^3)に落とせて成功である。\n"},{"originalNumber":13,"problem":" (AOJ2439:Hakone)\n チーム数nの駅伝で、ある区間を終えた後での順位変動が示される。(U,D,D,D,-)といったようにである。これを満たすような順位変動は何通りあるか。\n \n 制約\n 1\u003c\u003dn\u003c\u003d200\n","answer":" まず、順位変動無しは面倒なので縮める。\n \n 次に、左右に一列順位を並べてみる。左が古い方で右が新しい方。新しい方には前開と比較してのU,Dがついているものとする。\n \n 順位の良い方から処理をしていき, i番目を考えてみよう。このとき左側でDのために残してある個数をjとして、右側で対応していないUの個数をkとする。\n このとき、次の遷移はU,Dによって分かれるが、j,kを使用することで表現することができる。\n さて、ここで重要な考察だが、j\u003dkが成立する。\n つまり、未マッチ数は左右ともに同数でなければならない。考えればある意味当たり前で、「全体の未マッチ数」 は同じ。「i以降の未マッチ数」も同じだからである。\n \n 以上により、j,kいっしょくたにして漸化式を作ることができる。\n \n これをもとにdp[i][j]なるものを作ると、一つの遷移あたり2カ所からの更新を考えればよいのでO(n^2)で済むことがわかる\n"},{"originalNumber":10,"problem":" (DPの高速化テクニック / スライド最小値)\n 1. dp[i][j] \u003d min[0\u003c\u003dk\u003c\u003dD[i]] (dp[i-1][j-k] + A[i] * k)\n 2. dp[i][j] \u003d min[0\u003c\u003dk\u003c\u003dD[i]] (dp[i-1][j-k] + sum[j-k\u003c\u003dp\u003c\u003dj-1] A[i][p] )\n \n 模擬地区予選2013 G など。\n 蟻本にも掲載されている\n","answer":" スライド最小値を用いて高速化する\n スライド最小値とは、次のような数列BをO(n)で列挙する技法のことである\n  n, k, A[0],,,A[n-1]が与えられ、B[i] \u003d min(A[i],...,A[i+k-1]) (0\u003c\u003di, i+k-1\u003c\u003dN-1) \n \n これが登場する形に漸化式を修正していく。ポイントは、元々のDPの添字に合うように関数を修正すること\n 1.\n dp[i][j] \u003d min[0\u003c\u003dk\u003c\u003dD[i]] (dp[i-1][j-k] - (j-k) * A[i]) + j*A[i]\n T[i-1][j] \u003d dp[i-1][j] - j*A[i]とおくことで、\n dp[i][j] \u003d j*A[i] + min[0\u003c\u003dk\u003c\u003dD[i]] (T[i-1][j-k])\n \n 2.\n まず、S[i][0]\u003d0, S[i][j] \u003d S[i][j-1] + A[i][j-1] とおく\n 最初の式は dp[i][j] \u003d min[0\u003c\u003dk\u003c\u003dD[i]] (dp[i-1][j-k] + S[j] - S[j-k])\n  \u003d S[j] + min[0\u003c\u003dk\u003c\u003dD[i]] (dp[i-1][j-k] - S[j-k])\n となり、これも上の式同様スライド最小値の技法で解くことができる。\n"},{"originalNumber":11,"problem":" (最小包含円)\n 最小包含円（もしくは球）を解くアルゴリズムを与えよ","answer":" https://www.ipsj.or.jp/07editj/promenade/4309.pdf\n \n http://homepage2.nifty.com/TOMOMI/text/relax1.pdf\n"}]
[{"childTag":[],"name":"ROOT"}]