mayoko’s diary

プロコンとかいろいろ。

TopCoder

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 …