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

mayoko’s diary

プロコンとかいろいろ。

AtCoder

AtCoder Regular Contest 050 C - LCM 111

問題 arc050.contest.atcoder.jp 解法 「1 を A 個並べた数」を one(A) と書くことにします。この問題では one(A) と one(B) の最小公倍数を求めたいですが, そのためにとりあえず最大公約数を求めることを考えます(A one(B) を one(A) で割った余りを考える…

AtCoder Regular Contest 050 B - 花束

問題 arc050.contest.atcoder.jp 解法 二分探索で解けます。ok(med) = (med 個の花束を用意することが出来るか?) というのを判定したいです。満たさなければならない制約条件は, (それぞれの花束を作る数を a, b として)x*a + 1*b 1*a + y*b です。med = a+…

Typical DP Contest G - 辞書順

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

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…

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

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

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

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

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] + ... +…

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

Xmas Contest 2015 夜の部 B - Broken Christmas Tree

問題 xmascontest2015.contest.atcoder.jp 解法 S: (禁止されている辺の集合), unvisit: (現時点でまだ訪れていない頂点の集合) とします。で, ある頂点 v に訪れた時は, unvisit の頂点を見ていって, (u, v) が S に含まれるものでなかったら v -> u に辺を…

Chokudai Contest 001 に参加しました

Chokudai Contest 001 に参加しました。CodeVS でマラソンマッチ楽しい〜となったので参加したいと思っていたんですが, btk さんがチームメイト募集してたので一緒に参加しました。@btk15049 一緒に出たい気がします(途中で抜けちゃうかもですが)— マヨ子@大…

AtCoder Regular Contest 049 C - ぬりまーす

問題 arc049.contest.atcoder.jp 解法 タイプ 1 の制約は, 「y -> x という順番で塗る」という制約であると考えることが出来ます。順序関係は有向グラフで表せます。タイプ 1 の制約しかないと考えた場合, 閉路があるところを除いてすべての頂点を通ることが…

AtCoder Regular Contest 049 B - 高橋ノルム君

問題 arc049.contest.atcoder.jp 解法 二分探索します。「時間 t ですべての頂点が一箇所に集まることが出来るか」というのを判定したいです。そのために, i 番目の高橋ノルム君がどの範囲を動けるのかをまず調べてみると, これは 「Xi, Yi を中心とする, 一…

AtCoder Regular Contest 018 D - 僕は友達が少ない

問題 arc018.contest.atcoder.jp 解法 解説を読みました。 AtCoder Regular Contest 018 解説 from AtCoder Inc. www.slideshare.net要するに「最小全域木のコストとそれを構成する場合の数を求めよ」という問題です。解くための前提として, 行列木定理とい…

AtCoder Regular Contest 018 C - 席替え

問題 arc018.contest.atcoder.jp 解法 まず全体を(値, 行, 列) についてソートすることによって, 生徒がそれぞれどの行に行くか, というのが決定します(同じ点数の場合は, 行順にソートするのが明らかに得)。で, そうすると各行に対して, 「誰をどの列に配置…

AtCoder Beginner Contest 004 D - マーブル

問題 abc004.contest.atcoder.jp 解法 よく考えたら最小費用流解が何も考えず出来て頭良いですが, 普通に解きました。まず考察ですが, 赤, 緑, 青のマーブルはそれぞれ連続に置くのが明らかに得です。 「緑のマーブルの左端をどこにするか」というのを決める…

AtCoder Beginner Contest 008 D - 金塊ゲーム

