問題 codeforces.com 解法 配列がすべて d の倍数になるように出来るとすると, 配列のすべての数が m*d + x (x は min(k, d-1) 以下の数)という形で表せることになるので, このようになっているかを調べます。d を全列挙したとしても, これを調べるのにかか…

問題 No.301 サイコロで確率問題 (1) - yukicoder 解法 N が十分大きい時は N+(5/3) に収束します。 他の場合は No.75 と同じです。mayokoex.hatenablog.comが, 別の方法で解きました。 各 dp[i] は dp[0] の線形で書けるので, dp[0] = a0 * dp[0] + b0 とい…

問題 No.75 回数の期待値の問題 - yukicoder 解法 冷静に漸化式を立てます。dp[i] = (今のマスが i の時にゴールするために必要なサイコロをふる回数の期待値)とすると, dp[i] = 1/6 * dp[i+1] + ... + 1/6 * dp[i+6]とします。求めたいのは dp[0] ですね。…

Codeforces Round #331 (Div. 2) に参加しました。 AB しか解けず撃沈。C は誤読して難しい問題を解いていたようでアレですが, それに気づいてからも実装に時間がかかるなどしてやっぱり実装力無いなぁと。 問題 codeforces.com 解法 とりあえず誤読してない…

体調悪かったので SRM 673 は不参加です。 問題 TopCoder Statistics - Problem Statement 解法 流れとしては, warrior[0] が何番目の horse を使うかで場合分けをして, それらの場合の足し算をする, という方針でやります。ということで, 1 番目以降の warr…

電車の中で考えて解法がわかったのでワクワクしながらコードを書いたんですが double 周りでつらみが生えた。 問題 www.hackerrank.com 解法 2 進数の各桁 i ごとに, そのビットが立つ確率 p_i を求めると, 期待値の線形性により, 答えは 2^0 * p_0 + 2^1 * …

全然自力で解けないんですが, それは… 問題 code-festival-2015-final-open.contest.atcoder.jp 解法 まず, 区間が 3 つ以上重なっている必要はないことがわかります。3 つ以上重なっている場合, それらを合わせた区間で左端にも右端にもならないものはある…

問題 code-festival-2015-final-open.contest.atcoder.jp 解法 やっぱり解説がわかりやすいと思いますね…前準備として, depth[i] = (i 番目の頂点の高さ), maxDepth[i] = (i を根とする部分木に属する頂点の高さの中で最大のもの) という値を簡単な木 DP で…

問題 code-festival-2015-final-open.contest.atcoder.jp 解法 解説見るのがわかりやすいと思いますが一応こっちでも書きます。まず問題を言い換えます。頂点を通った回数だとわかりづらいので, ド⇔レ の辺を通った回数, レ⇔ミ の辺を通った回数, ..., シ⇔ド…

問題 code-festival-2015-final-open.contest.atcoder.jp 解法 絵がないと険しいので解説に丸投げします(ごめんなさい)。 CODE FESTIVAL 2015 解説 from AtCoder Inc. www.slideshare.net木 -> オイラーツアー -> 区間ごとに分けることが出来るじゃん, とい…

CODE FESTIVAL 2015 決勝 に参加しました。5 完最下位です。ABCDE で辛い思いをしていたら終わってしまって, あまりおもしろいところに食い込めなかったのが残念です。 問題 code-festival-2015-final-open.contest.atcoder.jp 解法 本番は脳筋遅延評価セグ…

