C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder豆一つをnimの山として考えられる。 よって、全ての茶碗についてgrundy数を求め、A[i]回xorを取った物たちをxorすればいい。難しいのはgrundy数を求める方法。 区間 [ i - c[i] , i ) に含まれない最小…

C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoderN人の中からK人が勝つのにかかる回数の期待値が分かれば解ける。 N人の内、k人が勝つ確率をp(N,K)、N人のじゃんけんが終わる回数の期待値をENとして 整理してやって P(N,K)を求めるには、N…

G - Perm Query問題文より、全ては周期40以下の巡回群である。 あるli~riが揃うまでにはそれらの周期の最小公倍数回だけ操作が必要である。 区間の最小公倍数はセグ木で持てる。 また、操作の和も調べられるので持てる。Submission #3879423 - Japan Alumni …

D - 一次元オセロ (1D Othello)kmjpさんの実装を参考にしました Submission #3867975 - パ研合宿コンペティション 2日目解法 白黒を区間として持てばひっくり返すのが楽です。 操作中の区間は高々N+1個であり、消える区間は端であるため、dequeを使えば実装…

A - Taro vs. Jiro解法 Kの制約が大きすぎるので、少ない場合と同じに考えられることが予想できる。 実際に考えてみると、Kが1なら隣にBがあれば勝ち。 次にどんな操作をされても、Bに戻せるため、Kが奇数のときと1の時を同視していいと分かる。 Kが偶数の場…

A - YahooYahooYahoo編集距離DPをいじった感じでやる。 y f o o y 0 a h o odp[i][j] := yahoo[i]までを、s[j]までで作れる最小手数とする まず、yahoo[i]までをs[j-1]までで作れる時、jを消せばs[j]までを作れるため 右に+1で遷移できる また、s[j]において…

A - Irreversible operation いくつか紙に書いてみるべきだった 毎回WWWWBBBBのようになる Submission #3806738 - AtCoder Grand Contest 029 signed main() { string s = sin(); N = s.size(); int now = 0; rep(i, N) { if (s[i] == 'W') { cou += i - now…

E - Tough Journey解法 安いところでたくさん買いたいので、貪欲に考えたくなる。考えると 今いる場所をiとして K以内の距離でiより安く買える地点がいくつかあるなら、その中の最も近い地点jで買ったほうが得なので、jまで行ける程度に買い、jに飛べばいい…

D - サプリメントdp[i] := i個目まで食べる組み合わせとする 最後の日に添字iを食べる組み合わせは i i-1,i i-2,i-1,i i-3,i-2,i-1,i …のように分けられる また、上はdp[i-1],dp[i-2],dp[i-3]… である この時添字i以前で同じでない最長の区間を足し合わせれ…

A - Uncommonxと互いに素なものを数える場合、xの約数について、それらの倍数の個数が全て分かれば 素因数の数をcとして、包除原理でO(2^c * c)で解ける今回a1 ~ an よって包除原理が使える ここで素因数分解したとき、その数は高々6個である よって、O(N * …

H - Median Game解法 中央値は二分探索 いつものDPで後ろから解けば解ける vi A, B, C; int dpa[1001];//+ int dpb[1001];//sum以上 - sum 以下を最小で何個に vi rui; bool calc(int v) { fill(dpa, -LINF); fill(dpb, LINF); dpa[N] = dpb[N] = 0; for (in…

E: すぬけ君の地下鉄旅行 / Snuke's Subway Trip - AtCoder Regular Contest 061 | AtCoder解法 路線別にvectorへもたせ、dfsで繋がっているもの同士を超頂点に接続する 毎回、すでに見た頂点をusedしたいが、fillするとTLEするので最後に見たtypeをもたせれ…