Hoi_koro memo

Editorialと異なる解法をしたら更新するblog

AtCoder AGC025 B RGB Coloring (解説記事ではない)

AGC AtCoder

問題

B - RGB Coloring

解法

赤と青を独立に塗るだけ．

note

{S = \{ (x’,y') | x',y'\in \mathbb Z, 0 \leq x',y' \leq N, x'A+y'B=K\}}

とする．まず{ (x,y)\in S} を1つ固定し，A点をx回，B点をy回得てK点にする組み合わせを考える．

緑色に塗る個数をi個で固定すると，赤x-i個 青y-i個 緑i個 無(N-x-y+i)個の組み合わせとなるので，塗り方は

{\displaystyle \frac{N!}{(x-i)!(y-i)!i!(N-x-y+i)!}} 通り．

iを動かすことでA点をx回，B点をy回得てK点にする方法の総数が求められ，

{\displaystyle\sum_{i=0}^{\min(a,b)} \frac{N!}{(x-i)!(y-i)!i!(N-x-y+i)!}}通り.

よって答えは

{ans = \displaystyle \sum_{(x,y)\in S} \sum_{i=0}^{\min(a,b)} \frac{N!}{(x-i)!(y-i)!i!(N-x-y+i)!}}

なのだが，解説の通り赤と青は独立に考えることができるので，

{ans = \displaystyle \sum_{(x,y)\in S} \frac{N!}{x!(N-x)!}\frac{N!}{y!(N-y)!}}.

ここから

{\displaystyle \sum_{i=0}^{\min(x,y)} \frac{N!}{(x-i)!(y-i)!i!(N-x-y+i)!} = \frac{N!}{x!(N-x)!}\frac{N!}{y!(N-y)!}}

という等式が得られる??

yukicoder No.5002 stick xor

yukicoder

https://yukicoder.me/problems/no/5002yukicoder.me

成績

51,325点 (4位)

最終的な解法

各長方形を{向き(y軸方向 or x軸方向)，左上の点のy座標，左上の点のx座標}の3整数で表した．従って動かせる値は3k個となる．

3k個の整数をランダムに与えることで長方形の初期配置を行い，焼きなまし法で改善した．遷移は以下の3タイプを1/3ずつの確率で行った．

1長方形の軸方向移動

長方形の長い方向に沿って1マス移動させる．更新O(1). f:id:hiko3r:20180530235250j:plain

平行な2長方形間の長さの交換

平行で，同じ行(または列)上にない2長方形A,Bの長さを交換する(実装上は長方形の位置を入れ替える)．長方形Xの長さをlen(X)とすれば，更新O(|len(A)-len(B)|). 平行・同一行でないという条件をつけているのは，2長方形が重なりを持たないようにして更新を単純にするため． f:id:hiko3r:20180530235254j:plain

1長方形のランダム移動

1長方形Xを取り除き，ランダムな配置で置き直す．更新O(len(X)).

参加記

5/25

参加宣言．なお5/27のマラソン勉強会はこの時点で補欠であり，参加できると思っていなかった．

勉強ということで，レプリカ交換法を焼きなまし法に使ってみることをテーマとした．

上記3種類の遷移によって影響を受けるマスの数を考えると，遷移の「大きさ」は軸方向移動＜長さ交換＜ランダム移動　となりそう．そこで以下の方針を考えた．

  • 3つのレプリカを用意する
  • T1<T2<T3となる3つの温度をそれぞれに与え，徐々に冷却する．
  • 温度T1となっているレプリカは軸方向移動のみの遷移，T2のレプリカは長さ交換のみの遷移，T3はランダム移動のみを行って焼きなます
  • 定期的にスコア差によって決まる確率に従ってレプリカの交換を行う
5/27

マラソン勉強会に参加した． 帰宅後，ランダム移動のみの遷移で焼きなましを書いた．4万点．

5/28

上記のレプリカ交換法を実装した． 49,669点. その後はビット演算を利用して高速化したり，レプリカ交換法をやめて普通の焼きなましに変えるなどの調整のみ行った．

通常の焼きなましに変えた時点で51,089点まで上昇し，暫定トップに． レプリカ交換は実は足を引っ張っていたらしい．

また，長さ交換の遷移を除き，軸方向移動とランダム移動のみの遷移で焼きなましを行ったところ，ローカルの32テストケースで42000点ぐらいしか得られなかった．長さ交換遷移が有効そうだとわかった．

5/29

温度調整のみ行った．残り秒数をtとして

これで51,325点．

5/31

6/1はマラソンに取り組めなさそうなのでこの記事を書き，予約投稿とした．

感想

  • 長さ交換遷移のところを長さiと長さ(i+1)の長方形の交換とするのはよりよい遷移な感じがする．
  • 貪欲で5万点，強すぎる
  • マラソン勉強会の参加記も書く

codeforces ICM Technex 2018 and Codeforces Round #463 E. Team Work

codeforces

codeforces.com

問題

{\sum_{i=1}^n \binom{n}{i} i^k} を{mod 10^9 +7}で求めよ． ({1\leq n \leq 10^9, 1\leq k \leq 5000} )

editorial解法

{\displaystyle f(n,k)= \sum_{i=1}^n \binom{n}{i} i^k}とする．ここで

\displaystyle(1+x)^{n} = \sum_{i=1}^{n} \binom{n}{i} x^{i}\

が成立している．両辺を{x}で微分して{x}をかけると

{\displaystyle x\left(\frac{d}{dx}(1+x)^n\right) = \sum_{i=1}^n \binom{n}{i} i x^{i}}.

両辺を{x}で微分して{x}をかける操作をさらに{k-1}回繰り返すと

{\displaystyle x\left(\frac{d}{dx}\cdots x\left(\frac{d}{dx}(1+x)^n\right)\right) = \sum_{i=1}^n \binom{n}{i} i^k x^{i}}.

右辺で{x=1}とした値は{f(n,k)}なので，左辺を評価して{x=1}とすれば{f(n,k)}を求められる．操作を{a}回行った時の{x^{b}(1+x)^{n-b}}~~(0\leq b \leq k)の係数を{dp[a][b]}とすると{O(k^{2}})時間で計算できる.

codeforcesのコメント欄にあった解法

http://codeforces.com/blog/entry/57761?#comment-414448

{\displaystyle 
\begin{align*}
 f(n,k) & = \sum_{i=1}^{n} \binom{n}{i}  i^{k}\\\
&= \sum_{i=1}^{n} \binom{n}{i}i\cdot i^{k-1}\\
&=n \sum_{i=1}^{n} \binom{n-1}{i-1} \cdot i^{k-1}\\
&=n \sum_{i=1}^{n}\left(\binom{n}{i}-\binom{n-1}{i}\right) \cdot i^{k-1}\\
&=n\left(f(n,k-1)-f(n-1,k-1)\right) \\
\end{align*}}

{\displaystyle f(n,0)= \sum_{i=1}^n \binom{n}{i} =2^{n}-1}を利用すれば{O(k^{2}})時間で計算できる.

他の方法

\displaystyle f(n,1)= \sum_{i=1}^{n} \binom{n}{i} i =n \sum_{i=1}^{n} \binom{n-1}{i-1} = n 2^{n-1}．

また，

{\displaystyle 
\begin{align*}
&\sum_{d = 1}^{k}(-1)^{k-d}\binom{k-1}{d-1}f(n,d)\\
&= \sum_{i=1}^{n} \binom{n}{i}i(i-1)^{k-1}\\
&=\sum_{i=1}^{n} \binom{n}{i-1}(n-i+1) (i-1)^{k-1}\\
&=\sum_{j=0}^{n-1} \binom{n}{j}(n-j)  j^{k-1} ~~(j= i-1)\\
&=\sum_{j=1}^{n} \binom{n}{j}(n-j) j^{k-1} \\
&= nf(n,k-1) -f(n,k).
\end{align*}}

整理すると

{\displaystyle f(n,k)= \frac{1}{2}\left( nf(n,k-1) -\sum_{d=1}^{k-1}(-1)^{k-d}\binom{k-1}{d-1}f(n,d) \right)}.

これらを利用すると{\displaystyle f(n,k)}を{O(k^{2}})時間で計算できる.

note

codeforcesのコメント欄にあった解法が強い．

AtCoder AGC002 D Stamp Rally

AtCoder AGC

agc002.contest.atcoder.jp

問題

グラフ{G=(V,E)}中の辺に番号{1,\dots,|E|}がつけられている。クエリ{(x_i,y_i,z_i)}{(i=1,\dots,Q)}が与えられるので、「辺{1,\dots,p}のみを残した部分グラフ{G_p=(V,E_p)}中で頂点集合{x_i}または{y_i}から到達可能な頂点が{z_i}個以上になる」ような{p}の最小値を各{i}について求めよ。

解法

愚直にやるなら各クエリに対してN要素のUnion-Findを作り、辺1から順に両端の頂点をuniteしていく。到達可能な頂点数（{x_i}と{y_i}が非連結なら{size(x_i)+size(y_i)}）が{z_i}以上になる時の辺番号が答えとなる。{O(QM\alpha(N))}でTLE。

愚直手法ではuniteして{size(x_i)}を調べる操作をクエリあたり{M}回もループしているので、平方分割によりこれを減らせば間に合う。あらかじめ{0,\sqrt{M},2\sqrt{M},\dots}までuniteした{\sqrt{M}}個のUnion-Findを構築しておけば、各クエリは「{k\sqrt{M}\leq ans_i} < {(k+1)\sqrt{M}}となる{k}を二分探索で見つける→{k\sqrt{M}}のUnion-Findからスタートして、辺を1つずつuniteする(最大{\sqrt{M}}回)→解{ans_i}を見つけたら使ったUnion-Findを元に戻す(revert)」操作で処理できる。以下の解答コードではUnion-Findの経路圧縮をしていないので、計算量{O(M\log N+N\sqrt{M}+Q\sqrt{M}\log N)} (1.4sでAC)．第1項は辺1...Mをuniteする操作、第2項は{\sqrt{M}}個のUnion-Findを保存する操作、第3項はクエリの処理。

解答例

note

辺{i}までuniteしたときの{size(x_i)}がすぐにわかるなら二分探索できるので、永続Union-Findを使えば解ける。 永続Union-Findや平方分割のメリットはクエリを1つずつ処理できること。