mayoko’s diary

プロコンとかいろいろ。

2016-03-01から1ヶ月間の記事一覧

VK Cup 2016 - Round 1 D. Bear and Contribution

問題 codeforces.com 解法 まず単純な解法を考えてみます。目標になる値を決めると, 各値(vals という配列にまとめておくことにします)を目標の値にするために必要なコストが決定します(t だけ contribution を増やしたいとすると, t/5 * c1 + (t%5)*c がか…

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) から頂点に訪…

Educational Codeforces Round 10 D. Nested Segments

気づかなかった…ガックシ。Codeforces の data structure の問題解いてきます… 問題 codeforces.com 解法 条件は, 「a_i まず a_i の大きい順番にソートし, 順番に a_i を見ていくと, 後から見る a_i は, それ以前に考慮されたすべての a_j について, a_i 落…

Educational Codeforces Round 10 C. Foe Pairs

問題 codeforces.com 解法 しゃくとり法を使って解きます。まず前準備として, pos[i] = (数 i がある位置), memo[i].first = (数 i より左側にある数で, Foe Pair になってしまううち最も右側にあるもののの位置), memo[i].second = (数 i より右側にある数…

Typical DP Contest G - 辞書順

問題 tdpc.contest.atcoder.jp 解法 まず少し小さい問題として, 「答えが Eel になるかどうか」というのを考えてみます。これは, 「部分文字列は何種類考えられるか」という問題が解ければ良いです。文字列の各位置を頂点とみなします。 各頂点から, 'a', 'b…

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) に分けて考え…

SRM 686 div1 easy: BracketSequenceDiv1

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

AtCoder Regular Contest 009 C - 高橋君、24歳

問題 arc009.contest.atcoder.jp 解法 「0 から K-1 がバラバラ, 残りは揃っている」の場合の数が分かれば, 後は答えを comb[N][K] 倍するだけです。comb[N][K] はおよそ O(K log K) で求めることができるので, 問題は「」の中身の場合の数です。これは, 包…

AtCoder Regular Contest 027 D - ぴょんぴょんトレーニング

問題 arc027.contest.atcoder.jp 解法 解説を参考にしました。 AtCoder Regular Contest 027 解説 from AtCoder Inc. www.slideshare.neth[i] の値は 10 以下であるので, dp[t] = (t 番目の石までたどり着く方法は何通りあるのか) というのは, t より前の 10…

SRM 537 div1 med: KingXMagicSpells

問題 TopCoder Statistics - Problem Statement 解法 bit ごとに考えます。dp[day][index][bit] = (day 日目に, index 番目の部屋の duck の数について, bit 目の値が 1 になっている確率) とします。 例えば初日に duck の数が 5 だったら 0 bit 目と 2 bit…

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

京都大学プログラミングコンテスト2014 C - 占い

問題 kupc2014.contest.atcoder.jp 解法 i 回目の操作では A[i%N], B[i%M] が一致していないといけない, という要求がたくさん来ているので, 一致させれば良いわけですが, 例えば A[*], B[*] のすべての値が一致してしまうと, 相性度は 0 になってしまいます…

lay_contest round 00002 近所迷惑高橋くん

問題 www.hackerrank.com 解法 kmjp さんの解法を参考にしました。 kmjp.hatenablog.jpL bit の bitset を考えて, i bit 目が立っていたら, 「時刻 i に目覚ましが鳴る」と考えることにします。愚直にやるなら, 各 (A[i], B[i]) について, A[i] からスタート…

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 から順番に見ていき…

AtCoder Beginner Contest 035 D - トレジャーハント

問題 abc035.contest.atcoder.jp 解法 結局一つの町でお金を稼ぐ戦略が有効(少なくともそういう戦略で損することはない)なのでそうします。頂点 i でお金を稼ぐ戦略で得られるお金は, T - (i に行くのにかかる時間) - (i から帰ってくるのにかかる時間) なの…

CodeVS に参加しました

