人の不幸で飯がうまい 問題 TopCoder Statistics - Problem Statement数 n が与えられる。n 以上の数で, 以下の条件を満たす最小の整数を求めよ。 10 進法で表したとき, その数には count1 個以上の digit1 が含まれる。 10 進法で表したとき, その数には co…

問題 TopCoder Statistics - Problem Statement数 X から始まる数列を以下のように定義する。 X が偶数なら, 次の要素は X/2 X が奇数なら, 次の要素は X-1 これを無限に繰り返す 最初の要素が [A, B] のもののうち, 数 K が少なくとも一つ含まれるようなも…

問題 TopCoder Statistics - Problem Statement有向グラフ G について, p(G) は, 「頂点 (v, u) について, v -> u のパスがあるような組み合わせの数」と定義する。今, 無向グラフで木のグラフが与えられる。このグラフのそれぞれの辺の向きを決め, 有向グラ…

問題 1, 2, ..., 100 が書かれたカードを使って A 君と B 君がゲームをする(カードはそれぞれ 1 枚ずつ)。ある数 N, K が与えられて, A 君は K 枚のカードにかかれている数を足し引きして合計を N にしたい。 B 君はカードを上手く選ぶことによって A 君がど…

問題 TopCoder Statistics - Problem StatementL*H のグリッド平面が与えられる。以下の条件を満たす K 個の点の組は何通り考えられるか。 K 個の点は同一直線上にある 上記の直線は, y = 0 において x 座標が整数になる 解法 K=1 の場合は, 答えは明らかに …

問題 TopCoder Statistics - Problem Statementx(1 以上の整数) 人の有権者が n 人の候補者に投票をする。n 人の票獲得率(a 人から票を獲得した場合 a/x*100 )を四捨五入した一覧が与えられるので, x としてあり得る最小値を求めよ(ない場合は -1)。 解法 10…

問題 TopCoder Statistics - Problem StatementH*W の盤面があり, それぞれのセルには 0 か 1 が書かれている。これを以下の操作を繰り返すことでセルに書かれた数をすべて 0 にしたい。操作：盤面の辺を通る経路で, 左上から右下まで最短経路で行く。最短経…

問題 TopCoder Statistics - Problem Statement地点(0, 0) から 地点(n, L) まで移動したい。ただし, 地点 (i, y) と地点 (i+1, y) は距離 w[i] だけ離れている。 移動の仕方としては 2 通りの移動の仕方がある。 (i, l1) から (i, l2) まで速度 walk で歩い…

問題 TopCoder Statistics - Problem StatementL から R までの xor を取った整数の値を求めよ。 解法 各桁ごとに bit が立っているかを調べます。 2^i の桁が立っているかどうかを調べる時は, i 桁目の bit は 2^(i+1) 周期ごとに現れたり消えたりすること…

問題 TopCoder Statistics - Problem Statement同じ長さ L の文字列が n 個与えられる。これを辞書順にソートするのだが, ソートの仕方が少し特殊で, 長さ L の順列 p が与えられて, p[0] 番目の文字, p[1] 番目の文字, ..., p[L-1] 番目の文字, という順番…

問題 TopCoder Statistics - Problem Statement点(x1, y1) から点(x2, y2) への距離を |x2-x1|+|y2-y1| と定義する。0 A, B, C の x の値は異なる。 A, B, C の y の値は異なる。 A -> B -> C -> A と一周する長さは minT 以上, maxT 以下でなければならない…

