ABC189参戦記　 - chacoderのブログ

f:id:chacoder:20210124110941p:plain

はじめに

2021年1月23日21:00-22:40 ABC189に参戦しました。
結果は4完72分18秒1ペナで2000位/8938人中　パフォ―マンス1162、レーティングは前回814から+40で854となりhighestを更新しました。

f:id:chacoder:20210124111106p:plain

https://atcoder.jp/users/chacoder/history/share/abc189

過去4回の入緑後はいずれも直後のコンテストで冷えて茶落ちしていたので初めて緑が維持できてホッとしています。
またレーティンググラフ自体も新たな成長の予感を感じさせるカーブとなり嬉しいです。

A問題

３つの英大文字がすべて同じかどうかを判定する問題です。

空白区切りになっていないのでstringで受けて分解して判定しなければなりませんが，横着すると間違えてWAを吐きそうです。
しっかり確認して2分56秒でＡＣ。さすがにちょっとかけすぎだったかも知れませんがA問題にしてはWA出している人が多かったのでこの程度は許容範囲かと思います。

B問題

B - Alcoholic

アルコールの量と濃度が与えられ累積アルコール量が一定値を超えるかどうかを判定する問題です。
double型を使って素直に書いたらWA。

割り算に何となくいやーな予感はしていたのですが的中しました。
１００倍して割り算を消すことを思いつきAC。
すぐに思いついたのはいいのですが、いやーな予感がしたときに工夫すべきでした。

8分36秒1ペナ　累積11分32秒1ペナ

ここでだいぶ出遅れたと思ったのですが推定パフォみるとまだ緑でしたのでB問題にてこずっていた人は多かったようです。

提出コード

▶クリックで展開

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

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
signed main(){
  int n;
  ll x,v[n],p[n];
  ll  sum=0;
  cin>>n>>x;
  x*=100;
  rep(i,n){
    cin>>v[i]>>p[i];
    sum+=v[i]*p[i];
    if(sum>x){
      cout<<i+1<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
  return 0;
}

C問題

C - Mandarin Orange

一列に並んだN個の皿のi番目にAi個のみかんが乗っています。
この皿の上のみかんを横に連続して同数以上のみかんをとる場合の最大値を求める問題です。

難しかったです。
最初はなかなか解法を思いつかず飛ばしてＤ問題を見に行きましたがＤも難しそうなので戻ってきました。

以前にJOIか何かにあった日本沈没という問題を思い出しました。水面があがってきて陸地が沈んでいく問題です。
それと同じように考えてAiの全範囲について連続する最大長を求め，その積の最大値を出力する方針を思いつきました。

ぱっと見でO(N^２）では厳しいかと思いましたが計算量の工夫を思いつきません。
せめてもの工夫としてＮの数がAiの範囲より１桁小さいのでmapを使ってユニークな要素のみで探索してみました。

もっとも試してみるとAiの範囲１～100000を全探索しても間に合ってました（約800ms）。
Submission #19664090 - AtCoder Beginner Contest 189

Aiの範囲がもう１桁大きいと差が出たと思います。

27分42秒　通算39分14秒1ペナ　解けてよかったです。

提出コード

▶クリックで展開

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

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
signed main(){
  int n;
  cin>>n;
  vector<int> a(n);
  map<int,int>mp;
  rep(i, n){
    cin >> a[i];
    mp[a[i]]++;
  }
  int maxans=0;
  for(auto e:mp){
    int cnt=0;
    int maxcnt=0;
    rep(i,n){
      if(a[i]>=e.first){
        cnt++;
      }
      else{
        cnt=0;
      }
      maxcnt=max(maxcnt,cnt);
    }
    maxans=max(maxans,e.first*maxcnt);
  }
  cout<<maxans<<endl;
  return 0;
}

D問題

D - Logical Expression

この問題も難しかったです。
問題の意味を理解し，小さなケースで試してＤＰでの実装を考えました。

もらうＤＰで後ろの方から見ていって，演算がANDの場合には一つ前のＤＰの値を足す，ORの場合は，一つ前のＤＰの値と２^Ｎを足す，とすればできそうです。ＤＰ［０］は１とします。

この方針で実装してみましたがうまく数字が合いません。
サンプル２で気づいたのは，これは二進数表記そのものではないか，ということです。（63==2^6-1==111111(2進))
１桁目は１にして，その後の桁は演算子がANDなら0，ORなら1として二進数にします。

実際にはDPでやっていることと変わりませんがシンプルになりました。

28分04秒　通算67分18秒1ペナ　

ACしたコード

▶クリックで展開

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
int n;
string s;
int f[61];
  
signed main(){
  cin>>n;
  ll ans=0;
  rep(i,n){
    cin>>s;
    if(s=="OR"){
      f[i]=1;
    }
    else{
      f[i]=0;
    }
  }
  for(int i=n;i>=0;i--){
    if(f[i]==1){
      ans+=1;
    }
    ans*=2;
  }
  ans++;
  cout<<ans<<endl;
  return 0;
}

E問題

愚直に解くコードは書けそうでしたがどう考えても計算量オーバーで落とす工夫を思いつきませんでした。

解説を見てそれぞれの操作が行列式で表されることから，N回目の操作後までの操作をまとめてそこまでの操作行列の積で表せることを学びました。
なるほどこれなら間に合いそうです。

後日改めて復習します。

F問題

問題を見るだけは見ましたが実質的に考察するところまで行けませんでした。
はやくF問題にも取り組めるようになりたいです。

おわりに

今回は運もよかったのだと思いますが４完して高いパフォーマンスがでました。
最近は精進もスランプで難しい問題の考察ができず，簡単目の問題を解くことを続けていました。

続ければ続けるなりにいいことはあって，例えば，データ構造の扱い方や基本的なテクニックなどが少しづつ定着しているように思います。
Ｂ問題で１００倍して割り算をなくすようなところは，ちょっと前までだとなかなか気づけなかったように思います。

また多少込み入った実装も破綻なくまとめられるようになりました。
しばらくは最近の方針に沿って基礎固めをしっかりやりたいと思います。

長らく凸凹で横ばいだったレーティンググラフの傾きがちょっと上を向いたような気がします。
まずは緑をしっかり安定させ，さらに上を目指せるよう頑張ります。