問題 abc008.contest.atcoder.jp 解法 まず 99 点の部分点解法を考えてみます。一回金塊を取ると, 長方形は 4 つに分断されます。分断された各長方形からは, 別れた他の長方形の金塊を取りに行くことは出来ません。よって, 区間 dp 的に, dp[dlX][dlY][urX][…

AtCoder Beginner Contest 008 C - コイン

昔の ABC 難しくないですか… 問題 abc008.contest.atcoder.jp 解法 あるコイン C[i] が表を向く確率をそれぞれの i について求める, という方針で行きます。C[i]%C[j] = 0 かつ i != j を満たす j の集合を S, S の大きさを cnt とします(つまり C[i] の約数…

AtCoder Beginner Contest 025 D - 25個の整数

問題 abc025.contest.atcoder.jp 解法 1 から順番に数を入れていくことを考えます。この時, ある数 a を入れる場所に応じて場合分けをしてみます。上下に対しても同じようにできるので, 左右についてのみ考えます。 a が端っこにある時 … a がなんであろうと…

AtCoder Beginner Contest 034 D - 食塩水

問題 abc034.contest.atcoder.jp 解法 ヒントに書いてあるとおり, 食塩水の濃度 x について二分探索します。濃度が x 以上になるかどうかは以下のようにしてわかります。食塩水全体の質量を S, 食塩の量を T とすると, 条件は T/S >= x i.e. T - x*S >= 0 と…

東京大学プログラミングコンテスト2013 I - 支配と友好

問題 utpc2013.contest.atcoder.jp 解法 ペアプロの動画で一緒に解きました。 続・ペアプログラミング - YouTube頂点 v から子でも親にもなっていない頂点は, v から dfs して行けない点, および u -> ... -> v と dfs して到達できる点ではない点, …

AtCoder Regular Contest 048 C - 足の多い高橋君

問題 arc048.contest.atcoder.jp 解法 解説スライドを見るとわかりやすいです。 AtCoder Regular Contest 048 from AtCoder Inc. www.slideshare.netまず, 配列 L の中で, 一番値の小さいものについては, そこに書く数字は何でも大丈夫です(一番値の小さいの…

九州大学プログラミングコンテスト2014 D - 切符分割

問題 qupc2014.contest.atcoder.jp 解法 「最大 2 枚」の切符しか使えないので, s -> i -> g というように切符を使うか, s -> g に切符 1 枚を使うかの 2 通りしか考えられないです。s から i, i から g への最小費用はダイクストラを使えば簡単に計算できま…

Typical DP Contest R - グラフ

問題 tdpc.contest.atcoder.jp 解法 まず強連結成分分解して, DAG の形にします(下のコードでは SCC ライブラリを使わないで Warshall-Floyd を使っていますが)。そしたら, DAG のあるノードに訪れたとすると, そのノードに含まれる頂点数(強連結成分の数)分…

MUJIN プログラミングチャレンジ D - 括弧列 / Parenthesis Sequence

問題 mujin-pc-2016.contest.atcoder.jp 解法 正しい括弧列は, 「'(' の数が ')' の数を下回ることなく進んでいき, 最終的に '(' と ')' の数が等しくなる文字列」と解釈することも出来ます。これ結構よく出るので覚えておいたほうが良いです。そう考えると,…

MUJIN プログラミングチャレンジ C - オレンジグラフ / Orange Graph

MUJIN プログラミングチャレンジ に参加しました。企業紹介がとても面白かったです。 問題 mujin-pc-2016.contest.atcoder.jp 解法 C は「奇数長 閉路」でぐぐったら答えがわかった— マヨ子@だがしかし可視化 (@mayoko_) 2016年2月27日ググりましょう。する…

DDPC C - 特別講演「括弧列と塗り分け」

問題 discovery2016-final.contest.atcoder.jp 解法 valid な括弧列は木構造になっています。例えば入力例 3 では, でっかい括弧から, 小さい括弧 2 つに向かって辺が伸びている木グラフであると考えることが出来ます。一つの頂点は 2 つの括弧 () に対応し…

DDPC B - DDPC特別ビュッフェⅡ

問題 discovery2016-final.contest.atcoder.jp 解法 ある時間 t までに得られる最大の美味しさを priority_queue で管理します。時間 t には, t 個のビュッフェを取ることが出来ますが, どのように取るのが良いかというと, 美味しさが大きいものから取るのが…

第2回 ドワンゴからの挑戦状 本選 B - 道迷い

問題 dwango2016-honsen.contest.atcoder.jp 解法 速度 v に対して二分探索します。check(v) = (速度 v で足りるかどうか) というのは, dp で確かめることが出来ます。dp[l][r][rflag] = (区間 [l, r] は既に到達済みという状態になるための最短時間(rflag =…

第2回 ドワンゴからの挑戦状 本選 A - 通勤

問題 dwango2016-honsen.contest.atcoder.jp 解法 考察です。 ニコニコ数は 18*2 = 36 個程度しかない L, x*L, ... とか言うように L を小さい順に並べるのではなく, つかう L の数を大きい順に並べていくと考えると, 「大きい数から貪欲に使っていく」とい…

AtCoder Regular Contest 021 D - だいたい最小全域木

問題 arc021.contest.atcoder.jp 解法 5000*5000/2 のすべての辺を貼ってから最小全域木のアルゴリズムを適用しても間に合いませんが, 最小全域木に使われる可能性の高い辺のみに注目して辺を貼れば, 最小全域木に近いものを作ることが出来ます。今回の場合,…

AtCoder Regular Contest 021 C - 増築王高橋君

問題 arc021.contest.atcoder.jp 解法 まず浮かぶのは, priority_queue に値を突っ込んでいく形でコストが小さい順に貪欲にやることです。ただ, K そこで, K 回の増築の中で, 最もコストのかかる増築のコスト x について二分探索しましょう。コスト x 以下で…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 D - DDPC特別ビュッフェ

問題 discovery2016-qual.contest.atcoder.jp 解法 まず部分点解法を考えてみます。K == 1 の場合は, O(NM) で処理すれば大丈夫です。 K > 1 の場合は, 2 回の操作で交換をなかったことにする 1 回の操作で交換をなかったことにする というテクニックが使え…

AtCoder Beginner Contest 033 D - 三角形の分類

問題 abc033.contest.atcoder.jp 解法 各頂点 i について i 以外の頂点について偏角ソートします。あるペア (j, k) (j pi/2 であったら, 三角形(i, j, k) は確実に鈍角三角形であると言えます。また, 直角や鈍角になる場所はたかだか 1 つしかないので, 重複…

Typical DP Contest C - トーナメント

問題 tdpc.contest.atcoder.jp 解法 普通に dp[k][i] = (i が k 回戦まで勝ち抜く確率) とやれば良いんですが, 微妙に遷移で迷ったので書いておきます。i が k 回戦で戦う可能性がある競技者を考えます。p = 1= med であるとすると, いままでは [med, maxi) …

すぬけのお誕生日コンテスト D. Subsequence

問題(というかトップページ) snuke21.contest.atcoder.jp 解法 t を作って, そこから s を作ることを考えます。例えば t が 11001 とかだったとすると, s は, (0...0)1(0...0)1(1...1)0(1...1)0(0...0)1(適当な文字列) というようにして構成できます。t[i] =…

すぬけのお誕生日コンテスト C - Supermarket

解法 bitDP します。dp[s] = (s で表される集合は既に優先順位が上になることが決まっていて, 新しく別の種類の食品を食べることが出来ないと決まっている月である時, まだ追加することの出来る食品の種類の数) とします。mask[i] = (食品 i が売られている…

すぬけのお誕生日コンテスト B - Snuke

問題(というかトップページ) snuke21.contest.atcoder.jp 解法 's' を消せるので, 's' が連続した部分文字列の直後の文字 c が c 's' を満たすなら, なるべく消したくないですが, 消さないといけないとしたら, 辞書順に影響を与えにくい後ろから消していくの…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C - アメージングな文字列は、きみが作る!

問題 discovery2016-qual.contest.atcoder.jp 解法 入力文字列 s の長さを N とします。もし s の中に N-K 個以上 a がある場合は, N-K 個の a を最終的な文字列にするのが最強です。別の場合は, a のみを残す, という戦略は出来ないので, a をなるべく手前…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 B - ディスコ社内ツアー

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選に参加しました。なんとなく早解きコンテストになるんじゃないかと思っていましたが面白かったです。非競プロ勢には厳しかったような気がしますが。 問題 discovery2016-qual.con…

square869120Contest H - 3人の昼食 (The Lunch)

問題 s8pc-1.contest.atcoder.jp 解法 半分全列挙 + 平面走査 で解きます。半分の要素について, 残す食品が e 個あるという前提での残りの食品のわけかたを全列挙します。 square1001とE869120の合計値段の差を x 軸に, square1001とうさぎの合計値段の差を …

第2回 ドワンゴからの挑戦状 予選 C - メンテナンス明け

問題 dwango2016-prelims.contest.atcoder.jp 解法 二分探索します。ok(x) = (時間 x 以下で目的地にたどり着けるか) を判定する関数を作ります。そのために, ダイクストラのようなことをしますが, ある頂点 v に時間 t にたどり着けることがわかったとして,…

第2回 ドワンゴからの挑戦状 予選 D - 庭園

第2回 ドワンゴからの挑戦状 予選 に参加しました。結果はあんまり良くなかったですが 17 卒パワーで予選通過したと思います。 問題 dwango2016-prelims.contest.atcoder.jp 解法 まず考察です。memox[x1][x2] = (長方形の x1 〜 x2 を使うと決めた時, y1, y…

AtCoder Regular Contest 047 C - N!÷K番目の単語

問題 arc047.contest.atcoder.jp 解法 まず, X 番目の順列がどのような順列になるのか, という問題を考えてみます。並べる数が 0-index であるとすると, 一番最初の数は X/(N-1)! で与えられます(X これは N-1 最初の数を決めて残りの N-1 個の数の並べ方が …