フローの理解が深まる君 問題 n頂点のグラフがあり、最初は辺がm本ある 全ての辺は容量1の無向辺である 辺の追加と削除のクエリがq個与えられる 各操作後の頂点1から頂点nへの最大流を求めよ2 1 解法 最大流はfordfulkerson法で求めるとして計算量はO(FE) も…

問題 n個の町があり、i番目の町の価値はa[i]である 最初は町0にいてスコアはa[0] スコアがpの状態で町iに移動するとスコアはp xor a[i]に変化する 好きな町で終了できるときスコアの最大値を求めよ1 0 解法 d[i][j]: 町iにスコアjでたどり着けるかどうか と…

最小費用流の勉強になった 問題 n個の積み木があり、i番目は1*a[i]*b[i]の直方体の形をしている これらを積み重ねてなるべく高い塔を作りたい 長さ1の辺を奥行き方向に用いて、他の2辺を横方向と縦方向に1つずつ割り当てる(どっちをどっちにしてもok) 積み上…

creep06.hatenablog.com これにだいぶ似てる 問題 以下の条件を全て満たす数列aを用意する 1) 長さn 2) 各要素は1以上k以下の整数 3) 回文(∴ aを逆順にした数列はaと一致する) その後aを好きな回数rotateする 最終的なaとしてあり得るものは何通りか1 1 解法…

包除原理 問題 高橋くんにはn個の筋肉があり、これからd日間毎日トレーニングをする 高橋くんは毎日筋肉を1つ選んでトレーニングしてその筋肉を1kg増やす またi番目の筋肉は最低でもa[i]kgは増やすという目標がある n個全ての目標を達成するようなトレーニン…

包除原理 問題 以下の条件を満たす文字列のペア(a,b)の個数を求めよ 1) aとbの長さはどっちもn 2) aもbもアルファベットの最初のk文字のみからなる 3) a+c = c+bとなるような文字列cが存在する1 1 解法 3つ目の条件は、 (aの先頭x文字) = (bの末尾x文字) か…

http://compro.tsutajiro.com/archive/181015_incexc.pdf (包除原理 解ける数え上げの範囲を広げよう - tsutaj) 今の俺が求めていたものはこれだった 包除原理を極め鯛 問題 L以上r以下の整数を重複を許してn個選んで数列を作る 全要素のgcdがkになるような…

なんか本番中ずっと不適合度って言葉が気になってた 社会不適合度本戦はtokumini君と寿司食ってきます✨ 問題 略 解法 まずn人の空腹度が a[1],a[2],...,a[n] (昇順) で各皿に乗った寿司の個数が b[1],b[2],...,b[n] (昇順) である場合の不適合度は Σ |a[i]-b…

問題 n個のブロックが一列に並んでおり、左からi番目のブロックの重さはa[i]である これらのブロックに対して「まだ取り除かれていないブロックを1つ取り除き、そのブロックと連結なブロックの重さの総和をスコアに加える」という操作をn回行う 操作の列n!通…

包除原理って良いなぁ 問題 Iahubは長さnの順列aを持っていたが、席を外している間に会社の同僚によってaのいくつかの要素を-1に書き換えられてしまった 書き換えられる前のaは、a[i]=iとなるような要素が1つもなかったことだけは覚えている 元のaとしてあり…

包除原理は便利だなぁ！☺️ 問題 n人の競技プログラマとm個の競技プログラミング問題がある ・各競技プログラマはどれかの問題を1問だけ解く ・各問題は必ず1人以上のプログラマによって解かれないといけない ・同じ問題を担当するプログラマが複数いてもいい…

スーパー包除原理マン 問題 n個の整数aとn個の整数pと整数mが与えられる i番目の整数a[i]をp[i]%の確率で選ぶ、という操作を各iについて行い、0個以上n個以下の整数を選ぶ 1以上m以下の整数の中で、選ばれた整数の少なくとも1つで割り切れるものの個数の期待…

包除原理マスターになりたい 問題 n個の相異なる整数aと整数mが与えられる 1以上m以下のそれぞれの整数iについて、aのうちiと互いに素であるものの個数を求めよ1 1 解法 xと互いに素な数 ってのは xの素因数のどれでも割り切れないような数 と言い換えられる…

問題 n(:偶数)頂点の木が与えられる これらの頂点を端点を共有しないペアn/2組に分け、各ペアの2頂点間にリボンを張る どの辺にも少なくとも1本のリボンが張られているようなペアの分け方は何通りあるか2 解法 f(S): Sのどの辺にもリボンが張られていないよ…

春に解説pdfを見ても全く意味がわからなくてずっと放置してて、さっき解説放送見たらやっと理解できた 700点とかの問題と比べると恐ろしいほどむずいけど勉強になる問題だった 問題 あるラーメン屋はn種類のトッピングを提供している 各トッピングは乗せるか…

