ＡＢＣ１９７参戦記 - chacoderのブログ

はじめに

2021年3月27日21:00-22:40 ABC197に参戦しました。
結果は89分42秒3完ノーペナ 3316位／7885人中でパフォーマンス736、レーティングは前回862から12下がって850でした。

f:id:chacoder:20210328101740p:plain

f:id:chacoder:20210328101900p:plain

A問題

３文字の文字列の１番目を３番目に移す問題です。
あまりうまい方法を思いつかずs[1],s[2],s[0]の順に出力しました。
2分05秒。

B問題

B - Visibility

H*Wのグリッドに障害物が置かれていて(x,y)から見通せるマスの数を数える問題。
よくあるパターンで素直に実装。サンプルを試して8分27秒通算10分32秒はまずまず。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;

char c[110][110];
int main(){
  int h,w,x,y;
  cin>>h>>w>>x>>y;
  x--;
  y--;
  string s;
  rep(i,h){
    cin>>s;
    rep(j,w){
      c[i][j]=s.at(j);
    }
  }
  int ans=0;
  for(int j=y;j>=0;j--){
    if(c[x][j]=='.') ans++;
    if(c[x][j]=='#') break;  
  }
  for(int j=y+1;j<w;j++){
    if(c[x][j]=='.') ans++;
    if(c[x][j]=='#') break;  
  }  
  for(int j=x;j>=0;j--){
    if(c[j][y]=='.') ans++;
    if(c[j][y]=='#') break;  
  }
  for(int j=x+1;j<w;j++){
    if(c[j][y]=='.') ans++;
    if(c[j][y]=='#') break;  
  }      
  cout<<ans-1<<endl;
  return 0;
}

C問題

C - ORXOR

長さ２０までの数列Aを１つ以上の区間に分け，各区間のビットORの全ての値のXORの最小値を求める問題です。
未だにビットOR、XORの演算に慣れていない上、数え上げの方法をすぐに思いつけず、いったん飛ばしてD問題に進みました。D問題で詰まって戻ってきて解き切りました。

数え上げはN-1個の仕切りをbit全探索で試す方法でよさそうです。
仕切りがでてくるまでbitOR演算で各区間の値を計算し，仕切りがでてきたらvectorにストックしておいて，最後にすべてのXORを出し，最小値を更新していく方針でときました。

ビット演算に慣れていないこともあり，バグ取りに手間がかかりましたが，なんとか解ききれてほっとしました。

79分10秒　通算89分42秒　20分ぐらいD問題を考えていたので実質60分くらいでした。

提出コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;
ll a[20];
int main(){
  int n;
  cin>>n;
  rep(i,n) cin>>a[i];  
  ll maxans=10000000007;
  ll tempans=0;
  ll totalans;
  for(int i=0;i<(1 << (n-1));i++){
    vector<ll>vec;
    tempans=a[0];
    for(int j=0;j<(n-1);j++){
      if(i & (1<<j)){
        //cout<<i<<" "<<j<<" "<<tempans<<"%"<<endl;
        vec.push_back(tempans);
        tempans=a[j+1];
        //cout<<tempans<<"#"<<endl;
      }
      else{
        tempans=(tempans|a[j+1]);
      } 
    }
    //tempans=(tempans|a[n-1]);
    vec.push_back(tempans);
    //cout<<vec.size()<<" "<<tempans<<endl;
    totalans=vec[0];
    for(int k=1;k<vec.size();k++){
      //cout<<vec[k]<<"#"<<endl;
      totalans=(totalans^vec[k]);
    }
    //cout<<totalans<<endl;
    maxans=min(maxans,totalans);
  }
  cout<<maxans<<endl;
  return 0;
}