問題 TopCoder Statistics - Problem Statement 解法 roads[i][j] == 'Y' だったら頂点 i と頂点 j の間に辺を貼ってみます。すると, それによっていくつかの連結成分が出来ます。その連結成分の中に, 次数が 3 以上の頂点 v があると, v に 2 回以上通らな…

問題 TopCoder Statistics - Problem Statement 解法 石を置く場所を o, 置かない場所を x とすると, ooxxooxxoo ooxxooxxoo xxooxxooxx xxooxxooxxのように, 2 マスおきに見た時市松模様っぽくなるようにするのが最適です。理由を考えてみます。単純な問題…

問題 https://www.facebook.com/hackercup/problem/798506286925018/ 解法 dp[now][num] = (now 個目の問題がコンテストの num 問目で使われる時の追加すべき問題の最小値) という dp をやります。D[now] > 100-(3-num) だと, コンテスト最後の問題の難易度…

問題 https://www.facebook.com/hackercup/problem/1424196571244550/ 解法 制約が 2^K となっていますが, この制約により, この問題のトーナメント方式は, 普通のトーナメント方式と同じであることがわかります(下図)。 そうすると, dp[state][i] = (選手 i…

Yattaze。 問題 https://www.facebook.com/hackercup/problem/512731402225321/ 解法 ある区間 [a, b] における余りが [c, d] となるとすると, あまりの期待値は (c+d)/2 で, 区間の幅 b-a と掛け算すると, (b-a)*(c+d)/2 となります。この掛け算した値のこ…

Facebook Hacker Cup 2016 Round 1 に参加しました。結果は x-oo で, 今回は 30pt 以上あれば良いらしいので Round 2 に行けるみたいです。やったぜ。 問題 https://www.facebook.com/hackercup/problem/1611251319125133/ 解法 貪欲にやっていきます。まず,…