ABC199参戦記 - chacoderのブログ

f:id:chacoder:20210425114907p:plain

はじめに
A問題
B問題
- 提出コード
C問題
- 提出コード
D問題
E問題
感想など

はじめに

2021年4月24日21:00-22:40に開催されたABC199（Sponsered by Panasonic）に参戦しました。
結果は23:23 ３完ノーペナで1946位/8716人中のパフォ1142、レーティングは前回887から+29の916となりhighestを更新しました。

f:id:chacoder:20210425115149p:plain

A問題

A^2+B^2とC^2の大小を判定する問題。
１分３０秒。

B問題

B - Intersection

いずれも長さNの数列Ai,BiについてＡi以上Bi以下を充たす整数Xの数を求めます。
Aiの最大値とBiの最小値の間にあるXの数を出力します。

提出コード

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

int main(){
  int n;
  cin>>n;
  int a[n];
  int b[n];
  rep(i,n) cin>>a[i];
  rep(i,n) cin>>b[i];
  int minx=-1;
  int maxx=1001;
  for(int i=0;i<n;i++){
    minx=max(minx,a[i]);
    maxx=min(maxx,b[i]);
  }
  cout<<max(0,maxx-minx+1)<<endl;
  return 0;
}

4分56秒　通算６分26秒

C問題

C - IPFL

長さ２Nの文字列Sに対し，①Ai番目とＢi番目を入れ替える，②前半と後半を入れ替える，の２種類のクエリを繰り返した結果のSを出力します。文字列長が最大４＊１０＾５　クエリが最大３＊１０＾５あるので，入れ替えクエリをまともに処理してるとTLEになることにはすぐ気づきました（進歩してる♪）。

入れ替えはやったふりをして，入れ替えている状態かどうかのフラグをたてる方針で解きました。
実装はちょっと手間取りましたが沼らずに書けてよかったです。

16分47秒　通算23分13秒

提出コード

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

int main(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  int q;
  cin>>q;
  int flag=1;
  
  rep(i,q){
    int t,a,b;
    char temp;
    cin>>t>>a>>b;
    a--;
    b--;
    if(t==1){
      if(flag==1){
        temp=s[b];
        s[b]=s[a];
        s[a]=temp;
      }
      else{
        int na,nb;
        if(a<n){
          na=n+a;
        }
        else{
          na=a-n;
        }
        if(b<n){
          nb=n+b;
        }
        else{
          nb=b-n;
        }
        temp=s[nb];
        s[nb]=s[na];
        s[na]=temp;
      }
    }
    if(t==2){
      flag*=-1;
    } 
  }

  if(flag==1){    
      cout<<s<<endl;
  }
  else{
    cout<<s.substr(n,n)<<s.substr(0,n)<<endl;
  }
  return 0;
}

D問題

D - RGB Coloring 2

残り時間のうち１時間ほどを費やして考えましたが解けませんでした。
方針としてはUnionFindで連結成分にわけ，連結成分毎に方法の数を出して掛け合わせる方法に思い至りました。
各連結成分の組み合わせ数は最初の頂点の色の選び方は３通り，それにつながる頂点の色の選び方は２通り，ただしループする場合には１通り，２か所からループがつながると塗れなくなる，ということでDFSに乗せようとしましたがうまく書けず。まだまだ修行がたりません。