HHKB プログラミングコンテスト 2020 参戦記録 p.20

itsukiです。
HHKB プログラミングコンテスト 2020 に参戦した様子です。解説記事ではありません。

HHKB Programming Contest 2020 - AtCoder

結果は A, B, C の 3完でした。

考察の流れ

A. Keyboard

A - Keyboard

小文字 -> 大文字にするために、ASCIIコード表検索をして時間ロス

なんで何も出力されない！？と思ったら入力し忘れていた…

#include <stdio.h>
int main(){
   char s[2]={0}, t[2]={0};
 	scanf("%s%s",s,t);
   if( s[0]=='Y' ){
       printf("%c\n",t[0]-32);
   }else{
       printf("%c\n",t[0]);
   }
   return 0;
}

コンテスト後：

「32 を xor することで大文字小文字が切り替わる」という解説をみて衝撃を受ける

B. Futon

B - Futon

最近解いた ABC096-C に少し似ている

S_i == "." のとき、上下左右のマスを調べて "." であればカウント

布団のサイズは 2 マスなので、一方のマスから見た場合ともう一方のマスから見た場合とで、2重カウントしてしまうため最後 2 で割る

入力例1 :
○と△の位置に布団を敷くことを考えると、
S_i==○ からみた場合と S_i==△ から見た場合は同じ敷き方になる

#include <stdio.h>

char s[102][102]={0};

int check(int h, int w){
   if     ( h<0 || w<0 )   return 0;
   else if( s[h][w]=='.' ) return 1;
   else                    return 0;
}

int main(){
   int h,w,cnt=0;
   scanf("%d%d",&h,&w);
   for(int i=0; i<h; i++){ scanf("%s", s[i]); }

   for(int i=0; i<h; i++){
       for(int j=0; j<w; j++){
           if( s[i][j]=='.' ){
               if( check(i-1,j) ){ cnt++; }    //上
               if( check(i+1,j) ){ cnt++; }    //下
               if( check(i,j-1) ){ cnt++; }    //左
               if( check(i,j+1) ){ cnt++; }    //右
           }
       }
   }
   printf("%d\n",cnt/2);
   return 0;
}

C. Neq Min

C - Neq Min

N <= 2*10^5 なので、O(N^2) だと間に合わない

現時点での最小値を常に保持することを考える

数列 p_i,…,p_N とは別に フラグ用の配列を用意し、
p_i として出現（＝最小値候補から外れた）時点でフラグを立てる

現時点での最小値が p_i として出現してしまった場合、
フラグ用の配列内を検索して次の最小値候補を決める

p_i <= N と勘違いしていたため、コメント部分で WA
しかも p_i <= N だとしても WA になるコードだった…
何でもかんでも for文 で書かない！（自戒）

#include <stdio.h>
int main(){
   int n, p[200001]={0}, c[200001]={0}, min=0;
   scanf("%d",&n);
   for(int i=0; i<n; i++){
       scanf("%d", &p[i]);
       c[p[i]]++;
       if(min==p[i]){
//         for(int j=min; j<n; j++){
           for(int j=min; j<200001; j++){
               if( c[j]==0 ){ min=j; break; }
           }
       }
       printf("%d\n",min);
   }
   return 0;
}

D. Squares

D - Squares

たどり着けなかった様子（現時点で未AC）

まとめ

・つい最近 Grid を解いていたため、苦手意識が薄まっていたのが良かった
・本番でも計算量を落とせるようになったのが嬉しい
・とはいえ TLE しないか自信はなかった…計算量の見積精度を上げないと…
・他の方々のソースを見ると、もっと簡単に書いてあったので真似たい
・久々の茶パフォだった！

引き続き、のんびり精進します。

#note初心者 #備忘録 #参戦記録 #AtCoder #HHKB #プログラミング #競プロ #C言語 #数学 #Grid