ABC386の振り返り

A問題(diff:25)

以下のように考えました。

• フルハウスである⇔カード $i(1 \le i \le 13)$ が $3$ 枚、カード $j(1 \le j \le 13、i \neq j)$ が $2$ 枚ある
• カードが $4$ 枚あり、数字の種類数が $2$ 種類であった時、適切に $1$ 枚追加するとフルハウスになることを証明したい。
• $4$ 枚で $2$ 種類であるとき、パターンは次の2つである。(順番の違いを除いて2パターン)
• $i$、$i$、$i$、$j$ または $i$、$i$、$j$、$j$
• 1つ目のパターンでは、カード $j$ を追加すればフルハウスにでき、2つ目のパターンでは、カード $i$ またはカード $j$ を追加すればフルハウスにできる。よって証明できた。
  問題文から、カードが $4$ 枚あることは分かっているので、種類数が $2$ 種類化を判定すれば良いです。これはc++でのstd::setやstd::mapに $A$、$B$、$C$、$D$をぶち込んでsize()で種類数を判定すれば良いです。
  ACコード(1ms)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
  set<int> card;
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  card.insert(A);
  card.insert(B);
  card.insert(C);
  card.insert(D);
  int s = card.size();
  if(s == 2) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

AC時間:2:46

B問題(diff:42)

$S$ を前から順に見ていって、もしその数字が $S$ の最後ではなく、その数字も1つ次の数字も $0$ なら、$1$ 文字進めてその回の動作を終了する、ということをやったらACできます。
ACコード(1ms)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
  string S;
  cin >> S;
  int s = S.size();
  int ans = 0;
  for(int i = 0; i < s; i++) {
    if(i < s - 1 && S.at(i) == '0' && S.at(i + 1) == '0') {
      i++;
    }
    ans++;
  }
  cout << ans << endl;
}

AC時間:4:55

C問題(diff:254)

いろんな条件試して、全部駄目だったらNoとする方針でした。

• まず $S = T$ の時(入力例5)→Yes
• そうでないとき、$S$ の長さと $T$ の長さを計測(それぞれ $s$、$t$ とする)
• $s = t$ の時(入力例1、6)→ $S$ と $T$ を前から順に見ていって、違うところがあったらそれをカウントする→もしカウント $= 1$ ならYes
• $s + 1 = t$ の時(入力例2、4)→空文字列tmpと、違うところがあったかのflagを用意する。(最初は $0$)$S$ の $i(i \le i \le N)$ 番目と $T$ の $i + flag$ 番目を順に見ていって、違うところがあったらflagを $1$ にする。順に見ている時に、同時にtmpに $T$ の $i + flag$ 番目を追加する。最後に、$S = tmp$ であればYes
• $s = t + 1$ の時(入力例3)→$s + 1 = t$ の時の判定を $S$ と $T$ を逆にしてしてすれば良い。
• 全部当てはまらないならNo
  ACコード(15ms)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
  int K;
  string S, T;
  cin >> K >> S >> T;
  if(S == T) {
    cout << "Yes" << endl;
    return 0;
  }
  int s = S.size(), t = T.size();
  if(s == t) {
    int cnt = 0;
    for(int i = 0; i < s; i++) {
      if(S.at(i) != T.at(i)) {
        cnt++;
      }
    }
    if(cnt == 1) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  if(s + 1 == t) {
    string tmp = "";
    int flag = 0;
    for(int i = 0; i < s; i++) {
      if(T.at(i + flag) != S.at(i)) {
        flag = 1;
      }
      tmp += T.at(i + flag);
    }
    if(tmp == S) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  if(s == t + 1) {
    string tmp = "";
    int flag = 0;
    for(int i = 0; i < t; i++) {
      if(S.at(i + flag) != T.at(i)) {
        flag = 1;
      }
      tmp += S.at(i + flag);
    }
    if(tmp == T) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

AC時間:18:50

感想

初の緑パフォを出しました。成績表
4完はできませんでしたが速解きができたと思います。
今回判定問題が多かったですね(A、C、D)
ABC387は4完を頑張ります。