ABC176を解いた感想

先ほど開催されたABC176に参加しました。つらつらと感想を書いていきます。

A問題はたこ焼きを焼く問題。

x個同時に焼けるたこ焼き器を持っていて、1回あたりt秒かかるとき、n個を焼き終えるにはどれくらいかかりますか。という問題。

端数の有無で場合分けをすることに注意をすれば、あっという間です。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main()
{
 int n,x,t;
 cin >> n >> x >> t;
 int ans;
 if(n%x == 0) ans = n / x *t;
 else ans = (n/x +1) * t;
 cout << ans << endl;
 
 return 0;
}

B問題は9の倍数を判定する問題です。%9で答えが出ると思いきや、求める数字はn<10^200000なのでint型はおろか、long longでもオーバーフローします。でも、親切なことに、9の倍数は10進数の各桁の和が9の倍数となるということを明示してくれているので、それを使います。

ポイントは2つ。

入力をintで受け取るとオーバーフローするので、stringで受け取って、１文字ずつintにキャストする。

純粋にsumで足し合わせていくとオーバーフローするのでmodの性質を使い、sumを9で割った余りを保持する。

これで答えが出ます。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main()
{
 string str;
 cin >> str;
 
 int sum = 0;
 while(1){
   if(str.empty()) break;
   
   char c = str[0];
   int n = c - '0';
   sum = (sum + n) % 9;
   str.erase(0,1);  
 }
 
 string ans;
 if(sum%9 == 0) ans = "Yes";
 else ans = "No";
 
 cout << ans << endl;
 
 return 0;
}

C問題です。これは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> a(n);
 rep(i,n) cin >> a[i];
 
 int max = 0;
 ll sum = 0;
 
 rep(i,n){
   if(max > a[i]){
     sum += max - a[i];
   }
   else max = a[i];
 }
 cout << sum << endl;
 return 0;
}

とてもシンプルでした。

今回は9300提出中、7100位ぐらいでした。あと１問解けると一気に順位が伸びるので、一つの壁といいますか、非常に問題が良く作られてると言いますか、、

今回も解説を見てしっかりと復習したいと思います。

ただその前に前回の175回の問題のF問題がなかなか解けないので、そちらから頑張ります。