読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

TopCoder

SRM 566 div1 med: PenguinEmperor

問題 TopCoder Statistics - Problem Statement 解法 入力の名前が長いので, n, m とします。 見た目からして行列累乗っぽい感じがします。具体的には, まず dp[i][j] = (i 日目に場所 j にいるような場合の数) というのを i で, それを調べ終わったら m/n …

SRM 566 div1 easy: PenguinSledding

問題 TopCoder Statistics - Problem Statementn 頂点の無向グラフが与えられる。このグラフから辺をいくつか選ぶとき, 以下の条件を満たす選び方の場合の数を求めよ。条件: 選んだ辺上の頂点を 2 次元平面上でどのように配置しても(ただし 3 頂点が同一直線…

SRM 565 div1 med TheDivisionGame

med にしてはかなり簡単ですね。復帰戦だったのでちょうど良いけど。 問題 TopCoder Statistics - Problem StatementU さんと K さんがゲームをする。ゲームは S = {L, L+1, ..., R-1, R} という数の集合を使って行う。そして, 集合 S の中から何らかの数 X …

SRM 565 div1 easy MonstersValley

院試が終わりました。受かったらそれについてもなんか書きます。 問題 TopCoder Statistics - Problem Statement0 ~ N-1 番までの商品を順番に買っていく。それぞれの商品には値段と重さがあり, 値段は 1 か 2 である。 あなたは, 今までに買った商品の重さ…

SRM 562 div1 med CheckerFreeness

問題 TopCoder Statistics - Problem Statement白い頂点と黒い頂点が与えられる。白い頂点からなる線分と黒い頂点からなる線分で, 交差するものは存在するか。 解法 実は, 線分が交差する場合, 白い頂点の線分か黒い頂点の線分のいずれかはその凸包のいずれ…

SRM 562 div1 easy PastingPaintingDivOne

問題 TopCoder Statistics - Problem Statementクリップボードが与えられる。これは H*W 個のセルがあり, それぞれのセルは透明か RGB いずれかの色をしている。このクリップボードを, 左上が(0, 0), (1, 1), ..., (T-1, T-1) になるように (0, 0) が一番下…

SRM 561 CirclesGame

問題 TopCoder Statistics - Problem StatementAlice と Bob がゲームをする。ゲームは交差しないいくつかの円が書かれた平面上で行う。 まだ円内に赤点がない円を選ぶ。 その円内に赤点をいれる。 赤点を入れることができないほうが負け。 両者が最適に動い…

SRM 561 div1 easy ICPCBalloons

問題文長すぎな。 問題 TopCoder Statistics - Problem StatementN 種類のボールがある。これらは以下のような特徴がある。 大きさが決まっている(medium と large の 2 種類がある) 種類ごとにいくつあるか決まっている 種類ごとに色が異なることは保証され…

SRM 695 div1 hard BearEmptyCoin

問題 TopCoder Statistics - Problem Statementあなたは K 回コインを投げるゲームをする。コインは表裏がそれぞれ 1/2 の確率で出る。ルールは以下のとおりである。 コインを投げてまだ何も書いてない面が出たら, その面に好きな数字を書く。 出た面に書か…

SRM 695 div1 med BearKRoads

問題 TopCoder Statistics - Problem Statementグラフが与えられる。各頂点にはスコアがある。 このグラフから K 本の辺を選び, 以下のようにスコアを計算する。頂点から少なくとも 1 本の選ばれた辺が伸びている場合, その頂点のスコアを得られ, その和がス…

SRM 695 BearPasswordLexic

問題の勘違いはな。 問題 TopCoder Statistics - Problem Statement 以下の条件を満たす文字列を求めよ。ただし, 解が複数ある場合は辞書順最小のものを求めよ。 文字列の長さは N 文字列は 'a', 'b' のみで構成される 配列 x が与えられる。長さ i+1 の部分…

SRM 559 div1 med HatRack

問題 TopCoder Statistics - Problem Statement頂点の接続関係が与えられる。 以下の性質を持つような木の場合の数を求めよ。 葉を除くすべての頂点は, 子を 1 つか 2 つ持つ 木の根からの距離を rank とすると, rank = k の場所には 2^k 個(ただし rank が…

SRM 559 div1 easy HyperKnight

問題 TopCoder Statistics - Problem Statementチェスのナイトのようなものを考える。チェスのナイトは今いる位置から (+1, +2), (+1, -2), (-1, +2), (-1, -2), (+2, +1), (+2, -1), (-2, +1), (-2, -1) と動くことができるが, 今回のナイトは (+a, +2), (+…

SRM 694 div1 easy: TrySail

珍しく秒で解ける問題でした(ここまで簡単じゃなくていいけどこういうの 1 つある方が参加する方も楽しくて良いです)。 問題 TopCoder Statistics - Problem Statementn 人の人がいる。それぞれの人には強さ s[i] が定義されている。n 人を 3 グループに分け…

SRM 557 div1 med Incubator

問題 TopCoder Statistics - Match OverviewDAG が与えられる。次の条件を満たす頂点集合 S の最大の大きさを求めよ。 条件: 任意の異なる 2 つの頂点 i, j S について, i から j へのパスも j から i へのパスもない。 解法 この問題に関して, dilworth の…

SRM 555 div1 med XorBoard

問題名がめっちゃヒント。 問題 TopCoder Statistics - Problem StatementH 行 W 列のグリッドが与えられる。最初グリッド上のセルはすべて 0 であるが, rowCount 回どこかの行を選んでそこのすべての 0 を 1 に変え, 1 を 0 に変える, という作業をしたのち…

SRM 693 div1 easy: BiconnectedDiv1

問題 TopCoder Statistics - Problem Statement無向グラフが 2-edge-connected とは, 任意の頂点の組(u, v) について, グラフ上のどの辺 e を削除しても, いまだ u から v へのパスが存在することを言う。 n 頂点の無向グラフ G が与えられ, 以下の条件を満…

SRM 553 div1 med TwoConvexShapes

問題 TopCoder Statistics - Problem StatementN*M のグリッドを考える。セルのいくつかはすでに黒色か白色に塗られている。残りの箇所を, 以下の性質を満たすように塗りたい。 各色のセルは連結である。 各色のセルは凸である。ここで, 凸とは, 各行, 各列…

SRM 553 div1 easy Suminator

問題 TopCoder Statistics - Problem Statement最初に十分たくさん 0 が詰まっているスタックがある。これに次のような操作をする。 スタックに数 p を入れる スタックから 2 つの数 p, q を取り出し, p+q を入れる このような操作を順番にするプログラムが…

SRM 552 div1 easy FoxPaintingBalls

いろんな意味で嫌らしい問題だった… 問題 TopCoder Statistics - Problem Statementi 行目に i 個のボールを並べるようにして N 行の三角形を作る。この三角形に色を塗るが, 塗る色は R, G, B の 3 種類のみ 三角形内の任意のボールについて, 隣り合ったボー…

SRM 551 div1 med: ColorfulWolves

問題 TopCoder Statistics - Problem Statementあるオオカミは, 毎夜毛の色を変える。毛は colormap[i][j] = Y のとき i -> j に色を変えることができる。毛を変えるアルゴリズムは, colormap[i][j] = Y を満たす 最小の j に毛の色を変える, というものであ…

SRM 551 div1 easy: ColorfulChocolates

問題 TopCoder Statistics - Problem Statementn 文字の文字列が与えられる。maxSwap 回以内の隣り合った文字の交換を許すとき, 「同じ文字が連続して p 個並んでいる」という性質を満たす最長の部分文字列の長さを求めよ。 解法 真ん中の文字を決めます。で…

SRM 550 div1 easy: RotatingBot

問題 TopCoder Statistics - Problem Statement 解法 素直に実装するだけです。あんまりおもしろくない… const int SIZE = 1000; bool done[SIZE][SIZE]; class RotatingBot { public: int minArea(vector <int> moves) { int n = moves.size(); if (n == 1) retu</int>…

2016 TCO Algorithm Round 2B easy: TriangleTriples

はぁ… 問題 TopCoder Statistics - Problem StatementA, B, C が与えられる。1 解法 三角形の辺の組としてあり得ないものを数え, それを A*B*C から引く, というように考えます。あり得ない辺の組としては, a が最大のもの(a >= b+c を満たす) b が最大のも…

SRM 549 div1 med: MagicalHats

問題 TopCoder Statistics - Problem Statement魔法使いとあなたがゲームで勝負をする。ゲームでは, 二次元座標上にいくつかの帽子を置き, そのいくつかの帽子の中にはコインを隠しておく。 あなたは, numGuess 回だけ, 好きな帽子の中身を見ることができる…

SRM 549 div1 easy: PointyWizardHats

問題 TopCoder Statistics - Problem Statement円錐のセットを 2 つ用意する。2 つのセット Top, Bottom は次のように使う。 Top の円錐を Bottom の円錐の上にかぶせるように乗せる。 ここで, Top の円錐の半径は Bottom の円錐の半径より小さくなければな…

SRM 548 div1 med: KingdomAndDice

オーダー落とせずに死んでました。 問題 TopCoder Statistics - Problem Statement1 ~ X の目が書いてあり, 面が N 個あるさいころを二つ用意する。この二つのさいころの目はすべてバラバラである(よって 2*N このさいころを使って簡単なゲームをする。さい…

SRM 548 div1 easy: KingdomAndTrees

問題 TopCoder Statistics - Problem Statementn 本の木が与えられ, それぞれは高さ h[i] である。レベル X の魔法を使うと, それぞれの木の高さを, [max(1, h[i]-X), h[i]+X] の範囲に変化させることが出来る(ただし高さは整数にしなければならない)。この…

SRM 547 div1 med: RectangularSum

問題 TopCoder Statistics - Problem StatementH*W の長方形に, 以下のように数字が書いてある。 (1 行目): 0, 1, ..., W-1 (2 行目): W, W+1, ..., 2*W-1 ... (H-1 行目): (h-2)*W, (h-2)*W+1, ..., (h-1)*W-1ここからうまいこと長方形の区間を取って, その…

SRM 547 div1 easy: Pillars

問題 TopCoder Statistics - Problem Statementw だけ離れて二本の柱が立っている。 一方の長さは 1, 2, ..., x の長さを等確率で取り, もう一方の長さは 1, 2, ..., y の長さを等確率で取る。二本の柱の先端距離の期待値を求めよ。 解法 1 本目の柱と 2 本…

SRM 546 div1 med: FavouriteDigits

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

SRM 546 div1 easy: KleofasTail

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

SRM 690 div1 med: TreeWalker

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

SRM 690 div1 easy: WolfCardGame

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

SRM 545 div1 med: Spacetsk

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

SRM 544 div1 easy: ElectionFraudDiv1

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

SRM 544 div1 med: FlipGame

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

SRM 543 div1 med: EllysRivers

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

SRM 543 div1 easy: EllysXors

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

SRM 542 div1 med: StrangeDictionary2

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

SRM 542 div1 easy: PatrolRoute

問題 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 以下でなければならない…

SRM 688 div1 easy: ParenthesesDiv1Easy

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

SRM 541 div1 med: AkariDaisukiDiv1

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

SRM 540 div1 med: RandomColoring

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

SRM 687 div1 med: AllGraphCuts

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

SRM 687 div1 easy:AlmostFibonacciKnapsack

問題 以下のような漸化式で数列が与えられる。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} が存…

SRM 539 div1 easy: Over9000Rocks

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

SRM 538 div1 med: TurtleSpy

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

SRM 538 div1 easy: EvenRoute

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

SRM 686 div1 easy: BracketSequenceDiv1(その 2)

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