ZONeエナジープログラミングコンテスト参戦記（5月1日）

はじめに

5月1日21:00-22:40に開催されたZONeエナジープログラミングコンテストに参戦しました。
結果はABDの３完97:26 2ペナでパフォ―マンス849、レーティングは前回916から-7の909になりました。

f:id:chacoder:20210502170457p:plain

A問題

A問題にしては難し目に感じました。今回はＢ問題以下も難し目でしたが。
substrの位置をよく間違えるので４文字程度だしと思って配列で処理しました。
2分55秒。

提出コード

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

signed main(void) {
  string s;
  cin>>s;
  int cnt=0;
  for(int i=0;i<9;i++){
    if(s[i]=='Z'&& s[i+1]=='O'&&s[i+2]=='N' && s[i+3]=='e'){
      cnt++;
    }
  }
  cout<<cnt<<endl;
  
  return 0;
}

Ｂ問題

今回冷えた一番の原因。
最初は方針を間違ってスタートし、その後はうまく立式できず後回しにしました。
戻ってきて解いたのですがなかなか合わずに40分以上かかってしまいました。
落ち着いてゆっくり解くこと、変数名を間違えにくいものでしっかり設定すること、あたりが反省点です。

最初に間違えた方針は答えの高さを二分探索する、というもので書きあげたあとで整数でないことに気づきぎゃふんとなりました。

型のキャストとかの知識もあやふやで一度しっかり押さえておかなければと思いました。
40分＋αかかっていて完全に嵌りました。

提出コード

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

signed main(void) {
  int n,d,h;
  cin>>n>>d>>h;
  int dn[n];
  int hn[n];
  rep(i,n){
    cin>>dn[i]>>hn[i];
  }
  double maxans=0.0;
  double ans=0;

  rep(i,n){
    maxans=max(maxans,((double)hn[i]-(((double)h-(double)hn[i])/((double)d-(double)dn[i]))*(double)dn[i]));
  }
  cout<<maxans<<endl;
}

C問題

ちらっと見て難しそうで飛ばしました。
昨晩解説ACし、今日、午前中に書きなおしましたがbitを使ったスマートな方法やunique関数による圧縮など新しい技がいろいろあって勉強になりました。

D問題

文字列操作のいろいろなテクニックがてんこ盛りでした。
dequeを使った実装はすぐに思いつきましたが重複を削除するのにdequeのままでは処理が難しく血迷って試行錯誤して無駄なWAを出してしまいました。

最後は愚直にdeque処理のあとstringに落として処理しました。
追加する方向を間違えたまま最後に無理無理合わせてるのでだいぶへんてこなコードになりました。

提出コード

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

signed main(void) {
  string s;
  cin>>s;
  deque<char>deq;
  int len=s.length();
  int flag=1;
  rep(i,len){
    if(s[i]=='R'){
      flag*=-1;
      continue;
    }
    if(flag==1){
      deq.push_front(s[i]);
    }
    else{
      deq.push_back(s[i]);
    }
  }
  string ans="";
  len=deq.size();
  rep(i,len){
    ans+=deq[i];
  }
  if(flag==1){
    reverse(ans.begin(),ans.end());
  }
  ans+='0';
  int cur=0;
  while(cur != ans.length()){
    if(ans[cur]==ans[cur+1]){
      ans.erase(cur,2);
      cur--;
      continue;
    }
    cur++;
  }
  if(ans=="0"){
    return 0;
  }
  else{
    ans.erase(ans.size()-1,1);
  }
  cout<<ans<<endl;
}

E問題

コンテスト中は手が出ず。
午前中にがんばって書きました。
もっとシンプルな方法がありそうなので勉強します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
int a[550][550];
int b[550][550];
int used[550][550];
int r,c;

signed main(){
  const int INF=1001001001;
  vector<vector<int>> d(550,vector<int>(550,INF));
  cin>>r>>c;
  rep(i,r+1) rep(j,c+1){
    used[i][j]=0;
  }
  for(int i=1;i<=r;i++){
    for(int j=1;j<=c-1;j++){
      cin>>a[i][j];
    }
  }
  for(int i=1;i<=r-1;i++){
    for(int j=1;j<=c;j++){
      cin>>b[i][j];
    }
  }
  priority_queue<tuple<ll, ll, ll>,
    vector<tuple<ll, ll, ll>>,
    greater<tuple<ll, ll, ll>>> p;
  p.push(make_tuple(0, 1, 1));  
  while(!p.empty()){
    ll cs = get<0>(p.top());
    ll x = get<1>(p.top());
    ll y = get<2>(p.top());
    p.pop();
    if(x==r && y==c){
      cout<<cs<<endl;
      return 0;
    }    
    if(used[x][y]==1){
      continue;
    }
    used[x][y]=1;       
    if(y<c && used[x][y+1] != 1){
      if(d[x][y+1]>cs + a[x][y]){
        d[x][y+1]=cs + a[x][y];
        p.push(make_tuple(cs + a[x][y], x, y + 1));
      }
    }
    if(y>1 && used[x][y-1] != 1){
      if(d[x][y-1]>cs+a[x][y-1]){
        d[x][y-1]=cs+a[x][y-1];
        p.push(make_tuple(cs + a[x][y-1], x, y - 1));
      }
    }
    
    if(x<r && used[x+1][y] != 1){
      if(d[x+1][y]>cs + b[x][y]){
        d[x+1][y]=cs+b[x][y];
        p.push(make_tuple(cs + b[x][y], x+1, y));
      }
    }
    for(int i=1;i<x;i++){
      if(used[x-i][y] != 1){
        if(d[x-i][y]>cs+i+1){
          d[x-i][y]=cs+i+1;
          p.push(make_tuple(cs + i + 1, x-i, y));
        }
      }
    }
  }
}