問題文が長い！ 問題 ICPCの問題正解者に渡すための風船があり、色はn通りある 色iのものはc[i]個あり、それら全てのサイズはs[i]である ('M'edium or 'L'arge) 問題はm問あり、j番目の問題は最大でa[i]チームにしか解かれることはない それぞれの風船は金を…

問題 n個の容器がありi番目の容器にはa[i]リットルの水を入れることができる これらから2個の容器を選び、以下の操作をそれぞれ任意の回数行い、2個の容器に合計でkリットルの水が入っている状態にしたい 1) 一方の容器を水で満たす 2) 容器xからもう一方の…

本番の出来は酷かったけど程よい難易度の問題が揃ってて良い感じのコンテストだった J問題はまだよくわかってない 問題 (言い換え) n頂点の木が与えられる 最初x個の頂点は赤で、y個の頂点は青で塗られており、残りの頂点は色が付いていない この色が付いて…

問題 略 解法 keySizesの各要素s[i]について、ある文字を1〜s[i]回のストロークで入力できるように割り当てることができる 多い文字ほど少ないストロークで入力できるようにするのが明らかに最善だから、ソートして貪欲に割り当てればok class TomekPhone { …

問題 サイズh*wのボードがある 今いるマスから(±a, ±b) or (±b, ±a)に移動できるハイパーナイトというコマがある このコマのあるマスからの1手での移動先は最大8通りあり得るが、ボードからはみ出すような動きはできない このコマが1手でk通りのマスに移動で…

問題 長さnの無色のセルの列があり、左からi番目のセルはs[i]色で塗りたい 何色で塗ってもいいセルもある このために、まず好きなサイズのスタンプを1つ選ぶ サイズLのスタンプを使うにはst*Lだけコストがかかる またスタンプを押す度にpsだけコストがかかる…

フローの理解が深まる君 問題 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) 下…