問題 TopCoder Statistics - Problem Statement 解法 まず, クライアント - クライアント間には data-gate をつなげる必要がないことがわかります。 これは, 例えばクライアント i-j 間に data-gate をつなげることによって, i-j-k-...-n -> Server とつなが…

問題 TopCoder Statistics - Problem Statement 解法 最後の数以外は, number[i] なぜなのかを考えてみます。 貪欲を考えるときは, p 番目の数 number[p] と p+1 番目の数 number[p+1] について, number[p] 最後の数以外を考えているので, number[p] を足し…

これ英語読めない日本人には厳しすぎる… 問題 TopCoder Statistics - Problem Statement 解法 やるだけ。stringstream 使うとなんとなく簡単に書けます。 bool done[55]; class InternetSecurity { public: vector <string> determineWebsite(vector <string> address, vecto</string></string>…

問題 discovery2016-qual.contest.atcoder.jp 解法 入力文字列 s の長さを N とします。もし s の中に N-K 個以上 a がある場合は, N-K 個の a を最終的な文字列にするのが最強です。別の場合は, a のみを残す, という戦略は出来ないので, a をなるべく手前…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選に参加しました。なんとなく早解きコンテストになるんじゃないかと思っていましたが面白かったです。非競プロ勢には厳しかったような気がしますが。 問題 discovery2016-qual.con…

問題 TopCoder Statistics - Problem Statement 解法 2 つ解法があるみたいですが, とりあえず DP 解で書きました。topcoder の 解説に他の解(最大マッチングに持ち込む)があったので, そっちにも少し触れます(書いてないので言ってることが正しいかわかりま…

問題 TopCoder Statistics - Problem Statement 解法 div2 hard と同じく, 各ユーザーごとに, 合計時間が短いやつ順に並べるのが最適です。 mayokoex.hatenablog.com 合計時間ごとに並べるので, あるユーザー u が使いたい合計時間 total 未満で処理が終わる…

問題 TopCoder Statistics - Problem Statement 解法 user ごとに, タスクの合計時間が決まります。 合計時間が短いものから順にタスクをこなしていくのが明らかに最適なので, そのように並べましょう。 class BatchSystem { public: vector <int> schedule(vecto</int>…

問題 TopCoder Statistics - Problem Statement 解法 落ち着いて状況を整理すると, 以下のような表になります。 表の i を決定すれば, j, k, l は決定されるので, i を全探索しましょう。 真実が egg の時は k+i が eggCount になり, 真実が chicken のとき…

問題 No.340 雪の足跡 - yukicoder 解法 ある頂点から進むことのできる方向に制限ができるので, それを基に幅優先探索するのが基本です。ただ, 進むことの出来る方向を愚直に決定すると から の間で, 進む方向をメモするのに最悪 O(W) (O(H)) かかって, 入力…

問題 TopCoder Statistics - Problem Statement 解法 「こんなの二分探索するだけでしょｗｗｗｗ」って感じですが, それだけだと落ちます。単調性を持たないからです。ただ, ある数 C が最小の答えであるとすると, C+maxw でも羊を運ぶことが出来ます(maxw …

問題 TopCoder Statistics - Problem Statement 解法 influence の値はたかだか 500 なので, now 番目の人は, now+8 番目までの人にしか影響は及ぼしません。そこで, dp[now][state] = (now 番目の人で, now-8 番目から now+7 番目の人への賄賂を送ったか送…

問題 TopCoder Statistics - Problem Statement 解法 mayokoex.hatenablog.comさっきとほとんど同じです。今度は maxDen の値が大きいので, B を決めた後の A の範囲をある程度絞り込みます。 A の値はだいたい B*number となっているのが良いので, B*number…

問題 TopCoder Statistics - Problem Statement 解法 maxDen の値が小さいので, A, B のすべての候補を総当りします。B/A の小数点以下の数は, B/A をそのまま見ると整数部分, 10*B/A を見ると小数点第一位以上, 100*B/A を見ると小数点第二位以上が見れる, …

問題 TopCoder Statistics - Problem Statement 解法 1 回の操作で必ず component の数が半分以下になります。 また, sample 1 のように, 「あと 1 回で操作をやめたい」と思ったら, component のひとつ目の要素と, 他の component を小さい辺で結べば終わり…

問題 TopCoder Statistics - Problem Statement 解法 dp[b][even][odd] = (b 以下の数の set で, 偶数の数が even で奇数の数が odd であるようなものは存在するか) とします。普通に dp して dp[b][n/2][n/2] が true かどうか見るだけですね。 int dp[1010…

問題 TopCoder Statistics - Problem Statement 解法 2 つの交わらない凸多角形が存在するときは, それらの凸多角形の間にそれら２つを分断する直線が存在します。よって, あり得る直線の候補を列挙して, 分断された直線による凸多角形を求めて, 最小面積を…

問題 codeforces.com 解法 p 個の数字を使えるとすると, その p 個の数字は w の大きい方から順に選ぶのが明らかに最適です(w は関係ないですね)。ということで, 問題は N 個からなる数列が与えられた時, 最大いくつまで数字を使えるか, の p を求めることで…

問題 codeforces.com 解法 配列 a の s 〜 s+p*(m-1) にある, p 個おきの 配列 b の要素数を数えます。この要素数が b の要素数と一致していれば嬉しいですが, これを高速に数えたいです。これは, 蟻本の p137, p138 に書いてある問題と似ています。 cnt[i] …

問題 codeforces.com 解法 まず, 2 文字以下なら絶対にアルゴリズムは終了します。3 文字以上の時は, xzy または yxz または zyx が繰り返し並ぶ構造になっていれば収束しますが, これは 指定された区間における x, y, z の数が区間の長さの大体 1/3 になっ…

問題 A Broken Door | Aizu Online Judge 解法 前のドワコンの C 問題に似てるということで解いてみました。今回は前回のように二分探索で解くのではなく, ダイクストラっぽく解きたいと思います。ゴール地点からスタート地点に向かって探索します。ゴール地…

問題 https://www.codechef.com/problems/CIELBTL 解法 基本的に dp[va][vb][m] = (自分の残り HP が va で敵の残り HP が vb で残り MP が m である時の勝率)という DP で解けますが, いろいろ難しいところがあるので, ひとつずつやっていきます。まず, 「…

問題 TopCoder Statistics - Problem Statement 解法 配列の最小値と最大値を決めると, 配列内の数字の並びは一定になります。 よって, dp[mini][maxi] = (配列内の最小値が mini で, 最大値が maxi であるような配列で, swap する回数の期待値) とすれば, …

ぶっちゃけ Crazy ではない。 問題 TopCoder Statistics - Problem Statement 解法 明らかにデコボコに人を並べるのが良いです。 大まかな方針としては, 背の高さを低い方から半分, もう半分に分けて, 奇数番目に背の低い人, 偶数番目に背の高い人を並べるよ…

問題 TopCoder Statistics - Problem Statement 解法 s から t を考えるといろいろ可能性があって面倒ですが, t から s を考えれば, ・t が平方数 -> s は t の平方根 ・t が偶数 -> s は t の半分 とほとんど場合分けがなくなり, また, t の遷移回数は 2^30…

問題 TopCoder Statistics - Problem Statement 解法 この問題は typical DP contest の準急に非常に似ています(というかこれが元ネタかな？)。ある数 x について, g(x) がどうなるか, と考えるのではなく, 逆に考えます。1 から逆順に作れる数を辿って行っ…

問題 TopCoder Statistics - Problem Statement 解法 答えが -1 でないとすると, 答えは m/k となります。答えが -1 でない時, RandomAnser は 1 〜 k の答えを等確率で出力します(x 番目の答えとして選ばれる数字は 1 〜 k すべて等確率であり得る。対称性…

問題 s8pc-1.contest.atcoder.jp 解法 半分全列挙 + 平面走査 で解きます。半分の要素について, 残す食品が e 個あるという前提での残りの食品のわけかたを全列挙します。 square1001とE869120の合計値段の差を x 軸に, square1001とうさぎの合計値段の差を …

問題 TopCoder Statistics - Problem Statement 解法 x の値から 次の y を考えるのは難しいですが, y の値から 元の x が何であったかを推定するのは, x = -y^2 - z^3 (mod n) と簡単に出来ます。よって, 各 y について対応する x を求め, x -> y に辺を貼…

問題 dwango2016-prelims.contest.atcoder.jp 解法 二分探索します。ok(x) = (時間 x 以下で目的地にたどり着けるか) を判定する関数を作ります。そのために, ダイクストラのようなことをしますが, ある頂点 v に時間 t にたどり着けることがわかったとして,…