実は引っ越しして一人暮らし始めたんですが、今日になってやっとwifi環境を用意出来たので、精進再開です。http://codeforces.com/contest/959/problem/C 真ん中に2つ点がある木と、rootに全ての点が隣接している木を出力する。 http://codeforces.com/conte…

https://agc010.contest.atcoder.jp/tasks/agc010_fO(N)で心配になった…。まずある頂点vに対して、隣接している全ての頂点piに対してA[v] なぜなら高橋君がvからどこに動かしても、青木くんがvに駒を戻せばいいです。そうすればA[v]がいずれ0となり高橋君は…

https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_d面白い。petrが赤のサイコロを選ぶ確率をX,touristがiが出た時に赤という確率をxiとします。するとtouristが勝つ確率は f(X,x1...x6)=1-X+Σ((pi+qi)X-qi)xiとな…

https://beta.atcoder.jp/contests/agc010/tasks/agc010_dやっぱこういうのは偶奇ですね…。操作を良く観察すると、奇数で割っても偶奇が変わらないことに気づきます。なので列に奇数が2つ以上ある場合、または奇数が1つでもそれが1の場合、結局1ずつdecremen…

http://agc017.contest.atcoder.jp/tasks/agc017_d(ある点vのsubtree)と(vから親pへ向かう辺)で構成されるグラフについてgrundyが求まれば、あとはXORをとれば、pのsubtreeに対してgrundy(p)が求まります。grundy(v)は再帰的に求まるとして、このグラフにvか…

grundy数について勉強したのでお話します。grundy数はご存知の通り、ゲームの勝敗を求める際に使う数なのですが、こんな感じの性質があると思います。1.grundy数は非負整数であり、grundy数=0ならば負け、grundy数>=1ならば勝ちを意味する。 2.grundy数=kの…

http://arc078.contest.atcoder.jp/tasks/arc078_b解法自体は簡単だけど、バグらせたので。 こういう境界でバグらせやすい問題は[a b)の区間で考えるのがよさそう。 [a (a+b)/2)にすると半分、またはそれより1小さくなり、 [a (a+b+1)/2)にすると半分、また…

http://arc072.contest.atcoder.jp/tasks/arc072_bゲームこわいと思ったが、終了状態が(0,1)か(1,1)なのだから、そこからbacktrackしたら結局abs(X-Y) (Brownの勝利)となることがすぐわかる。 ll N, M; void solve() { cin >> N >> M; if(abs(N - M) <= 1) c…