問題 長さnで '0' と '1' のみからなる文字列sが与えられる これを2進数として見るとき、全ての部分列がleading-zeroなしで5の冪乗になるようにいくつかの部分列に分けたい 最小でいくつの部分列に分ける必要があるか求めよ 不可能な場合は-11 解法 s[L,r]の…

問題 高さrhの赤いブロックがrc個、高さbhの青いブロックがbc個ある これらのブロックを1個以上使い、同じ色のブロックが隣接しないように積み上げてタワーを作る タワーの高さとしてあり得るものの個数を求めよ1 解法 (rh=bhのとき) rc=bcのとき) 答えは明…

問題 suminatorという装置がある この装置には最初無限に0が詰まったスタックが入っており、長さnの非負整数のみからなる数列aを入れると、 1) 数列aの各要素を手前から1個ずつ見ていき、a[i]が0のときはスタックから2個取り出してそれらの和をスタックに入…

これはどういうことですかね 問題 1辺の長さがnである正三角形を成すようにボールが並べられている (合計n(n+1)/2個) このball triangleは無限にある ball triangleのボールを全て赤or緑or青で、隣り合う2つのボールは違う色であるように塗りたい 赤緑青で塗…

問題 1〜kが等確率で出るk面サイコロをn個振る 2 ただしサイコロ同士は区別しない1 2 解法 どの2つの出目の和もtにならない組の個数を求めたい これは a+b = t となる各(a,b)について、どちらか一方が現れない or 両方とも現れなければいい (ただしtが偶数の…

問題 n個の点があり、i番目の点の座標は(x[i],y[i])である これらの点を全て内側(または境界)に含み、かつy=0と接する円を1つ描きたい 描けるならその半径の最小値を求めよ 描けない場合は-11 |x[i]|, |y[i]| 解法 各点のy座標の正負が全て一致していれば必…

問題 m頂点の凸多角形があり、各頂点には0〜m-1の番号が割り振られている ここに2つの頂点同士を結ぶような線分をn個追加する 追加した線分同士の交点の数を求めよ1 3 解法 任意のiでa[i] a[i] を満たすときになる BITで↑を満たすようなjの個数を求めていけ…

問題 長さnの文字列sが与えられる sの隣り合う2文字をswapするという操作を最大k回まで行い、sで同じ文字が連続している部分の長さの最大値を最大化せよ 解法 s[i]を真ん中にして、s[i]と同じ文字をなるべく多く隣まで持ってくることを考えればいい 便宜上、…

問題 円錐状の帽子を2つ組み合わせて魔女の帽子を作りたい 上側用の帽子がn個、下側用の帽子がm個ある 上側用の帽子iと下側用の帽子jは以下の条件を満たすときのみ組み合わせて魔女の帽子にできる 1) 上側の帽子の頂点は下側の帽子の頂点より上にある 2) 下…

問題 木がn本あり、i本目の高さはa[i]である コストxの魔法を使うと各木の高さを0〜xだけ増やすか減らすことができる aを競技単調増加にするために使う必要のある魔法の最小コストを求めよ2 1 解法 二分探索 使う魔法のコストを決めたとき、各木の高さは単調…

問題 2本の塔があり、距離はwである これらの塔の高さは1本目が[1,x]、2本目が[1,y]の範囲から等確率で決まる 2本の塔それぞれの頂上同士をまっすぐなロープで繋ぐ ロープの長さの期待値を求めよ1 1 解法 1本目の塔の高さをkに固定する 更に2本目の高さがmに…

問題 長方形が2つ、それぞれ左下と右上の点の座標が与えられる これらの長方形の共通範囲が 長方形 or 線 or 点 or 存在しない のどれであるか判定せよ0 解法 初期値0の2次元配列で2つの長方形が占める領域をそれぞれ全部+1すると、重なってる部分は2になる …

問題 「xのkleofas tail」とは、1個目の要素がxで、i(>2)個目の要素が i-1個目の要素=yが偶数のとき) y/2 yが奇数のとき) y-1 であるような長さ無限の数列である a 0 0 解法 kからスタートして逆操作をしていく kが偶数のときはk*2かk+1へ、奇数のときはk*2…

ちょっと面白かった 540台はなかなか解き応えのある問題が多い 問題 以下の条件を満たす文字列を作れ 1) 長さnで、アルファベット26文字の最初のn文字を1文字ずつ使っている 2) 転倒数がk以上 3) 辞書順でs以上 4) これらの条件を満たす中で辞書順最小 解法 …

問題 長さkの板が無限にある これらを切ったりくっつけたりして長さLの板をn枚作りたい 長さkの板を必要最小限の枚数だけ使うとき、最低何回板を切る必要があるか求めよ1 解法 貪欲 長さkの板を切って余った板を寄せ集めてちょうど長さLにできる場合はコスト…