おじさんの競プロ記録

自分の力で解答できた問題を振り返り、理解を深めたいです。

AtCoder Regular Contest 007 B - 迷子のCDケース

AtCoder ARC-B

問題

CDケースをN枚、CDをN+1枚持っています。CDは0からNの連番がついていて、0がプレイヤーに入っていてケースはありません。他のCDは同じ番号のケースに入っています。

CDをM枚交換したリストが与えられます。最後のCDケースの状態を出力します。

制約

${1 \leqq N \leqq 100}$
${0 \leqq M \leqq 100}$

考えたこと

CDケースの状態を保存する配列を用意します。NとM共に100なので、毎回ケースを探索して交換先を探すとシンプルなコードで書けそうです。

が、今回は各CDがどこに入っているかも保存することにしてみました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


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

  vector<int> cd_case(N + 1);
  iota(cd_case.begin(), cd_case.end(), 0);
  vector<int> cd_pos(N + 1);
  iota(cd_pos.begin(), cd_pos.end(), 0);

  vector<int> set_list(M);
  rep(i, M) cin >> set_list[i];

  rep(i, M) {
    // 聞きたいCD(set_list[i])とプレイヤーのCD(cd_case[0])を入れ替える
    int cd_in_player = cd_case[0];
    swap(cd_case[cd_pos[set_list[i]]], cd_case[0]);
    cd_pos[cd_in_player] = cd_pos[set_list[i]];
    cd_pos[set_list[i]] = 0;
  }

  rep(i, N) cout << cd_case[i + 1] << endl;
  
  return 0;
}

解説を読んで

とくにありません。

AtCoder Regular Contest 016 B - 音楽ゲーム

AtCoder ARC-B

問題

N行の譜面が与えられます。譜面は9個の文字列です。xならばボタンを押す。oならばボタンを押し続けます。

何回ボタンを押したでしょうか？

制約

${1 \leqq N \leqq 100}$

考えたこと

1行ずつ確認します。xであれば数えます。oの場合、前の行がo以外ならば数えます。1行目のoは前の行がないため、処理をわけます。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N;
  cin >> N;
  vector<string> v(N);
  rep(i, N) cin >> v[i];

  int ans = 0;
  rep(i, N) {
    rep(j, v[i].size()) {
      if (v[i][j] == 'x') ++ans;
      else if (v[i][j] == 'o') {
        if (i == 0) ++ans;
        else if (v[i - 1][j] != 'o') ++ans;
      }
    }
  }

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

解説を読んで

とくにありません。

AtCoder Beginner Contest 064 C - Colorful Leaderboard

AtCoder ABC-C

問題

N人のAtCoderのレートが与えられます。レートごとに色を与えます。最小で何色、最大で何色必要かを求めます。

制約

${1 \leqq N \leqq 100}$
${1 \leqq a_i \leqq 4800}$
${a_iは整数である。}$

考えたこと

レート3200以上は自由に色を選べるため、処理を分けます。

レート1~3199は400で割れば0~7になるため、8個の配列に記録すれば何色が使われたかわかります。

3200以上だけで与えられたときの場合分けができず、WAになってしまいました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N;
  cin >> N;
  
  vector<int> colors(8, 0);
  int over = 0;
  rep(i, N) {
    int num;
    cin >> num;

    if (num >= 3200) {
      ++over;
    } else {
      colors[num / 400]++;
    }
  }

  int sum = 0;
  rep(i, colors.size()) {
    if (colors[i]) ++sum;
  }

  int ans_min = max(1, sum);
  int ans_max = sum + over;

  cout << ans_min << " " << ans_max << endl;

  
  return 0;
}

解説を読んで

場合分けをきちんとしなければいけませんでした。

AtCoder Beginner Contest 183 C - Travel

AtCoder ABC-C

問題

N個の都市があります。各都市間の移動時間が与えられます。

都市1を出発し、すべての都市をちょうど1度ずつ訪問して都市1へ戻る経路のうち、移動時間の合計がちょうどKになるものの個数を答えてください。

制約

