サンプルがすごく丁寧。 問題 TopCoder Statistics - Problem Statement 解法 ビンの大きさが 300 で固定であり, かつ入れる品物の大きさが 100 〜 300 で固定されているので, 200 より大きい品物は一つで入れるしかない 101 以上 200 以下の品物は それより…

これ難しい…(というか気づけばやるだけ系は難易度の判定が難しそう)(競プロの問題の 8 割は気づけばやるだけ) 問題 TopCoder Statistics - Problem Statement 解法 頂点 i について, 0 -> i に到達可能でかつ i -> n-1 に到達可能である, という条件を満たす…

問題 TopCoder Statistics - Problem Statement 解法 切り取られていなければならない部分を左上から探索します。 class GogoXCake { public: string solve(vector <string> cake, vector <string> cutter) { int H = cake.size(), W = cake[0].size(); int n = cutter.size(</string></string>…

問題 TopCoder Statistics - Problem Statement 解法 暗号化する前の文字列を str0, 一回暗号化した後の文字列を str1, もう一回暗号化した後の文字列を str2 とします。 入力として与えられるのは str2 ですが, str2 から str1 を求めるのは, O(N^2) の dp …

問題 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>…

問題 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 のとき…

問題 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 つの交わらない凸多角形が存在するときは, それらの凸多角形の間にそれら２つを分断する直線が存在します。よって, あり得る直線の候補を列挙して, 分断された直線による凸多角形を求めて, 最小面積を…

問題 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 すべて等確率であり得る。対称性…

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

なんか早解き出来ない… 問題 TopCoder Statistics - Problem Statement 解法 問題の条件を考えると, 例えば k = 2 の時は, 0, 3, 6, 9, ... 番目の preference に関連性があり, 1, 4, 7, 10, ... 番目の preference に関連性があり, 2, 5, 8, 11, ... 番目の…

SRM 488, やたらと boring が出てくるけど競プロer が「頭悪い」って言うのと似た空気を感じる。 問題 TopCoder Statistics - Problem Statement 解法 以前に似たような問題を解いています。 mayokoex.hatenablog.comB の 2 つの連続部分文字列 C, D では, C…

問題 TopCoder Statistics - Problem Statement 解法 よくわからないので, とりあえずいろいろ実験するためのコードを書きます。 ll bag[5]; int main() { cin.tie(0); ios::sync_with_stdio(false); ll N; cin >> N; bag[0] = N; bag[1]++; ll cnt = 1; whi…

問題 TopCoder Statistics - Problem Statement 解法 1 ラウンドの終わり方は 9 種類あります。(F が J を kill した後 B に kill される… etc)それぞれの回数を p1, p2, ..., p9 とすると, scoreJ, killedJ, ... がその値によって一意に決まります。p1 〜 p…

問題 TopCoder Statistics - Problem Statement 解法 pekempey さんの解法を参考にしました。 pekempey.hatenablog.com凸多角形は上側と下側に分けることができ, 上側の頂点では, 座標を時計回りに見ていった時, 今見ている頂点 p と次の頂点 q について, (p…

問題 TopCoder Statistics - Problem Statement 解法 dp[n][m] = (退屈な人が n 人, そうでない人が m 人である際に, すべての人が 退屈になるのにかかる時間) とすると, 以下のような漸化式が成り立ちます。dp[n][m] = ((1+dp[n][m]) + (1+dp[n+1][m-1]) + …