agc017.contest.atcoder.jp 木の根を含まない部分木を交互に取り除いていき、操作ができなくなった(根しかない状態になった)ほうが負けとする。最適な行動を取る時先手後手どちらが勝つか？ Green Hackenbushとかいう有名問題とのこと。明らかにGrundy数であ…

agc017.contest.atcoder.jp 数列A[i]が与えられる。この数列は時刻tにX[i]番目がY[i]に変化する。時刻tでの数列に於いて、「k個の数がある時、kの数字を削除する」という操作を繰り返すことで数列を空にしたい。そのためには時刻tでの数列から何個の数字を変…

arc078.contest.atcoder.jp 数列a[i]が与えられる。|(a[1]+...+a[k]) - (a[k+1]+...+a[N])|を最小化せよ。 a[i]の累積和sum[i]を計算しておくと、(a[1]+...+a[k]) 及び (a[k+1]+...+a[N]) はそれぞれO(1)で計算可能。これでkを全探索すればよい。O(N)。