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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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