AtCoder Beginner Contest 290
結果
A - Contest Result:AC(2:19)
B - Qual B:AC(6:23)
C - Max MEX:AC(25:39)
D - Marking:AC(79:53)
E - Make it Palindrome:提出無し
A - Contest Result
$${N}$$問の問題からなるコンテストが開催され、$${i}$$問目の点数は$${A_{i}}$$点である
すぬけ君は$${B_{1},B_{2},…,B_{M}}$$問目の$${M}$$問を解いた
すぬけ君の総点数を求める問題
自分の回答
int main(){
int N, M;
cin >> N >> M;
vector<int> A(N + 1);
for(int i = 1; i <= N; i++){
cin >> A[i];
}
int ans = 0, b;
for(int i = 0; i < M; i++){
cin >> b;
ans += A[b];
}
printf("%d\n", ans);
}そのまま
公式解説
省略
B - Qual B
プログラミングコンテストの予選に$${N}$$人が参加した結果として、$${i}$$文字目が「o」であるとき$${i}$$位の人が決勝への参加を希望し、「x」のとき希望していないことを表す文字列$${S}$$が与えられる
参加希望者の内上位$${K}$$人が予選通過できるとき、通過者を「o」、そうでない人を「x」で表す文字列を出力する問題
自分の回答
int main(){
int N, K;
cin >> N >> K;
string S;
cin >> S;
int i = 1;
for(char c : S){
if(c == 'o' && i <= K){
printf("o");
i++;
}
else{
printf("x");
}
}
printf("\n");
}そのまま
公式解説
省略
C - Max MEX
長さ$${N}$$の非負整数列$${A}$$が与えられ、$${A}$$から順序を保ったまま$${K}$$要素抜き出した列を$${B}$$とした時、$${MEX(B)}$$の最大値を求める問題
$${MEX(B)=m}$$は
・$${0 \leqq i < m}$$を満たす全ての整数$${i}$$が$${B}$$の要素である
・$${m}$$は$${B}$$の要素でない
自分の回答
int main(){
int N, K;
cin >> N >> K;
vector<int> A(N);
for(int i = 0; i < N; i++){
cin >> A[i];
}
sort(A.begin(), A.end());
int m = -1;
for(int x : A){
if(x == m){
continue;
}
else if(x == m + 1){
m++;
}
else{
break;
}
}
if(m >= K){
printf("%d\n", K);
}
else{
printf("%d\n", m + 1);
}
}抜き出すときの順序を保ってとかMEXの定義の2つ目とかで惑わされて問題文の理解がなかなか大変だったけど要は0からいくつまで連続して数があるかなためAをソートして調べて終わり
setでよかったかな
公式解説
int main(){
int n,k;
cin >> n >> k;
set<int> st;
for(int i=0;i<n;i++){
int a;
cin >> a;
st.insert(a);
}
for(int i=0;i<k;i++){
if(st.find(i)==st.end()){
cout << i << "\n";
return 0;
}
}
cout << k << "\n";
return 0;
}https://atcoder.jp/contests/abc290/editorial/5756より
やっぱりそうか
D - Marking
0から$${N-1}$$までの番号が付けられたマスが並んでいて、以下の手順に従って全てのマスに印を付けていく
1.マス0に印を付ける
2.次の i - iii の操作を$${N-1}$$回繰り返す
i.最後に印をつけたマスの番号を$${A}$$としたとき、変数$${x}$$を$${(A+D) \space mod \space N}$$で初期化する
ii.マス$${x}$$に印が付いている限り、$${x}$$を$${(x+1) \space mod \space N}$$に更新することを繰り返す
iii.マス$${x}$$に印をつける
$${K}$$番目に印を付けたマスの番号を求める
以上について$${T}$$個のテストケースが与えられるためそれぞれ答えを求める問題
自分の回答
int main(){
int T;
cin >> T;
for(int i = 0; i < T; i++){
int64_t N, D, K;
cin >> N >> D >> K;
int64_t lcm = N * D / gcd(N, D);
int64_t ans = (D * (K - 1) + D * (K - 1) / lcm) % N;
printf("%ld\n", ans);
}
}動的計画法みたいな感じで事前に計算するのかなと思ったりしたけどN,D,K全て最大$${10^9}$$で配列作れないし毎回値違うしどうすればいいかと思ったけど、試してたらN,Dの最小公倍数毎に同じマスを踏んでその次のマスは必ず空いてるから
累計何マス進んだかをNで割った余りが基本的な答えでそこに補正を加えた
((累計マス数)+(同じマスを踏んだ回数))%N
で答えだった
こんなシンプルだったか…
公式解説
省略
E - Make it Palindrome
数列$${X}$$に対し$${f(X)}$$を$${X}$$を回文にするために操作する必要のある最小の文字数とする
与えられた数列$${A}$$の全ての連続部分列$${X}$$に対する$${f(X)}$$の総和を求める問題
自分の回答
毎回求めてたら時間足りないのはわかるが計算量の削減方法は一切思いつかなかった
Aから何かしら求められるんだろうけど
公式解説
int main(){
long long n;
cin >> n;
vector<vector<long long>> p(n+1);
for(int i=1;i<=n;i++){
long long x;
cin >> x;
p[x].push_back(i);
}
long long res=0;
for(long long i=1;i<=n;i++){
res+=(n+1-i)*(i/2);
}
for(long long i=1;i<=n;i++){
long long l=0,r=p[i].size()-1;
while(l<r){
if(p[i][l]<(n+1-p[i][r])){
res-=(r-l)*p[i][l];
l++;
}
else{
res-=(r-l)*(n+1-p[i][r]);
r--;
}
}
}
cout << res << "\n";
return 0;
}https://atcoder.jp/contests/abc290/editorial/5757より
まず任意の2つの要素を結んだものを「線」とし、その値が等しいならば「良い線」、異なるならば「悪い線」と呼称する
答えは全ての連続部分列における悪い線の総和だが、それを求めるのは厳しいため悪い線=線-良い線から良い線の方を求めて悪い線を求めることにする
良い線があった時、それが連続部分列において何回出てくるかは良い線の値から左右に広げて行ってどちらかがAの端に到達するまでであるため、$${l}$$要素目と$${r}$$要素目が良い線であったときそれが何回出て来るかはmin(l,N-r+1)で求められる
pはxの値がどの位置で出てきたかを昇順に入れたもの
後はpで良い線を作ってそこから良い線の総数を線の総数から引いて行ったものが答え
最後ざっくりしたけどこんな感じかな