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

mayoko’s diary

プロコンとかいろいろ。

TopCoder

SRM 686 div1 easy: BracketSequenceDiv1

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

SRM 537 div1 easy: KingXNewCurrency

問題 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 が存在し…

2016 TCO Algorithm Round 1A hard: EllysTree

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

2016 TCO Algorithm Round 1A med: EllysSocks

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

SRM 536 div1 med: RollingDiceDivOne

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

SRM 536 div1 easy: MergersDivOne

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

SRM 535 div1 med: FoxAndBusiness

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

SRM 635 div1 easy : FoxAndGCDLCM

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

SRM 684 div1 med: DivFree

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

SRM 534 div1 med: EllysNumbers

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

SRM 534 div1 easy: EllysCheckers

問題 TopCoder Statistics - Problem Statement 解法 制約が小さいので脳筋 bitDP しましょう。 int n; int dp[1<<20]; int dfs(int state) { int& ret = dp[state]; if (ret >= 0) return ret; for (int i = 0; i < n-1; i++) { if ((state>>i)&1) { int ne…

SRM 684 div1 easy: CliqueParty

この問題, 感覚的にはそこそこ速く解いたつもりだったのにクッソ点数が低くなって, もうダメという感じでした。 問題 TopCoder Statistics - Problem Statement 解法 この問題で大切なのは結局配列 a の最小値 mini と最大値 maxi が, k*mini >= maxi を満た…

SRM 683 div1 med: GCDLCM2

問題 TopCoder Statistics - Problem Statement 解法 まず x と y を使って操作をしたらどうなるのかを考えてみます。x と y の最大公約数を g として, x = g*x1, y = g*y1 であったとすると, 新しくつくられる 2 つの整数は g, g*x1*y1 となります。これが …

SRM 683 div1 easy: MoveStones

問題 TopCoder Statistics - Problem Statement 解法 円環の問題では, 円環のまま考えるのではなくどこかでぶった切って直線にして考えるのが定石です。今回の問題でもその手法が使えます。移動する石の数は, 隣接している皿同士を結ぶ辺について, 「その辺…

SRM 533 div1 med: MagicBoard

問題 TopCoder Statistics - Problem Statement 解法 見た目がハミルトンパスに見えますが, 実はオイラー路の問題になります。蟻本の p205 に書いてあるようなグラフを作るようなイメージです。二部グラフ (U, W) を作るのですが, board[i][j] == '#' ならば…

SRM 533 div1 easy: CasketOfStar

問題 TopCoder Statistics - Problem Statement 解法 区間 DP で解くことが出来ます。dp[l][r] = (区間 [l, r] において得ることの出来るスコアの最大値) とします。区間 [l, r] の中では, 最後に残るのは, l 番目と r 番目の数です。最後に m 番目(l 区間の…

2013 TCO Algorithm Round 2B med: ScotlandYard

問題 TopCoder Statistics - Problem Statement 解法 まず, Jiro 君が今 Ciel さんのいる場所を特定する方法を考えてみます。 Ciel さんは最初, 0, 1, ..., n-1 のいずれかにいる可能性があります。この集合を S としましょう。そこで Ciel さんが "taxi" と…

SRM 682 div1 med: SuccessfulMerger

問題 TopCoder Statistics - Problem Statement 解法 最終的には, スターグラフにして, その中心みたいな頂点を capital にすることになりますね。 Star Graph -- from Wolfram MathWorldグラフは木 + 1 本の辺, という形をしていて, 1 つだけ閉路があります…

SRM 682 div1 easy: SmilesTheFriendshipUnicorn

何もわかってなかった僕が言うのもなんなんですが何も考えず脳筋 dfs で通ってしまうのはちょっとアレですね… 問題 TopCoder Statistics - Problem Statement 解法 結局脳筋 dfs (各頂点からスタートして, パスの長さが 4 になるようなものがあるのかを調べ…

2013 TCO Algorithm Round 2B easy: FruitTrees

問題 TopCoder Statistics - Problem Statement 解法 まず, りんごの木の位置は 0 に固定しても問題ないです。他の 2 つの初期位置を動かしましょう。これで O(n^2) みたいな感じになるので, あとは O(1) で木の最小距離 x を求められるようにしたいです。り…

2012 TCO Algorithm Round 2B med: HeavyBooks

本が 10^6 グラムってそれ 1 トンやんけ! 問題 TopCoder Statistics - Problem Statement 解法 Tomek 君が最初に押し付ける本を決めたら, 後は両者とも, 貪欲に「できるだけ重い本を相手に押し付ける」というのが最適です。そうしないと, 余計に重い本を相…

2012 TCO Algorithm Round 2B easy: BlurredDartboard

問題 TopCoder Statistics - Problem Statement 解法 見えない部分の得点が小さい順に a1, a2, ..., aK であるとすると, 見えない部分については, 順番に a1, a2, ..., aK というように投げていくのが最適です(例えば 1 箇所に集中狙いのような投げ方では, …

SRM 573 div1 hard: WolfPack

問題 TopCoder Statistics - Problem Statement 解法 45 度回転させることを考えます。もとの x, y に対して, x' = x+y, y' = x-y とすると, 各移動に対して, x', y' の遷移は以下のようになります。 x++ -> x'++, y'++ x-- -> x'--, y'-- y++ -> x'++, y'--…

SRM 573 div1 med: SkiResorts

問題 TopCoder Statistics - Problem Statement 解法 d[i][j] = (i 番目の場所の高さを altitude[j] にするようなもので, 0 番目から i 番目に行くのにかかる最小コスト) というのを dijkstra で計算します。グラフは, まず d[0][i] = abs(altitude[0]-altit…

SRM 532 div1 med: DengklekBuildingRoads

問題 TopCoder Statistics - Problem Statement 解法 直前 K 個 の頂点の次数の偶奇がわかっていれば, dp に持っていけそうです。dp[now][restEdge][atLeast][flag] というように状態を与えます。 now 番目の頂点を見ていて, 残り貼る辺の数は restEdge で, …

SRM 532 div1 easy: DengklekMakingChains

問題 TopCoder Statistics - Problem Statement 解法 3 つ連続になっているものを全部並べて, あと左側と右側にプラス要素があったら添える, ということをやれば良いだけです。真ん中 only に値があるものは, これだと全く無視されますが, 他になんの値もな…

SRM 573 div2 hard: WolfPackDivTwo

まだ見てないけど div1 hard がこれの強化版らしく震えている。 問題 TopCoder Statistics - Problem Statement 解法 集まる可能性のある場所が, [-50, 100] * [-50, 100] ぐらいしか無いので, それぞれの集合場所でそれぞれの牛が集合場所に何通りの場合で…

SRM 573 div1 easy: TeamContest

問題 TopCoder Statistics - Problem Statement 解法 貪欲法で解けます。自チームに勝つためには, 相手はとりあえず強さが max の人はなるべく強いほうが良くて, それ以外の人はなるべく小さいほうが良いです。この規則でチームをどんどん作っていきましょう…

SRM 531 div1 med: MonsterFarm

問題 TopCoder Statistics - Problem Statement 解法 まず強連結成分分解して, グラフを DAG にします。この DAG において, 終点(その頂点から辺が伸びていないような頂点)への行き方が何通りあるか, というのが, 答えが -1 でない場合の答になります。これ…

SRM 531 div1 easy: NoRepeatPlaylist

問題 TopCoder Statistics - Problem Statement 解法 包除原理で解きました。i 個以下の曲を使って P 曲を並べる場合, 最初の曲は i 通り, 次の曲は i-1 通り, ..., M 曲目は i-M 通り, となり, それ以後は i-M 通りだけ使える曲があります。i 個の曲の選び…

SRM 681 div1 med: LimitedMemorySeries2

問題 TopCoder Statistics - Problem Statement 解法 愚直にやって普通に解が得られます。配列 X の最大値を xmax とすると, xmax 未満の値は xmax を超えて半径が飛んでいくことはないので, xmax で配列が分割されることになります。xmax が真ん中にあると…

SRM 681 div1 easy: FleetFunding

問題 TopCoder Statistics - Problem Statement 解法 二分探索で答えを求めていきます。ok(x) = (x 個の spaceship を作ることが出来るか?) とします。b の小さいのから順にパーツを作っていくと, 後ろのパーツを作るのになるべく余裕をもたせられるように…

SRM 568 div2 hard: ShuffleSort

問題 TopCoder Statistics - Problem Statement 解法 問題見てすぐに dp[n] = (残り n 枚の時, card をソートし終えるのにかかる回数の期待値) というのが思いつきますが, 素直に遷移を書くと面倒なので, もう少し考えます。n 枚のカードが残っている際に, …

SRM 568 div1 easy: BallsSeparating

問題 TopCoder Statistics - Problem Statement 解法 box i に色を残しておけない際に, ボールが逃げる場所を作っておかなければなりません。各色が逃げる場所を r, g, b とした時, ボールを動かす回数は, i==r の時は, green, blue を動かす回数 i==g の時…

SRM 593 div1 hard: WolfDelaymasterHard

問題 TopCoder Statistics - Problem Statement 解法 topcoder の解説を参考にしました。 http://apps.topcoder.com/wiki/display/tc/SRM+593こっち読むほうが絶対わかりやすいので, 概要しか書きません。下に書いてあるのも, この解説に書いてある変数を普…

SRM 593 div2 hard: MayTheBestPetWin

問題 TopCoder Statistics - Problem Statement 解法 tA = sum(A), tB = sum(B) とします。すると, ある集合 S を決めたとして, maxdiff(S, T) は, max(, ) となります。これを簡単化すると, max(, )となります。よって, のあり得る値がなにかに関する dp を…

SRM 593 div1 easy: HexagonalBoard

問題 TopCoder Statistics - Problem Statement 解法 4 色定理とかあるので, せいぜい 4 色あれば塗りきれることがわかりますが, 実は今回の場合はせいぜい 3 色あれば塗りきれることがわかります。例えば n = 4 の場合は, 以下のようにすれば良いです。RBGR…

SRM 598 div1 hard: TPS

問題 TopCoder Statistics - Problem Statement 解法 頂点数が 1 の場合を除いて, とりあえず 1 つのビーコンを置く必要があります。最初にビーコンを置いた場所を root にした木で, あと最低いくつのビーコンを置かなければならないか, というように考えま…

SRM 598 div1 med: FoxAndFencing

簡単じゃない? 問題 TopCoder Statistics - Problem Statement 解法 ゲーム始まった直後に Ciel が勝てる(d そうでない場合に, Ciel がどこへ逃げても Liss が勝てる場合(d+mov1 これ以外は, どちらかがじりじり攻めていく感じで勝つしかない まず, じりじ…

SRM 598 div2 hard: FoxAndFencingEasy

問題 TopCoder Statistics - Problem Statement 解法 mov1 >= abs(d) なら, 一回で Ciel さんが Liss さんに追いつけるので, Ciel の勝ち そうでない場合, mov1 > 2*mov2 なら, 最初に近づいた時, mov2 以内に近づかないでかつ次に相手がどう動こうと mov1 …

SRM 598 div1 easy: BinPacking

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

SRM 530 div1 med: GogoXMarisaKirisima

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

SRM 530 div1 easy: GogoXCake

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

SRM 480 div1 hard: StringDecryption

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

SRM 480 div1 med: NetworkSecurity

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

SRM 480 div2 hard: SignalIntelligence

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

SRM 480 div1 easy: InternetSecurity

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

SRM 481 div1 hard: TicketPrinters

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

SRM 481 div1 med: BatchSystemRoulette

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

SRM 481 div2 hard: BatchSystem

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