${2 \leqq N \leqq 8}$
${i \neq jのとき1 \leqq T_{i,j} \leqq 10^8}$
${T_{i,i} = 0}$
$T_{i,j} = T_{j,i}$
${1 \leqq K \leqq 10^9}$
入力はすべて整数

考えたこと

都市の数が少ないので全探索できそうです。すべての順序はnext_permutationでがあります。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  ll N, K;
  cin >> N >> K;
  vector<vector<ll>> T(N, vector<ll>(N, 0));
  rep(i, N) rep(j, N) cin >> T[i][j];

  if (N == 2) {
    if (K == T[0][1] + T[1][0]) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
    return 0;
  }


  ll ans = 0;
  vector<int> perm;
  for (int i = 1; i < N; ++i) {
    perm.push_back(i);
  }

  do {
    ll time = 0;
    time += T[0][perm.front()];
    rep(i, perm.size() - 1) {
      time += T[perm[i]][perm[i + 1]];
    }
    time += T[perm.back()][0];
    if (time == K) ++ans;
  } while (next_permutation(perm.begin(), perm.end()));

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

解説を読んで

C問題ならば答えられるようになってきましたが、細部が違います。

next_permutation(index.begin()+1, index.end());の部分がクールです。与えられる都市が2つの時に場合分けをしましたが必要ないようです。

AtCoder Beginner Contest 022 B - Bumble Bee

AtCoder ABC-B

問題

N個の花があります。i番目に訪れた花は $A_i$ です。i>jかつ ${A_i == A_j}$ である花の個数を求めます。

制約

${1 \leqq N \leqq 10^5}$
${1 \leqq A_i \leqq 10^5}$

考えたこと

1番目から順番に、花の種類である $A_i$ の値を補完するとともに、すでに保管しているかを調べます。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];

  unordered_map<int, int> mp;
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    auto itr = mp.find(A[i]);
    if (itr != mp.end()) {
      ++ans;
    }
    mp.insert(make_pair(A[i], 1));
  }

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

解説を読んで

花の種類数という考え方の方が、よく考えられている気がします。

AtCoder Beginner Contest 037 C - 総和

AtCoder ABC-C

問題

長さNの数列{ $a_i$ }と1以上N以下の整数が与えられます。この数列には長さKの連続する部分がN-K+1個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。

制約

${1 \leqq K \leqq N \leqq 10^5}$
${0 \leqq a_i \leqq 10^8}$
${a_i}$ は整数である。

考えたこと

すべてのパターンを逐一足し算したのでは間に合わなさそうです。累積和を使うことにしました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  ll N, K;
  cin >> N >> K;
  vector<ll> a(N);
  rep(i, N) cin >> a[i];

  vector<ll> s(N + 1, 0);
  for (int i = 0; i < N; ++i) s[i + 1] = s[i] + a[i];

  ll ans = 0;
  int left = 0;
  int right = K;
  while (right <= N) {
    ans += s[right] - s[left];
    ++left;
    ++right;
  }

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

解説を読んで

とくにありません。

AtCoder Regular Contest 059 C - いっしょ

問題

与えられたN個の整数を、書き換えてすべて同じ整数にします。1つの整数に対して、次の操作を一度だけ行えます。

整数をxを整数yに書き換える時、 $(x－y)^2$ のコストがかかります。

すべて同じ整数にするための必要な最小のコストを求めます。

制約

${1 \leqq N \leqq 100}$
${-100 \leqq a_i \leqq 100}$

考えたこと

与えられる整数は最大100個です。書き換える整数は、a_iの取り得る範囲内に収まると思います。

100を200にする必要はなく、与えられた数列の中心へ向かうと考えました。

与えられる整数の個数と試す範囲も狭いため、すべてを試しました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N;
  cin >> N;
  vector<ll> a(N);
  rep(i, N) cin >> a[i];

  ll ans = 10000000000;
  for (ll c = -100; c <= 100; ++c) {
    ll cost = 0;
    rep(i, N) {
      cost += (a[i] - c) * (a[i] - c);
    }

    ans = min(ans, cost);
  }

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

解説を読んで

とくにありません。