mayoko’s diary

プロコンとかいろいろ。

AtCoder

AtCoder Regular Contest 061 F - 3人でカードゲーム / Card Game for Three

問題 arc061.contest.atcoder.jp 解法 まず普通に解法を考えます。一度それぞれのカードを決めたらすでにゲームの勝敗は決まっていることを考えるとなんか dp ではないような気がします。で, 問題の性質をよく考えると A さんが勝つには A さんに N 回ターン…

AtCoder Regular Contest 061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題 arc061.contest.atcoder.jp 解法 koyumeishi さんに教えてもらいました。@mayoko_ こんな感じでわかるかなぁ…? 赤がコスト 1 、 黒がコスト 0 の辺で、最後に2で割るようにしました。 人のを見ると中継点に入る辺(出る辺)のみコスト1にする派もいるっ…

JAG 夏合宿 Day3 G - Share the Ruins Preservation

問題 jag2016autumn.contest.atcoder.jp二次元平面上に点が N 個与えられる。ある X 座標を境に二つの頂点を分割し, それぞれで凸包を作る。この二つの凸包の面積の和を最小化せよ。 解法 蟻本に載っている凸包は, 凸包の下側と上側に分けて凸包を構成します…

JAG 夏合宿 Day3 F - Escape from the Hell

問題文は面白かったんですが実装はつらかったです。 問題 jag2016autumn.contest.atcoder.jp 解法 最後に A[i] 登るところ以外は, 明らかに D[j] = A[j] - B[j] が大きい順に使うのが最適です。この j をどこまで使うかで場合分けします。j の最大値も j あ…

JAG 夏合宿 Day2 A - Parades

問題 jag2016summer-day2.contest.atcoder.jpN 頂点からなる木がある。各頂点の次数はたかだか 10 である。このグラフ上でいくつかのパレードを開きたい。パレードの候補は M 個あり, その各パレードは頂点 u から 頂点 v へのパスで構成される。 これらのパ…

AtCoder Regular Contest 060 F - 最良表現 / Best Representation

問題 arc060.contest.atcoder.jp 解法 n = |w| とします。全て同じ文字で構成されている場合答えが n 1 となること, および w が良い文字列である場合答えが 1 1 になることは明らかです。その他の場合は最良表現が 2 になることが分かるようです。よって, …

AtCoder Regular Contest 060 E - 高橋君とホテル / Tak and Hotels

