えんじにあ備忘録

脱よわよわエンジニアを目指すブログ

AtCoder Beginner Contest 297 に参加しました＆反省会

競技プログラミング

AtCoder Beginner Contest 297 の振り返り

  • C問題まで解けました
  • A問題：ダブルクリックが成立した時刻を変数に格納後、ループから抜けます
  • B問題：対応する文字の出現位置を格納する変数を用意し条件を満たすかを調べます
  • C問題：TTと連続する部分文字列をPCに置き換えます
  • D問題：問題文中の減算する処理を除算に置き換えることで計算量を削減します。WAが 3つ出ました

B問題

atcoder.jp

方針

  • B,K,Rそれぞれの出現位置を変数に格納します
  • 与えられた条件を満たすかを判定します

解説*1から

  • 条件 1 の偶奇が異なるとは%2で得られる余りが一致するかどうかで判定します
  • 条件 2 は問題文の通りです
  • 出現位置を取得するにはfind,rfind関数を使います

実装例

#include<bits/stdc++.h>
using namespace std;

int main () {

  string S;
  cin >> S;
  
  int b_left = S.find('B');
  int b_right = S.rfind('B');
  int r_left = S.find('R');
  int r_right = S.rfind('R');
  int k = S.find('K');

  bool flag = true;
  if (b_left % 2 == b_right % 2) flag = false;
  if (!(r_left < k && r_right > k)) flag = false;

  cout << (flag ? "Yes" : "No") << endl;

  return 0;
}

C問題

atcoder.jp

方針

  • Sを左から見ていき、Tが 2 個連続しているならばPCで置き換えるという操作を行います

解説*2から

  • 指定した文字列または正規表現にマッチする全ての部分文字列を置換します
  • regex_replace関数を使います

実装例

#include<bits/stdc++.h>
using namespace std;

int main () {

  int H, W;
  cin >> H >> W;
  
  for (int i = 0; i < H; i++) {
    string S;
    cin >> S;
    cout << regex_replace(S, regex("TT"), "PC") << endl;
  }

  return 0;
}

D問題

atcoder.jp

方針

  • 問題文中の減算する処理を除算に置き換えることで計算量を削減します

解説*3から

  • はじめに、 A > B になるようにswapを行います。
  • B = 0 になるまで以下を繰り返します。
    • 答えに \lfloor \frac{A}{B} \rfloorを足し、 Aを A \, mod \, Bで置き換えます。
    • A,B をswapします。
    • 最後に答えから 1 を引きます。
  • 元の操作での A,B の大小関係が同じ操作を一度にまとめて行っています。最後に 1を引くのは A=B となったとき更に 1 回多く操作をしてしまうからです。
  • 計算量は O(logA+logB) です。

実装例

#include<bits/stdc++.h>
using namespace std;
int main() {
  long long a,b;
  cin>>a>>b;
  long long ans=0;
  if(a<b) swap(a,b);
  while(b>0){
    ans+=a/b;
    a%=b;
    swap(a,b);
  }
  cout<<ans-1<<endl;
}

*1:https://atcoder.jp/contests/abc297/editorial/6178

*2:https://atcoder.jp/contests/abc297/editorial/6177

*3:https://atcoder.jp/contests/abc297/editorial/6160