こういうの苦手っす。 問題 TopCoder Statistics - Problem Statement 解法 近いところでどう動くのが最適かを調べるのは面倒なので, 銀がゴール付近に近づいたら, あとは幅優先探索でごまかす, という方針で解きます。ゴール付近に近づくまでは, 斜めに動き…

問題 No.336 門松列列 - yukicoder 解法 こういう会話があったので, 包除原理で解いてみました。@mayoko_ 包除原理で解けると思います（https://t.co/GQAodcQbvS の部分問題です）— すぎむ (@sugim48) 2016, 1月 15この問題は, 下の問題の部分問題です。 may…

未だに Nisoku ってどういう意味かよくわかってないんですがどういう意味なんでしょう? 問題 TopCoder Statistics - Problem Statement 解法 入力される数が 1.5 以上なので, 大抵の場合 a+b とするより a*b としたほうが得な感じがします。 a 後は, どのよ…

問題 TopCoder Statistics - Problem Statement 解法 数字を小さい順に並べると, i+1 番目の数字は, i 番目の数字が取れる数字はもちろん取れるし, それより大きな数字も取りうる可能性があります。よって, 数字を小さい順に並べて i 番目の数が取りうる数字…

問題 TopCoder Statistics - Problem Statement 解法 まず入力の性質に注目します。カードの枚数を n として, 1, 2, ..., n の n 頂点からなるグラフを考えます。taro[i] から hanako[i] に辺を引く, ということを考えると, 各頂点は必ず次数が 2 になるので…

問題 https://www.facebook.com/hackercup/problem/1525154397757404/ 解法 まず, 前準備として ある文字列から別の文字列に変換する際に必要なコストを計算します。これは, それぞれの suffix がどこまで一致しているかを調べることで求められます。また, s…

問題 https://www.facebook.com/hackercup/problem/1527664744192390/ 解法 X.X... ...... とかなっている場合, X.X の中の . を見えるようにするためには, X.X の . に警備員を置くか, その下に警備員を置くしかないですが, どう考えても下に置くのが得です…

問題 https://www.facebook.com/hackercup/problem/910374079035613/ 解法 点 A, B, C で AB = AC となるときの頂点 A について全探索します。 頂点 A からの他の頂点への距離を全部調べてソートすると, 例えば距離のリストとして 3, 3, 4, 4, 4 となったと…

問題 TopCoder Statistics - Problem Statement 解法 半分全列挙します。N を与えられる文字列 s の長さであるとして, n = N/2 とします。最後の n 文字を, red と blue のどちらにするかは O(2^n) で決められますが, この時 red の文字列のほうが長い場合は…

問題 TopCoder Statistics - Problem Statement 解法 10 の倍数のうなぎは例えば 30 -> 20, 10 -> 10, 10, 10 というように, n*10 のうなぎは n-1 回の切断で n 個の長さ 10 のうなぎを錬成出来ます。ということで, 10 の倍数で短いうなぎから切断していくと…

問題 abc032.contest.atcoder.jp 解法 まず, s[i] のいずれかが 0 だったらすべての値を掛け算した結果は 0 になるので, 答えは N です。 そうでない場合に K = 0 だったら, s[i] > K が任意の i で成り立つので, 答えは 0 です。 それ以外の場合は, しゃく…

「ナップサック問題か〜どのナップサックかな〜 多分半分全列挙？」「全部です」「はい」 問題 abc032.contest.atcoder.jp 解法 蟻本に載ってるナップサック問題の解法を試せば良いです。蟻本第二版での話ですが, 半分全列挙 -> p148 w[i] p52 v[i] p60に書…

ハル研プロコンに参加しました。結果はまだ出てないので後で書きます。そんなにいい順位ではないはずです。もうコンテストは終わって解法について触れても良さそうなので考えたことを書きたいと思います。問題文はこちら↓ www.hallab.co.jp問題文からはわか…

問題 TopCoder Statistics - Problem Statement 解法 x 方向と y 方向の動きが独立であることを利用します(こういう系の AtCoder であったような気がするけどなんだっけ)。x 方向に動く回数を sx, y 方向に動く回数を sy とすると, 回数がこのようになる確率…

問題 TopCoder Statistics - Problem Statement 解法 結論を言うと, 5 で割った余りが 0 か 2 だと先手の負けで, それ以外は先手が勝ちます。勝ち負け表書いたら気づきました。理由は, Nim と同じような証明でいけます。 まず 0, 2 で必敗であることは明らか…

問題 TopCoder Statistics - Problem Statement 解法 N 個の箱とは別の箱 (another box) を「箱」と呼び, i 番目の箱を指すときは 「i 番目の box」とか言うことにします。この問題では, j 種類目のりんごを箱から取り出す確率を直接求めるのではなく, 箱か…

微妙に理由わかってないんですが解説ないのでうーん。ていうかこれ… 問題 TopCoder Statistics - Problem Statement 解法 理由がよくわからないんですが, ある集合 s を選んで, その集合同士でのみジュースのやり取りをした場合, 必ずジュースの量の割り当て…

問題 TopCoder Statistics - Problem Statement 解法 dp[n][r][g] = (n 個目の箱の時点で, 赤色のりんごが r 個, 緑色のりんごが g 個入っているような場合の数) という dp は簡単に解けます。これがわかれば, 求める確率は, dp[N][r][g]/(2^n-1) * r/(r+g) …

問題 TopCoder Statistics - Problem Statement 解法 8x+7 と 4x+3 ですが, 8x+7 = 2(4x+3)+1 です。 また, 4x+3 = 2(2x+1)+1 です。つまり, これらの数は, すべて 2x+1 という式を元につくられています。init に init = 2*init+1 という操作を繰り返して, i…

問題 codeforces.com 解法 greedy に解くことが出来ます。まず, a+b+c それでなかったら, とりあえず a multiset に 各 criminal さんの戦闘力を詰め込みます。 a+b+c 以外で勝てない criminal さんは a+b+c で応戦するしかないので, それで応戦しましょう。…