AtCoder Beginner Contest 090

はじめに

AtCoderのBeginner Contest 091の解説と勉強です。
問題はこちらを参照してください。

A - Diagonal String

自分の回答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<math.h>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define print(x) cout << #x << " = " << x << endl;

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;


int main() {
  string s1, s2, s3;
  cin >> s1;
  cin >> s2;
  cin >> s3;

  cout << s1[0] << s2[1] << s3[2] << endl;

  return 0;
}

改善点

特になし
ちなみに出力部分を以下のように記述してしまうと、char型も整数の仲間なので整数の足し算の結果が表示されてしまいます。

cout << s1[0] + s2[1] + s3[2] << endl;

B - Palindromic Numbers

もう少し美しい回答がありそうでしたが、時間を優先して全探索をすることにしました。
整数から文字列に変換する関数to_stringはよく使用するので、覚えておくといいかもしれないです。

自分の回答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<math.h>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define print(x) cout << #x << " = " << x << endl;

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;


int main() {
  int A, B;
  cin >> A >> B;

  int ans = 0;
  for (int i = A; i <= B; ++i) {
    string str = to_string(i);
    bool bCheck = true;
    for (int j = 0; j < str.size() / 2; j++) {
      if (str[j] != str[str.size() - j - 1]) {
        bCheck = false;
        break;
      }
    }
    if (bCheck) ans++;
  }

  cout << ans << endl;
  return 0;
}

改善点

特になし

C - Flip, Flip, and Flip......

この問題はLights Out問題という問題と非常に類似しています。Lights Out問題は非常に有名な問題で、ググれば様々な記事が出てきますので、是非調べてみてください。

大事な点は問題文にも書いてある「すべての操作を行った後の各カードの状状態は操作を行う順番に依らないことが証明できます」という部分です。したがって、周囲にいくつカードが存在しているかで場合分けをすることができます。

縦と横が1マスずつであれば、表になっている1マスが一度だけ裏返されるため、裏を向いているカードの枚数は1です。
次に、縦横の一方が1マスで、もう一方が2マス以上の場合は、端のカードは2回裏返されるので表、それ以外のカードは3回裏返されるので裏になります。したがって裏を向いているカードの枚数は、全てのカードから端の2枚を除いたカードの枚数です。
最後に縦横ともに2マス以上の場合、四隅のカードは4回裏返されるので表にになり、辺に接しているカードは6回裏返されるので表になり、それ以外の内部のカードは9回裏返されるので裏になります。したがって裏を向いているカードの枚数は$(M-2) \times (N-2)$ になります。

自分の回答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<math.h>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define print(x) cout << #x << " = " << x << endl;

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;


int main() {
  ll N, M;
  cin >> N >> M;

  if (N == 1 && M == 1) {
    cout << 1 << endl;
  }
  else if (N == 1) {
    cout << M - 2 << endl;
  }
  else if (M == 1) {
    cout << N - 2 << endl;
  }
  else {
    cout << (N - 2) * (M - 2) << endl;
  }

  return 0;
}

改善点

はじめ$ M $と$ N $をint型で定義していたがために通りませんでした。おかげで5分のペナルティーを受けてしまいました。本当であればintの値の範囲、long longの値の範囲を知っておくべきですが、時間が求められている場合は常にlong longを使用することをオススメします。

D - Remainder Reminder

僕はまだまだ競技プログラミングを始めたばかりで、まだまだ雑魚なので毎度Dを解くことができるかでレートが上がるかどうかが決まると言っても過言ではありません。
今回は配点が400点で比較的優しい問題だったので、時間内に解くことができました。

今回の問題は、全探索をすれば、正しい答えを導き出すことができます。僕もまずは全探索で正しい答えが出るプログラムを作成してから、数学的解法に着手しました。

本問題で満たすべき式は$ bn+K \leq a < b(n+1) $である。ただし$0 < a, b \leq N$である。
$ N $を$ b $で割ったときの商を$ n $、余りを$ k $とする。つまり、$ N = bn + k $とする。
ここで$ b $を固定する。

1. $ a < bn $の場合
   上述の条件を満たす組み合わせは$ n \times (b - K) $個となる。ただし、$
   K=0 $のとき、$ a=0 $を含むため、1デクリメントする。
2. $ bn <= a < bn + k $の場合
   
   1. $ k < K $ならば、上述の条件を満たす組み合わせは存在しない
   2. $ K \leq k $ならば、上述の条件を満たす組み合わせは$ k - K + 1 $個存在する。

自分の回答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<math.h>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define print(x) cout << #x << " = " << x << endl;

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;


int main() {
  ll N, K;
  cin >> N >> K;

  ll ans = 0;

  for (int b = K + 1; b <= N; b++) {
    int n = N / b;
    int k = N % b;

    ans += (b - K) * n;
    if (K == 0) ans--;
    if (K <= k) {
      ans += k - K + 1;
    }
  }


  cout << ans << endl;
  return 0;
}

改善点

今回、問題Dが解けた要因としては、一度全探索のコードを書いて正しい答えが導き出せていることを確認した上で、数学的解法に着手した点だと思います。特に$ K=0 $の時にデクリメントするところなどは、数学的解法よりも全探索の時の方が発見しやすいです。回答速度は若干遅くなってしまいますが、この方法で時間がかかっても問題Dが確実に解けるようにしたいところですね。