便宜上、時刻を[1, n]=> [0, n)で表すことにする。f(i):= 時刻iにコンテストを開始したときの参加人数の合計とする。(f(i), -i) を最大にするようなiを求めたいのでf(i)が知りたい。f(i)は累積和で計算する。f(i) = g[i] のような配列gを考えるとタイムゾー…

f(n, m):= nxnのときの配置可能な最大の1の数とする。ただし、1<=m<=n任意のnについてf(n, 1) = 0よって x = 0 のときは例外として処理する。以下、m>=2、x>=1とする。nxnのm-free行列について1が最大となる置き方の一つはmxmの部分行列ごとに、右下に1個0の…

すべての頂点iについて(a[i], i)を終点候補として優先順位度付きキューに突っ込んおく。(u[i], v[i]) 間をコスト2w[i]の無向辺で接続したグラフでダイクストラ法っぽいことをする。 まず往復についてであるが、往路と復路の最短経路の長さが等しいことは明ら…

すべての順列を見ていくのは明らかに無理なので、a[j]ごとに計算していく。つまり、f[a] = f[a] + a[M(もとの配列の添字はj)] となるような順列を数える。その数えをg(j)としておく。g(j)さえ求まれば解はΣa[j]g(j) a[j]より大きい値の数えをx, a[j]以上値の…

dp[i][d]:= 「i番目の台からd∈{左, 右}に落ちたとき最後にボールが行き着くx座標」とする。 iをyの昇順に決定することでこのDPを解ける。よって、事前にソートしておくことでi<=j ⇔ y[i]<=y[j]とする。台iの端dからボールが落ちたとする。このとき、x[i][d]…

実験すると以下を得る最下位ビットが1のとき勝ち最下位ビットが0のとき負け 証明(1)最下位ビットが1のとき常に最下位の1を選ぶことで相手に最下位ビットが0の状態を押し付けられる。値の変化はDAGになっていて(つまり値が必ず減少する)相手のターンで最後に…