ABC191参戦記

atcoder.jp

はじめに

2021年2月6日21:00-22:40に開催されたABC191に参戦しました。
結果は20:39ノーペナABCの３完でパフォーマンス1256、レーティングは前回844から+48の892となりhighestを更新しました。パフォーマンス1256は過去最高で、水パフォは2回目。C問題が比較的早く解けた上にD,Eがかなり難しく崖になっていたことに助けられましたが好成績でよかったです。

A問題

A問題としては難しめでした。
早さＶm/sで投げた球がＴ秒後からＳ秒後まで消えているとき、Dm離れた位置で打てるかどうか（消えていないかどうか）を判定する問題です。

T*V<=D<=S*Vであれば消えていることになります。
2分47秒で提出しAC。

B問題

長さＮの整数列からＸと等しい要素を取り除き残った数列を出力する問題です。
前から順にＸと等しいかどうかを判定し、等しくない場合だけ出力します。
空白区切りの出力にちょっともたつきました。

4分40秒、通算7分37秒で提出しAC。
これもまあまあのスピードでした。

C問題

問題文が一見理解しにくかったですが，図を描いて素直に理解してわかりました。
一番外側のマスが必ず白いというのもありがたかったです。

２＊２の４マスごとに見ていって黒が３か所もしくは黒が１か所のところが頂点になります。

サンプルが少なかったので自分でいくつか追加のサンプルをつくって動作を確認しました。

13分02秒（通算20分39秒）で提出しAC。
提出直後の順位が500位台、青パフォがでていて驚きました。

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

int main(){
  int h,w;
  cin>>h>>w;
  string s;
  char d[h][w];
  for(int i=0;i<h;i++){
    cin>>s;
    for(int j=0;j<w;j++){
      d[i][j]=s.at(j);
    }
  }
  int ans=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      int cnt=0;
      for(int k=0;k<2;k++){
        for(int l=0;l<2;l++){
          if(d[i+k][j+l]=='#') cnt++;
        }
      }
      //cout<<cnt<<endl;
      if(cnt==1 || cnt==3) ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}

D問題

円の中の格子点の数を求める問題です。
単純な全探索でトライしましたがサンプルは通るもTLEに。

本番中はX軸方向を全探索、Y軸方向を二分探索で解くことを考えていましたが、実装しきれませんでした。

もしこれで実装できていたとしても誤差でWAになっていたのがわかりました。

手も足もでない問題というわけではなく，もう少しでACに手が届いた問題だと思います。

E問題

本番中はBFSでカウントしていくようなことを考えていましたがうまくいきませんでした。

自己ループがあるかどうかを確認し，ない場合は，別の点までいって戻ってくる距離をダイクストラで求める，という解法自体は解説を見て理解しました。これを自力で思いつけるようになるには，ちょっとまだ修行が足りません。

ダイクストラは一時期勉強しましたが自力ですんなり実装するのはちょっとおぼつかない状態です。
ライブラリはあるので時間をかければ使えそうですが，このあたりをスムーズに使いこなせるかが課題だと思います。