ABC197 参戦記録 p.43
itsukiです。
AtCoder Beginner Contest 197 に参戦した様子です。解説記事ではありません。
結果は A, B, C の 3完でした。
回答時間合計：87分17秒
パフォーマンス：740
考察の流れ
A - Rotate
文字列で受け取って、2文字目、3文字目、1文字目の順に出力する
初めて1分以内にACした…！（58秒）
#include <stdio.h>
int main(){
char s[4]={0};
scanf("%s",s);
printf("%c%c%c\n",s[1],s[2],s[0]);
return 0;
}B - Visibility
マス ( X, Y ) から見て、左方向、上方向、右方向、下方向 の順に、合計いくつのマスが見えるかを数える
マス ( X, Y ) 一か所から見た場合のみを考えればいいので、for文を4つ（左/上/右/下）並べ、マス ( X, Y ) から外側に向かって障害物にぶつかるまで数える
障害物にぶつかった場合、break して for文を抜ける（最初マス目端までカウントしててサンプルが通らなかった）
X が縦軸で Y が横軸だった（最初気が付かなくてサンプルが通らなかった）
下図は 入力例2 ( H=3, W=5, X=1, Y=4 ) の様子
#include <stdio.h>
int main(){
int i,h,w,x,y,cnt=1;
char s[105][105]={0};
scanf("%d%d%d%d",&h,&w,&x,&y); x--; y--;
for(i=0; i<h; i++){ scanf("%s",s[i]); }
//l
for(i=y; i>=0; i--){
if( s[x][i]=='.' ){ cnt++; }
else{ break; }
}
//u
for(i=x; i>=0; i--){
if( s[i][y]=='.' ){ cnt++; }
else{ break; }
}
//r
for(i=y; i<w; i++){
if( s[x][i]=='.' ){ cnt++; }
else{ break; }
}
//d
for(i=x; i<h; i++){
if( s[i][y]=='.' ){ cnt++; }
else{ break; }
}
printf("%d\n",cnt-4);
return 0;
}C - ORXOR
A xor B を考える場合、A xor B がゼロになるのは A と B が等しいときだから…と色々考えたが、制約が 1<= N <= 20 なので bit全探索できそう？
A_i を各区間に分割する、仕切り（下図の赤線）の位置を bit全探索する
各区間の OR を求めたあと、すべての区間の XOR を求める
端の仕切りを忘れない！（上図の青線）
変数名を or と xor にしていたらコンパイルが通らなくて焦った…予約語か？と思って適当な名前に変更した
#include <stdio.h>
#define MIN(x,y) ((x)<(y)?(x):(y))
int main(){
int n,a[25]={0},min=2147483647;
scanf("%d",&n);
for(int i=0; i<n; i++){ scanf("%d",&a[i]); }
for(int b=0; b<(1<<n); b++){
// OR
int l=0, r=0, oorr[25]={0}, ori=0;
for(int i=0; i<n; i++){
if(b >> i & 1){
r=i;
// 各区間内をOR
for(int j=l; j<=r; j++){ oorr[ori] |= a[j]; }
l=r+1;
ori++;
}
}
for(int j=l; j<n; j++){ oorr[ori] |= a[j]; }
ori++;
// XOR
int xxor=oorr[0];
for(int i=1; i<ori; i++){
xxor ^= oorr[i];
}
min = MIN( min, xxor );
}
printf("%d\n",min);
return 0;
}まとめ
・初めて本番で緑perf. 問題を AC できたので嬉しい
・前回の ABC196 で 3ペナしてしまったので慎重に解いた
・次はもっと早く解くことを目指す
・茶色まであと少し！
引き続き、のんびり精進します。
この記事が気に入ったらサポートをしてみませんか？