CodeVS に参加しました。最後のほうあきらめて回さなかったので何とも言えないですが 50 位くらいでした。 この記事では, 最初に自分のやったこと, 次に初心者(100 位以内入れなかった, もしくは難しすぎて何すれば良いか全くわからなかった人)向けに「こう…

AtCoder Regular Contest 028 D - 注文の多い高橋商店

問題 arc028.contest.atcoder.jp 解法 まず 10 点の解法を考えてみましょう。これは, 各 Q に対して正直に dp すれば良いです。 dp[i][j] = (i 番目の種類までで合計 j 個の賞品を選ぶ方法) ということにすると, dp[i+1][j] = dp[i][j] + dp[i][j-1] + ... +…

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[…

AtCoder Regular Contest 040 D - カクカク塗り

問題 arc040.contest.atcoder.jp 解法 スタート地点から出るときの方向(横 or 縦), ゴール地点に向かうときの方向(横 or 縦) を決定すると, 各列について, 以下のようにして移動方法が決まります。 基本的に, 列の 2 つの連続したセルを使って縦方向は移動す…

第2回早稲田大学プログラミングコンテスト E - 独立記念日

解法はすぐわかったけどめっちゃバグらせまくりました… 問題 wupc2nd.contest.atcoder.jp 解法 閉路がない場合を考えます。この場合は, 辺を一本切るごとに独立したグループが一つ増えるので, コストが小さい順に貪欲に辺を切っていって大丈夫です。閉路があ…

Xmas Contest 2015 昼の部 A - Accumulation

ほとんど同じ問題を考えたことがあったので割りと一瞬でした。 問題 xmascontest2015noon.contest.atcoder.jp 解法 X = (A*X + B) mod C というのは, 行列計算で言うと mat[0][0] = A, mat[0][1] = B, mat[1][0] = 0, mat[1][1] = 1 というのを使って mat * …

AtCoder Regular Contest 024 D - バス停

なんとなくマラソンマッチっぽい問題だと思いました。 問題 arc024.contest.atcoder.jp 解法 解説を参考にして解きました。 AtCoder Regular Contest 024 解説 from AtCoder Inc. www.slideshare.net今, [xl, xr) の間で条件を満たそうとしているとします。…

東京大学プログラミングコンテスト2013 D - 壊れかけのヒープ

問題 utpc2013.contest.atcoder.jp 解法 N const int INF = 1e9+7; bool ok(const vector<int>& A, int m) { int n = A.size(); set<int> S; vector<int> B(m+1, INF); for (int i = 0; i < n; i++) { B[m-n+i] = A[i]; S.insert(A[i]); } for (int i = m-1; i >= 1; i--) {</int></int></int>…

東京大学プログラミングコンテスト2013 C - 直径

問題 utpc2013.contest.atcoder.jp 解法 2 つのグラフの直径, 半径を求めて, 最大値については, (直径1) + (直径2) + 1 最小値については, max((半径1) + (半径2) + 1, max((直径1), (直径2))) を求めれば良いです。直径, 半径は O(nm) で求められるので計算…

AtCoder Beginner Contest 003 D - AtCoder社の冬

問題 abc003.contest.atcoder.jp 解法 ちょっとアホな方法で通してしまったんですが, 後で紹介します。まず前提として, この問題は結局「X*Y の長方形を作るように D+L 個の物体を配置する方法は何通りあるのか」というのが求められれば, あとはそれに comb[…

KMP 法について

文字列処理アルゴリズム全然知らないので調べてみることにしました。とりあえず KMP 法について書きたいと思います。 そもそも KMP 法とは KMP 法は, 文字列 S (sentence?) の中で, 文字列 W(word?) が現れる場所を列挙するアルゴリズムです。例えば, S = "a…

IndiaHacks 2016 - Online Edition E. Bear and Forgotten Tree 2

問題 codeforces.com 解法 さっきの問題とよく似ています。 mayokoex.hatenablog.comまず, 頂点 0 からつながる頂点を列挙します。これが k 個以下だったら impossible です。で, それらの点からスタートして, 0 以外の頂点となるべく連結させていきます。こ…