各点間のマンハッタン距離の和 = 長方形の周長ってのが完全に抜けてた なんで解けなかったんだマジで そういう問題最近SRMでやったし 問題 n頂点の凸多角形が与えられ、時計回りでi番目の頂点の座標は(x[i],y[i])である このn個からk個の頂点v1, v2, ..., vk…

良問だった 問題 n個の整数aが与えられる aの部分集合のうち全要素のgcdが1になるようなもののサイズの最小値を求めよ (存在しない場合は-1)1 1 解法 2*3*5*7*11*13 より答えはたかだか7であることがまずわかる dp[i][j]: i個の要素を含み、それらのgcdがjに…

超凡ミスで2問落としてまた1893まで落ちちゃった マジで深夜はパフォーマンス落ちる 問題 長さnの順列がm個与えられる それぞれの順列の先頭と末尾からいくつかの数字を消し、全ての順列を一致させたい 数字の消し方は何通りあるか1 1 解法 1個目の順列が 1,…

かなり残念な落とし方をした 4完でもhighest更新したからこれも通ってれば・・ 問題 L以上r以下の整数のうち、各桁の数字の種類がk以下であるものの和を求めよ1 1 解法 とりあえず求めるものは (r以下の条件を満たす数字の和) - (L-1以下の〜) としてok 1桁…

これ割とあからさまなdpじゃない？ 問題 いくつかの要素が-1になっている長さnの数列が与えられる ↓の条件を満たすように-1を1〜200に変えるとき、何通りの数列が作れるか 1) a[1] 2) a[n-1] >= a[n] 3) a[i] 2 解法 dp[i][j][k]: i-1番目まで埋め終わってて…

こんなしょうもない構築が解けなくてまたdiv1に戻れなかった もう深夜のコンテストはレート落ちるの覚悟で出るべきかな・・ 問題 色がn個あり、m個のペア(a[i],b[i])も与えられる 10^9 * 10^9のチェス盤があり、好きな位置にルークを最大5000個置くことがで…

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

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

問題 n頂点の完全無向グラフがあり、そこからアリスはm本の辺を取り、残りの辺はボブに渡した 二人が持っているグラフそれぞれにおける長さ3の閉路(=triangleと呼ぶ)の個数の和を求めよ1 0 解法 各頂点を1個ずつ見ていき、その頂点に繋がっているn-1本の辺か…

問題 家が燃えている！ 家には品物がn個あり、i個目の品物は、運び出すのにはt[i]秒かかり、燃え始めてからd[i]秒後には完全に燃え尽きてしまい、価値はp[i]である 品物は1個ずつしか運べず、完全に燃え尽きた瞬間に品物の価値は無くなる (t[i]>=d[i]の品物…

問題 重み付き連結無向グラフが与えられる またq個のクエリが与えられ、各クエリで頂点uiとvi間の最短距離を出力する1 m-n 1 解法 制約より、グラフから辺をm-n+1本適切に削れば木になる この木をT、削った辺をMとする Tにおける2点間の距離は、適当な頂点を…

問題 h*wの行列aがあり、最初は(r,c)にチップが置いてある Vasyaはランダムな「今チップが置いてあるマスに書かれた数より小さい数が書いてあるマス」にチップを動かすという操作を、チップを動かせなくなるまで続ける チップを動かす度に、動かす前のマスと…

問題 長さnの数列aが与えられる aの連続する部分列のうち、総和がt未満になるものの個数を求めよ1 |a[i]| |t| 解法 とりあえず累積和sを取る a[i]が全部正なら累積和が単調増加になるから二分探索で解けるけど、今回は負の数もあるから無理 BITが使えれば各i…

問題 y=yaとy=ybに挟まれた領域(チューブ)がある このチューブの両側の壁上にいくつかのセンサーが付いている (x座標は非負整数) 両側の壁上の任意の格子点を2つ選び、それらを通るようなレーザーを放射するとき、最大で何個のセンサーに同時に光を入射でき…

問題 線分がn本与えられる これらのうち1本以上が通る格子点の個数を求めよ ただし異なる2本の線分は交差することはあるが同一直線上にあることはない1 ー10^6 解法 まず線分ごとに格子点の数を計算して足し合わせる (x1,y1)と(x2,y2)を結んだ線分上の格子点…

問題 n行m列の行列がある i行目[j列目]の要素全てのxorが各i,jで与えられる これに矛盾しない行列が存在するか判定し、存在するなら1個示す 解法 ↓みたいにすればa[n-1], b[m-1]以外は全て矛盾しない n-1行m-1列の数字をXとおくと、Xは X = a[n-1] ^ (b[0] ^…

問題 2行n列の畑があり、マスごとに毎秒生えるキノコの本数が決まっている 最初vasyaは1行1列にいて、キノコは畑全体に1本も生えていない 1マス移動するのには1秒かかる 全マスをちょうど1回ずつ通り、通る時にそのマスに生えているキノコを全て収穫するとき…