ARC 138 参加記
88分3完599位、パフォーマンスは1791でした。
A
問題
長さ$N$の数列$A$が与えられます。$A$の先頭$K$項の和をスコアと呼ぶことにします。与えられた$A$のスコアを$s$と置きます。
$A$の隣接する2要素を入れ替える操作を好きな回数行うことができます。スコアを$s + 1$以上にすることが達成可能か判定し、また可能であるなら必要な最小の操作回数を求めてください。
- $2 \leq N \leq 4 \times 10 ^ 5$
- $1 \leq K \leq N - 1$
- $1 \leq A_i \leq 10 ^ 9$
考察
$K+1$番目以降の要素のいずれかを先頭$K$個に持ってくることを考えます。$j > K$番目の要素を$i \leq K$番目まで持ってくるとき、$j - i$手かかります。
$j$番目の要素を$K+1$番目の位置に持ってくるのに$j - (K + 1)$手、$i$番目の要素を$K$番目の位置まで持ってくるのに$K - i$手、$K$番目と$K + 1$番目を交換するのに$1$手で合計$j - i$手となります。
$i = 1, 2, \cdots, K$について、どの要素を持ってくるのが最適かを考えると、$K+1$番目以降で$A_i$より大きいいちばん左側(インデックスが小さい)ものを持ってくるのが最適です。これは二分探索をすることで求めることができます。
提出コード
template<class T>
T bisect_right(vector<T> &array, T key){
return upper_bound(all(array),key) - array.begin();
}
ll N, K; cin >> N >> K ;
vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
if(K == N){
cout << -1 << endl; exit(0);
}
vll R;
for(int i = K; i < N; i++){
R.pb(A[i]);
}
rep(i, R.size() - 1) chmax(R[i+1], R[i]);
ll ans = INF;
for(int i = 0; i < K; i++){
ll r = bisect_right(R, A[i]);
r++;
if(r != R.size() + 1){
chmin(ans, K + r - i - 1);
}
}
if(ans == INF) ans = -1;
cout << ans << '\n';
}
upper_bound
などをきちんと理解していないかつPythonで競プロを始めたということでbisect_right
を自作しています。本当にごめんなさい。イテレーターとかなにもわかりません…
B
問題
空の数列$x$を持っています。次の2種類の操作を好きな順番で$N$回行います。
操作A : $x$の要素をすべてflipする(0は1に、1は0になります)。 その後、$x$の先頭に0を追加する。
操作B : $x$の末尾に0を追加する
0と1からなる長さ$N$の数列$A$が与えられます。$x$を$A$に一致させることが可能か判定してください。
- $1 \leq N \leq 2 \times 10 ^ 5$
- $0 \leq A_i \leq 1$
考察
わからなかったので小さい$N$に対して作れる数列を列挙してエスパーしようとしたりしましたが、ダメでした。結局2WAしたのちぐちゃぐちゃなコードで一応ACはしました。
正しい考察
逆から操作を行うことを考えます。末尾が0の状態で操作Aを行うと末尾が1となってしまい、再度操作Aを行わなければ操作Bが行えなくなってしまいます。ゆえに末尾が0であるならば操作Bを行うべきです。末尾が1の状態の時は操作Aを行うしかないので行います。この時先頭が0でなければ不可能となります。
逆から操作を行うことは考えたのですが末尾が0の状態で操作Aを行うべきでないことに気づけず、時間を溶かしていました…
ACコード
int main(){
ll N; cin >> N;
deque<int> A;
rep(i, N){
int a; cin >> a;
A.pb(a);
}
int flip = 0;
bool ans = true;
while(!A.empty()){
if(A.back() == flip) {
A.pop_back();
}elif(A.front() == flip) {
A.pop_front();
flip ^= 1;
}else{
ans = false;
break;
}
}
YesNo(ans);
}
C
問題
$N$枚のカードがあり、$1$から$N$までの番号がついています。カード$i$には整数$A_i$が書かれています。また、$N$は偶数です。
すぬけくんと最小太郎くんがゲームをします。$N$ターンからなり、すぬけくんから交互にターンをプレイします。各ターンでは、
すぬけくんのターン : まだ誰にもとられていないカードのうち、好きなものを1枚とる
最小太郎くんのターン : まだ誰にもとられていないカードのうち、番号が最小のものを1枚とる
あなたは、このゲームで次の不正を1度だけすることができます。
- 整数$k(0 \leq k \leq N - 1)$を選び、カードに書かれている整数を左に$k$個ずらす。つまり、カード$1, 2, \cdots, N$に書かれている数を、$A_{k+1}, A_{k + 2}, \cdots, A_N, A_1, A_2, \cdots, A_{k}$に書き換える。
あなたがすぬけくんのスコアを最大化するように不正をしたとき、選ぶべき$k$の値と$k$を選んだ場合のスコアを求めてください。
- $2 \leq N \leq 2 \times 10 ^ 5$
- $1 \leq A_i \leq 10^9$
考察
すぬけくんがとることのできる最大スコアは$A$のうち整数の大きいもの上位$N / 2$個の総和です。実際これが可能です。
$A$のうち整数の大きいもの上位$N / 2$個をとればよいので、各カードについてとる/とらないが確定します。取らないカードでは1を、取るカードでは-1とする数列$R$を考えます(公式解説と逆です!注意!)。数列$R$について累積和をとります。正の値をとる箇所ではすぬけくんがとるべきカードが最小太郎くんに取られてしまっていることになります。ここで、数列$R$の累積和の最小となるインデックスが1となるように$k$を定めると、正の値をとらなくなります。よって解くことができます。
提出コード
int main(){
ll N; cin >> N;
vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
vector<tuple<int, ll, bool>> Card;
rep(i, N){
Card.pb({i, A[i], false});
}
sort(all(Card),[](auto a,auto b){ return get<1>(a) > get<1>(b); });
rep(i, N / 2){
Card[i] = {get<0>(Card[i]), get<1>(Card[i]), true};
}
sort(all(Card),[](auto a,auto b){ return get<0>(a) < get<0>(b); });
vector<int> R;
ll su = 0;
for(auto [idx, val, use]: Card){
if(use) R.pb(-1);
else R.pb(1);
if(use) su += val;
}
rep(i, R.size() - 1){
R[i+1] += R[i];
}
int ans = 0;
rep(i, N){
if(R[ans] > R[i]) ans = i;
}
cout << ans << " " << su << '\n';
}
インデックス/値/使うか否か の3つの値を持ちたかったのでtuple
を使いましたが、書いていてだいぶ嫌な気持ちになりました。よい書き方を知りたいです。
AtCoderのハンドルネーム: Kyo_s_s
— きょ (@Kyo_s_s) April 9, 2022
目標レーティング: 1600
必要パフォーマンス: 1846.19
https://t.co/VQD8mPP73q
明日のABCで1847をだしたら、入青......!!!
青になりたいです。 よろしくおねがいします。
Comment is disabled to avoid unwanted discussions from 'localhost:1313' on your Disqus account...