AtCoder Beginner Contest 086 - takahiro_itazuriの公倍数的ブログ

はじめに
A - Product
- 自分の解答
- 改善点
B - 1 21
C - Traveling
- 自分の解答
- 改善点
D - Checker
- 解答
総評

はじめに

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

A - Product

入力された2つの数字の積が偶数か奇数かを判定する問題。
言語を正しく使うことでできればできる問題。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
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;

  if ((a * b) % 2 == 0) {
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }

  return 0;
}

改善点

特になし。

B - 1 21

入力の二つの整数を結合し、それが平方数であるかを判定する問題。
簡単ですが、平方数の判定は別の記事を書きます。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
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 c = a * pow(10, (int)log10(b) + 1) + b;
  int s = sqrt(c);
  if (c == s * s) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}

改善点

入力の部分でbの桁数をlog10を使用することで取得していましたが、stringで入力を受け取り、結合した後にstoiでstring型からint型に変換する方が、良さそうです。

改善後のコード

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
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 a, b;
  cin >> a >> b;

  int c = stoi(a + b);

  int s = sqrt(c);
  if (c == s * s) cout << "Yes\n";
  else cout << "No\n";

  return 0;
}

C - Traveling

二次元のマス目上を上下左右に動く場合に、ある場所からある場所へ決まった時間で行くことができるかという問題。
注意したい点としては、その場にとどまることができないという点です。

その場にとどまれない点は無視して、まず考えることとしては「たどり着くことができるか」です。上下左右に動く最短距離なので、L1距離（マンハッタン距離）で計算することができます。1秒に1マス進むので、決まった時間で移動できるかが判定できます。

そして、最短経路で目的地に着いてしまった場合、先程のその場にとどまることができないという制約を考える。すると、もう一度同じところに戻って来るには偶数秒が必要となり、その最小となるパスは1マスずれて戻るという操作です。したがって、最短経路でたどり着いた場合に、残っている時間が偶数秒であれば、ちょうどその時間で着くことができます。

この問題のように「実際に経路をたどる必要がない」ことが、シミュレーション問題ではよくありますね。

自分の解答

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<string>

using namespace std;

int N;
// 現在の場所
int now_t, now_x, now_y;
// 次に行く場所
int t, x, y;

int main() {
  int N;
  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    scanf("%d %d %d", &t, &x, &y);

    // まず最低限必要な時間
    int rest_t = t - now_t - (abs(x - now_x) + abs(y - now_y));
    if (rest_t < 0 || rest_t % 2 == 1) {
      printf("No\n");
      return 0;
    }

    // 更新
    now_t = t;
    now_x = x;
    now_y = y;
  }

  printf("Yes\n");
  return 0;
}

改善点

特になし

D - Checker

規則的な塗りつぶし方を考える問題。

問題を見てまず考えたことは、塗りつぶし方に周期性があるということ。
$K \times K$の正方形が白黒交互に配置されているので、周期が$2K$であることに気づきます。
したがって、どんなに遠くにあるものでも$2K$で割ったあまりと同じ色が塗られていることがわかります。

次に「$2K \times 2K$の中で、どこを黒の左下（基準点）にするのか」という問題になります。したがって全探索の場合、探索する量は$2K \times 2K$となり、各探索について入力の$N$個のうち、何個が満たされているのかを考えるため、計算量のオーダーは$O(NK^2)$となります（まず初めにこのアルゴリズムでプログラムを書きました）。ここで問題文を見ます。すると$1 \leq N \leq 10^5$となり、到底2secで解くことができないとわかります。

そこで、予めどこを基準点にするかという行列を作成し、$N$個の入力がされた時点で投票をしていき、その行列の最大の投票数を探すという方針にすると、オーダーは$O(N + K^2)$となり、入力サイズが大きい時の速度はかなり向上します（時間内ではこのアルゴリズムでプログラムを書いているところで時間切れになってしまいました）。
こういう考え方は良くでてくるイメージがあります。「AtCoder Beginner Contest 084 D - 2017-like Number」でも、予め配列を用意し、累積和を取っておくことで速度を向上するという問題がありました。今回の問題では、「入力に対して、そこをその色で塗るためにはどこを基準点にすればよいかということを投票していく」形になります。

さらにここで工夫できる点があります。今回は闇雲に投票するより、正方形のパターンであることをさらに利用することで早くできます。「いもす法」という方法が存在します。こちらの「いもす法 - いもす研 (imos laboratory)」がわかりやすく解説していました。つまり、投票する区域が連続しているような場合では、その両端で$+1$と$-1$を記述しておき、あとから累積和を考えることで、その領域内全体に投票を行わなくてもよくなるというような発想です（頭良いなあ）。

解答

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#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++)

using namespace std;

using ll = long long;
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 N, K;
int memo[2001][2001];//黒の始点,x,y

void imos(int x, int y, int x2, int y2)
{
  ++memo[x][y];
  --memo[x][y2];
  --memo[x2][y];
  ++memo[x2][y2];
}

int main() {
  scanf("%d %d", &N, &K);

  for (int i = 0; i < N; i++) {
    int x, y; char c;
    scanf("%d %d %c", &x, &y, &c);

    // 白を黒に変換
    if (c == 'W') x += K;

    // 2K×2Kの領域に収める
    x %= 2 * K; y %= 2 * K;

		
    if ((x < K && y < K) || (x >= K && y >= K)) {
      int x_ = x % K, y_ = y % K;
      imos(0, 0, x_ + 1, y_ + 1);
      imos(x_ + K + 1, 0, 2 * K, y_ + 1);

      imos(0, y_ + K + 1, x_ + 1, 2 * K);
      imos(x_ + K + 1, y_ + K + 1, 2 * K, 2 * K);

      imos(x_ + 1, y_ + 1, x_ + K + 1, y_ + K + 1);
    }
    else {
      int x_ = x % K, y_ = y % K;

      imos(x_ + 1, 0, x_ + K + 1, y_ + 1);
      imos(x_ + 1, y_ + K + 1, x_ + K + 1, 2 * K);

      imos(0, y_ + 1, x_ + 1, y_ + K + 1);
      imos(x_ + K + 1, y_ + 1, 2 * K, y_ + K + 1);
    }
  }

  for (int i = 0; i < 2001; i++) {
    for (int j = 1; j < 2001; j++) {
      memo[i][j] += memo[i][j - 1];
    }
  }

  for (int i = 1; i < 2001; i++) {
    for (int j = 0; j < 2001; j++) {
      memo[i][j] += memo[i - 1][j];
    }
  }

  int m = 0;
  for (int i = 0; i < 2 * K; i++) {
    for (int j = 0; j < 2 * K; j++) {
      m = std::max(m, memo[i][j]);
    }
  }
	
  printf("%d\n", m);

  return 0;
}

総評

A, B, Cの問題は非常に簡単でしたので、素早く解くことができれば、それなりに上位が狙えます。一方でDを解けている人はBeginner Contestには10人程しかいませんでした。Dが解ければ一桁順位、解けなければA~Cを早く解けた人が上位になっていました。

僕もDがすらすらと解けるようになりたいですね。アルゴリズムを思いつくことはできるようになってきました。