HHKBプログラミングコンテスト2020参戦記

はじめに

2020年10月10日21:00～HHKBプログラミングコンテスト2020に参加しました。

結果は27;55 ノーペナルティ3完で2622/6097位。
パフォ843でレーティングは779から7あがって786でした。

コンテスト成績証 - AtCoder

A問題

A - Keyboard

２つの文字入力があり最初の入力が'Y'か'N'かにより２つ目の入力をそのまま出力するか大文字で出力するかします。

２つ目の入力は　a　か　b　か　ｃ　の３種類しかないので全部書き出しても解けますが，最初の入力がYなら大文字と小文字を変換する形で書きました。

文字列操作はたまにでてくると少し悩みますが大文字小文字はコードで３２違っているというのは身についていたけど引くのか足すのかわからなくなったので小文字を引いて大文字を足す形で実装し、念のためテストケースの出力をして提出。ACしました。３分４２秒はちょっともたついた感がありますがこんなものかな。

提出コード

#include <bits/stdc++.h>
using namespace std;

int main(){
  char S,T;
  cin>>S>>T;
  if(S=='Y'){
    cout<<char(T-'a'+'A')<<endl;
  }
  else{
    cout<<T<<endl;
  }
  return 0;
}

B問題

B - Futon

グリッドに２×１の布団を置く問題ですが，最初は布団の置き方の総数を求めるような問題かと思い，後回しにしました。後で読み返すと置き方の数だけを求めればよいということなのでだいぶ簡単でしたが，それでもB問題でこの問題，しかも９割近い参加者が通しているのは驚きです。

グリッドの情報を入力し，注目するセルから４方向に布団をおけるかどうかを判定し，総数を２で割る（２回数えることになるので）方針でACしました。

丁寧に確認しながら実装したこともあり１２分くらいかかってます。飛ばす前の最初に２，３分悩んでるのでトータルで１５分くらい。

スピードを意識すればもう５分くらい縮められかなと思います。

提出コード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int H,W;
  cin>>H>>W;
  string S[110];
  char C[110][110];
  for(int i=0;i<H;i++){
    cin>>S[i];
    for(int j=0;j<W;j++){
      C[i][j]=S[i].at(j);
    }
  }
  int cnt=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(C[i][j]=='#') continue;
      if(j<W && C[i][j+1]=='.') cnt++;
      if(j>0 && C[i][j-1]=='.') cnt++;
      if(i>0 && C[i-1][j]=='.') cnt++;
      if(i<H && C[i+1][j]=='.') cnt++;
    }
  }
  cout<<cnt/2<<endl;
      
  /*for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cout<<C[i][j];
    }
    cout<<endl;
  }*/
  
  return 0;
}

C問題

C - Neq Min

長さNの数列について、１～Nまでの数字i毎にP1～Piのいずれとも等しくない０以上の整数の最小値を出力します。

mapをつかって既出のPiにフラグを立てながら最小値を更新していく方針でACしました。

実質１０分くらいで解けていて、この解法もよく思いついたなと思います。

相当難しい問題だと感じました。ちょっと前なら緑ぐらいは軽くあったように思います。
それが参加者の７割も解いていて灰difとは全体のレベルの上がり方には恐ろしいものがあります。

緑になって維持するのも大変なことだなと改めて思いました。

ACしたコード

#include <bits/stdc++.h>
using namespace std;

int P[200010];
int main(){
  int N;
  cin>>N;
  for(int i=1;i<=N;i++){
    cin>>P[i];
  }
  int temp=0;
  map<int,int>mp;
  for(int i=1;i<=N;i++){
    while(1){
      mp[P[i]]++;
      if(P[i] != temp){
        cout<<temp<<endl;
        break;
      }
      while(mp[temp] !=0){
        temp++;
      }      
    }
  }
  return 0;
}

D問題

D - Squares

正方形の中に２種類の正方形を重ならないように入れる入れ方を出力する問題です。

サンプルケースにヒントがあり重なるものを引く方針でできることがわかりましたが，解ききれませんでした。あとでじっくり復習します。

まとめ

今回のA～C問題はだいぶ難しかったように思いますが、それ以上に参加者のレベルがあがっていることに驚きました。C問題がすんなりとけるなど，自分としては出来はよかったのですがそれでもようやくぎりぎりの緑パフォです。

反省点としてはB問題で見た目で怖気づいて飛ばしてしまったことがあります。全体にもう少しスピードアップはできそうです。あと５分縮めらるとパフォ９２０、１０分縮められるとパフォ１０１６です。

水色から上を目指すにはD以下が解けないと勝負になりません。

D以下はまだまだ実力不足で，不足する実力の内容としてはアルゴリズムやプログラミング自体というより数学的思考力にあったと感じています。

数学の基礎力を涵養することも怠らずに，あせらずじっくり精進を重ねていきたいと思います。