AtCoder Beginner Contest 107 - Median of Medians
AtCoder Beginner Contest 107 - AtCoder
A - Train
問題
考察
一列に並んだ個のものがあり、左から数えて
番目のものは右から数えて何番目か。だいたい
だが、テストケースから
だとわかる（雑）。
コード
int main(){ ll n,i; cin >> n >> i; cout << n-i+1 << endl; return 0; }
B - Grid Compression
問題
考察
「.」または「#」が格子状に並んでおり、「.」のみからなる列や行を削除して表示する。どの列・行が「.」のみからなるかを調べ、それらを除いて表示すればよい。
コード
int main(){ ll h,w; cin >> h >> w; char a[h][w]; REP(i,h)REP(j,w) cin >> a[i][j]; bool blank_row[h], blank_col[w]; fill(blank_col,blank_col+w,true); fill(blank_row,blank_row+h,true); REP(i,h)REP(j,w){ if(a[i][j]=='#') blank_row[i] = false; } REP(j,w)REP(i,h){ if(a[i][j]=='#') blank_col[j] = false; } REP(i,h){ REP(j,w){ if(!blank_row[i]&&!blank_col[j]) cout << a[i][j]; } if(!blank_row[i]) cout << endl; } return 0; }
C - Candles
問題
考察
数直線上に並んだ個の点列のうち
個を廻り、その後原点に達する経路の最短経路の距離を求める。
個の点を廻る間に向きを変えるのは無駄なので、この間は同一方向に進み、この距離は
を座標が小さい方の番号として
である。
を固定したとき、左右どちらの頂点から原点に達するかを考えて答えは
で、さらにについても動かして、求める値は
コード
int main(){ ll n,k; cin >> n >> k; ll x[n]; REP(i,n) cin >> x[i]; ll ans = INF; REP(i,n-k+1){ ans = min(ans,abs(x[i]-x[i+k-1])+abs(x[i])); } REP(i,n-k+1){ ans = min(ans,abs(x[i]-x[i+k-1])+abs(x[i+k-1])); } cout << ans << endl; return 0; }
D - Median of Medians
問題
考察
長さの数列
が与えられ、すべての部分列
の中央値によって新たな数列を作るとき、その数列の中央値を求める。最終的な答えは元の数列
の要素であるので、
をソートしてから二分探索で答えを求めることを考える。ソート済みの数列
の
番目（
とする）が求める中央値よりも大きいかどうかは、以下のように判定できる。
いま、ある部分列の中央値が
以上であるということは、その部分列の中に含まれる
よりも小さい要素の個数が、
以上である要素の個数以下であることと同値である。さらに言い換えると、数列
の各要素が
よりも小さければ
,
以上であれば
とした数列
を考えて、区間
の中に
なる
の個数が
なる
の個数以下であることと言いかえられる。
これをそのまま解くのは難しいので、累積和を用いる。]の累積和を
]とおくと（ただし
とする）、上の条件は
と言いかえられる。これをみたす
の組の個数を求めるのはBIT（Binary Indexed Tree）を用いると実現できる。
いまの値の範囲は
以上
以下であることに注意し、
個のBITを考える。蟻本162ページを参考にして個数を求めるが、
の要素数は
個であることに注意が必要。中央値からなる数列の個数は、
の場合と
の場合を分けて足すことにより
コード(本問)
int main(){ ll n; cin >> n; ll a[n]; ll a_sort[n]; REP(i,n){ cin >> a[i]; a_sort[i] = a[i]; } sort(a_sort,a_sort+n); ll lb = 0, ub = n; while(ub-lb>1){ ll x = (lb + ub)/2; ll b[n]; REP(i,n) b[i] = (a[i]<a_sort[x]) ? -1 : 1; ll s[n]; REP(i,n){ s[i] = (i==0) ? b[i] : s[i-1]+b[i]; } ll cnt = 0; BIT bit(2*n+1);//値の範囲は-n<=x<=n bit.add(n,1); REP(j,n){ cnt += bit.sum(s[j]+n); bit.add(s[j]+n,1); } if(cnt>=ceil(n*(n+1)/2/2)){ lb = x; }else{ ub = x; } } cout << a_sort[lb] << endl; return 0; }
コード(BIT部分)
struct BIT{ ll M; std::vector<ll> bit; BIT(ll n){ init(n); } void init(ll n){ M = n; bit.resize(M+1); fill(bit.begin(),bit.end(),0); } ll sum(ll i){ ll s = 0; while(i>0){ s += bit[i]; i -= i & -i; } return s; } void add(ll i, ll x){ while(i<=M){ bit[i] += x; i += i & -i; } } };
雑感
完全にDはお手上げ状態でした。蟻本だと中級編の総合的な理解が必要とされるレベルで、さすがに厳しかったです。Cまでを14分で解き切って、その後はアイスを食べたりしていました(笑)。
