考えたこと EMでEとして使う問題数をw、Mとして使う問題数をx、MHでMとして使う問題をy、Hとして使う問題数をzとする min(E+w, M+x+y, H+z)を最大化すればよい 最小の最大化はにぶたんをしたくなる 問題セットの数cntを作れるかの判定をしたい Eがcntより小…

考えたこと どんなマスなら白から黒に変えられるか考える そのマスの右と下にkマスずつ余裕があれば白から黒にできる 各方向からn-k列は何であっても実現できそうなので残りのk列が実現できるか判定できればよさそう n-k列の方が埋まってたらk列の方が黒く塗…

考えたこと 部分文字列[l,r]が同じ文字になる確率を考える ?がなくて全部同じ文字→1 違う文字が混ざっている→0 ?がm個で他が全部同じ文字c→(cの確率)^m 全部?でm個→sum(p[i]^m) よくよく考えると各部分文字列について独立っぽい 全ての部分文字列について確…

考えたこと dp[i] = (i番目までで終わるパターン数) dp[i] = sum(dp[j]) (j<i, (j, i]が全員同じ国の条件を満たす) みたいな遷移をすればよさそう (j, i]が条件を満たすのは質問に答えた人がいない or 質問に答えた人が全員同じ人数でi-jと等しいとき dp[n-1] = 1 なら確定できるのでsufficient DP遷移で頭爆発して実装に手間取った、むずかしい #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; type…</int></i,>

考えたこと 巡回置換を何回やったら1に戻ってくるか 長さNのとき周期1,2,…,Nで1にループする したがってxはlcm(1,2,…,N)になる x*y/gcd(x,y)を使ってlcmを求めようとするとMODでうまくいかない 1~Nを素因数分解してそれぞれの素因数について出現数のmaxを数…

考えたこと Sと同じ列、行のどこかに一つでも'#'があればそこに向かって永遠に動けばいいので-1 これ以外のときは最初の位置から進み続けて落ちないぎりぎりの回数各方向に移動するのが上限になるはず この移動方法で途中で落ちるような部分列はありえない #…

考えたこと 両端が同じ文字で間が偶数、両端が違う文字で間が奇数ならちゃんと埋めれば0にできて1パターンしかない これ以外の場合どうやっても+1は回避できない +1になるパターン数を求めて掛けていけばよさそう 実験したら(間の数+1)パターンになった MOD…

考えたこと 部分文字列を全列挙しようかと思ったけど制約的に不可能 部分文字列で共通なものを探せるとよさそう ---oo--oo-- (ooが共通) みたいな文字列があったら共通な部分文字列では7文字が最長 ロリハとか使って共通部分を探すのかと思ったけど愚直でも…

考えたこと AtCoder Expressを思い出す x[i-1] から x[i] までの区間についてどこまで上げられるのかみたいなのを考える よくよく考えると前後それぞれから見ていけばいいだけ dp1[i] = (i以前の条件を満たす最大の高さ), dp2[i] = (i以後の条件を満たす最大…

考えたこと ソートしていい 全ての区間[l,l+k-1]についてi番目に合わせて連続するk個の列にするのにかかる操作量を計算 全部愚直にやってもO(nk^2)で余裕 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typ</vi></int></bits/stdc++.h>…

考えたこと 区間i,jが被っていれば頂点iと頂点jに辺を張ったグラフを考える グラフの任意の頂点について含まれているか集合のいずれかの頂点と隣り合っているような頂点集合Sが全員をカバーできるような配置になる この頂点集合のうち要素数が最小のものを構…

考えたこと ソートしてよさそう lを買う中で最も小さいお好み焼きとすると買える最大のお好み焼きのindexは単調性がある [l, r) を尺取みたいな感じでもとめていく 区間の要素数からその区間で買うときのパターン数は求まる lは必ず買うものとしてr-l-1要素…

考えたこと 素因数分解は試し割りでO(sqrt(N))なので愚直にやるのは間に合わない ヒントとして与えられた素因数でNを割っておいていい primes[i] = primes[i+1] ならば間に入る素因数はprime[i]で確定 O(primes[i+1]-primes[i])かけて全て試せば間に入る素因…

考えたこと 期待値と言われたので線形性を考えるとn回バスが到着するまでの時間の期待値は求まる気持ちになる 何回目のバスに乗ることになるかがわからないので上のが求まったとしてもよくわからない気がする i回目のバスでsに達しておらずi+1回目のバスでs…

考えたこと 問題文を整理するとn頂点のグラフで同じ色の頂点が隣り合う数を最小にした全域木を求める問題 グラフでは頂点条件を辺に置き換えるといいというのを見たことがあったので考えるhttps://www.slideshare.net/tmaehara/ss-17402143 同じ色の頂点が隣…

考えたこと 奇数の和は平方数なのでx+yが平方数でなければ不可能 sqrt(x+y) でターン数は求められる できるだけ少ない個数の奇数の和で表したいので大きい奇数から貪欲に使っていけばいい気がした この貪欲でつくれない数が存在しない気がしたので出したら落…

考えたこと Nが一個あったら該当する一列には置くことはできない おけないところを全て消し、置けるところだけからなる連結成分ごとに考えてよさそう 連結成分に全部置いたとして'Y'の条件を満たすような連結成分が存在するか判定するとよさそう 愚直な実装…

解法 二次元累積和を計算しておくと矩形の範囲の値の総和を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…

概要 Aliceはa個のb面ダイス、Bobはc個のd面ダイスを投げる。このとき、ダイスの目の合計が大きい方を勝ちとする(引き分けはどちらの勝ちでもない)。Aliceが勝つことがありえないときは-1を出力しろ。そうでないときはAliceが勝った条件下でAliceのダイスの…

概要 2次元グリッド上で亀が左上のセルから右下のセルに右か下への移動を繰り返して移動する。グリッド上には障害物があり亀は通ることができない。このグリッドを用いて2人でゲームを行う。各プレイヤーはそれぞれの手番でグリッド上に障害物を配置する。こ…

概要 英アルファベットから成る文字列Sが与えられる。文字列Sは同じ種類の文字を2個ずつ含んでいる。この文字列Sを同じ種類の文字が1個ずつになるように文字を消去する。辞書順最小になるときに文字を消去したとき、文字列の最初の文字を出力しろ。 解法 辞…

解法 まず、回文が存在する条件として * それぞれの文字種の個数が全て偶数 * 一つの文字種だけ奇数でそれ以外は偶数 のいずれかの条件を満たす必要がある。文字種ごとに文字列内の個数を数え、奇数のものが2個以上あれば存在しないので0を出力する。 cnt[i]…

考えたこと 題意がよくわからなかったのでサンプルを試してみると、同じ高さのビルをi個(1<=i<=N)つくるために必要なコストをA[i]としたとき、A[1]^A[2]^…A[N]を出力すればよさそう。離れた階層のビルの高さを同じにする利点はないのでソートして考える。 dp…