競技プログラミング練習記 No.62【ABC174参加】

初回 -> はじめに

ABC174に参加しました。
5完です！
C問題が時間内に解けませんでした。
かなり悔しいです。。。

問題	時間	アルゴリズム	実行時間
A	1min	-	3ms
B	3min	距離	49ms
C	-	mod	23ms
D	10min		6ms
E	22min	二分探索	86ms

まとめ

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

距離は $\sqrt{xx + yy}$ ですが、ルートを外した形でも判定できます。
また、そちらの方が高速です。(累乗根を求める処理は重いです)

mod k の値は循環性があって、最大でもk通りです。

A - Air Conditioner

  int x;
  cin >> x;
  cout << (x >= 30 ? "Yes" : "No");

入力値が30以上かどうかで答えが変わります。

B - Distance

  ll n, d, x, y;
  cin >> n >> d;
  ll ans = 0;
  for(int i = 0; i < n; ++i)
  {
    cin >> x >> y;
    if (x*x + y*y <= d*d) ans++;
  }
  cout << ans;

距離を求める問題ですね。
距離は $\sqrt{xx + yy}$ ですが、ルートを外した形でも判定できます。
また、そちらの方が高速です。(累乗根を求める処理は重いです)
x*x + y*y <= d*d で判定して答えがわかります。

この問題の制約から、オーバーフローにも注意です。

C - Repsept

  int k;
  cin >> k;

  if (k % 2 == 0)
  {
    cout << -1;
    return;
  }

  ll num = 0;
  for(int i = 1; i <= k; ++i)
  {
    num = num * 10 + 7;
    num %= k;
    if (num == 0)
    {
      cout << i;
      return;
    }
  }  
  cout << -1;

777777...7を上から1桁ずつkで割るイメージです。
割ったときに0になった時点が答えです。

例えば、123456789123456789123のような大きい数を割るときは上から1桁ずつ割りますよね。
これと同じです。
ちなみに、上から一桁ずつ割るというのは割り算のひっ算と同じ仕組みです。

この問題では
num = num * 10 + 7;
num %= k;
でやっています。

% k の値は循環性があって、最大でもk通りです。
つまり、ループは最大k回で大丈夫です。
循環性をうまく使えばもっと速く解くこともできます。

D - Alter Altar

  int n;
  string s;
  cin >> n >> s;

  int r = 0;
  for(int i = 0; i < n; ++i)
  {
    r += s[i] == 'R';
  }

  int ans = 0;
  for(int i = 0; i < r; ++i)
  {
    if (s[i] == 'W') ans++;
  }
  cout << ans;

色を変える操作は入れ替える操作で置き換えることができます。
また、赤い石をすべて左に寄せれば求める状態になります。
入れ替える操作だけをすることを考えると、赤い石の数をrとして、求める状態では最初のr個が赤い石になります。

文字列を前からr個見て、白い石ならばそれより後ろにある赤い石と入れ替えます。
こうすると最小手数で求める状態になります。

E - Logs

  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for(int i = 0; i < n; ++i)
  {
    cin >> a[i];
  }

  if (k == 0)
  {
    cout << *max_element(a.begin(), a.end());
    return;
  }

  auto f = [&](ll arg)
  {
    ll cnt = 0;
    for(int i = 0; i < n; ++i)
    {
      cnt += a[i] / arg;
      if (a[i] % arg == 0) cnt--;
    }
    return cnt <= k;
  };

  ll le = 0LL, re = 1000000001LL;
  while(re - le > 1)
  {
    ll mid = (le + re) / 2;
    if ( f(mid) ) re = mid;
    else le = mid;
  }
  cout << re;

切られた後の丸太の長さで二分探索です。
二分探索を選択した理由は、、、勘です。。。(理由はあるのですが言語化できないです)

$K$ と $A_i$ の制約から計算時間が足りないと分かるので、残る「丸太の長さ」を思いつきました。
丸太を長さLに切れるかどうかの判断は $O(N)$ でできるので計算量的に間に合います。

割り切れるときと割り切れないときで計算結果が意図しないものになります。
floor関数やceil関数をうまく使いましょう。
私は if (a[i] % arg == 0) cnt--; で調整しました。

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