CF #670 (Div. 2) 参戦記録 p.5
itsukiです。
Codeforces # 670 (Div. 2) に参戦した様子です。解説記事ではありません。
Codeforces 初参加でした！
AtCoder も灰なのに他にも手を出してどうする…とずっと悩んでいたのですが、久々の人権こどふぉ(※)と聞いて好奇心が勝ちました。
※Codeforces Div. * は 23:35 開始 が多いので、
22:35 開始のコンテストは人権こどふぉと呼ばれるらしい
結果はA問題1完でした。1完もできないかと思っていたので嬉しいです。
考察の流れ
A. Subset Mex
英語を理解するのをあきらめそうになる
subset（部分集合？）と聞いて一歩下がる
バケット法で各数字の出現回数をカウントしたあと、
配列A と 配列B に振り分けていく
各数字の出現回数が2回以上あれば、両方の配列に振り分け、
1回であれば、片方の配列（今回は配列A）に優先的に振り分け、
0回であれば、break
一度でも「出現回数が1回」の数値があったら、
もう配列B に値を振り分ける必要はないので、フラグを立てておく
A配列 と B配列 を作って振り分けていたが、各配列に振り分けた値の最大値だけ分かればいいので配列不要であることに気づく
#include <stdio.h>
int main(){
int t;
scanf("%d",&t);
while(t){
t--;
int n, m, cnt[101]={0}, amax=-1, bmax=-1, flag=0;
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d", &m);
cnt[m]++;
}
for(int i=0; i<n; i++){
if( cnt[i] >= 2 ){
amax = i;
if(!flag){ bmax = i; }
}else if( cnt[i] == 1 ){
amax = i;
flag = 1;
}else{
break;
}
}
printf("%d\n", amax+1 + bmax+1);
}
return 0;
}まとめ
・直前にひとつ前のDiv.2 A問題を通しておいたので、なんとなく傾向がつかめていたのでよかった
・英語なので、自分がちゃんと問題を理解できているか不安になる
・↑ のおかげで、時間はかかったけど確実にコードに落とし込めた気がする
・いつもより慎重にコーナーケースを潰したのがよかった
・B問題悔しい！（後で解き直す）
引き続き、のんびり精進します。
#note初心者 #備忘録 #参戦記録 #codeforces #プログラミング #競プロ #C言語 #数学 #バケット法