問題ページ E - Avoiding Collision 解法 ある頂点uから頂点vへの最短経路が何通りあるか求めたい。ある辺(u,v)を最短経路に使う可能性が存在するかどうかは d[u] + cost = d[v] で判定できる。ある無向辺(u,v)が存在したとき最短経路にu→vとv→uの経路を両方…

問題ページ D - People on a Line 考えたこと r[i] と l[i] を繋いでいった連結成分ごとにバラバラに考えてよさそう 各連結成分について1つ値を決めれば残りの値が順番に決めていけそうなので連結成分ごとにDFS 各連結成分ごとに最も左にいる人の位置を0とし…

問題ページ C - 広告 考えたこと ドミノ敷き詰めみたいなbitDPかと思いながら読むと制約的に違う 各連結成分で2部グラフの大きい方を取る気持ちになる→WA よくよく考えると嘘なケースがある 各行ごとに考えると下の行のために看板を置く個数を減らす理由はな…

問題ページ Problem - J - Codeforces 概要 nCk mod m を求める。 1 <= n <= 10^18, 0 <= k <= n, 2 <= m <= 1000000 考えたこと JAG夏合宿で見た問題 パット見nCk mod m求めるいつものやつだ！と思って制約を見たら真顔になった n, kが大きすぎるのでn, kま…

問題ページ C: Kill/Death - 第4回 ドワンゴからの挑戦状 予選 | AtCoder 考えたこと sample1を読むと5デスを4人に割り振るようなのを求められればよさそうでこれは分割数なのでできる sample2を読むとキル数が違う人ごとにまとめてそれぞれ計算していくとよ…

解法 二次元累積和を計算しておくと矩形の範囲の値の総和をO(1)で計算できる。あとは切る位置を全通り試すO(H^2W^2)をすればよい。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typed</ll></vi></int></bits/stdc++.h>…

解法 i,jから始まる部分列について同型である直線の長さを考える。各区間について傾きが等しく、比率が等しいならば同型であると判定できる。 i+k→i+k+1、j+k→j+k+1の線分について傾きが等しく、day[i+k+1]-day[i+k] と day[j+k+1] - day[j+k] の比率が等し…

概要 M種類の品物を売っている店でN人の人が買い物に来た。同じものを2つ以上買った人はいない。商品iが売れた数はS[i]である。このとき、K個以上の商品を買った人を大口顧客と呼ぶ。このとき、大口顧客の最少人数を求めろ。 解法 できるだけ大口顧客の数を…

概要 正の整数列であるaがある。aは与えられず、d[i] = (a[i]の末尾の0が連続する数) である数列dが与えられる。この数列の部分列で、a[i]が1ずつ増加していく部分列はいくつ存在するか求めろ。 解法 2^6 = 64、n <= 50 から部分列においてd[i] = 6が二つ以…

概要 各マスが黒か白に塗られているn*nの二次元グリッドが与えられる。同じ色がN/2マスより長く連続している列が存在する時、そのグリッドはだめなグリッドである。操作を繰り返すことでだめなグリッドを解消したい。このとき最小の操作回数を求めろ。なお、…

概要 n頂点の重み付きの木が与えられる。集合の任意の2頂点の距離が等しくなるような頂点集合のうち、集合の要素数の最大を求めろ。 解法 ある頂点を根とした木で根からの距離を考える。根からの距離が等しい2頂点a, bでaとbのLCAが根であるような頂点であれ…

概要 holeH、holeWの大きさの穴を複数の板を使って塞ぐ。板iの大きさはboardH[i]、boardW[i]である。板は重なっても良いが全ての角が穴の外に位置していなければならない。このとき塞ぐのに必要な最小枚数を答えろ。不可能なら-1を答える。 解法 holeH >= bo…

概要 d(n) = (nの正の約数の個数)、h(n) = n^d(n)とする。x = h^-1(n) を求めろ。複数存在する場合は最も小さいものを求めろ。 解法 d(x) として使われうる値は20程度までしか存在しない。d(x)を決め打って、そのd(x)のときh^-1(n)が存在するか考える。nのm…

概要 文字列S(|S|<=50)が与えられる。この文字列から異なる文字の2つ組を取り除く処理を繰り返していき最後に残る可能性のある文字の集合を求めろ。 解法 文字cが最後に残る可能性があるかどうかについて考える。文字c以外を全て消せるかどうか判定できれば…

問題ページ C - ABCAC 公式解説のaとcを高速に求める方法について 解法 aとcをそれぞれ求めたあと a>0 && c>0 && a+c>=|y| を満たしていればABCACが構成できる文字列ABCの組み合わせは a+c-|y|+1 通りある。 SAとlcp配列とRMQ SAとlcp配列を構築する。rank[s…

問題ページ C - 部門分け 考えたこと O(N!)すれば部分点40点ははい 部門数とか何か条件を決め打てばスコアが一意に定まるみたいなのを考える 部門数M = N からはじめてもっともスコアが上がる方法で M = N-1 につなぐ貪欲→明らかにだめなパターンが存在 すで…