ABC177の感想

昨日行われた、abc177の感想を書いていきます。
問題は以下から。
https://atcoder.jp/contests/abc177/tasks/abc177_a

A問題は時間に間に合うかどうかの問題。速度sでd離れた場所に時間t以内で到着できるかという問題。

簡単な「みはじ」の問題です。がd/sとtを比較したら間違えました。入力の最大値は10^4なので大人しくs*tと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()
{
  int d, t, s;
  cin >> d >> t >> s;
string ans;
  if(s*t >= d) ans = "Yes";
  else ans = "No";
cout << ans << endl;
  return 0;
  }

私は道のり、速さ、時間で「みはじ」と習いましたが他の方はどうなのでしょうか。

B問題は文字列の比較です。ある文字列sに対して、別の文字列tがsの部分文字列となるには最低何回文字列を変更する必要があるか。という問題。

初めはどのように解くかと悩みましたが、tとsを先頭から比較して、文字が一致してる数を数える。それを末尾まで行えばできました。

#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 s, t;
  cin >> s >> t;
int ls = s.length();
  int lt = t.length();
  int ans = 0;
rep(i,ls-lt+1){
    int cnt = 0;
    rep(j,lt){
      if(s[j+i] == t[j]) ++cnt;
    }
    ans = max(cnt,ans);
  }  
  cout << lt-ans << endl; 
  return 0;
}

C問題は要素の積の総和を計算する問題です。ただし、mod(10^9+7)で求めます。
愚直に全部掛けてそれを足す、10^9+7を超えたらそれを引けばよい。という感じで実装したら、TLEでした。

そのため、要素を受け取るときにそれらの部分和を計算しておき、計算の際には要素と対応する部分和を掛けることで計算量を減らしました。

共通項で括ってあげるイメージです。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
#define div 1000000007
int main()
{
  int n;
  cin >> n;
  vector<ll> a(n);
  vector<ll> b;
  ll sum = 0;
rep(i,n){
    cin >> a[i];
    sum += a[i];
    if(div <= sum){
      sum = sum % div;
    }
    b.emplace_back(sum);
  }
  ll ans = 0;
  rep(i,n-1){
      ans = (ans + a[n-1-i] * b[n-2-i]) % div;
  }
  cout << ans << endl;
  return 0;
}

forの降順処理って
for(int i = n;i > 0; —i)
と書いた方が良いのでしょうか。

D問題にも手を出しましたが、TLEで解けませんでした。ネットワークのリンクを考える問題で、研究室の配属課題にて似た問題解いたのでいけるかなと思いましたが、愚直にやってはダメでした。

1番リンクが繋がってる人のリンク数+1が答えになるという方針で考えましたが、あっているのでしょうか。復習します。

今回も3問で5000位/9000人ぐらいでした。さすがに慣れてきたのか解くスピードが上がっているので、順位も上がりました。

C問題まではなんかガチャガチャやっていれば解けるけど、Dからは解法のアルゴリズムが要求されると感じました。いつになったら解けるのでしょうか。

最近アウトプットをサボりがちなので頑張って書きます。