AtCoder Beginner Contest 299
結果
A - Treasure Chest : AC(5:23)
B - Trick Taking : AC(18:01)
C - Dango : AC(49:04)(3ペナ)
D - Find by Query : WA
DDoS攻撃によりUnrated
A - Treasure Chest
「.」「|」「*」からなる長さ$${N}$$の文字列$${S}$$が与えられ、$${S}$$には「|」がちょうど$${2}$$つ、「*」がちょうど$${1}$$つ含まれている
「*」が「|」の間にあるか判定する問題
自分の回答
int main(){
int N;
string S;
cin >> N >> S;
bool b = false, a = false;
for(char c : S){
if(c == '|'){
b =! b;
}
else if(b && c == '*'){
a = true;
}
}
printf(a ? "in\n" : "out\n");
}今|に挟まれているかを判定してその上で*があるかを文字列の先頭から見て終わり
公式解説
省略
B - Trick Taking
$${1}$$から$${N}$$までの番号が付けられたプレイヤーがカードを1枚場に出す
カードは色$${C_{i}}$$と値$${R_{i}}$$の属性を持ち、$${R}$$は全て異なる
色が$${T}$$であるカードが場にあるならばその色の中で最も値の大きいカードを出したプレイヤーの勝ち
色が$${T}$$であるカードが場にないならばプレイヤー$${1}$$が出したカードの色の中で最も大きい値を出したプレイヤーの勝ち
どのプレイヤーが勝ったかを判定する問題
自分の回答
int main(){
int N, T;
cin >> N >> T;
vector<int> C(N), R(N);
for(int i = 0; i < N; i++){
cin >> C[i];
}
for(int i = 0; i < N; i++){
cin >> R[i];
}
int tmax = 0, twin, p1c = C[0], cmax = 0, cwin;
bool ft = false;
for(int i = 0; i < N; i++){
if(C[i] == T){
ft = true;
if(R[i] > tmax){
tmax = R[i];
twin = i + 1;
}
}
else if(C[i] == p1c){
if(R[i] > cmax){
cmax = R[i];
cwin = i + 1;
}
}
}
printf("%d\n", ft ? twin : cwin);
}Tとプレイヤー1の色で同時にそれぞれどのプレイヤーが勝つかを見て行ってTがあったらtwinを、無かったらcwinを出力
公式解説
省略
C - Dango
長さ$${L+1}$$の文字列の先頭もしくは末尾の一方が「-」であり、残りの$${L}$$文字が「o」である文字列をレベル$${L}$$のダンゴ文字列とする
「-」と「o」からなる長さ$${N}$$の文字列$${S}$$が与えられ、その中の連続する部分文字列におけるダンゴ文字列の最大レベルを求める問題
自分の回答
int main(){
int N;
string S;
cin >> N >> S;
bool o = false, b = false;
int D = 0, d = 0;
for(int i = 0; i < N; i++){
if(S[i] == '-'){
b = true;
D = max(D, d);
d = 0;
}
else{
o = true;
d++;
}
}
D = max(D, d);
if(o && b){
printf("%d\n", D);
}
else{
printf("-1\n");
}
}文字列を先頭から見て行って連続するoの最大をDに保存
後はoと-が両方あるならダンゴ文字列は成立するためDを出力、少なくとも一方が無いなら成立しないため-1を出力
最初-が存在しないか長さが1でふるいにかけたけど-のみの場合を見逃してWA
判定を上のに変更
公式解説
省略
D - Find by Query
ジャッジが$${0}$$と$${1}$$からなる長さ$${N}$$の文字列$${S}$$を持っていて$${S_{1}=0}$$、$${S_{N}=1}$$である
$${N}$$のみが与えられ、ジャッジに対して「? $${i}$$」を標準出力することで$${i}$$文字目が何であるかを質問することができ、その結果として$${S_{i}}$$の値が標準入力で与えられる
$${S_{p} \neq S_{p+1}}$$である$${p}$$を見つけたら「! $${p}$$」と出力しプログラムを終了する
質問$${20}$$回以内で$${p}$$を求める問題
自分の回答
初めての形式で一応ちゃんと動くものは書けたけど20回以内で見つける方法がわからなかった
20回って制限が二分探索っぽいんだけどその先が見えない…
公式解説
https://atcoder.jp/contests/abc299/editorial/6245より
二分で0なら右に、1なら左にでいいのか
なるほど