1/27 日記
心が乱れてからいつものペースに戻るのに時間がかかる、くうう
結局自力じゃ解けなかったので、ヒントを見てAC。
・最初の方針
連結成分ごとに分ける
各頂点のCを配列に入れ、ソート
→サイクルじゃなければどこかの頂点のCは1
→頂点Cから到達できる頂点のを1ずつ減らす（減らしたいが、到達できる頂点がどこか定まらないので、この方針は断念）
・次の方針
ある辺に着目して、辺が結ぶ頂点i, jのCi, Cjが異なれば辺の方向は定まる。
→Ci, Cjが同じになるような辺の集合が残り、これらは連結成分ごとに同じ値になっているはず。ただ、具体的な構成の仕方が分からず。
・結局すぬけさんの解説を見て、dfs木という単語を目にしてやることが分かった。
low linkとかよく知らなかったからこれを機に学ぶ。
・OMC…ただただ破滅した()
1/25 日記
今日は作問を少し進めた。
あとはゆっくり休む。おやすみなさい。
1/24 日記
ねむねむにゃんこ
今日はあまり問題数をこなせなかったけど、黄diffを二つ撃破できたからよしとする。
昨日のABC-F。
すごろく系で期待値を求める問題なので、まずは漸化式を立てる。
振り出しに戻るマスの集合をAとすれば、マス i にいるときの期待値dp[i]は
dp[i]=( (1/M) ∑ ( ( j=i+1~i+M )/{A} ) dp[j] ) +( (1/M) ∑ ( j ∈A ) dp[0] ) +1
と表される。
ここで問題になるのはMが大きいという点だけど、dp[j]は何度も計算に使われるから累積和を取りたくなる。後ろから見たときの累積和を rui 、j∈Aとなる j の個数を cnt とすれば、
dp[i]=(1/M)*(rui[i+1]-rui[i+M]) + cnt*dp[0] /M +1
となる。dp[0]の分は別に累積和をとって、dp[0]を求めるときに左辺に寄与分を移行してあげればいい。
・F - Distributing Integers (atcoder.jp)
ちょっと悩んだけど構造は意外と単純だった。
頂点vの子をch 1, ... ch kとし、頂点 i の部分木のサイズをsz[i]すると、
頂点vの部分木に整数を書き込む場合の数dp[v]は
dp[v]=(sz[v])! * ∏dp[ch]/(sz[ch])!
と書ける。（色が着いた球の順列の個数の数え上げを思い出してみよう）
なので、O(N^2)で解ける。これをO(N)で解きたいので、例によって全方位木DPをする。
この問題ではdpとszはともに根とする頂点によって値が変わるため、この二つの値をpairにして全方位木DPをすればいい。
・作問
ちょっとサボっていたけど、今日はテストケースを見直してyukicoderに問題文とテストケースをアップした。明日もう一度見直す予定。
流れが分かったからどんどん問題を作りたいな。
みんな好き。おやすみなさい。
1/23 日記
今日はコンテストもあったけど、あまり集中できていなかった。
バチャを積極的にやっていって集中しようとする時間を増やそうかと思う。
Mが大きいため、A(M)を求めるには何かしらの高速化が必要になる
①ビットごとにみるのはどうか→周期が見えそうな数列ではないため厳しい
➁行列累乗は使えないか→これが上手くいく。単位行列の対角成分はandを取った時に値が変わらないようにする必要があるから、1LL<<32-1としておく。普通の行列累乗をやるときの要素の掛け算がandに、足し算がxorに対応する。
各i ( 1~N )について、A[i]を使わないときのK未満の値の最大値を求められればいい。
普通にdpしようとするとO(N^2K)かかってしまう。ここで、左からのdplと右からのdprをそれぞれ求めておくことで、K未満の値の最大値を高速に求められる。
dplとdprのマージは、それぞれの最大値がKであることからO(K)で可能。
・E - Rotate and Flip (atcoder.jp)
今日のABC。各操作は単純なので、初期位置が与えられたときに各操作後の座標を高速に求められるようにしたいと考えると行列計算みたいのが思いつく（他の方法でも可）。行列計算のとき、初期位置をp=(X, Y)、2×2行列A、2次元ベクトルcを考えると、現在の座標はnow=Ap+cと求めることができる。
つまり、各操作後のA、cを更新していけばいい。
このときに行列の掛け算の順番に注意()。
ABC-Fは明日考える。
ぷらにゃが可愛すぎるね。好き好き
1/22 日記
ねむすぎ ねむねむにゃんこ
今日はなんかとても疲れていたけど、ぷらにゃのぎゅーで復活！
一見難しそうに見えるけど、意外とそうでもない。
後手に必勝法があるとき、先手に毎回同じ状態（負け状態）で手を渡せる操作があることが言える。
負け状態を考えると、二つの山の石の数がどちらも0か1のときとなる。
ここから、二つの山の数の差が1以下という状態が負け状態と予想できる。
実際、山の石の数がどちらもNのとき、片方から2*i個取ってN-2*i, N+iとなり、多い方からまた2*i個とるとN-i, N-iとなって石の数の差は0で保存される。石の数がN, N+1のときも同様に示せる。
・yukicoder（Aのみ）
N, K, Hのうち最も大きいものをXとすると、条件から10^6*X≧Yが言える。
なので、Xの係数を0から10^6まで全探索する。
Xの係数をpとし、Y-p*X=cとすると、ax+by=cみたいな式が出てくる。
これは拡張ユークリッドの互除法を用いると一般解を求めることができる。
G、方針は合ってたみたいだからもう少し考えてみよう。
1/21 日記
ううううう 今日も結局ぷらにゃ～と言ってしまった
やっぱりぷらにゃはかわいいね
まあ精進も出来てるからいいとしよう
のこのこに教えてもらったやつ。
とにかくクエリ数が多いから、まとめて処理したい。
まとめて処理するときは要素をソートすると上手くいくことが多いような気もする（？）
すると辺を番号が小さい順に見ていき、辺が結ぶ2頂点をマージしていくとうまい具合に訪れる頂点数zについても評価ができることが分かる。
ここまでくれば後は並列二分探索で解ける。
ぷらにゃがオイラーツアーをやっていてかわいかったので自分も履修した。
この問題では辺を訪れた順に配列recに入れていき、そのときの深さも記録しておくといい。クエリで与えられた2頂点a, bについて、その頂点の上にある辺の番号i, jを求め、区間[i, j]の深さの最小値mをセグ木で求める。
a, bの深さをそれぞれda, dbとすれば、
ans=da+db-2*m+1
で閉路の長さを求めることが出来る。
明日はこれ↓も読む
2種類のEuler Tourについて - beet's soil (hatenablog.com)
今日は眠いからそろそろ寝かなあ
1/20 日記
今日は一日中ぷらにゃたんと言っていました 流石にまずいね
明日は一日中にうにうたんと言います（反省）
とても眠い
やったこと
この問題を並列二分探索と部分永続UFで解きました
並列二分探索はCODE THANKS FESTIVAL 2017 H - Union Sets （並列二分探索解法） - ARMERIA (hateblo.jp)
部分永続UFは部分永続Union-Find Treeについて - noshi91のメモ (hatenablog.com)
がとても分かりやすかった（部分永続UFはライブラリ化した。まだ任意時刻での集合サイズを実装してないから、明日にでも作ろうか）
・OMC
A~Cの3完だった。D問題、自分がとても好きな構造をしていたから解きたかった。
EもFもとてもきれいな構造をしていて好き。こういう問題作れるの凄いな。
ぽや
