ABC183参戦記 - chacoderのブログ

f:id:chacoder:20201116170655p:plain

はじめに

2020年11月15日21:00-22:40 ABC183に参戦しました。

48分10秒で４完ノーペナでパフォーマンスは986でレートは29あがって758になりました。

f:id:chacoder:20201116170403p:plain

最近５回レートの単調減少が続いていたので久しぶりにあたたまってよかったです。
ただノーペナで解けたところには運もあるので，引き続き精進して早く緑に戻りたいなと思います。

A問題

数字を入力し，負の場合は０を，正の場合はそのまま出力する問題です。
max(0,n)で出力するのが賢いですが，愚直にif文で場合分けして提出しました。

丁寧にチェックして1分22秒。このあたりの10秒，20秒を縮めても意味がないと思うので丁寧にチェックして出すスタンスを続けたいと思います。

B問題

幾何問題でB問題にしては骨がありました。
ビリヤードでクッションを使って玉を跳ね返す場合に目標地点に到達するためのクッション位置を計算します。

作図して三角形の相似を使って丁寧に立式しました。
double型を使い，setprecisionを忘れずに入れてAC。

10分24秒（累積経過時間11分46秒）は丁寧に解いたにせよ，少しかけ過ぎかなという感じです。

TLで二分探索で解ける，というのをやっている人がいてなるほどと思いました。

#include <bits/stdc++.h>
using namespace std;
 
int main(){
  double sx,sy,gx,gy;
  cin>>sx>>sy>>gx>>gy;
  cout<<　setprecision(12)　<<sx+sy*(gx-sx)/(sy+gy)<<endl;
  return 0;
}

C問題

C - Travel

巡回ルートで一定の時間になるルートの数を求める問題です。
最短時間を求めるような問題はよくでてきます。

N<=8なので全探索，next_permutationを使うのはすぐに見えました。

1からスタートし1に戻る，というのがひねったところで，なかなかエラーがとれず実装には少し手間取りました。
22分04秒，通算33分50秒。ちょっとかけ過ぎですが，実力相応か。

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

int T[10][10];
int main(){
  int N,K;
  cin>>N>>K;
  for(int i=0;i<N;i++){
    for(int  j=0;j<N;j++){
      cin>>T[i][j];
    }
  }

  vector<int>vec(N-1,0);
  for(int i=0;i<N-1;i++){
    vec.at(i)=i+1;
  }
  int cnt=0;

  do{
    //cout<<"#"<<vec.at(0)<<endl;
    int len=0;
    len+=T[0][vec.at(0)];   
    for(int i=0;i<N-2;i++){
      len+=T[vec.at(i)][vec.at(i+1)];
    }
    len+=T[vec.at(N-2)][0];
    //cout<<len<<endl;
    if(len==K) cnt++;
  }
  while (next_permutation(vec.begin(), vec.end()));

  cout<<cnt<<endl;
  return 0;
}

D問題

D - Water Heater

一定の水が供給され，時間SiからTiの間に水量Piを使うとき，不足する時間がないかという問題です。

シンプルないもす法の問題であっさり書けたつもりでしたが，14分20秒と意外に時間を使っていました。
思い返してみると，最初，SとTについても配列にしてソートしようとしていた気がします。

途中でもっとシンプルに書けることに気づきました。

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

long long R[200100];

int main(){
  long long N,W;
  cin>>N>>W;
  for(int i=0;i<N;i++){
    long long s,t,p;
    cin>>s>>t>>p;
    R[s]+=p;
    R[t]-=p;
  }
  long long temp=0;
  for(int i=0;i<N;i++){
    temp+=R[i];
    if(temp>W){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}