問題 TopCoder Statistics - Problem Statementいつもの様に valid な括弧列を定義する(stack で上手くいく〜ってアレ)。 ある括弧列 s が与えられ, これを valid な括弧列にしたい。s に対して行える操作は l, r で特徴づけられ, 次のことを順番に行う。 [l…

問題 TopCoder Statistics - Problem Statementstring X に対して, f(X) = W+X+A+X+D と定義する(+ は文字列をつなぎ合わせることを表すオペレータ)。 また, f^k(X) = f(f^(k-1)(X)) と定義する。f^k(S) の中に, 文字列 F が何回現れるかを数えよ。 解法 「X…

解法わかっても結構エグイ問題。 問題 TopCoder Statistics - Problem Statement0, 1, ..., N-1 番目の看板に順番に色を塗っていく。塗る色は RGB 値で構成されている。i 番目と i+1 番目の看板の間で塗る色には d1, d2 で表される制約があって, i 番目の看…

問題 TopCoder Statistics - Problem Statement頂点のペア (i, j) に対して, 「頂点 i と頂点 j に対する最小カットは x[i*n+j]」という条件を表す n*n 要素の配列 x が与えられる。 この条件を満たす重みつき無向グラフがあるならそれを出力し, 存在しない…

問題 以下のような漸化式で数列が与えられる。a[1] = 2 a[2] = 3 a[n] = a[n-1] + a[n-2] - 1また, 2 以上 10^18 以下の整数 x が与えられる。各値が互いに異なる数列 b1, b2, ... を用いて x = a[b1] + a[b2] + ... + a[bn] としたい。このような {bi} が存…

問題 TopCoder Statistics - Problem Statement 解法 選ぶグループを決めればその箱のグループで得られる石の最小値, 最大値がわかります。得られる石の数は明らかに連続に取れるので, mp という配列を用意して, mp[最小値] = (最大値) となるようにしておき…

問題 TopCoder Statistics - Problem Statement 解法 forward に全振りして進む -> 適当に回転 -> backward に全振りして進む -> 余った分の回転をする というのが最適になります。以下しばらく適当な説明↓「forward に全振り」って言うのが正しい場合は, ba…

問題 TopCoder Statistics - Problem Statement 解法 実はめっちゃ簡単です。 「(0, 0) からの距離が wantedParity と一致する点が一つでもあれば YES, そうでなければ NO」と言えます。なぜかというと, 一致する点が一つでもある場合, (0, 0) から頂点に訪…

さっきの問題の dp 解です。 mayokoex.hatenablog.comdp[l][r] = [l, r) の区間における, valid な括弧列の数, とします。valid な括弧列の生成の仕方は, l 番目を無視する(区間 [l+1, r) ) l 番目と i 番目が一致する時, [l+1, i) と [i+1, r) に分けて考え…

問題 TopCoder Statistics - Problem Statement 解法 制約からして半分全列挙だろと思い dp は考えませんでした(あとで dp 解書きます)。前半部分で例えば " ( ( ) ( [ ] [ (" という文字列を取り出したら, 対応する括弧を取り除いて " ( ( [ ( " にします("…

問題 TopCoder Statistics - Problem Statement 解法 求める条件は, 「任意の p, q(>= 0) に対して, ある r, s(>= 0) が存在して, p*A + q*B = r*X+s*Y」が成り立つことですが, この条件と 「"ある r, s が存在して, A = r*X+s*Y" かつ "ある r, s が存在し…

問題 TopCoder Statistics - Problem Statement 解法 まず最初に, 「ある頂点からはどの頂点に行けるか」というのを dfs してメモっておきます。この問題は実は貪欲に解けます。すなわち, 「now = 0 からスタートし, now -> next と移動してもすべての頂点を…

問題 TopCoder Statistics - Problem Statement 解法 二分探索します。check(x) = (ペアの socks の差が x 以内で P 個のペアを作ることが出来るか) というのを求められれば良いです。 これには貪欲解法が使えます。まず S をソートし, 0 から順番に見ていき…

Laycrs さんがこどふぇすの時言ってた問題多分これですね。 問題 TopCoder Statistics - Problem Statement 解法 ｴｲﾔでサンプル合わせたら WA 食らったので editorial 見ました。 http://apps.topcoder.com/wiki/display/tc/SRM+536まず様子を観察して見るた…

問題 TopCoder Statistics - Problem Statement 解法 先に併合されるものほど, 影響が小さくなります。よって, 以下のような解法で解けます。まず小さい順にソートして, dp をします。dp[i] = (i 番目までで得られる平均値の最大値) とすると, dp[i] は, dp[…

問題 TopCoder Statistics - Problem Statement 解法 とりあえずいろいろ書いてみましょう。0, 1, ..., K-1 の社員を選択するとします。この時, ability の和を A とすると, 各社員は等しい時間働くので, 各社員のはたらく時間は totalWork / A です。で, 各…

問題 TopCoder Statistics - Problem Statement 解法 各素因数に対して (L の指数) >= (G の指数) を満たしていなかったら, すなわち L%G != 0 なら -1 を返します。そうでない時は, A, B は a = G*a, b = G*b と表されています(a, b は互いに素)。 で, この…

問題 TopCoder Statistics - Problem Statement 解法 kmjp さんのブログを参考にしました。 kmjp.hatenablog.jp包除原理(ってこれは言うのか)で解きます。ok[i] = (i 個の数を並べた時の valid な数列の数), ng[i] = (i 個の数を並べた時の valid でない数列…

問題 TopCoder Statistics - Problem Statement 解法 互いに素なものしか使えませんが, 例えば n が 4 の倍数の時, 掛け算の要素として 2 を選んでしまうと, もうひとつ 2 の倍数を取らないといけなくなるので, 条件に合いません。このように, n の各素因数…