ABC175の感想

昨日ABC175が開催されました。リアルタイムでは参加できなかったため、本日バーチャル参加として取り組みました。どのような感じだったかを書いていきます。問題はこちらから。
https://atcoder.jp/contests/abc175/tasks

先に結果を述べると、今回はC問題まで解けました。問題見て、どのように解こうか考えて、実装して、バグ直してみたいなことをやってると、思ったより時間が足りなかった。そのため、残りの問題に関してはあとでのんびり考えてみます。

さて行きます。

A問題はRとSの3文字の文字列が与えられて、Rが何個連続してるかを答える問題。全パターンを書き出しても2^3で8通りしかないから、どうやっても解けるけど、できる限りスマートに書きたいなと思って、少し考えました。

Rの数を数えて、もしR=2で真ん中がSだったらRは連続してないから、1にする。という、今見るとそんなにスマートでもない解法です。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
int main()
{
 string str;
 cin >> str;
 
 int cnt = 0;
 rep(i,3)
 {
   if(str[i] == 'R') cnt++;
 }
 if(cnt == 2 && str[1] == 'S') cnt = 1;
 
 cout << cnt;
 return 0;
}

B問題です。与えられた数のうち3角形を構成できるものは何組ありますか？という問題。前回のB問題は距離を求めるだけだったのですが、今回は一瞬どのように解こうか戸惑いました。

要素を固定して、残りを探査して、長さの条件を満たすかを全通り試すという、かなり愚直な方法なので、書いてるときは計算時間を超過しないか心配でしたが、全然余裕でした。ただ、nが増えると爆発的に計算量が増えるので、もっと良い方法がありそうです。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
int main()
{
 int n;
 cin >> n;
 vector<int> l(n);
 
 rep(i,n) cin >> l[i];
 
 int cnt = 0;
 int length = 0;
 
 rep(i,n-2)
 {
   int l1 = l[i];
   
   for(int j = i+1; j < n-1; ++j)
   {
     if(l[j] != l1)
     {
       int l2 = l[j];
       
       for(int k = j+1; k<n; ++k)
       {
         if(l[k] != l1 && l[k] != l2)
         {
           int l3 = l[k];
           
           length = max({l1,l2,l3});
           length = length + length - (l1+l2+l3);
                 
           if(length < 0) ++cnt;
         }
         
       }
     }
   }
   
 }
 cout << cnt;
 return 0;
}

C問題です。数直線上に暮らす高橋君の問題。現在座標xにおり、+dか-dだけ移動する行為をk回行ったときの絶対値の最小値を求める問題。

まず、x // dの演算で原点に戻ってから、残りの移動回数が奇数か偶数かで答えを分けました。今思うとかなりシンプルに書けそうなのに、試験中はとてもプログラムが煩雑になって、かなり時間がとられました。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
int main()
{
 ll x, k, d;
 cin >> x >> k >> d;
 
 
 int isPlus;
 ll cnt = 0;
 ll ans = 0;
 
 bool isEven;
 bool isOver;
 
 ll korn = k;
 
 
 
 //xを正で考える。
 if(x > 0) isPlus = 1;
 else
 { 
   x *= -1;
   isPlus = -1;
 }
 
 cnt = x / d;
 
 if(x % d < -(x%d)+d)
 {
   k -= cnt;
   isOver = false;
 }
 else
 {
   k -= (cnt+1);
   isOver = true;
 }
 
 if(k < 0)
 {
   cout << abs(isPlus * (x-d*korn));
   return 0;
 }
 
 if(k%2 == 0) isEven = true;
 else isEven = false;
 
 if(isOver && isEven) ans = isPlus*(x - (cnt+1)*d);
 else if(isOver && !isEven) ans = isPlus*(x-cnt*d);
 else if(!isOver && isEven) ans = isPlus*(x-cnt*d);
 else ans = isPlus * (x-(cnt+1)*d);
 
 cout << abs(ans);  
 
 return 0;

}

絶対値で出力とかを考えると、もっと要素を減らして書けそうです。途中のreturn 0とかを見ると、慌てて付け足したことがよくわかります。

今回はここまででした。時間との戦いになるので、結構焦りました。前回よりC問題は簡単だったとはいえ、スコアが上がったことは純粋に嬉しいので、モチベーションを保って頑張ります。

また、解答、解説を見ながら復習をして、自分なりの解答をまとめたいと思います。