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問題は簡単だったとはいえ、スコアが上がったことは純粋に嬉しいので、モチベーションを保って頑張ります。
また、解答、解説を見ながら復習をして、自分なりの解答をまとめたいと思います。
この記事が気に入ったらサポートをしてみませんか?