mayoko’s diary

プロコンとかいろいろ。

AtCoder

AtCoder Regular Contest 054 B - ムーアの法則

問題 arc054.contest.atcoder.jp 解法 凸関数 + 凸関数 という形になっているので, 全体としても凸関数です。ということで三分探索をしましょう。 int main() { double P; cin >> P; double l = 0, r = 1e18; auto f = [&](double x) { return x+P/pow(2, x/…

Typical DP Contest L - 猫

問題 tdpc.contest.atcoder.jp 解法 dp[i][j] = (猫 i までの幸福度の最大値。ただし, 猫 i は 猫 j, j+1, ..., i の猫と距離 1 以内の場所にいる) という dp を考えます。すると, dp の遷移はdp[i+1][j] = max(0 sum の部分については事前に累積和を計算し…

Typical DP Contest K - ターゲット

問題 tdpc.contest.atcoder.jp 解法 円の右端が小さい順に円を並べます。円iがほかの円jを内包している条件は, (円iの左端の座標) であるので, 上記のような並べ方をすると, すでに 右側の条件は満たしていることになります。なので, あと考えるべきなのは …

Typical DP Contest J - ボール

問題 tdpc.contest.atcoder.jp 解法 dp[state] = (state で表されるものはすでに倒されている場合の, あと必要な投球数) とします。ある state においては, どこか 1 つの座標に向かってボールを投げ続けるのが最適です(外れたからやっぱこっち, とかやるよ…

AtCoder Regular Contest 053 C - 魔法使い高橋君

問題 arc053.contest.atcoder.jp 解法 まず, (a1, b1) (ただし a1 b2) という二つの組があった場合, (a1, b1) を先に並べるのが得です。 これは, max(a1, a1-b1+a2), max(a2, a2-b2+a1) を比較すればわかります。(a1 ということで, 並べ方としては, (a, b) (…

AtCoder Regular Contest 052 D - 9

問題 arc052.contest.atcoder.jp 解法 K の値に応じて場合分けします。K が小さい場合は, 桁dp で解けます。よくある dp[桁][あまりの差][smallFlag] ってやつです。K が大きい場合は, 各桁の和がせいぜい 100 であることを利用します。すると, 解の候補は i…

AtCoder Regular Contest 052 C - 高橋くんと不思議な道

問題 arc052.contest.atcoder.jp 解法 まず自明な解法として, d[v][b] = (頂点 v までに, b 回タイプ B の道を通る場合の最短距離)というのがあります。b は N より大きかったらどこかの頂点を複数回通っていることになるので, 頂点の個数は O(N^2) でダイク…

square869120Contest #2 E - 部分文字列

問題 s8pc-2.contest.atcoder.jp 解法 文字列が共通している場合, i1 からスタートする文字列 i2 からスタートする文字列 が一致している, というようになっているはずです。S[i1:N), S[i2:N) に共通文字列がある場合, それらの文字は辞書順的に連続である, …

square869120Contest #2 H - Counting 1's (その 3)

一度で三度おいしい。 問題 s8pc-2.contest.atcoder.jp 解法 すぎむ先生に教えてもらいました。クエリで平方分割する方法です。@mayoko_ 反転クエリの両端 l, r を multiset S へ突っ込んでいくと、質問クエリに O(|S|) で答えることができます。|S| が √Q …

square869120Contest #2 H - Counting 1's

問題 s8pc-2.contest.atcoder.jp 解法 遅延評価セグメント木で解きました。update で [l, r) の区間を反転させ, query で [l, r) の 1 の数を求めるような機能を実現します。lazy 配列には「今考えている区間は後で反転させるつもりか」というのを覚えておき…

square869120Contest #2 F - Range Sum Queries

問題 s8pc-2.contest.atcoder.jp 解法 なんか調べると b^(a-1-i) に掛け算される係数は 1/i! * c*(c+1)*...*(c+i) になります。なのでそれを実装すれば OK です。調べ方ですが, b^3 あたりの列を調べると, b^0 の項が 1, 4, 10, ... となっています。b^2 で…

square869120Contest #2 B - Division 2

面白かったです。 問題 s8pc-2.contest.atcoder.jp 解法 「どの数で割られるか」で 2^q の場合分けをします。i1, i2, ..., im 番目の数で割られて 1 になる場合, 元の数は q[i1] * a[i2] * ... * a[im] です。 これが本当に i1, i2, ..., im でのみ割られる…

square869120Contest #2 D - 2016

問題 s8pc-2.contest.atcoder.jp 解法 「約数 多い」で調べると, 高度合成数という言葉が出てきます。 高度合成数 - Wikipedia結局この問題ではこれを求めろ, ということなのですが, 高度合成数には次のような特徴があるようです。高度合成数は という形で素…

JAG Contest 2016 Domestic E - 選挙活動

問題 jag2016-domestic.contest.atcoder.jp 解法 候補になる直線は, 有権者と障害物の頂点を結んだ直線ですが, これを何本も引くことを考えると結局考えるべき頂点は「有権者と障害物の頂点を結んだ直線」同士の交点であることがわかります。この点を列挙し…

JAG Contest 2016 Domestic D - インビジブル

誤読死しました。 問題 jag2016-domestic.contest.atcoder.jpわからなくてここを読みに来てる人はとりあえず問題文を読みなおすことをオススメします。 解法 スタックに積まれるカード群は必ず [l, r) と言った区間的になることに注目します。これに気づくと…

JAG Contest 2016 Domestic C - みさわさんの根付き木

JAG Contest 2016 Domestic に参加しました。チーム戦楽しいですね。もう全部チームで参加したい。 問題 jag2016-domestic.contest.atcoder.jp 解法 愚直にやりました。 A, B の文字列から木を構成(dfs) 2 つの木の情報から目的の木を構成(dfs2) 目的の木を…

AtCoder Regular Contest 051 D - 長方形

問題 arc051.contest.atcoder.jp 解法 rng さんの解説放送を聞いて解きました。やっぱり解説放送聞くとスッと理解しやすいですね。 rng さんが書いてたコード↓ arc051.contest.atcoder.jpまずひとつのクエリを O(WH) で処理することを考えます。長方形の形を…

AtCoder Regular Contest 051 C - 掛け算

問題 arc051.contest.atcoder.jp 解法 問題見た瞬間 KitayutaMart に似てると思ったんですけど Twitter 見る感じあんまりそういう感想を持った人がいなかったようです。 mayokoex.hatenablog.comただ, この問題の発想のベースは使えます。数列 a を小さい順…

AtCoder Regular Contest 050 D - Suffix Concat(その 2)

問題 arc050.contest.atcoder.jp 解法 これを参考に RollingHash でも解いてみました。 topcoder.g.hatena.ne.jp考え方(ソートの仕方)はさっきと同じです。問題なのは, RollingHash を使ってどうやってソートをするか, ということなんですが, s.substr(lhs),…

AtCoder Regular Contest 050 D - Suffix Concat

問題 arc050.contest.atcoder.jp 解法 問題設定が以前解いた問題に似ています。 mayokoex.hatenablog.comこれから, 文字列のソートの仕方は, p suffix array の lcp を使うと上手く行きそうな気がするのでそれを考えましょう。 suffix array 求める -> lcp[i…

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 解法 閉路がない場合を考えます。この場合は, 辺を一本切るごとに独立したグループが一つ増えるので, コストが小さい順に貪欲に辺を切っていって大丈夫です。閉路があ…