問題 abc014.contest.atcoder.jp 解法 lca 使ってやるだけ。木構造では２つの頂点の距離が一意に決まるのが本質的? class Tree { public: Tree(int V, int root) : V(V), root(root) { T.resize(V); for (int i = 0; i < MAXLOGV; i++) parent[i].resize(V);…

問題 No.42 貯金箱の溜息 - yukicoder 解法 持っている硬貨をそれぞれ C[0] = 1, C[1] = 5, ..., C[5] = 500 とします。普通の dp で解こうとすると, dp[x][M] = (C[x] 円以下の硬貨で M 円を支払う場合の数)となりますが, この dp はdp[x][M] = dp[x-1][M] …

問題 TopCoder Statistics - Problem Statement 解法 まず, 明らかにブロックは 高い -> 低い -> 高い -> 低い というような感じでデコボコになっている方が良いです。ということで, ブロックを低い方から順番に並べると, 低い方 8 つは白, 高い方 8 つは黒,…

問題 Angel Stairs | Aizu Online Judge 解法 後ろからたどっていけば良いです。 例えば, ひとつ目の入力例を見ていきましょう。C E D# F G A C E F Gまずそれぞれの配列を逆さまにします。A G F D# E C G F E Cまず G を作る必要があります。スタートが A …

問題 TopCoder Statistics - Problem Statement 解法 「それぞれの人が A と B どちらの噂を先に伝えるか」で 2^n 通りの場合分けをして, それぞれの場合についてシミュレーションします。 const int INF = 1e9; const int MAXN = 20; bool done[MAXN]; clas…

問題 TopCoder Statistics - Problem Statement 解法 右端から何列落とすか/左端から何列落とすか/上端から何行落とすか/下端から何行落とすか で場合分けして全探索します。下のコードは O(h^3 w^3) ですが h, w が十分小さいので間に合います。 const int …

問題 codeforces.com 解法 各マグネットの中心(重心)座標しか興味ないので入力値からそれを求めます。この時, double で管理しようとすると不幸になるのですべての座標が 2 倍されてると考えて座標が整数になるようにしましょう。この重心座標については, ど…

つい最近, 作問ミスをしたので他人事ではない。 問題 codeforces.com 解法 なんとなく思うのは, Warrior 側の人は, 端っこ以外の数字をとっても得しないということです。つまり, Warrior 側の人が取る数字は左端から l 個, 右端から r 個 (l+r = (n-2)/2) と…

問題 codeforces.com 解法 問題の様にセンサを取り付けると, センサはサイクロイドと呼ばれる軌道を描きます。 d = f-s とすると, d の の部分の倍数の部分はどうなろうと関係ないので, 結局のところ調べるべき図形は以下のような部分だけになります。 は左…

問題 No.41 貯金箱の溜息（EASY） - yukicoder 解法 1 円玉を除けば, 六並び国では 111111 円の倍数のお金しか支払うことが出来ません。よって, M 円を 111111 円で割った商を 1, 2, ..., 9 の和で何通り表すことができるか, という dp 問題にすることが出来…

はい･････････････････････････････ 問題 No.298 話の伝達 - yukicoder 解法 割と引っかかる人多い気がするので誤解法も紹介します。 想定誤解法では, dp[i] = (i に話が伝達しない確率)として, 1-dp[N-1] を求めることを目標にします。各 i の dp[i] を求め…

yukicoder に参加しました。初めて作問して出題したのですが, 想定解が間違っていて申し訳ないです… 問題 No.297 カードの数式 - yukicoder 解法 一つ巨大な数を作ってそれ以外の数をひと桁にすると最大, 最小の数が作れそうです。 ただ, マイナス演算子がひ…

問題 No.14 最小公倍数ソート - yukicoder 解法 先に解法を説明してからなんでそれで良いのかを説明する感じでいきます。まず解法ですが, 最初に 各 ai の約数 div を求めていき, divs[i] という配列にその約数を入れていくと同時に, set を用意して set[div…

問題 No.31 悪のミックスジュース - yukicoder 解法 まず, N >= V の場合はそれぞれのジュースを 1 リットルずつ買って適当に分配すれば良いです。 V > N の場合もとりあえずすべてのジュースを 1 リットルずつ買っておけば「使わない果物があってはいけない…

問題 TopCoder Statistics - Problem Statement 解法 まず問題の本質に気が付きましょう。topcoder の解説(http://apps.topcoder.com/wiki/display/tc/SRM+495)がわかりやすいのでそちらを見たほうが良いです。ここでも, 解説の図は topcoder の解説のものを…

問題 TopCoder Statistics - Problem Statement 解法 まず, 問題をもうちょっと噛み砕いてみます。m = firstPicture.size, n = secondPicture.size とします。まず, 場合分けとしては「firstPicture と secondPicture でどれだけボールが移動したか」という…

問題 codeforces.com 解法 Darsein さんの解法を参考にしました。方針としては, dp[m][l][r] = (m 個の n 文字で作ったカッコを並べた時, regular bracket sequence にするために左側に "(" を l 個つける必要があって, 右側に ")" を r 個つける必要がある…

気づくべきことはすぐ気づいたのに漸化式間違えて時間食った。 問題 codeforces.com 解法 要するに, 反転数が 0 になるために何回操作が必要か, という問題です。方針としては, とにかく反転数を減らすのが良いです。状態は反転数のみで記述できて, 反転数が…

Codeforces Round #204 (Div. 1) の練習会に参加しました。今回は B 問題 codeforces.com 解法 まず, 各実数の整数部分は関係ないのでそぎ落としましょう。すると, 基本的には ai の床関数を取ることは ai に対応する整数として 0 を取ることに, ai の天井関…