なんだかんだ 3 完できてうれぴー。 問題 arc060.contest.atcoder.jp 解法 クエリでは a 戦略としては, 「その日にたどり着けるところまでなるべく遠くへ行く」というのが明らかに最適です。ということで, nxt[0][i] = (頂点 i からなるべく遠くへ行こうとし…

AtCoder Grand Contest 003

問題 agc003.contest.atcoder.jp 解法 全ての数が異なるので, ソートされた後それぞれの数がどこに移動するかが決まっている, ということと, 操作 2 が「偶数番目のみ, 奇数番目のみを入れ替えることができる」ということに対応している, ということがポイン…

AtCoder Regular Contest 059 F - バイナリハック / Unhappy Hacking

問題 arc059.contest.atcoder.jp 解法 まず部分点解法を考えます。dp[n][m][now] = (すでに n 回キーを押したときに, 目標の文字列と m 番目までは一致していて, 生成されている文字は now 個であるような場合の数) という dp をします。これは各状態で 0 を…

AtCoder Regular Contest 059 E - キャンディーとN人の子供 / Children and Candies

問題 arc059.contest.atcoder.jp 解法 まず部分点解法を考えてみますと, dp[i][rest] = (i 番目まで考えた時点でべき乗する数が C から rest まで減っているような時の和) というのを考えると, この i 番目でべき乗する数をいくつ使うかで場合分けして A[i]^…

AtCoder Grand Contest 002 D - Stamp Rally

問題 agc002.contest.atcoder.jp 解法 クエリが 1 個の場合を考えると, UnionFind を使うことで O((N+M)logM) ぐらいで答えを求めることができます(単体だけを考えたら O(N+M) でできそうだけどそれは今はいいです)。というのは, ok(m) = (辺の id が m の部…

AtCoder Regular Contest 058 E - 和風いろはちゃん / Iroha and Haiku

問題 arc058.contest.atcoder.jp 解法 余事象を考えます。つまり, 「XYZ が含まれない数列の数」を求めることを目的にします。これを dp で解くことを考えましょう。状態として, 直前の X+Y+Z 個の数字を持っておけば良いのはわかりますが, これだと 10^(X+Y…

AtCoder Regular Contest 058 D - いろはちゃんとマス目 / Iroha and a Grid

問題 arc058.contest.atcoder.jp 解法 左上の座標を (1, 1), 右下の座標を (H, W) とします(座標は (y, x) )。y 座標が H-A+1 に初めて到達したときの x 座標の値で場合分けします。y 座標が H-A+1 に初めて到達したときの x 座標が i ( > B) であるとすると…

AtCoder Grand Contest 001 C - Shorten Diameter(その2)

問題 agc001.contest.atcoder.jp 解法 想定解のほうで解きます。木の直径周りではいろんな定理が成り立っていて, この辺りは知っておいた方が良いかもしれません。定義 頂点 v からの距離が最大の点との距離が最小であるような頂点を木の中心という。 木の中…

AtCoder Grand Contest 001 C - Shorten Diameter

問題 agc001.contest.atcoder.jp 解法 よくわからない理論で通ってしまったので後で想定解も書きます。ここでは本番に自分が書いた解法を書きます。頂点 v が, 木の直径をなす一つの頂点であるとします。このとき, v は葉になっていないといけないので, v か…

AtCoder Grand Contest 001 B - Mysterious Light

問題 agc001.contest.atcoder.jp 解法 こういうの, 直感的に gcd もしくはその考え方を使うような気がします。と考えて適当にやると解けそうです(本番そんな感じで適当に書いたら AC してびっくりしました)真面目な話をすると, 2 回光が反射したのちは, 必ず…

AtCoder Grand Contest 001 E - BBQ Hard

天才か… 問題 agc001.contest.atcoder.jp 解法 普通に計算しようとすると, (Ai + Aj + Bi + Bj)! / (Ai+Aj)! / (Bi+Bj)!を各 i, j について求めてその和を計算することになります。が, これだと間に合いません。そこで, 上の式をよく見ると, これは (0, 0) …

AtCoder Regular Contest 057 C - 2乗根

こっちのほうが B っぽくない?(C++ でどうやるのか知らないけど) 問題 arc057.contest.atcoder.jp 解法 L とすると, L^2 となります。これが最小かどうかは分からないので, (L/10)^2 というように続いていきます。上の表記は実数で考えていますが, これを整…

AtCoder Regular Contest 057 B - 高橋君ゲーム

全然解けなくて悲しい… 問題 arc057.contest.atcoder.jp 解法 sum = a1 + a2 + ... + an とします。K L x 日目以前では機嫌の良い日の日数は変わらない x+1 日目以降は全勝しているので, 勝率は常に上昇しており, 機嫌が良かったのに悪くなることはない。ま…

AtCoder Regular Contest 056 D - サケノミ

問題 arc056.contest.atcoder.jp 解法 kmjp さんの解法を参考にしました。 kmjp.hatenablog.jpdp[t] = (「t の時間に飲む」と決めたとき, t の時間までに得られる美味しさの総和の最大値)とします。部分点解法では, t の前に飲む時間 t1 を全探索します。t1 …

AtCoder Regular Contest 056 C - 部門分け

うーん, 80 点はほしかったかも。 問題 arc056.contest.atcoder.jp 解法 bitDP します。dp[state] = (state にあるものをうまく使ったときの最大スコア) とします。このとき, dp の更新は, state から適当な集団(state2 とする)を取り出して, 集合を state2 …

AtCoder Regular Contest 056 B - 駐車場

問題 arc056.contest.atcoder.jp 解法 答えに x が含まれるかどうかは, 以下のようにして判定できます。 x 以上の頂点のみを用いて, S から x に到達できる。 これはなぜかというと, もし x 未満の頂点 y が行き止まりになっておらず, その頂点を使って x に…

AtCoder Beginner Contest 039 D - 画像処理高橋君

問題 abc039.contest.atcoder.jp 解法 目標になる画像のある点(i, j)が黒色なら, その点もしくはその回り 8 マスのいずれかを塗る必要があります。このいずれかで, 白色になるべきところを黒く塗ってしまうようなのがあったらダメですが, そういうのがなけれ…

AtCoder Regular Contest 055 C - ABCAC

問題 arc055.contest.atcoder.jp 解法 ABCAC の 2 つ目の A の開始位置について全探索します。この位置を rp として, 最大で A の長さをどこまで長くできるか(lenA とする)を考えます。これはローリングハッシュを使って二分探索すればできます。また, C に…

AtCoder Regular Contest 055 B - せんべい

難しすぎる… 問題 arc055.contest.atcoder.jp 解法 鹿の立場に完全に寄り添って考えます。今回は問題の性格からして動的計画法な気がします(ゲームの流れ(状態)に応じて戦略を変えるというような感じになるはずなので)。ということで dp を考えるのですが, …

Typical DP Contest N - 木

問題 tdpc.contest.atcoder.jp 解法 解いたときのメモ。 木dp で解くことを考えます。そうすると dp[v] = (v の部分木での場合の数), のようにするのが自然です。これの遷移を考えると, 上の写真のように, 子 v1 の部分木について辺を張る作業をするもの, 子…

AtCoder Beginner Contest 038 C - 単調増加

今回の ABC は久しぶりにちょっと難しかったです。 問題 abc038.contest.atcoder.jp 解法 [l, r) の区間が単調増加の場合, その間にある条件を満たすペアの数は (r-l)*(r-l+1)/2 で求められます。各単調増加列ごとにこれを求めれば答えが得られます。 int ma…

Typical DP Contest H - ナップザック

問題 tdpc.contest.atcoder.jp 解法 sugim さんの解法を参考にしました。O(NCW) から計算量を落とせなくてずっと悩んでたんですが多分 O(NCW)…?(間違ってたらすみません)ちなみに僕が考えていた解法より 2 倍くらい定数倍早くて実装も楽でした。各色ごとに …

Typical DP Contest M - 家

問題 tdpc.contest.atcoder.jp 解法 mat[i][j] = (同じ部屋に訪れることなく部屋 i から部屋 j に行く方法) とします。これが求まったとすると, dp[h][i] = (h 階において 部屋 i にいる場合の数) というのは, dp[h+1][i] = dp[h][k] * mat[k][i] となります…

AtCoder Regular Contest 054 C - 鯛焼き

ほとんどの人にとって知識ゲー or ググりゲーだったんですが, 日本語でしかググらなかったのはミスでした。 問題 arc054.contest.atcoder.jp 解法 結論から言いますと, 行列 S の行列式の偶奇を見れば終わりです。理由を考えていきます。この問題では要する…

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…