ABC178参戦記

atcoder.jp

成績　－　Highest更新するも反省の多い回

2020年9月13日21:00-22:40に開催されたABC178に参戦しました。

結果はABDの3完　4ペナ　85:05で3798位､パフォーマンスは835で旧レーティング780から6あがって新レーティングは786、Highestを更新しました。

Highest更新はよかったのですがいろいろと反省の多い回でした。しっかり振り返って次につなげたいと思います。

なかなか緑の道は遠いです。

最近の精進

前回ABC177が8月29日で先週はABCがなかったため久しぶりな感じです。

この間の精進は、新しいことを追うよりこれまでの知識の復習を中心とした内容でした。
EDPCなどにも手を出しています。

difのついていない問題も多くHeatmapの雰囲気も少し変わってます。

A問題

A - Not

入力が１なら０を、０なら１を出力する、というシンプルな問題ですが、ペナを出してしまいました。
入力忘れの痛恨のミス。

テストケースを１つしかやらず、入力がないと０なので１を出力して合ってしまったのが運の付き。

このA問題でWAするなんて・・・と思ったらsnukeさんも提出言語間違いでWA出してて救われました（救われてない）。

B問題

B - Product Max

はまりました。

範囲の正負の場合分けを延々とやってWAを重ね、あきらめて先に進みました。

後で戻ってきて、範囲の両端の積４種類のMAXを出力すればよい、と気づきAC。

ここで３０分ほど溶かし、ペナ３つを重ねたのは痛かったです。

C問題

C - Ubiquity

最初に見たときは手が出ず先にD問題に進みました。

後で戻ってきて包除原理に気づき、試しにテストケース出したら合ってて鳥肌が立ちました。
しかし時間はあと１分を切っており、ぎりぎりで提出したらCEに。

変数のNを大文字・小文字混在させてました。

その後に提出したものもWA。

   for(int i=0;i<n;i++){
    temp*=10;
    temp%=MOD;
    def*=9;
    def%=MOD;
    def2*=8;
    def2%=MOD;
   }
  if(temp-def*2+def2<0){
    temp+=MOD;
  }
  cout<<temp-def*2+def2<<endl;

これ、def*2でdefを２回引いているので、MODを1回足しただけではまだ負の場合があったのです。

  if(temp-def*2+def2<0){
    temp+=MOD;
  }
  if(temp-def*2+def2<0){
    temp+=MOD;
  }
  cout<<temp-def*2+def2<<endl;

２枚重ねにしてAC。
これはBではまらなければ時間内に書けてたなと思います。

悔しいけどBではまったのも実力のうちだし、Cで時間がかかったのも実力のうちです。

D問題

この問題は、B問題、C問題とはまって取り組んだので背水の陣の気持ちでした。

D - Redistribution

１３ぐらいまで実際に書き出してみて法則性を見ると、

0 0 0 1 1 1 2 3 4 6 9 13 19

F(ｎ)=F(n-1)+F(n-3)になっていることに気づきました。

再帰で書いてテストでTLEしたのでメモ化再帰にしてクリアー。

何とか解けてとても嬉しかったです。

提出コード

#include <bits/stdc++.h>
using namespace std;
static const long long MOD=1000000007;
long long memo[2010];

long long func(long long x){
  if(memo[x] != -1) return memo[x];
  if(x<3){
    return 0;
  }
  else if(x==3){
    return  1;
  }
  else{
    memo[x]=(func(x-1)+func(x-3))%MOD;     
    return memo[x];
  }
}

int main(){
  int s;
  cin>>s;
  for(int i=0;i<2005;i++){
    memo[i]=-1;
  }
  cout<<func(s)<<endl;
  return 0;
}

E問題

最初に考えたのは全探索すると(2*10^5)^2でとても間に合わないだろうからこれまでにでてきたx,yのいずれかの最大値を上回る点だけを集めた配列にしてサイズを圧縮した上で全探索する、という方針でした。

この方針でやると120msぐらいで収まりTLEはしないのですが、WAするケースがでてきます。
いろいろ考えたのですが結局解決できませんでした。

WAしたコード

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

int main(){
  long long x,y,maxx,maxy,minx,miny;
  
  int n;
  cin>>n;
  vector<pair<long long ,long long >>vec;
  cin>>x>>y;
  maxx=x;
  minx=x;
  maxy=y;
  miny=y;
  vec.push_back({x,y});
  for(int i=1;i<n;i++){
    cin>>x>>y;
    if(x>maxx || y>maxy ||x<minx ||y<miny){
      maxx=max(x,maxx);
      maxy=max(y,maxy);
      minx=min(x,minx);
      miny=min(y,miny);
      vec.push_back({x,y});
    }
  }
  //cout<<vec.size()<<endl;
  long long maxman=0;
  long long temp=0;
  for(int i=0;i<vec.size();i++){
    for(int j=i+1;j<vec.size();j++){
      temp=abs(vec[i].first-vec[j].first)+abs(vec[i].second-vec[j].second);
      maxman=max(maxman,temp);
    }
  }
  
  cout<<maxman<<endl;   
  
  
  return 0;
}

復習

解説を見て４５度回転という手法（あるいは式変形）でO(N)で解けることがわかりました。
XiとXjが混ざってたのをバラバラにできる手法があることに感動しました。

自力で式変形を理解できるまでにはちょっとかかりそうですががんばります。

「４５度回転」「マンハッタン距離」で検索すると　競プロの世界では典型的な手法であることがわかりました。

まだまだ知らないことが多いなと改めて感じた次第です。

ACしたコード

解説ACですが自力で式変形してACできました。

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

int main(){
  int N;
  cin>>N;
  int x,y;
  int z[200100];
  int w[200100];
  for(int i=0;i<N;i++){
    cin>>x>>y;
    z[i]=x+y;
    w[i]=x-y;
  }
  int maxz=z[0];
  int minz=z[0];
  int maxw=w[0];
  int minw=w[0];

  for(int i=1;i<N;i++){ 
    maxz=max(maxz,z[i]);
    minz=min(minz,z[i]);
    maxw=max(maxw,w[i]);
    minw=min(minw,w[i]);    
  }
  int ans=0;
  ans=max(maxz-minz,maxw-minw);
  cout<<ans<<endl;
  return 0;
}

F問題

今回はF問題を見られていません。

早くF問題を考えられるレベルになりたいです。