まだ見てないけど div1 hard がこれの強化版らしく震えている。 問題 TopCoder Statistics - Problem Statement 解法 集まる可能性のある場所が, [-50, 100] * [-50, 100] ぐらいしか無いので, それぞれの集合場所でそれぞれの牛が集合場所に何通りの場合で…

問題 TopCoder Statistics - Problem Statement 解法 貪欲法で解けます。自チームに勝つためには, 相手はとりあえず強さが max の人はなるべく強いほうが良くて, それ以外の人はなるべく小さいほうが良いです。この規則でチームをどんどん作っていきましょう…

問題 codeforces.com 解法 見た目が明らかに Euler Tour + 遅延評価セグ木 です。今回, 色の種類が 60 種類しかないので, セグメント木には, 2^c[i] (色 c[i] が含まれるかどうかのフラグ) というのの OR を取る形のものを保持しておけば良いです。 struct S…

問題 codeforces.com 解法 まず 0 回交換の場合, 1 回交換の場合はそのまま O(nm) で調べることが出来ます。で, 2 回交換の場合は, a から b に渡すことの出来る 2 つの数の和のリストおよび b から a に渡すことの出来る 2 つの数の和のリストを O(n^2log n…

問題 codeforces.com 解法 前似たような問題解いてましたね… mayokoex.hatenablog.com 上の記事のは問題設定がわかりにくいですが, 今回のは問題設定が率直でわかりやすいです。10^7 程度までは正直に余りを計算します。それ以上の数での余りは, n/div の商…

問題 codeforces.com 解法 しゃくとり法やるだけ, なんですがバグらせまくりました…区間系書くときは, 「閉区間か半開区間か」とか「区間がどのような性質を持っているか」とかは意識すべきですね。そういえば珠玉のプログラミングにもそんなことが書いてあ…

問題 codeforces.com 解法 順列では「順列 p の i 番目の値が p[i] だったら i -> p[i] に有向辺を貼ってグラフを作る」というのがよくあります。この考えで問題文の順列 q のグラフを作り, そこから p = q^2 を作ることを考えると, p[i] は, 「q のグラフで…

問題 codeforces.com 解法 未だに問題の意味が正確にはわからないのでアレなんですが, 現れる数ごとに区間が重なっている数を +1, -1 していって, 重なる数が k 以上のところを取り出していけば良いです。 int main() { int n, k; cin >> n >> k; vector<pii> mem</pii>…

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

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

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

問題 No.344 ある無理数の累乗 - yukicoder 解法 r3 = sqrt(3) とします。(1+r3)^n と (1-r3)^n を足し算すると整数になります。また, この整数部分は, (1+r3)^n の整数部分の 2 倍と一致し, (1-r3)^n 部分は, 絶対値が常に 1 未満で, n が奇数の時は (1-r3)…

問題 codeforces.com 解法 前使ったばかりの, データ構造をマージする一般的なテクを使います。M[v][color] = (頂点 v 以下の subtree において, 色が color の頂点がいくつあるか) N[v][num] = (頂点 v 以下の subtree において, 頂点数が num 以上ある col…

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

問題 codeforces.com 解法 maxi[row][l] = (row 行目の l 番目の要素から始めると, 1 が最大どこまで連続しているか) というのを, 各行 row について, しゃくとりっぽく O(m) で求めます。そしたら, l 列目からスタートする長方形について, 面積が最大にする…

問題 codeforces.com 解法 1, 6, 8, 9 を適当に並び替えると, 7 で割った余りが 0, 1, ..., 6 のいずれにもなりえます。ということで, 0, 1, 6, 8, 9 以外をとりあえず並べて, 1, 6, 8, 9 を全体の数が 7 の倍数になるように並べます。最後に, 0 を並べて終…

問題 codeforces.com 解法 まず普通に MST を作ります。で, その木に辺 (u, v) を追加したと考えると, 閉路が出来ます。閉路のいずれかの辺を取り除くと再び木になるので, 閉路の中からコストが最大の辺を取り除けば良いです。最大の辺はどうやって取り除け…

問題 codeforces.com 解法 冷静に考えるとちょっと前準備をしてから答えに対して二分探索すれば良かったと思うんですが, 答えを 1 つずつ足していって, それが条件を満たすかを 3 分探索で調べる, という方法で AC しました。ある日程 ans について, i あと…

なんとなくメモ。 ラグランジュ補間のアイデア に関する N 次多項式 を, というヒントから表したいです。この時, とすれば, と表せることに注目します。 このように書くとハッピーなのは, とすると, を満たす について, が成り立つことです。このことから, …

問題 codeforces.com 解法 "データ構造をマージする一般的なテク" を使います。なにそれ, という人は以下のページをご覧ください。 topcoder.g.hatena.ne.jp今回の問題の場合, M[v][color] = (頂点 v 以下の部分木で, 色が color の頂点がいくつあるか) とい…

問題 codeforces.com 解法 アイデアだけなら大学受験の典型ですね(手計算でとけるかは置いておいて)2 つの円の半径を r, R (r R+r R-r >= d なら, 円 r は 円 R に完全に含まれるので, 答えは pi*r^2 それ以外の場合は, 辺の長さがそれぞれ R, r, d の三角形…

問題 codeforces.com 解法 回文になっているためには, 文字列の長さが偶数の場合, すべての文字が偶数個ずつ 文字列の長さが奇数の場合, 1 つの文字を除いて, すべての文字が偶数子ずつ ある必要があります。で, 辞書順最小にすることを考えると, ある文字の…

問題 codeforces.com 解法 落ち着いて dp すれば良いです。dp[n][m][k] = (n*m の長方形で, ぴったり k 個の square を作るには最低いくつのコストが必要か？) を考えます。分割の仕方は 縦に切るか横に切るかしかなく, 2 つに分割した長方形に対して, 一方…

問題 TopCoder Statistics - Problem Statement 解法 まず強連結成分分解して, グラフを DAG にします。この DAG において, 終点(その頂点から辺が伸びていないような頂点)への行き方が何通りあるか, というのが, 答えが -1 でない場合の答になります。これ…

問題 TopCoder Statistics - Problem Statement 解法 包除原理で解きました。i 個以下の曲を使って P 曲を並べる場合, 最初の曲は i 通り, 次の曲は i-1 通り, ..., M 曲目は i-M 通り, となり, それ以後は i-M 通りだけ使える曲があります。i 個の曲の選び…

問題 codeforces.com 解法 普通に dp しようと考えると, dp[m][n] = (m 個目の花火の時座標 n にいるような場合で, 喜び度の max 値) というのが考えられて, これは dp[m][n] = (dp[m][n-diff], dp[m][n-diff+1], ..., dp[m][n+diff] の最小値) + abs(A[m]-n…

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

問題 codeforces.com 解法 累積和の鬼になります。 まず, ok[y1][x1][y2][x2] = (長方形 (y1, x1, y2, x2) が good rectangle であるかどうか) というのを考えたいですが, これは長方形 y1, x1, y2, x2 内の値の cell の値の合計が 0 であれば良くて, これは…

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

問題 TopCoder Statistics - Problem Statement 解法 愚直にやって普通に解が得られます。配列 X の最大値を xmax とすると, xmax 未満の値は xmax を超えて半径が飛んでいくことはないので, xmax で配列が分割されることになります。xmax が真ん中にあると…