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 の行列式の偶奇を見れば終わりです。理由を考えていきます。この問題では要する…