競技プログラミング練習記 No.60【ABC103練習】

初回 -> はじめに

ABC103を解きました。
4完です！

問題	時間	アルゴリズム	実行時間
A	3min	-	8ms
B	11min	-	6ms
C	12min	mod	7ms
D	27min	-	41ms

まとめ

先にまとめを載せます。これ自体は最後に書いてます。

std::max関数とstd::min関数は引数にタプルを指定すると3要素以上の比較ができます。

A - Task Scheduling Problem

  int a1, a2, a3;
  cin >> a1 >> a2 >> a3;
  cout << max({a1, a2, a3}) - min({a1, a2, a3});

3つの入力値の中から最大のものと最小のものとの差が答えになります。
std::max関数とstd::min関数は引数にタプルを指定すると3要素以上の比較ができます。

B - String Rotation

  string s, t;
  cin >> s >> t;

  for(int d = 0; d < s.length(); ++d)
  {
    if (s[0] != t[d]) continue;
    bool ok = true;
    for(int i = 0; i < s.length(); ++i)
    {
      ok &= (s[i] == t[(i + d) % s.length()]);
    }
    if (ok)
    {
      cout << "Yes";
      return;
    }
  }
  cout << "No";

スマートに解けそうなのですが、よくわからなかったので全探索しました。
文字列tをd文字ずらしたものが文字列sと一致していたら "Yes" を出力します。

C - Modulo Summation

  int n, a;
  cin >> n;
  ll ans = 0;
  for(int i = 0; i < n; ++i)
  {
    cin >> a;
    ans += a - 1;
  }
  cout << ans;

mを全入力の最小公倍数に設定すれば答えは最大化できます。

そして実は最小公倍数は求めなくてもいいです。
mが最小公倍数の時は $\ \ m\ \ mod\ \ a_i\ =\ a_i-1\ \ $ という決まった数値になります。
そのため、入力値から1を引いたものの和が答えになります。

その点に気付かずに最小公倍数を求めてオーバーフローし、1WAしました。

D - Islands War

  int n, m, ina, inb;
  cin >> n >> m;
  vector<vector<int>> a(n + 1, vector<int>());
  for(int i = 0; i < m; ++i)
  {
    cin >> ina >> inb;
    a[ina].emplace_back(inb);
  }

  const int INF = 1 << 30;

  int border = INF;
  int ans = 0;
  for(int i = 0; i < n; ++i)
  {
    if (border <= i)
    {
      ans++;
      border = INF;
    }
    if (a[i].size() == 0) continue;
    border = min(border, *min_element(a[i].begin(), a[i].end()) );
  }
  ans += (border != INF);
  cout << ans;

各入力は $a_i < b_i$ より、 $a_i$ を始点、$b_i$を終点とします。
始点が同じとき、終点が最小のものが条件を満たすように橋を落とせば、始点が同じ入力は全て条件を満たしますね。
つまり、始点が同じもの同士をまとめて、そのなかで終点が最小のものだけを見ればいいです。
落とすべき橋の最小位置を記録しながら始点を次々とみていって、みている始点が橋を落とす位置を超えた時に答えをカウントします。
このやり方だと$O(N + M)$ で解けます。

以上です。ありがとうございました。