デラノイ数って? (以降「縦」と表現) (以降「横」と表現) (以降「斜め」と表現) 漸化式 表現方法その1 を「斜めを使う回数」とする。 を固定すると，縦回，横回，斜め回を並び替えるので通り数は 。 これをすべての について足し合わせて となる。 表現方法…

おことわり この記事は厳密性を保証しません。 Floor Sum とは？ を高速に求めるやつ(ただしで，)。 どういうアルゴリズムを使えばいいのか まず，， として ， の状態を作り上げます。すると となります。 と は簡単に求められるので， の部分をうまく求め…

問題概要 から までの番号がついた 個の箱があり，箱 に入っているボールの数は である。 個の数から等確率で つ選んでボールを 足すという操作を 回 繰り返す。箱 に操作後に入っているボールの数を として の期待値はいくらか。 (問題文は https://atcoder…

問題概要 個のボールがあり，個は赤色で個は青色である。 個 のボールのうちの個を指定してその個のボールのうちどちらの色の方が多いか，という質問を 回まですることができる。 このとき， 個のボールの色をすべて当てよ。 (問題文は https://atcoder.jp/c…

問題概要 から までの 個の数を つずつ 個のペアにするとき，差が のペアが 個，差が のペアが 個，差が のペアが 個あるようなペアの作り方は何通りあるか。 (問題文は https://atcoder.jp/contests/cf16-exhibition-final/tasks/cf16_exhibition_final_j …

問題概要 とが与えられる。このとき かつ を満たす整数の組の個数を求めよ。 (問題文は https://atcoder.jp/contests/abc138/tasks/abc138_f に記載されている。) 制約 アイディア の条件下で が成り立つことが証明できる。よって， が成り立つときには必ず …

問題概要 頂点からなる木が与えられる。 番目の辺は と を結んでいる。 最初それぞれの頂点にコインが枚おいてある。高橋くんと青木くんはそれぞれコインが置いてある頂点 をつ選びその頂点に置いてあるコインをすべて取り，そのあとすべてのコインを に距離…

問題概要 が与えられる。 個の頂点と 個の辺を持ち，かつ頂点から頂点への異なるパスがちょうど個あってそれらのパスがそれぞれであるような有向グラフを構成せよ。 (問題文は https://beta.atcoder.jp/contests/arc102/tasks/arc102_b に記載されている。) …

問題概要 の個の数の組が与えられる。を満たすそれぞれのについてかつを満たすの個数を求めよ。 (問題文は https://beta.atcoder.jp/contests/abc106/tasks/abc106_d に記載されている。) 制約 アイディア の制約がと小さいことに注目する。 とりあえず，次…