AtCoder Regular Contest 144 C - K Derangement
解けなかったので、こういう流れで解きたかったという妄想を書きます
分かりやすさのために、以降i=0~N-1で0~N-1の順列を並び替える問題として考えます
解説
問題文で問われているのは辞書順最小なので、先頭からなるべく小さい数を入れていきたいです。
上のグラフは横軸がiの値、縦軸がAiの値で、赤線が理想の配置です
i=0~K-1の時は Aiにi+K以上の値しか使えないため、Ai = i+kとするのが理想で
i=K~2K-1の時はAiにi-Kも使えるようになるので、Ai = i-Kとするのが理想です
i = 2K ~ N-1以上の時は、Aiとして使える値も2K~N-1であり
両方から2Kを引けば上と同じ問題に帰着できます
よって、理想の配置は0~2N-1を順に並べた上で
2K個ずつのブロックに分け、各ブロックごとに前K個と後ろK個を入れ替えたような形になっています。
例えばN = 12, K = 3なら
3, 4, 5, 0, 1, 2, 9, 10, 11, 6, 7, 8
が答えで、上の説明の通りの並びになっています
(0-indexdで書いたので、値が1ずつ小さいことに注意)
Nが2Kで割り切れるなら上の理想形が作れますが、割り切れない場合の考察も必要です。
割り切れない場合、一番後ろに2K個未満のブロックが生まれてしまいますが、そのブロックの中だけでうまく並び替えて解を作ることはできません。
なぜなら後ろのK個は、K個以上前に移動させないといけませんが
今見ているブロックにその余裕は無いからです。
よって前のブロックにはみ出る必要があり、後ろの2K個について
後ろのK個を前に持っていき、前のK個を小さい順に並び替えて後ろに持ってくのが最適です(これは必ず成功します)
(入れ替え前)
(入れ替え後)
(ちなみにこれと同じ考察からN/2<Kの時に解がないことが分かります)
AOJ 2446 Enumeration
概要
包除原理と期待値の線形性（誤用かも）で解きました
既存の解説はメビウス変換が多かったので自分の解法を書いておきます。
問題
N個の整数S1...Snが与えられ、それらの整数をランダムにいくつか選ぶ。ここで(1<=i<=n)なるiで各Siが選ばれる確率はPi/100である。また、選ばれた整数集合をT1...Tkと呼ぶことにする。この時1以上M以下の整数について、T1...Tkの少なくとも一つで割り切ることができるようなものの個数の期待値を求めよ。
制約
1<= n <= 20
1<=m, ai <= 10^18
1<=pi<=99
解説
まず、Tについて1以上M以下の整数でT1...Tkの少なくとも一つで割り切れる個数というのは集合Tを決め打った場合、包除原理でO(N * 2^N)で解けます
↓この記事が詳しいです
https://compro.tsutaj.com//archive/181015_incexc.pdf
全てのTについて上の方法で求めようとすると間に合わないので式変形を考えます。
ここで、P(T)を集合としてTが選ばれる確率
V(T)を1~Mの内Tの少なくとも一つで割り切れる個数とすると
下の一つ目の式のように答えを表せますが
P2(U)をランダムなTについて、U⊆Tとなる確率とすると
1つ目の式は二つ目の式に変形できます。
何をしてるかというと、たとえばS={2, 3, 5}だとして
U={2, 3}の時の包除の計算は、T={2, 3}, {2, 3, 5}の時に行われますが
T(T⊆S)ごとにU(U⊆T)について計算するのではなく
U(U⊆S)毎にまとめて全てを計算するといった感じです(説明が雑になりすみません)
↓参考(Sが{2, 3}の場合)
using bint =__int128;
__int128 toi128(string &s) {
__int128 ret = 0;
for (int i = 0; i < s.length(); i++)
if ('0' <= s[i] && s[i] <= '9')
ret = 10 * ret + s[i] - '0';
return ret;
}
std::istream &operator>>(std::istream &iss, __int128& v){
string S;
iss>>S;
v = toi128(S);
return iss;
}
bint gcd2(bint a, bint b) {
while (b) a %= b, swap(a, b); return a;
}
void solve() {
bint N, M;
cin >> N >> M;
dna(A, N);
dna(P_, N);
vector<double> P(N);
rep(i, N) {
P[i] = P_[i] / (double)100;
}
double res=0;
rep(mas, 1, 1<<N){
bint mul = 1;
double per=1;
rep(i, N){
//masのibit目を取得
if(bget(mas, i)){
bint g = gcd2(mul, A[i]);
mul *= A[i];
mul /= g;
per *= P[i];
if(mul > M)goto end;
}
}
if(bcou(mas)%2){
res += (int)(M/mul) * per;
}else{
res -= (int)(M/mul) * per;
}
end:;
}
cout << res << endl;
}
D - Pure Straight - AtCoder Regular Contest 126
詰め切るのが難しかった
------------------------------------------------------------
問題
N項の整数列Aが与えれる、Aiは1...Kのいずれかである。
隣接する二項をswapする操作を何回でも行える時、ある区間が1...Kになるような最小の操作回数は何か。
--------------------------------------------------------
以下ではrainboyさんの実装を参考にしています。
解説
最終的に並び替える時に使うインデックス列
S1...Skを決め、まずそれらを隣接させることを考える。
上では小さい赤丸で囲ったのがS
全ての Sを中央(大きい四角で囲った所)に集めるように動かすと移動コストは最小になる。
（差分の合計の最小化は中央値）
次に並び替えのコストは転倒数である。
具体的な実装だが、bit dpで解く
dp[i][mask] := i個目まで見て、選んだ値の集合がmaskとした時に、maskの立っているビット数をkとして
maskをi-k+1 ~ i番目に並べたうえで昇順に並び替えるコストの最小値とすると
答えはdp[N][(2^K)-1]である。
iについてdpの遷移を考える。
iを選ばない時
今までに選んだmaskが半分以下なら、maskを全て右ずらし、半分以上選んでいる場合は残りのインデックスを全て左にずらすだけのコストがかかる。
雑な説明で申し訳ないが、上の様な図でK = 8とした時に
今までに選んだインデックスが赤丸で矢印の位置iについて考えているとする。
ここでiを選ばない場合、dpの定義的にdp[i+1][mask]に入る値は
左の3つを右端をi+1として右詰めする時のコストなので
dp[i+1][mask] = dp[i][mask] + 3になる
選んだ個数が半分以下の時は今までに選んだインデックスを右に（中央に）引っ張っていく必要があるが、半分以上選んでいるときは右の要素を左に（中央）引っ張る必要がある。
例えば今回右から引っ張ろうとすると
dp[i+1][mask] = dp[i][mask] + 5 となる
つまり毎回
dp[i+1][mask] = dp[i][mask] + min(pop_count(mask), K - pop_count(mask));
とすればいい。
iを選ぶ時は今までに選んだmaskについて、iを選ぶ事で発生する転倒数を加算すればいい
以下、自分用のメモ
void solve() {
din(N, K);
nad(A, N);
vi cous(bit(K));
rep(i, 1, bit(K)) {
cous[i] = cous[i & (i - 1)] + 1;
}
vvi(dp, N + 1, bit(K), linf);
dp[0][0] = 0;
fora(i, a, A) {
//今使わない
rep(mas, bit(K)) {
dp[i + 1][mas] = dp[i][mas] + min(cous[mas], K - cous[mas]);
}
//使う
rep(mas, bit(K)) {
if (bget(mas, a))continue;
chmi(dp[i + 1][mas | bit(a)], dp[i][mas] + cous[mas & ~mask(a)]);
}
}
out(dp[N][mask(K)]);
}
F - Grid and Tokens - AtCoder Beginner Contest 205
フローの張り方が分からなかった。
------------------------------------------------------
問題
H*Wのグリッドがある
N個のコマで、i番目のコマについて
・指定された長方形領域のどこかに一つ置く
・置かない
のいずれかを選択できる。
ここで同じ列、行に二つ以上のコマを置けないとして
最大で何個のコマを置けるか。
------------------------------------------------------
制約
1<=H, W, N <= 100
--------------------------------------------
解法
複数の選択について相互に制約が生まれる場合は大抵フローな気がする、実際この問題はそうで
行と列を頂点として扱うと上手くいく。
そうするとイメージ的には、行hと列wを繋ぐ辺を選ぶと(h, w)にコマを置いたという様な感じだ。
行列を頂点として扱うのはLotus Leavesでもそうだったので典型かもしれない。
具体的には以下のように辺を貼ればいい（辺の流量はすべて1）
赤く囲った部分は1,2行目と2,3,4列目について
コマを置けるという事を意味する
F - Insertion Sort - マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）
セグ木で差分を更新する方法が勉強になった。
----------------------------------------------------
問題
長さNの順列Pが与えられる。
左からi番目の値はPiである。
以下の操作を使ってPiを昇順に並べたい。
・i(1<=1<=N)を選ぶ。コストAiでiを好きな場所に移動
・i(1<=1<=N)を選ぶ。コストBiでiを左端に移動
・i(1<=1<=N)を選ぶ。コストCiでiを右端に移動
合計コストを最小化してください。
-----------------------------------------------------
動かさない番号をS1....Skとすると
S1未満の番号は左端に動かすべきであり
Skより上の番号は右端に動かすべきであり
それ以外は任意の場所に動かす必要があると決まる。
よって以下のようにdpを決める。
dp[i] := i番目が動かさない最後の番号とした時に、i番目までを昇順に並べる最小コスト
ここで答えはmin(dp[i] + (A[i+1] + ... + A[N-1]));になる
またdpの遷移は以下のように書ける。
dp[i] = min(B[0]+...+B[i-1], dp[j] + A[j+1]+...+A[i-1]);
左は自分の左に動かさない番号が無い場合であり
右は直前の動かない番号がjである場合である。
この遷移をセグ木で高速化する。
厄介なのは選んだjによって足されるAの値が異なる事であり、セグ木から取り出した値に同じ値を足せば
dpの値になるように出来ればいいので
seg[i] := dp[i] - A[i]
としておけば
任意のjについてdp[i] = seg(0, i) + A[0]+...+A[i-1]
と扱えるためこの問題が解けた
図にすると下のようになる
答えの値について緑の長さを足してやる必要がある時に
あらかじめ赤線の部分を引いておくことで
どの値についても同じ緑の長さを足せばいいようにした。
E. Fair Share - Codeforces Round #770 (Div. 2)
解けなかった...フローというかグラフ系が見えない事が多い。
------------------------------------------------------------
問題
M個の偶数長の整数配列が与えられる
それぞれの整数にL, Rを割り振り方で、以下を満たすものを一つ構築せよ。ない場合は-1を出力
・各配列についてL, Rの個数は同じである
・全てのLからなる多重集合とRからなる多重集合は等しい
------------------------------------------------------------
解法
同じ数字が半分にL, Rに分けられる必要があり
配列内が半分にL, Rに分けられる必要がある等
半分という条件が多い。
とりあえずグラフで扱う事を思いついたとして。
配列ごとの小問題を並列に扱いたいため
各配列のインデックスから存在する数字に、存在する個数分だけ辺を貼った2部グラフを考える。
すると各辺にL, Rを割り振る問題と言い換える事が出来る。
この時、配列から出ている辺の半分がLであり
各数字から出ている辺の半分がL,になれば良い。
これはオイラー路について、辺の向きによって割り振れば条件を満たす。
https://codeforces.com/contest/1634/submission/145730414
---------------------------------------------
実装について
同じ辺を複数回見ると計算量がおかしくなるため
各頂点iについて自分が何本目の辺までを見たかをpos[i]のように管理する。
バックトラックは起こらないため
以後はpos[i]以下の辺だけを見ればよく
pos[i]を使ったらpos[i]++とする。
また、各辺について逆辺のインデックスを持ち
auto[t, rev] = g[i][pos[i]];
if (t == -1) {
pos[i]++;
continue;
}
g[t][rev].fi = -1, g[i][pos[i]].fi = -1;
のように使った辺の逆辺の行き先を-1等にすることで
むこうで見た時に間違って使わないようにする
（削除した辺が向こうで見られるのは一回だけなので計算量は問題ない）
D - Range XOR - AtCoder Regular Contest 133
解説を理解するのに時間かかった...
以下はkmjpさんのブログ記事
AtCoder ARC #133 : D - Range XOR - kmjp's blog
を読んで理解したものなのですが、備忘録として残します。
問題
整数L, R, Vが与えられる。
L<=l<=r<=Rで、lからrまでのxorがVになるようなl, rの組は何通りあるか。
解法
f(x) := 0~x-1までのxorを取ったものとすると、mod4で周期があり
f(4n+0) = 0
f(4n+1) = 4n
f(4n+2) = 1
f(4n+3) = 4n+3
のようになります。
以後桁dpで解く
l, rを4で割った余りについて条件を満たすものを数え上げると
X(l, r) := [l, r)のxorとすると
X(l, r) = f(l) ^ f(r)ですが
l, rの値からX(l, r)を4で割った余りはO(1)で分かります。
少なくとも4で割った余りが正しいかについてはそれで判定が出来て
bitで2桁よる上の物について、L < Rになるようにbit毎に値を決めていく
この際、4nが付いている者はここで選んだbitが値に反映され
4nが付いていない物はここで選んだbitが値に反映されない。
この上でxorがVになるように決めてやればいい。
最終的にL, Rの大小関係は4で割った余りを反映して考える事に注意
